= Variance of cyclic Bernoulli run counts
{title2=$\operatorname{Var}X=np^k(1-p^k)+2n\sum_{j=1}^{k-1}(p^{k+j}-p^{2k})$}
On a cyclic sequence of $n$ independent <Bernoulli random variables> with success probability $p$, count all runs of $k$ consecutive successes, allowing overlaps and taking $1\le k\le n/2$. The count has <expected value> $np^k$. Its <variance> is the displayed expression: each starting indicator has variance $p^k(1-p^k)$; two starts at cyclic distance $j<k$ have joint probability $p^{k+j}$; nonoverlapping starts are independent. There are $2n$ ordered overlapping pairs at each such distance, because the two ranges do not meet when $k\le n/2$.
For $p\le1/2$, summing a <geometric series> gives $\operatorname{Var}X\le np^k(1+2p/(1-p))\le3np^k$. <Markov's inequality> therefore proves absence with high probability when $np^k\to0$, and <Chebyshev's inequality> proves existence and relative concentration when $np^k\to\infty$. This remains valid for varying probabilities eventually at most one half.
Back to article page
