# Explain why the Hamming distance satisfies the triangle inequality

The Hamming distance satisfies the triangle inequality that is for all $x,y,u$ in $c$ such that $d(x,y) \le d(x,u) + d(u,y)$ where $c$ is a code. Also when does the equality hold?

My approach is: turn $x$ to $u$ by changing at most $d(x,u)$ letters and turn $u$ to $y$ by changing at most $d(u,y)$ letters. So turning $x$ to $t$ will change no more than $d(x,u) + d(u,y)$ letters.

By looking at the following example, $x = 001111, \ y = 111111, \ z = 011111$, the equality holds when changing $x$ to $y$, $z$ is just an intermediate step.

Does this make sense?

It’s a good intuition, but some work is needed in order to translate it into a proof. For $x\in C$ assume that $x=x_1\ldots x_n$. For $x,y\in C$ let $D(x,y)=\{k:x_k\ne y_k\}$; then by definition $d(x,y)=|D(x,y)|$.

Now suppose that $x,y,z\in C$. Then

$$D(x,y)=D(x,z)\mathrel{\triangle}D(z,y)\subseteq D(x,z)\cup D(z,y)\;,$$

where $\triangle$ denotes the symmetric difference, and therefore

$$d(x,y)=|D(x,y)|\le|D(x,z)\cup D(z,y)|\le|D(x,z)|+|D(z,y)|=d(x,z)+d(z,y)\;.$$

The equality $D(x,y)=D(x,z)\mathrel{\triangle}D(z,y)$ is really just your observation that to get from $x$ to $y$, we can first flip the bits in $D(x,z)$ to get from $x$ to $z$ and then flip the bits in $D(z,y)$ to get from $z$ to $y$. The bits that are affected by at least one stage of this process are those in $D(x,z)\cup D(z,y)$, and those that are affected by both stages are those in $D(x,z)\cap D(z,y)$. Thus $D(x,y)$, the set of bits that are actually changed in going from $x$ to $y$ by way of $z$ are those in

$$\big(D(x,z)\cup D(z,y)\big)\setminus\big(D(x,z)\cap D(z,y)\big)=D(x,z)\mathrel{\triangle}D(z,y)\;.$$