The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
937 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 (18k points) | 937 views

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

5 Answers

+23 votes
Best answer

answer - D

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

probability of this occouring is,

$^{n}C_{k}.\text{(prob. of mismatch)}^{k}\text{(prob. of match)}^{(n-k)}$

$ = ^{n}C_{k}\left(\dfrac{1}{2}\right)^{k}\left(\dfrac{1}{2}\right)^{(n-k)} $

$= ^{n}C_{k}\left(\dfrac{1}{2}\right)^{n}.$

$k$ can range from $1$ to $n$ hence required probability $\sum \left(^{n}C_{k}\left(\frac{1}{2}\right)^{n}\right)$ where $k$ ranges from $1$ to $n$

hence $\left(\dfrac{1}{2^{n}}\right)\left(2^{n} - 1\right).$


Alternatively

Probability of matching at given place $\dfrac{1}{2}.$

there are n places hence probability of matching $\dfrac{1}{2^{n}}.$

hence probability of mismatch $1 - \dfrac{1}{2^{n}}.$

answered by Boss (9.3k points)
edited by
Nice explanation by using Binomial distribution.Thanks :)
+19 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 (14.6k points)
nice explanation ....
This is very easy to understand than the selected answer. Thanks !
0 votes
let us suppose if outcome is head =>0, tail => 1 Since the coin is fare, P(H) = P(T) = 1⁄2 Length of the string is => n P(X) = both the strings should not be identical P(-X) = both are not identical = 1 – P(X) If both the strings are equal, every character should be same w.r.t its positions i.e P(X) = 1/2*1/2*.......(n times) = (1/2)^n P(-X) = 1 – (1/2)^n
answered by Boss (8.4k points)
0 votes
Let the 1st string generated be 010101 and the 2nd string be 110011. (N=6)

To check whether they are totally identical, we can apply XOR to them. If the output comes as 000000 then we can be sure that the pattern is same else different.

Here we will see that xor comes as 011001 which is not equal to 000000 hence it is not same.

Now, probability of getting '0' in each of the n places is 1/2. Hence probability of getting 0 in all n places is (1/2)^n.

All other cases which contain mixture of 0's and 1's imply that the two strings are not fully identical ( they may be same at some bit position but not all).

So probability of getting different strings=1-probability of getting identical strings

=1-(1/2)^n.

Option D.
answered by Boss (5.7k points)
–2 votes
Favourable case is 1 and the total sample space is $2^n$ so it must be $1/2^n$
answered by Veteran (14.3k 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


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

33,646 questions
40,193 answers
114,178 comments
38,665 users