488 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}$

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

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)

selected by
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.
nice explanation ....
Favourable case is 1 and the total sample space is $2^n$ so it must be $1/2^n$
total strings that can be generated are 2^(n)

((2^(n)) * (2^(n) - 1)) / ( 2^(n) * 2^(n))

1- (1/2^(n))

in total outcomes for first string it can be any amongst 2^(n) and similar for choosing second string