Hamming distance ($d_H$)

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

The Hamming space of length $n$ over a finite field ${\mathbb{F}}_q$ is the set ${\mathbb{F}}_q^n$ equipped with Hamming distance, the number of coordinates at which two words differ. The Hamming weight of a word is its distance from zero.

This is the maximum Hamming distance between the characteristic vectors of members of a set family. In a down-set, one can replace a pair by disjoint subsets with the same union, so the maximum distance equals the largest size of a union of two members. A t-intersecting family has diameter at most $n-t$.

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 relative minimum distance of a length-$n$ code of minimum distance $d$ is $d/n$. It expresses the guaranteed separation as a fraction of the block length.

// Target: algebra.bigb

The quantity $A_q(n,d)$ is the largest cardinality of a length-$n$ code over an alphabet of size $q$ with minimum Hamming distance at least $d$. The code need not be linear.

// Target: algebra.bigb

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.