5,186 views

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

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

@sachinMittal,

For n=2 and d=1.

All 2 bit strings are: 00,01,10,11

Selecting two strings can be done in 4C2=6 ways. favourable cases are: (00,01) (00,10) (01,11) (10,11) -→ 4 cases

So, probability that “while selecting two strings , their hamming distance will be 1” equals 4/6.

But according to option a, answer should be 1/2

What is wrong in this?
edited
How is the probability of being different and being same are equal ,i.e 1/2 ?
@sameer_hack

Suppose S1 is 11111

Now you choose S2 such that it differs from S1 in exactly 3 places. This can be done in 5C3 ways. Suppose these places are 1st , 3rd and 5th. So these places in S2 will be 0 and remaining places in S2 are 2nd and 4th which will be 1. So, S2 is 01010. Each bit of S2 has two choices , so probability that S2 is 01010 will be 1/(2^5). Can you generalise now?
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).
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

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)

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

is there only one out of $2^n$ chance that both are identical? they can be identical in many ways, isn't it?

It should be like

nC0+nC1+ ... +nCn = 2n

where nCm is choosing m bits from n bits .... Total cases ...

Probability of two random n-bit stings being identical is $\frac{1}{2^{2n}}$ but not $\frac{1}{2^{n}}$.