From: "Adam Atkinson" <ghira@mistral.co.uk>
Subject: Re: Odds of a run existing
Date: 06 Mar 99 12:40:09 +0000
Newsgroups: sci.math

Elio Fabri and Francesco Romani did it this way. The method is used in
Feller, Vol 1.

Elio defined f(n,r) = prob. that the first run of length r appears at
trial n, g(n,r) = prob that a run of length r has appeared at or
before time n and h(n,r) = prob. that no run of length r has appeared.
also p(n,r) = prob. that max run to have appeared by time n was of
length r.

for the record, Fabri and Romani were considering runs of failures. p
is the probability of a success and q that of a failure.

clearly, g(n,r) = sum f(i,r) for i =0,...,n

f(n,r) = pq^r [1-g(n-r-1,r)]

h(n,r) = 1-g(n,r)

p(n,r) = h(n,r+1) - h(n,r)

Romani observed that you can obtain

h(n,r) = h(n-1,r) - pq^r h(n-r-1,r)

I don't know if any of this helps. I've forwarded your messages to
Fabri and Romani.

I thought "inclusion-exclusion" myself when thinking about the
problem, but couldn't see where I could actually use it.

-- 
Adam Atkinson (ghira@mistral.co.uk)
BRITISH PUSH BOTTLES UP ENEMY