If the probability of an individual event occurring (heads on a coin, 3 on a die, an error in a received...

[ Editor: from Richard Lay's August 1996 summary of the replies he
received. ]

Jim Landis solution:

I have a solution that is a little heavy in computation, but it does
solve the problem exactly, with out double counting or miscounting any
cases.

I don't know of any simple solution to that problem in "closed"
notation, but it yields very easily to a recursive formula, i.e. a
formula defined in terms of itself.

Define f(n, Y, S, p) as follows :
f(0, Y, S, p) = 1
f(n, Y, S, p) = 0    for all n > S >= 0
f(n, Y, S, p) = p*f(n-1, Y, S-1, p) + (1-p)*f(Y, Y, S-1, p)

n represents the number of successes needed to complete the current
  "streak", and should initially be set to Y
Y represents the total number of successes needed in a row
S is the number of remaining trials
p is the probability of success on any trial

f() could be interpreted as "the probability that you will have a
streak of n successes immediately, or a streak of Y successes later
on".  The two terms evaluate the remaining probability after each roll
of the die.  First term corresponds to success on the current roll, the
second term to failure.

So the probability of an unbroken string of four 3's in 20 rolls of a
fair die is f(4,4,20, 1/6) or approximately 0.011026 .

You can verify that Y=1, S=1 yields a probability p, as you would
expect.  You can also verify that Y=S yields p^^S.

This can be implemented in a simple computer program.  However,
because of the double recursion, the run time of the program is
O( 2^^(S-Y) ).  The formula is essentially called once for each of the
2 to the power of S outcomes.  For S=20, that is more than a million
times.  Beyond S = 30 or so, that approach is so slow as to be
impractical.

A non-recursive program could be written based on an S+1 by Y+1 array
of values, and running in time O( (S*Y)^^2).  The approach would be to
create an array.  Initialize one column of the array to value 1, based
on the first rule.  Initialize one half of the array to 0, as per the
second rule.  Every remaining cell of the array can be calculated from
2 other cells by the function definition.

-- Jim Landis

----------

Ken Butler solution:

Anyway, assuming that independence and constant probability are OK
here, my line of thinking is the following: let N be the total number
of words sent when Y consecutive words are received incorrectly for the
first time.  For example, if Y=3, in the following sequence of words
sent (C = correctly received, I = incorrect):

I C I I C C I I I

N = 9, since 9 words have been sent by the time the 3rd consecutive I
appears.  Relating this to your problem, if N>S, then the radios link
up, whereas if N <= S, the link is disestablished.  So prob(N>S) is the
probability you want.  (This takes care of the "at least" problem,
because once Y consecutive I's show up, we stop looking.)  You also see
that the last four (=Y+1) words sent are a C followed by K I's; this
must be the way the process stops, because if we'd gotten any more
consecutive I's, we would have stopped earlier, and if we'd gotten any
fewer, we'd keep looking.)

To show what happens with Y=2:

N cannot be 0 or 1;
N = 2 if we get I I, whose probability is P^2.
N = 3 if we get C I I, with prob. (1-P)*P^2.
N = 4 if we get I C I I or C C I I, ie. the last 3 are C I I no matter
what the first is.  Probability is (1-P)*P^2 as for N=3.

Then, a pattern:

N = 5 if we survive the first 2 words and then get C I I;
N = 6 if                      3                    C I I;
.
.
N = m if                    m-3                    C I I,

so that prob(N = m) = prob(N > m-3) * (1-P) * P^2.

Overall, the probability is 0 for a bit, P^2 once, (1-P)*P^2 for a bit,
and then the above relationship holds.  This was for Y=2, but the same
idea generalizes to other Y:

Prob(N = m) = :  0 if m < Y [Editor: "m < Y-1" in the original]
                 P^Y if m = Y
                 (1-P) * P^Y * prob(N > m-Y-1) if m > Y.

Because each probability depends on previous ones, you'll need to
calculate these probabilities one at a time, starting from 0 (or Y)
and continuing up to S.  It's probably easiest to keep track of
prob(N > m), since this is the quantity of interest anyway, noting that
prob(N > m) = prob(N > m-1) - prob(N = m), and prob(N > 0) = 1
[Editor: "= 0" in the original].

-- Ken Butler

[ Editor: prob(N>S) is the probability of no run of Y; the probability
asked for is 1 - prob(N>S).  "K I's" means Y I's. ]

[ Editor: a Markov-chain treatment, sci.math/rec.puzzles, May 1998. ]

In article <3557A2ED.F71BB0DC@yahoo.dot.com>, Stacy Friedman
<stacy_friedman@yahoo.dot.com> writes:
|> In the rec.puzzles archive, there is mention of a solution to "What is
|> the probability in n flips of a fair coin that there will be two heads
|> in a row?"
|>
|> I have tried, without success, to extend the solution (which involved
|> the n+2th Fibonacci number) to the following more general question:
|>
|> What is the probability in N flips of a coin where p(head)=P that there
|> will be M heads in a row?

Consider a Markov chain where the state is 0,1,2,...M, corresponding to
the current number of consecutive heads.  Thus you start out in state 0.
If you are in state i and flip heads you go to state i+1, while if you
flip tails you go to state 0.  Since we're interested in whether or not
we reach state M, make that state absorbing, i.e. if you are in state M
you just stay there.  The transition matrix P looks like this (in the
case M=4):

       0    1    2    3    4
   0  [q    p    0    0    0]
      [                     ]
   1  [q    0    p    0    0]
      [                     ]
   2  [q    0    0    p    0]
      [                     ]
   3  [q    0    0    0    p]
      [                     ]
   4  [0    0    0    0    1]

and the probability you want is the entry in row 0, column M of P^N.
A "closed-form" formula could be obtained in terms of the eigenvalues
and eigenvectors of P.  Unfortunately, I don't think there's a nice
formula for the eigenvalues, other than 1, for general M, except that
they are the roots of the polynomial

    t^M - q t^(M-1) - p q t^(M-2) - ... - p^(M-1) q.

and thus are the roots (other than p) of t^(M+1) - t^M + p^M q.
If r_1, ..., r_M are those roots, then the answer will be of the form

f(N) = 1 + sum_{i=1}^M c_i r_i^N

for some constants c_i.  We know the first term (corresponding to the
eigenvalue 1) is 1 because lim_{N -> infinity} f(N) = 1.  The c_i can be
determined by the initial conditions f(N)=0 for N=0,1,...,M-1.

-- Robert Israel <israel@math.ubc.ca>