= Avoidance recurrence for two consecutive successes
{title2=$p_n=(1-q)p_{n-1}+q(1-q)p_{n-2},\quad p_0=p_1=1$}
For <independent and identically distributed> trials with constant success <probability> $0<q<1$, let $p_n$ be the <probability> of avoiding two consecutive successes in the first $n$ trials. An acceptable <sequence> starts either with a failure, leaving $n-1$ unrestricted fresh trials to check, or with a success followed by a failure, leaving $n-2$. These disjoint cases prove the recurrence for $n\geq2$.
Its <characteristic roots> are
$$
r_\pm=\frac{1-q\pm\sqrt{(1-q)(1+3q)}}2.
$$
They are distinct, and the <initial conditions> yield
$$
p_n=\frac{1-r_-}{r_+-r_-}r_+^n+\frac{r_+-1}{r_+-r_-}r_-^n.
$$
If $T$ is the completion time of the first consecutive pair, then $p_n=\mathbb P(T>n)$. The recurrence describes the whole tail distribution rather than only its mean.
Back to article page
