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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.