A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is: A. 1/2^n B. 1 - 1/n C. 1/n! D. 1 - 1/2^n

GATE 2005 · Engineering Mathematics · Binomial Distribution · easy

Answer: P(not identical) = 1 - 1/2^n. Answer: D.

1. Probability that two strings are identical: Fix string 1. String 2 must match all n bits. P(each bit matches) = 1/2. By independence: P(all n bits match) = (1/2)^n = 1/2^n.
2. Apply complement rule: P(strings are NOT identical) = 1 - P(strings are identical) = 1 - 1/2^n.