Hamming Distance on Finite Strings

Counting Coordinate Mismatches

When two strings have the same length, one way to measure their difference is to count the positions where their symbols disagree. This count ignores how different the symbols themselves may be: changing one symbol to another contributes one mismatch, just as any other single-coordinate change does. The resulting distance is called the Hamming distance. It is useful for comparing finite strings and for describing how many coordinate changes separate one string from another.

Fix a nonempty alphabet \(\Sigma\) and a positive integer \(n\). A string of length \(n\) over \(\Sigma\) is an element \(x=(x_1,\ldots,x_n)\) of \(\Sigma^n\), where each coordinate \(x_i\) belongs to \(\Sigma\). We compare strings of the same length; the Hamming distance as defined here does not compare strings of different lengths.

The value is an integer between \(0\) and \(n\), inclusive. It is zero precisely when the strings agree at every coordinate. For a binary alphabet, \(\Sigma=\{0,1\}\), each coordinate contributes either zero or one to the count. The same definition applies to any nonempty alphabet, not just a binary one.

Why Hamming Distance Is a Metric

A metric on a set \(X\) is a function \(d:X\times X\to[0,\infty)\) satisfying four conditions: nonnegativity, identity of indiscernibles, symmetry, and the triangle inequality. Identity of indiscernibles means \(d(x,y)=0\) if and only if \(x=y\). The following result verifies these conditions for Hamming distance.

Proof. Let \(x,y,z\in\Sigma^n\). The number of mismatching coordinates is a cardinality, so \(d_H(x,y)\ge0\). If \(d_H(x,y)=0\), there is no coordinate at which \(x_i\ne y_i\). Therefore \(x_i=y_i\) for every \(i\), which means \(x=y\). Conversely, if \(x=y\), there are no mismatching coordinates and \(d_H(x,y)=0\).

For every coordinate \(i\), \(x_i\ne y_i\) holds exactly when \(y_i\ne x_i\), so the mismatch sets for \((x,y)\) and \((y,x)\) are equal. Hence \(d_H(x,y)=d_H(y,x)\).

It remains to prove the triangle inequality. Define \(M(x,z)=\{i:x_i\ne z_i\}\), and define \(M(x,y)\) and \(M(y,z)\) in the same way. If \(i\in M(x,z)\), then \(x_i\ne z_i\). It cannot be true both that \(x_i=y_i\) and that \(y_i=z_i\), because those equalities would imply \(x_i=z_i\). Thus \(i\in M(x,y)\) or \(i\in M(y,z)\). We have shown \(M(x,z)\subseteq M(x,y)\cup M(y,z)\). Taking cardinalities and using that the size of a union is at most the sum of the sizes gives \(d_H(x,z)\le d_H(x,y)+d_H(y,z)\). All four metric conditions hold, so \(d_H\) is a metric. \(\square\)

The triangle inequality has a coordinate-level explanation: every position where the first and third strings disagree must register a disagreement in at least one of the two comparisons that pass through the middle string. A coordinate may contribute to both comparisons on the right, but it cannot be missing from both.

Computing Distances Coordinate by Coordinate

A reliable calculation records the coordinates first and counts the disagreements second. This avoids confusing the location of a mismatch with the value of the distance. For strings with symbols other than \(0\) and \(1\), the rule is unchanged: equality at a coordinate contributes zero, and inequality contributes one.

Because the distance is integer-valued, it is sometimes helpful to describe strings by how many coordinates may differ from a fixed string. In the topology induced by a metric, an open ball of radius \(r>0\) about \(x\) is the set \(B_{d_H}(x,r)=\{y:d_H(x,y)<r\}\). The strict inequality matters: at radius \(2\), for example, strings at distance exactly \(2\) are not in the ball.

Which Distance Values Can Occur?

Proof. A mismatch set is a subset of \(\{1,\ldots,n\}\), so its cardinality is an integer between \(0\) and \(n\). This proves the first assertion. If \(\Sigma\) contains at least two symbols, choose distinct symbols \(\alpha,\beta\in\Sigma\). For any integer \(k\) with \(0\le k\le n\), let \(x\) have symbol \(\alpha\) in every coordinate. Let \(y\) have symbol \(\beta\) in its first \(k\) coordinates and symbol \(\alpha\) in its other \(n-k\) coordinates. Then \(x\) and \(y\) differ exactly in coordinates \(1,\ldots,k\), so \(d_H(x,y)=k\). This also covers \(k=0\), when there are no differing coordinates, and \(k=n\), when all coordinates differ. If \(\Sigma\) has exactly one symbol, every string in \(\Sigma^n\) has that symbol at every coordinate. Any two such strings are equal, so every distance is \(0\). \(\square\)

In particular, the maximum possible distance is \(n\) when the alphabet has at least two symbols, but this need not hold for every alphabet. For a one-symbol alphabet, no pair differs at any coordinate. This is a useful reminder that the length gives an upper bound on distance; it does not by itself guarantee that the upper bound is attained.

A Common Counting Pitfall

Common mistake. When comparing \(x=01010\) and \(z=00001\), it is incorrect to report mismatches at coordinates \(1\) and \(5\), and then conclude that the distance is \(2\). Check the entries in order: coordinate \(1\) is \(0=0\); coordinate \(2\) is \(1\ne0\); coordinate \(3\) is \(0=0\); coordinate \(4\) is \(1\ne0\); and coordinate \(5\) is \(0\ne1\). The correct mismatch set is \(\{2,4,5\}\), so \(d_H(x,z)=3\). Rechecking each coordinate is especially important when using a computed distance in a triangle-inequality check.

Hamming distance gives a simple metric structure to finite strings: it satisfies the metric axioms, counts symbol changes one coordinate at a time, and makes the integer nature of distances explicit. In applications such as comparing transmitted and received strings, the distance records the number of positions that disagree. The metric itself does not say why two strings differ; it supplies a precise, verifiable measure of how many coordinate positions separate them.