A random bit string of length n is constructed by tossing a fair coin n times…
2005
A random bit string of length n is constructed by tossing a fair coin n times and setting each bit to 0 or 1 depending on whether the outcome is head or tail, respectively. What is the probability that two such randomly generated strings are not identical?
- A.
1/2^n
- B.
1 - (1/n)
- C.
(1/n!)
- D.
1 - 1/2^n
Attempted by 7 students.
Show answer & explanation
Correct answer: D
There are 2^n possible bit strings of length n, and each is equally likely.
Generate the first string. For the second randomly generated string to be identical to the first, all n bits must match. Equivalently, among the 2^n possible second strings, exactly one string is identical to the first.
Therefore,
P(two strings are identical) = 1/2^n.
Hence,
P(two strings are not identical) = 1 - 1/2^n.