Two '$n$' bit binary strings $S_1$ and $S_2$ are chosen randomly with uniform probability. The probability that the hamming distance between these strings (the number of bit positions where the two strings differ) is equal to $d$ is ?

My approach

We can choose 2 random strings out of $2^n$ strings possible in $2^n C 2$ ways.

Now the probability of 2 bits being different is $0.5$

Applying binomial distribution we get,

$2^n C 2 * (0.5)^d * (0.5)^{n-d}$ .

Here $(0.5)^d$ means probability of 'd' bits being different in 2 strings which were chosen.

Why is this approach wrong ?


The approach is wrong because you don't say which random variable satisfies which binomial distribution. The answer is that the number $X$ of bits that differ between the two strings satisfies $B(n, \frac{1}{2})$. Hence the probability is $$ P(X=d)=\binom{n}{d}(1/2)^d (1/2)^{n-d} = \frac{1}{2^n}\binom{n}{d} $$

Edit As your comment implies that you want a more complete model, here it is: let $K = \{0, 1\}^n$ be the set of n-bit strings. Let $d\in [0, n]$ and $K_d$ the substet of $K$ consisting of the strings with exactly $d$ bits set. Note that $\text{Card}(K_d) = \binom{n}{d}$.

We choose randomly two strings $s_1, s_2\in K$. They can be the same string, so this amounts to choosing an ordered random pair $(s_1, s_2)\in K^2$. There are $2^{2 n}$ possible choices, each of them has the probability $2^{-2n}$. The number $\delta(s_1, s_2)$ of bits that differ between $s_1$ and $s_2$ is the number of bits set in their bitwise xor sum $s_1 \oplus s_2$, or bitwise sum mod 2. This operation makes $K$ a group where each element is its own opposite. We need to count the number of pairs $(s_1, s_2)$ such that $s_1\oplus s_2 \in K_d$. It is very easy, because this is equivalent to $s_2 = s \oplus s_1$ with $s \in K_d$. It follows that for each $s_1\in K$ and each $s \in K_d$, there is exactly one $s_2$. Hence the number of ordered pairs is $\text{Card}(K\times K_d) = 2^n \binom{n}{d}$. Finally, the probability is $$ 2^{-2n} 2^n \binom{n}{d} = \frac{1}{2^n}\binom{n}{d} $$

  • $\begingroup$ What about choosing 2 strings out of 2^n strings? Why are you not considering that ? $\endgroup$ – Zephyr Nov 19 '17 at 8:30
  • $\begingroup$ So in your first solution, you already assumed that we have two strings instead of choosing them? $\endgroup$ – Zephyr Nov 19 '17 at 10:01
  • $\begingroup$ No, the reasoning for the first solution is that for each bit, there are 4 equiprobable choices: $(0,0), (0,1), (1, 0), (1, 1)$. The probability that the two strings differ on this bit is $1/2$. As the values of the strings on each bit are independent, it follows that $\delta(s_1, s_2)$ obeys $B(n, 1/2)$. $\endgroup$ – Gribouillis Nov 19 '17 at 10:12
  • $\begingroup$ Yes I understand that. But you assume that you have 2 strings of n bits with you. Out of those n bits, probability of X=d is as shown by you right ? $\endgroup$ – Zephyr Nov 19 '17 at 10:14
  • 1
    $\begingroup$ Let's say we have $2n$ randomly and independently chosen bits. $\endgroup$ – Gribouillis Nov 19 '17 at 10:15

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.