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

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.