# Probability that hamming distance is d.

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}$$
• 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)$. – Gribouillis Nov 19 '17 at 10:12
• Let's say we have $2n$ randomly and independently chosen bits. – Gribouillis Nov 19 '17 at 10:15