Re: Probability question - honest, not homework!

matt271829-news@xxxxxxxxxxx wrote:
C6L1V@xxxxxxx wrote:
matt271829-news@xxxxxxxxxxx wrote:
djarvinen@xxxxxxxxx wrote:
Well, as usual, my math skills have failed again, and I can never seem
to get the same answer twice to a question which I am sure is trivial
to most of the readers here.

So I'm rolling a single 6-sided die.

How many times to I have to roll it to give myself a 50% chance of
getting four 1's in a roll?

Honest, not homework! It's just that too many of little grey cells
haved died from a mispent middle-age.

By coincidence I was looking at a very similar problem just recently,
and, as others have indicated, it seems far from easy to get a neat
formula for the answer.

Let n be the required run length (in your case 4), d be the number of
outcomes at each turn (in your case six, but, for example, if you were
tossing a coin it would be 2), and p(x) be the probability that the
first run of n consecutive identical outcomes *starts* at turn x. (By
symmetry it makes no difference which outcome you choose; for example,
you'd get the same answer for four 2's in a row, four 3's and so on.)
Somewhat counterintuitively, I am working with the *starting* position
just because of the way I worked it out.

Then I get

p(1) = (1/d) ^ n
p(x) = (1 - 1/d) * (1/d) ^ n, for 1 < x < n + 2

and then, for x >= n + 2, recursively,

p(x) = p(x - 1) - p(x - (n + 1)) * (1 - 1/d) * (1/d) ^ n

Using the values appropriate to your particular problem, summing the
p's over x = 1, 2, 3, ... (on a computer!) the cumulative probability
first exceeds 0.5 at x = 1075. Adjusting for the run length, that would
make the answer to your question 1078, if I didn't screw up somewhere.

This answer looks OK. If we let f(n) = probability that the first run
of 4 ENDS at toss n, the recursion is: f(1) = f(2) = f(3) = 0, f(4) =
(1/6)^4 = 1/1296, and
f(n)=(5/6) f(n-1) + (5/36) f(n-2) + (5/216) f(n-3) + (5/1296) f(n-4)
for n >=5. Letting Maple do the computations, we find that the smallest
n giving sum{f(k): k = 1 ... n} >= 1/2 is n = 1078, as you have
obtained. (However, I am not convinced about the correctness of your
recursion relation. I got mine from the Markov chain representation
with successive back-substitution.)

Well, it seems to give the right numbers - the same numbers as the
Markov method. If you can demonstrate otherwise then I would be
interested to see that.

I cast it in the above form because that suggested a reasonably
straightforward set of solutions to the recursion that I think will
lead to an exact closed-form expression for p(x). There is a similar
recursion for the cumulative probability (the sum of the p's), which
ought to have a similar method of solution. It becomes unwieldy to
actually exhibit the solution for large n, but should be doable for n =
4. I ought to sit down and do it then, just to prove the principle.
Either that or find that I overlooked something and it doesn't work out
the way I thought!

This is the method I alluded to.

As before, let n be the required run length and d be the number of
different outcomes at each turn. For brevity, define

k = (1 - 1/d) * (1/d)^n

Let q(x) be the probability that the required run has NOT appeared
anywhere in the first x turns (so the probability that it HAS is 1 -
q(x)). (Here I am working with the cumulative probabilities, but an
almost identical method can be used for p(x), the probability that the
first run will end at turn x.)

We can then set up:

q(n) = 1 - (1/d)^n
q(n + 1) = 1 - (1/d)^n - k
q(n + 2) = 1 - (1/d)^n - 2*k
...
q(2*n) = 1 - (1/d)^n - n*k

and then, for x > 2*n, the recurrence relation:

q(x) = q(x - 1) - k*q(x - (n+1))

which has a solution

q(x) = c[i] * u[i] ^ x

where c[i] is any constant and u[i] is a solution to the equation

u^(n + 1) - u^n + k = 0

Let the n + 1 (possibly complex) solutions be u[1], u[2], ... u[n+1]
(and let's assume they're all different!). Any linear combination of
solutions to the recurrence is another solution. To satisfy the
"initial conditions" q(n) through q(2*n) we need to find c[1], c[2],
.... c[n+1] to satisfy the (linear) simultaneous equations:

c[1]*u[1]^n + c[2]*u[2]^n ... + c[n+1]*u[n+1]^n = q(n)
c[1]*u[1]^(n+1) + c[2]*u[2]^(n+1) ... + c[n+1]*u[n+1]^(n+1) = q(n+1)
...
c[1]*u[1]^(2*n) + c[2]*u[2]^(2*n) ... + c[n+1]*u[n+1]^(2*n) = q(2*n)

Then the answer we're looking for is

q(x) = c[1]*u[1]^x + c[2]*u[2]^x + ... + c[n+1]*u[n+1]^x

This seems to give real values only for integer x. I'm not sure if
that's what I expected. There "ought to be" a real-valued expression
that works for all real x?

In the specific case of n = 4, d = 6, I get

c[1] = 5.28738904422804E-03 - 9.48079487645434E-03i
c[2] = -1.23861785422035E-02
c[3] = 1.00181139910127
c[4] = 5.2873904126344E-03 + 9.48079498332244E-03i
c[5] = 0

u[1] = -6.1855975705114E-03 - 0.158388694717914i
u[2] = -0.153650806646007
u[3] = 0.999355335120363
u[4] = -6.18559757051076E-03 + 0.158388694717915i
u[5] = 0.166666666666667

Some of the precision here may not be justified... I haven't
investigated to what extent rounding errors etc. have crept in.

.

Relevant Pages

  • Re: Probability question - honest, not homework!
    ... outcomes at each turn (in your case six, but, for example, if you were ... tossing a coin it would be 2), and pbe the probability that the ... straightforward set of solutions to the recursion that I think will ... I ought to sit down and do it then, ...
    (sci.math)
  • Re: Probability question - honest, not homework!
    ... getting four 1's in a roll? ... outcomes at each turn (in your case six, but, for example, if you were ... tossing a coin it would be 2), and pbe the probability that the ... Then general form of your recursion would be ...
    (sci.math)
  • Re: Boy Scouts make people nervous
    ... any probability. ... coin is not really significant because the coin is simply being used ... outcomes does not necessarily mean equal probability. ...
    (rec.martial-arts)
  • Re: Is State Vector Reduction a Process?
    ... outcomes rather than the description of the evolution of individual ... we choose the observables (the set of outcomes is the ... >> So you are saying that QM theory does not explain the preferred basis. ...
    (sci.physics.research)
  • Re: Boy Scouts make people nervous
    ... any probability. ... Yes, you can, based on the number of possible outcomes. ... Yes, true, in the case of a real coin, but the variance in the real ... left hander dodging right. ...
    (rec.martial-arts)