Consecutive Failures in Bernoulli Trials

Date: 07/07/99 at 07:46:21
From: Ofri Becker
Subject: Probability of at least k consecutive failures

Hi!

What is the probability that out of n experiments there will be a 
string of at least k (< n) experiments in a row that fail? Let q be 
the probability of failure and p = 1-q be the probability of success.

For example, out of 100 coin tosses, what is the probability of 
getting at least once a row of 6 consecutive "heads"?

Date: 07/08/99 at 17:37:58
From: Doctor Anthony
Subject: Re: Probability of at least k consecutive failures

Success Runs in Bernoulli Trials
---------------------------------
We must be careful in defining our terms here. If we want a success 
run of length r at the nth trial, then a further success at the 
(n+1)th trial could undo the run completed at the nth trial. Equally, 
if we stipulate AT LEAST r successes, then any run can be extended 
indefinitely and a run does not reestablish the initial situation. 
Either of the above definitions makes analysis very messy. We must 
define a run of length r so that it becomes a recurrent pattern. A 
first run of length r is uniquely defined and we can agree to start 
counting from scratch every time a run occurs. With this convention 
the sequence

     SSS|SFSSS|SSS|F 

contains 3 success runs of length 3 ending at positions 3, 8, and 11.

The formal definition we shall use is as follows:

A sequence of n letters S and F contains as many S-runs of length r 
as there are non-overlapping uninterrupted blocks containg exactly 
r letters S each. With this convention we say that a successful 
pattern occurs at the nth trial if a new run of length r is completed 
at the nth trial.

This defines a recurrent pattern and simplifies the theory.

We turn now to the original question of at least 6 successes in a row 
in 100 trials.

With the above definitions and a lot of hand-waving explanation, the 
probability of no run of length r in n trials is approximately

             (1 - px)      1
     q(n) = --------- . -------
            (r+1-rx)q   x^(n+1)


where x = 1 + q.p^r + (r+1)(q.p^r)^2 + ....

In your problem   p = q = 1/2, r = 6, n = 100

 x = 1 + (1/2)(1/2)^6 + 7(1/4)(1/2)^12 + .... =  1.00824

                 0.49588       1
and so   q(n) = --------- . -------- = 0.455493
                 0.47528     2.2906

and so the probability of at least one such run of 6 successes is

     Prob(at least 1 run of 6 heads) =  0.544507

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/09/99 at 05:31:30
From: Ofri Becker
Subject: Re: Probability of at least k consecutive failures

Hi again -

You gave me an approximation for the formula, but isn't there an exact 
analytical solution of having k successes (or failures) in a row out 
of n trials where the probability of one success in one trial is 
given as p?

You also did not really explain how the solution is reached.

Thanks again,
Ofri Becker

Date: 07/09/99 at 18:10:54
From: Doctor Anthony
Subject: Re: Probability of at least k consecutive failures

I'm afraid if you want the full theory behind the approximate solution 
shown above you will need to study 'Recurrent Events and Renewal 
Theory' in books like that by William Feller. The treatment requires a
knowledge of probability-generating functions, solution of recurrence 
relations, and the theoretical application of Normal approximations 
for large n. It covers about 23 pages in the Feller book and cannot be 
reproduced here.

If you want an exact but highly unworkable method you could try the 
following. 

We can set up a difference equation to find the probability of 6 
successes in a row.

Let y(n) be the probability that the pattern SSSSSS does not occur in 
the entire sequence.   n >= 6

   y(n-1) - probability it occurs at nth trial = y(n)

   y(n-1) - y(n) = probability the pattern occurs at the nth trial
                 = p^6.y(n-6)

so that   y(n) - y(n-1) + p^6.y(n-6) = 0   and with p = 1/2

The auxiliary equation is

     x^6 - x + (1/2)^6 = 0

     64.x^6 - 64.x + 1 = 0

If the roots are a, b, c, d, e, and f   then

     y(n) = A.a^n + B.b^n + C.c^n + D.d^n + E.e^n + F.f^n  ......(1)

     y(0) = y(1) = y(2) = y(3) = y(4) = y(5) = 1

So we get the 6 equations

     A + B + C + D + E + F = 1
     A.a + B.b + C.c + D.d + E.e + F.f = 1
     A.a^2 + B.b^2 + C.c^2 + D.d^2 + E.e^2 + F.f^2 = 1
     A.a^3 + B.b^3 + C.c^3 + D.d^3 + E.e^3 + F.f^3 = 1
     A.a^4 + B.b^4 + C.c^4 + D.d^4 + E.e^4 + F.f^4 = 1
     A.a^5 + B.b^5 + C.c^5 + D.d^5 + E.e^5 + F.f^5 = 1 

Having found A, B, C, D, E, and F we can find y(100) from equation (1) 
above.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/10/99 at 06:21:24
From: Ofri Becker
Subject: Re: Probability of at least k consecutive failures

Thanks,

Just another small thing... how is the auxiliary equation developed? 
Please show it in the general case and not over the example.

Thanks again,
Ofri Becker

Date: 07/10/99 at 08:08:51
From: Doctor Anthony
Subject: Re: Probability of at least k consecutive failures

If you have a difference equation such as

     u(n+2) - 5.u(n+1) + 6.u(n) = 0

The auxiliary equation is   x^2 - 5x + 6 = 0

                              (x-2)(x-3) = 0

with solutions x = 2  and  x = 3.

The general solution for u(n) is then

     u(n) = A.2^n + B.3^n

You obtain the values of A and B from further information about the 
values of u(0) and u(1) or any other known value of u(i).

You can check the truth of the above equation for u(n) by substituting 
it into the difference equation  u(n+2) - 5u(n+1) + 6u(n) = 0  and 
seeing that it satisfies this equation.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/