edited by
7,280 views
26 votes
26 votes

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

  1. $\dfrac{^{n}C_{d}}{2^{n}}$

  2. $\dfrac{^{n}C_{d}}{2^{d}}$

  3. $\dfrac{d}{2^{n}}$

  4. $\dfrac{1}{2^{d}}$

edited by

6 Answers

Best answer
40 votes
40 votes

Answer - A

there $n$ binary bits that can differ but only $d$ should differ in this case,

ways of choosing these $d$ bits $={^n}C{_d}$

probability of $d$ bits differ but, $n - d$ bits do not differ $=\left(\dfrac{1}{2}\right)^{d}.\left(\dfrac{1}{2}\right)^{(n - d)}$

no of ways $=\dfrac{{^n}C{_d}}{2^n}.$

edited by
23 votes
23 votes
S1 ⊕ S2 will give combinations of 0s and 1s resulting into 'n' bit string. In the Xor-ed result, 1's will be for those bits which are different in S1 and S2 (as 1⊕0 =0⊕1=1) and 0s will be for those bits which are same. Here we need to find the probability that there are 'd' 1s in the 'n' bit strings.

Total number of strings (S1 ⊕ S2) we can get is 2^n. Among them we want strings which have 1's in exactly 'd' positions. Ways of choosing 'd' positions among 'n' where 1 can be placed is nCd. The rest (n-d) positions will automatically get 0.

The probability becomes nCd/(2^n).
edited by
10 votes
10 votes
Basically the problem statement says that "From all the possible pairs of n bit binary strings(S1,S2 where both S1 and S2 are n bit binary strings) if we randomly select any pair then what is the probability that ,Hamming distance between the strings of that selected pair is d "

Number of binary string pairs (S1,S2) each having length n ,can be formed in 2^n * 2^n ways.

Now we have to find out the number of such pairs where hamming distance between S1,S2 is d.

In order to form such pairs first select any S1(which can be done is 2^n ways),

Now lets form S2: Select nCd positions from S2, once nCd bit positions from S2 is selected, for those positions we have only one choice(opposite of S1's value for that particular position). Remaining n-d places of S2 will have exactly same value as S1's value for those positions(this will make sure that hamming distance of S1, S2 is exactly d) hence only one way we can do so.
So , for a particular S1, we can form S2 in  nCd *1 *1=nCd ways ,such that hamming distance of (S1,S2)=d.

There are 2^n  ways to form S1, So total number of pairs where hamming distance is d = 2^n * nCd

We already know  number of binary string pairs each having length n ,can be formed in 2^n * 2^n ways.

 Hence required probability= (2^n * nCd) / ( 2^n * 2^n) = nCd/ 2^n
edited by
4 votes
4 votes

Alternate Approach

Hamming Distance: Number of positions at which the corresponding bits are different.

Probability of two random n-bit stings being identical = $ \frac{1}{2^n} $

Now choose $d$ positions where the strings will differ in $ ^nC_d $ ways.

Required Probability = $ \frac{^nC_d}{2^n} $

$\Rightarrow$ Answer is (A)

Answer:

Related questions

61 votes
61 votes
3 answers
4
Arjun asked Sep 26, 2014
17,269 views
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________ .