Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / B / 6

First take $0<p<1$. For $X\sim \mathrm{Bin}(n,p)$, independence of the Bernoulli trials givesFor $x\ge p$ and $t>0$, Markov inequality yieldsDifferentiate the logarithm of the right-hand side to minimize it. The stationary point satisfieswhich is at least $1$ when $x\ge p$. Substitution givesWhen $x=p$, use the limit $t_{\ast }\to 0$, giving the trivial bound $1$.

For $x\le p$, take $t<0$. On $\{X\le nx\}$ we have $e^{tX}\ge e^{tnx}$, so the same Markov inequality gives the same expression. Its minimizing $t_{\ast }$ is now nonpositive, yielding the stated lower-tail bound. No rounding of $nx$ is needed, because the exponential event inclusion holds for real thresholds. The cases $p=0$ and $p=1$ are deterministic and follow directly, or by the corresponding limits.

Write the bound in part (a) as $e^{-nD(x\Vert p)}$, where the Bernoulli Kullback-Leibler divergence with natural logarithms isFor fixed $p\in (0,1)$, $D(p\Vert p)=0$, its first derivative with respect to $x$ vanishes at $p$, andIntegrating this lower bound twice, on either side of $p$, gives the Bernoulli relative entropy lower bound $D(x\Vert p)\ge 2(x-p{)}^2$. Apply the two tails from part (a) at $x=p+h$ and $x=p-h$ and use the union bound:A tail with threshold outside $[0,1]$ is empty; thresholds at the endpoints follow by continuity of the bound. For $h=0$ the right-hand side is $2$, so the assertion is immediate. This is the binomial form of Hoeffding inequality.

The sum of the first $n/2$ variables has distribution $\mathrm{Bin}(n/2,1/2)$. For any fixed half-circle interval $I$, putThe $n$ terms defining $Z_I$ are independent Bernoulli variables of parameter $1/2$, so $Z_I\sim \mathrm{Bin}(n,1/2)$ and $D_I=Z_I-n/2$. Part (b), with $h=w/n$, givesThere are at most $n$ cyclic intervals of length $n/2$; this also covers the non-wrapping interpretation in the question. They need not be independent, since the union bound always applies. HenceWith $w=c\sqrt{n\log n}$ and natural logarithms, this becomes $2n^{1-2c^2}$, which tends to zero for every $c>1/\sqrt{2}$. In particular,The argument proves uniform half-circle balance for independent Bernoulli variables. It improves on separately bounding the two half sums by recognizing the difference as one centered binomial variable.