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:
- $\binom{n}{d} \over {2^n}$
- $\binom{n}{d} \over {2^n}$
- $d\over2^n$
- $1\over2^d$
…choose the right answer.
I tried to solve the problem, but I didn't find any suitable way to tackle this problem.
Best Answer
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}}$$