Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / B / 8

Chebyshev's inequality says that for a random variable $Z$ with finite mean and variance, and every $t>0$,

For each cyclic starting position $i$, let $I_i$ indicate that the next $k$ entries are all one. Then $X={\sum }_i{I}_i$ and $\mathbb{E}{I}_i=p^k$, hence $\mathbb{E}X=n{p}^k$.

For two starts separated by $j\in \{1,\dots ,k-1\}$ along either direction, their runs overlap in $k-j$ positions, so $\mathbb{E}(I_i{I}_{i+j})=p^{k+j}$. All other distinct starts use disjoint entries and are independent. Since $k\le n/2$, the two directions' overlap ranges do not intersect. Summing the variances and covariances givesIn particular, dropping negative terms and summing a geometric series yieldswhen $p\le 1/2$. The formula also covers $k=1$ with an empty covariance sum.

For $p=1/2$ and $k={\log }_{2}n+\omega (n)$,If $\omega (n)\to \infty$, the mean tends to zero. Markov's inequality gives $\mathbb{P}(X\ge 1)\le \mathbb{E}X\to 0$, so $\boxed{\mathbb{P}(X=0)\to 1}$.

Now $\omega (n)\to -\infty$ makes $\mathbb{E}X=2^{-\omega (n)}\to \infty$. Chebyshev's inequality and the variance bound giveFor every fixed $ϵ>0$, they likewise giveThus the count is concentrated about its growing mean, despite the overlapping runs.

For $p=1/4$, use $k={\log }_{4}n+\omega (n)$. Then $\mathbb{E}X=4^{-\omega (n)}$, so its limits are exactly those needed for the same two arguments.

For $p=1/{\log }_{e}n$, a convenient definition that also accounts for the varying probability isIt makes $\mathbb{E}X=e^{-\omega (n)}$. Thus $\omega \to +\infty$ gives no runs with high probability, and $\omega \to -\infty$ gives runs and relative concentration. For sufficiently large $n$, $p\le 1/2$, so the same uniform variance bound applies. Definitions are made from the actual integer $k$; no continuous rounding assumption is required. These conclusions retain the stipulated range $1\le k\le n/2$.