I choose two code words independently at random from $\mathbb F_2^n$ where each string has $n$ binary digits equally likely. $\mathbb F_2$ represens the binary digits.

The Hamming distance is between two vectors $x,y\in\mathbb F_2^n$ is the number of places where they differ: $d(x,y)=|\{j:x_j\not = y_j\}|$

How can I evaluate the expected distance then?


In effect you’re choosing one word at random and asking for its expected distance from the zero word. That’s clearly $n/2$: every word at distance $k$ has a word at distance $n-k$ as its complement.

  • $\begingroup$ Simple and easy, thank you very much. $\endgroup$ – Alexander Nov 12 '13 at 12:28
  • $\begingroup$ @Alexander: You’re very welcome. $\endgroup$ – Brian M. Scott Nov 12 '13 at 12:28

Nothing wrong with Brian's answer. Just adding a different way of looking at it. This has the advantage of being perhaps easier to generalize to alphabets larger than $\{0,1\}$.

The expected contribution (to the Hamming distance) of bit number $i$ is clearly $1/2$. After all, the contribution is either zero or one, and both are equally likely. Now the Hamming distance between two vectors is the sum of the contributions of individual bits. And the expected value of their sum is the sum of the expected values. As there are $n$ bits, this gives $n/2$ as the answer.

  • $\begingroup$ In this sense the Hamming metric is a bit like the squared Euclidean distance, where you can sum the squared contributions of individual components. $\endgroup$ – Jyrki Lahtonen Nov 12 '13 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.