GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
581 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.5k points) 156 264 327 | 581 views

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

3 Answers

+15 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.3k points) 12 55 123
selected by
Nice explanation by using Binomial distribution.Thanks :)
+11 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 Veteran (11.6k points) 7 63 149
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.6k points) 15 71 142
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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8962 Points

  4. srestha

    6460 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4892 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4052 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Popular Question makhdoom ghaya
Great Question makhdoom ghaya
Famous Question makhdoom ghaya
Notable Question PriDix
Popular Question ManojK
Reader Chandramani Adil
Regular qwerty007
Notable Question rishu_darkshadow
Popular Question Rishi yadav
Popular Question makhdoom ghaya
27,417 questions
35,262 answers
84,532 comments
33,497 users