8,378 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

Best answer
53 votes
53 votes

Answer - $D$

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

Probability of this occurring 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 the required probability $\sum \left(^{n}C_{k}\left(\frac{1}{2}\right)^{n}\right)$ where $k$ ranges from $1$ to $n$

is $\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}}.$

edited by
95 votes
95 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.
16 votes
16 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.
5 votes
5 votes

Two such randomly generated strings can be non identical in many ways

We have to sum them up.

As we can have 1,2,3,…. upto n many combinations

 

 

OPTION D

 

Answer:

Related questions

24 votes
24 votes
3 answers
1
gatecse asked Sep 21, 2014
11,440 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,445 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,012 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...