most recent 30 from http://mathoverflow.net 2013-05-19T04:00:21Z http://mathoverflow.net/feeds/question/3761 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3761/probability-of-observing-a-hamming-distance-k-in-a-pair-of-binary-strings-of-len sublimated 2009-11-02T06:57:41Z 2009-11-02T06:57:41Z

<p>Suppose I have two binary strings of the same length N. If I compute the Hamming distance on the strings, then I find the number positions in which the strings have the different values but the same index. So a simple case might be two 4-bit strings.</p> <pre><code>1000 0001 </code></pre> <p>Which have a hamming distance of 2. What is the probability of observing this distance k among randomly generated binary strings of length N?</p> <p>My colleague thinks the answer is:</p> <pre><code>N choose k / 2^N </code></pre> <p>An additional question: is it less probable to observe strings with a smaller Hamming distance.</p>