= Uniform half-circle balance for independent Bernoulli variables
Let $n$ be even and let $X_1,\ldots,X_n$ be independent <Bernoulli distribution>[Bernoulli] variables with parameter $1/2$, arranged on a circle. The probability that some consecutive half-circle $I$ has $|\sum_{i\in I}X_i-\sum_{i\notin I}X_i|\geq w$ is at most $2n\exp(-2w^2/n)$. For a fixed $I$, the variable $Z_I=\sum_{i\in I}X_i+\sum_{i\notin I}(1-X_i)$ has the <binomial distribution> $\operatorname{Bin}(n,1/2)$, and the signed imbalance is $Z_I-n/2$. Apply <Hoeffding inequality> to this single <binomial distribution>[binomial] variable, then take a <union bound> over the at most $n$ intervals. Consequently $w=c\sqrt{n\log n}$ suffices for uniform balance with probability tending to one whenever $c>1/\sqrt2$.
Back to article page
