The Gateway to Computer Science Excellence
+16 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}}$

in Probability by Veteran
edited by | 2.4k views

4 Answers

+28 votes
Best answer

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

by Loyal
edited by
Can it be think of in another way that total no of favourable cases =nCd and total no of cases are where in any of the n positions we can have any bit so 2^n total cases.
yes , it's also a way
@all can ny buddy tell how to understand this question?
Think like this: U already have one string of length with u, and now u want to create one other string that has hamming distance of $d$ then out of $n$ positions u have $d$ positions to choose, on which u might toggle bit.
@sachin awesome

Choose a no.S1 out of  2n. Now S2 should be such that differs in bits are d in number.

Favor= no. of such strings possible are = nCd


Prob = nCd/2n

+12 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).
by Boss
edited by
+7 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
by Active
edited by
0 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)

by Junior

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,006 answers
94,685 users