GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
449 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 (13k points)   | 449 views

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

3 Answers

+11 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
+5 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.7k 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 (13.1k points)  
Read the question once ! Answer should be D .


Top Users Jun 2017
  1. Bikram

    3912 Points

  2. Arnab Bhadra

    1526 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1491 Points

  5. Debashish Deka

    1460 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1280 Points

  8. Rupendra Choudhary

    1242 Points

  9. rahul sharma 5

    1240 Points

  10. Arjun

    1228 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    412 Points

  2. akankshadewangan24

    334 Points

  3. Arjun

    268 Points

  4. Abhisek Das

    230 Points

  5. Debashish Deka

    214 Points


23,433 questions
30,147 answers
67,595 comments
28,478 users