The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
1.1k 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}}$

asked in Probability by Veteran (59.5k points)
edited by | 1.1k views

4 Answers

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

answered by Loyal (9k points)
edited by
+8
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.
0
yes , it's also a way
–2
@all can ny buddy tell how to understand this question?
+13
^
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.
0
@sachin awesome
+2

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

Total=2n

Prob = nCd/2n

+6 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).
answered by Loyal (8.4k points)
edited by
0 votes
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 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
answered by Active (1.6k points)
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)

answered by Junior (713 points)
0

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?

0

It should be like 

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

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

Answer:

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

38,111 questions
45,619 answers
132,311 comments
49,291 users