Hamming ball ($B_r(x)$)

The Hamming ball of radius $r$ about a word $x$ is the set of words whose Hamming distance from $x$ is at most $r$.

For $0\le \rho \le 1-1/q$, the exponential growth rate of a q-ary Hamming ball is $H_q(\rho )$. Stirling's formula gives the exponent of each summand $\left(\genfrac{}{}{0ex}{}{n}{i}\right)(q-1{)}^i$, and the sum lies between its largest term and $n+1$ times that term. Above the entropy-maximizing radius fraction, the exponent is one.

// Target: algebra.bigb

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.

For $0<\rho \le 1/2$, the number of binary words within Hamming distance $\rho n$ of a fixed word is at most $e^{nh(\rho )}$, with the binary entropy function in natural logarithms. In $1={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right){\rho }^j(1-\rho {)}^{n-j}$, each summand weight for $j\le \rho n$ is at least ${\rho }^{\rho n}(1-\rho {)}^{n(1-\rho )}=e^{-nh(\rho )}$. Also $h^{\prime \prime }(\rho )=-1/(\rho (1-\rho ))\le -4$, so $\log 2-h(1/2-a)\ge 2a^2$. These two bounds give the approximate-recovery denominator in the list-decoding Fano inequality.