Hoeffding lower-tail bound for Hamming balls
= Hoeffding lower-tail bound for Hamming balls
{c}
{title2=$2^{-n}|B_{an}|\leq e^{-2n(1/2-a)^2}$}
For a uniform vertex of the <Hamming cube>, distance from a fixed vertex is the sum of $n$ <independent> <Bernoulli random variables> with parameter $1/2$. The lower-tail <Hoeffding inequality> implies that the fraction of vertices at distance at most $an$, $0<a<1/2$, is at most $e^{-2n(1/2-a)^2}$. Strict-radius balls satisfy the same upper bound.