Hamming distance ($d_H$)

The Hamming distance between two equal-length words is the number of coordinates in which they differ.

On binary words of length $n$, normalized Hamming distance is the fraction of differing coordinates. Unlike unscaled Hamming distance, it makes the Hamming cubes a Lévy family under uniform probability measures.

The Hamming cube is $\{-1,1{\}}^n$, or equivalently $\{0,1{\}}^n$, equipped with Hamming distance. Under its uniform probability measure, the distance from a fixed vertex has the binomial distribution with parameters $n,1/2$. This converts geometric ball sizes into probability tails.

An inclusion-maximal separated set of separation $an$ covers the Hamming cube by strict-radius $an$ balls. The Hoeffding lower-tail bound for Hamming balls then gives at least $e^{2n(1/2-a{)}^2}$ selected vertices. At $a=1/8$ this yields $e^{9n/32}$ vertices, all separated by at least $n/8$.

This Hamming distance on partitions identifies a group with its complement because exchanging the two group names does not change the partition. Complementation is an isometry of the ordinary Hamming distance, so minimizing over this two-element group action gives a quotient metric and preserves the triangle inequality. Negating a zero-one indicator is not complementation; with $\pm 1$ membership vectors, it is.

Suppose $v_i=\pm 1/\sqrt{n}$ encodes the true partition and $\hat{v}$ is a unit estimated eigenvector. Every coordinate of the wrong sign contributes at least $1/n$ to ${\min }_{\sigma =\pm 1}\Vert \hat{v}-\sigma v{\Vert }_2^2=2(1-|{\hat{v}}^{\top }v|)$. Since this is at most $2(1-|{\hat{v}}^{\top }v{|}^2)$, which is the squared Frobenius distance between the rank-one orthogonal projection matrices, the bound follows. Coordinates estimated as zero may be assigned consistently to either group.

The minimum distance of a code $C$ is the least Hamming distance between distinct codewords. For a linear code, translation invariance makes this equal to the least Hamming weight of a nonzero codeword.

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 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.