Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search