8,419 views
27 votes
27 votes

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

11 Answers

1 votes
1 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
1 votes
1 votes
Total combinations of strings that can be generated = 2^n.

We will get one such string in the first experiment.

So, favourable cases for the second string = 2^n - 1, so that it doesn't match with the previous generated string.

Hence Probability = (2^n - 1) /2^n = 1 - 1/2^n
1 votes
1 votes

2 Approaches to this question

 

  1. Total Probability– Not asked:Consider 2 bit strings=00,01,10,11 and take any one from these 4 by probability ¼ now 2nd string should come same as the previous string came so total choice for 2nd time=1,  So both strings are identical probability=¼ and we want not identical so 1- ¼ =¾ Option D
  2. 2nd time when we toss a coin, result must not be equal to Previous result if 00 came on 1st time in 2nd time result should be only from 01,10,11 so total prob. for that=¾ Option D.

Same logic can be applied for higher bits and upto n.

0 votes
0 votes
We could have also done it like this:

the number of strings that can be generated is 2^n.
Let S be a set containing the 2^n strings.

1st random bit string ->2^n possibilities
2nd random bit strings->2^n possibilities.

so the number of different combinations of  1st and 2nd string is (2^n * 2^n)-2^n)(let us consider it to be a relation  R from S->S having (2^n * 2^n)ELEMENTS).It is of the form (x,y)
now the number of  elements in R where the first string is not equal to the second string is ->( (2^n * 2^n)-2^n)

so  ((2^n * 2^n)-2^n)/ (2^n * 2^n) = 1-1/2^n
ANSWER IS D.
Answer:

Related questions

24 votes
24 votes
3 answers
1
gatecse asked Sep 21, 2014
11,448 views
Let $f(x)$ be the continuous probability density function of a random variable $x$, the probability that $a < x \leq b$, is :$f(b-a)$$f(b) - f(a)$$\int\limits_a^b f(x) dx...
22 votes
22 votes
5 answers
2
Kathleen asked Sep 15, 2014
10,458 views
Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is$\frac{1}{16}$$\frac{1}{8}$$\frac{7}{8}$$\frac{15}{16}$
72 votes
72 votes
8 answers
3
Ishrat Jahan asked Nov 3, 2014
30,408 views
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is$3...