+3 votes
382 views

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:

1. $\frac{1}{2^n}$
2. $1 - \frac{1}{n}$
3. $\frac{1}{n!}$
4. $1 - \frac{1}{2^n}$
asked | 382 views

Total possible selections ((2n)C1 ) * ((2n)C1 ) . Favorable outcomes   (2n) * (2n-1)

## 3 Answers

+9 votes
Best answer

answer - D

suppose there are k places within n bit string where mismatch has occoured

probability of this occouring is nCk(prob. of mismatch)k(prob. of match)(n - k) = nCk(1/2)k(1/2)(n-k) = nCk(1/2)n

k can range from 1 to n hence required probability sum(nCk(1/2)n) where k ranges from 1 to n

hence (1/2n)(2n - 1)

Alternatively

Probability of matching at given place 1/2

there are n places hence probability of matching 1/(2n)

hence probability of mismatch 1 - 1/(2n)

answered by Boss (9k points)
selected by
+3 votes
Total combinations of string that can be generated are 2^n. We will get one such string in the first experiment. So favourable cases for the second string are 2^n-1, so that it doesnt match with the previous generated string.

Hence Probablity= (2^n-1)/2^n= 1-1/2^n.
answered by Boss (5.5k points)
–1 vote
Favourable case is 1 and the total sample space is $2^n$ so it must be $1/2^n$
answered by Veteran (13k points)
Read the question once ! Answer should be D .
Answer:

+15 votes
3 answers
1
+1 vote
2 answers
2
+6 votes
1 answer
3