Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know how to compute the probability that 0 runs (or one or more) of M consecutive successes will occur in a sequence of N trials, each with probability P of success.

Is there an explicit formula (mass function) or a method of calculation (for example in Maple) to find the probability that exactly R runs of M consecutive successes will occur in a sequence of N trials, each trial with probability P of success?

I have the same question about the cumulative distribution function?

share|cite|improve this question
To clarify: in FFSSSF (S = success) how many "runs of M=2 consecutive successes" you'd count ? 2? 0? – leonbloy Jan 25 '11 at 17:44
I count SSS 2 successes – Jean-Pierre Jan 26 '11 at 2:20
up vote 3 down vote accepted

Let's first count the probability that exactly $R$ runs of $M$ successes happen in $N$ trials, and the last trial fails. Denote by $p$ the probability of success, and by $q$ the probability of failure.

Each set of runs can be "tokenized" into parts of the form $S^kF$ (this is because the last trial fails). If $k < M$ then we count no runs, and otherwise we count $k - M + 1$ runs. We're going to form a bivariate generating function, with $x$ being the total number of trials, and $y$ being the number of runs. Each part contributes the following: $$P(x,y) = xq(1 + px + \cdots + (px)^{M-1} + (px)^My + (px)^{M+1}y^2 + \cdots).$$ We can get an explicit formula for $P(x,y)$ using geometric series identities: $$P(x,y) = xq\left(\frac{(px)^{M-1}-1}{px-1} + \frac{(px)^{M-1}}{1-pxy}\right).$$ The required probability is the coefficient of $x^N y^R$ in $1/(1-P(x,y))$.

Now let's do the same when the last trial succeeds. The last piece is then $P(x,y)/xq$, and so we want the coefficient of $x^N y^R$ in $(P(x,y)/xq)/(1-P(x,y))$. In total, the required probability is the coefficient of $x^N y^R$ in $$ \frac{1+P(x,y)/xq}{1-P(x,y)}. $$

share|cite|improve this answer
Seems like the two formulas for $P(x,y)$ don't agree. Shouldn't the two fractions in the explicit formula be $((px)^M-1)/(px-1)$ and $(px)^M y/(1-pxy)$? – mjqxxxx Jan 26 '11 at 4:49
I broke it the other way, the two forms should be equivalent. – Yuval Filmus Jan 26 '11 at 6:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.