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

2 Answers 2

6
$\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$
1
  • $\begingroup$ Can someone please explain how we are getting the $2^n$ part in the numerator? $\endgroup$
    – Stupid Man
    Dec 19, 2019 at 11:50
3
$\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$
8
  • $\begingroup$ isn't when d=0 both strings will be same? $\endgroup$
    – Rishi
    Jan 26, 2014 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, 2014 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, 2014 at 19:36
  • $\begingroup$ OK, I think Dror's solution is correct. $\endgroup$
    – Alex
    Jan 26, 2014 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, 2014 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.