# Probability based on Hamming distance

Two $n$ bit binary strings $S_1$ and $S_2$ are chosen randomly with uniform probability.

The probability that the Hamming distance in between these strings (the number of bit positions where the two strings differ) is equal to $d$ is:

1. $\binom{n}{d} \over {2^n}$
2. $\binom{n}{d} \over {2^n}$
3. $d\over2^n$
4. $1\over2^d$

I tried to solve the problem, but I didn't find any suitable way to tackle this problem.

• Which of the four answers do you want to prove? Or, if they are all correct, can you at least try and prove that the four expressions are equal before attempting to prove that all of them are the answer to the problem posed? Jan 26, 2014 at 16:54
• What does the C stand for..? Jan 26, 2014 at 17:03
• @Dror: I think it is $\binom{n}{d}$
– Alex
Jan 26, 2014 at 18:11
• Ans 1 is correct.Sorry for late reply,was watching Good Will Hunting :) Jan 26, 2014 at 19:00
• @Dror C is Combination. Jan 26, 2014 at 19:02

If I understood the problem correctly, and correct me if I'm wrong:

First it is required that the number of $1$s in $S=S_1 \oplus S_2$ will be $d$.
The number of distinct ordered pairs of binary strings that satisfy the above for a given $S$ is $2^{n}$.
Second, the number of binary strings with exactly $d$ $1$s is $\binom{n}{d}$, and the total number of distinct pairs of strings is $2^{2n}$.

Given the above, the probability of the Hamming distnace being $d$, for two random strings is: $$P(d)=\frac{2^n \binom{n}{d}}{2^{2n}}=\frac{ \binom{n}{d}}{2^{n}}$$

• Can someone please explain how we are getting the $2^n$ part in the numerator? Dec 19, 2019 at 11:50

Start with a simple case, take $d=0$ (both strings are exactly the same). The probability of that a specific sequence coincides is $\frac{1}{2^n} \cdot \frac{1}{2^n}=\frac{1}{2^{2n}}$ and you have $2^n$ such possibilities, hence for $d=0$ this probability is $\frac{2^n}{2^{2n}}=\frac{1}{2^n}$. Can you extend this idea?

• isn't when d=0 both strings will be same? Jan 26, 2014 at 19:32
• you are right! Damn, I've done too much math today) But the idea stays the same: there are $2^n$ ways to have $d_{H}(x,y)=0$
– Alex
Jan 26, 2014 at 19:34
• I am trying to grasp and solve it further.will get back to you if don't find success. Thanks. Jan 26, 2014 at 19:36
• OK, I think Dror's solution is correct.
– Alex
Jan 26, 2014 at 19:37
• If you consider $d=0$, you immediately exclude b) and c) and clearly d) is false, so a) is the only correct solution
– Alex
Jan 26, 2014 at 19:41