Two n-bit binary strings, S_1 and S_2, are chosen randomly with uniform probability. The probability that the Hamming di...

Question

Two n-bit binary strings, S_1 and S_2, are chosen randomly with uniform probability. The probability that the Hamming distance between these two strings (the number of bit positions where the two strings differ) is equal to d is

A. C(n,d) / 2^n
B. C(n,d) / 2^d
C. d / 2^n
D. 1 / 2^d

Accepted Answer

P(Hamming distance = d) = C(n,d) / 2^n. Answer: A. We pick two n-bit strings uniformly at random from the 2^n possible strings each, giving 2^(2n) total ordered pairs (S_1, S_2). The Hamming distance equals d when exactly d of the n bit positions differ. We need to count how many (S_1, S_2) pairs have exactly d differing positions and divide by 2^(2n). Since S_1 is chosen uniformly, we can fix S_1 and count how many S_2 differ from it in exactly d positions.

Two n-bit binary strings, S_1 and S_2, are chosen randomly with uniform probability. The probability that the Hamming distance between these two strings (the number of bit positions where the two strings differ) is equal to d is A. C(n,d) / 2^n B. C(n,d) / 2^d C. d / 2^n D. 1 / 2^d