What is the probability of 3 or more consecutive successes in N trials

177 Views Asked by At

Let the probability of a success in a trial be $p$ (let $q = 1-p$).

We want to know $P(n)$, the probability of 3 (or more) consecutive successes happening at least once in $n$ trials.

$P(3)$ is $p^3$
$P(4)$ is $p^3 + qp^3$

i.e. the first 3 (and then we don't care), OR not the first one but the next three

$P(5)$ is $p^3 + qp^3 + q^2p^3 + qp^4$

If we let $Q(n)$ be $1-P(n)$ and consider further trials to a string of trials with no successes, we see (a 3rd order recurrence relation)

$Q(n)=qQ(n−1)+pqQ(n−2)+p^2qQ(n−3)$ for $n≥3$, $1$ otherwise

This well explained in https://math.stackexchange.com/q/1176022 (thanks @awkward)

My question is: can the solution be written explicitly as a function of $n$.
e.g. Could we solve say $P(20)$ without resorting to a computer program?

1

There are 1 best solutions below

1
On

Yes, you can give an explicit formula for $P(n)$. We will answer the complimentary question, finding the probability that there are never $3$ or more consecutive successes.

First, we find the number of outcomes where there are exactly $k$ successes, with no three successes in a row. There are $n-k$ failures, which divide the successes into $n-k+1$ contiguous blocks. Each block must have at most $2$ successes. Therefore, this is equivalent to counting nonnegative integer solutions to the equation $$ x_{1}+\dots+x_{n-k+1}=k, \\ 0\le x_i\le 2\;\text{ for each $i\in \{1,\dots,n-k+1\}$} $$ This problem is well-known, and the solution is $$ \sum_{i=0}^{n-k+1}(-1)^i\binom{n-k+1}{i}\binom{n-3i}{k-3i} $$ Putting this altogether, $$ 1-P(n)=\sum_{k=0}^n p^kq^{n-k} \sum_{i=0}^{n-k+1}(-1)^i \binom{n-k+1}i\binom{n-3i}{k-3i} $$ Some people would not call this a "closed" form, but it is an explicit formula for $P(n)$, since you are not required to know earlier values of $P(n-i)$ to compute $P(n)$.