GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
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}$
asked in Probability by Veteran (13.1k points)   | 488 views

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

3 Answers

+12 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 (9.1k points)  
selected by
+6 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 (6.8k points)  
nice explanation ....
–2 votes
Favourable case is 1 and the total sample space is $2^n$ so it must be $1/2^n$
answered by Veteran (13.1k points)  
Read the question once ! Answer should be D .
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


Top Users Aug 2017
  1. Bikram

    5034 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3296 Points

  5. rahul sharma 5

    3178 Points

  6. makhdoom ghaya

    2530 Points

  7. just_bhavana

    2428 Points

  8. stblue

    2240 Points

  9. Tesla!

    2076 Points

  10. joshi_nitish

    1830 Points


25,032 questions
32,178 answers
74,993 comments
30,218 users