5
$\begingroup$

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$

...choose the right answer.

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dilip Sarwate Jan 26 '14 at 16:54
  • $\begingroup$ What does the C stand for..? $\endgroup$ – user76568 Jan 26 '14 at 17:03
  • 1
    $\begingroup$ @Dror: I think it is $\binom{n}{d}$ $\endgroup$ – Alex Jan 26 '14 at 18:11
  • $\begingroup$ Ans 1 is correct.Sorry for late reply,was watching Good Will Hunting :) $\endgroup$ – Rishi Jan 26 '14 at 19:00
  • $\begingroup$ @Dror C is Combination. $\endgroup$ – Rishi Jan 26 '14 at 19:02
4
$\begingroup$

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}}$$

$\endgroup$
  • $\begingroup$ Can someone please explain how we are getting the $2^n$ part in the numerator? $\endgroup$ – Stupid Man Dec 19 '19 at 11:50
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ isn't when d=0 both strings will be same? $\endgroup$ – Rishi Jan 26 '14 at 19:32
  • 1
    $\begingroup$ 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$ $\endgroup$ – Alex Jan 26 '14 at 19:34
  • $\begingroup$ I am trying to grasp and solve it further.will get back to you if don't find success. Thanks. $\endgroup$ – Rishi Jan 26 '14 at 19:36
  • $\begingroup$ OK, I think Dror's solution is correct. $\endgroup$ – Alex Jan 26 '14 at 19:37
  • 2
    $\begingroup$ If you consider $d=0$, you immediately exclude b) and c) and clearly d) is false, so a) is the only correct solution $\endgroup$ – Alex Jan 26 '14 at 19:41

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.