Two n bit binary strings, S1 and S2, are chosen randomly with uniform…
2004
Two n bit binary strings, S1 and S2, 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
- A.
nCd /2n
- B.
nCd / d
- C.
d/2n
- D.
1/2d
Attempted by 1 students.
Show answer & explanation
Correct answer: A
Answer: C(n,d)/2^n
Reasoning:
Counting view: Pick the first string in 2^n ways. For a fixed first string, choose which d bit positions will differ (C(n,d)). That determines the second string. So there are 2^n * C(n,d) ordered pairs with Hamming distance d, out of 4^n total ordered pairs, giving probability C(n,d)/2^n.
Binomial view: For each bit position the two strings differ with probability 1/2 independently. The number of differing positions is therefore Binomial(n, 1/2), so
P(distance = d) = C(n,d) (1/2)^d (1/2)^{n-d} = C(n,d)/2^n.