= Solution
The <Hoeffding inequality> states that if $X_1,\ldots,X_n$ are <independent random variables> with $a_i\leq X_i\leq b_i$ almost surely, then for $t>0$
$$
P\left(\sum_{i=1}^n(X_i-EX_i)\geq t\right)\leq\exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right).
$$
The same bound holds for the lower tail. Consequently the two-sided tail is at most twice this bound. When all ranges have length zero, the sum is deterministic and every positive tail probability is zero.
We construct an <exponential packing of a Hamming cube>. Choose an <inclusion-maximal separated set> $S$ in $\{-1,1\}^n$ with separation at least $r=n/8$ for the <Hamming distance>. It exists by a finite greedy procedure: keep adding any vertex at distance at least $r$ from all selected vertices until none remains. By maximality, every vertex is within distance strictly less than $r$ of some member of $S$. This is the principle that <maximal separated sets give covers>.
For a uniformly random vertex $U$ and any fixed vertex $s$, the mismatch indicators in different coordinates are <independent> <Bernoulli random variables> with success probability $1/2$. Hence $\rho(U,s)$ has the <binomial distribution> with parameters $n,1/2$. The lower-tail <Hoeffding inequality> gives
$$
P\left(\rho(U,s)\leq\frac n8\right)=P\left(\rho(U,s)-\frac n2\leq-\frac{3n}8\right)\leq e^{-9n/32}.
$$
Thus the <Hoeffding lower-tail bound for Hamming balls> shows that every strict-radius ball $B_{<r}(s)$ has at most $2^ne^{-9n/32}$ vertices. Using a strict ball handles noninteger $n/8$ without changing the required separation.
The strict balls centered at $S$ cover the entire <Hamming cube>. Counting their union by the sum of their sizes yields
$$
2^n\leq\sum_{s\in S}|B_{<r}(s)|\leq|S|\,2^ne^{-9n/32},\qquad |S|\geq e^{9n/32}\geq e^{n/4}.
$$
Therefore
$$
\boxed{|S|\geq e^{n/4},\qquad\min_{s\ne s'\in S}\rho(s,s')\geq n/8.}
$$
In particular this proves the assertion for every $n\geq8$. Maximality here means that no further vertex can be added; finding a largest <separated set> is unnecessary.
Back to article page
