Total possible selections ((2^{n})C_{1} ) * ((2^{n})C_{1} ) . Favorable outcomes (2^{n}) * (2^{n}-1)

The Gateway to Computer Science Excellence

+17 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:

- $\frac{1}{2^n}$
- $1 - \frac{1}{n}$
- $\frac{1}{n!}$
- $1 - \frac{1}{2^n}$

+40 votes

Best answer

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

+7

@Arjun sir can we do like this, n places so total 2^n different strings are possible, now we have generated one string, so for identical we have only one favorable case (string must be same that we have already generated)

probability for identical 1/2^n

probability for not identical 1-1/2^n

+2

Expanding on the second part of the answer a bit:

Let us say we generate a random $n$ bit string as the first string. There's no restriction on this string. For the second string to match with this, each bit should match and each bit matches with a probability of $0.5$ and since they are independent, the probability of matching will be $0.5^n$. Subtract this from 1, we get probability of not matching.

Let us say we generate a random $n$ bit string as the first string. There's no restriction on this string. For the second string to match with this, each bit should match and each bit matches with a probability of $0.5$ and since they are independent, the probability of matching will be $0.5^n$. Subtract this from 1, we get probability of not matching.

+55 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.

Hence Probablity= (2^n-1)/2^n= 1-1/2^n.

+10 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.

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.

0

And probably the 2 upvoters of this answer :P

P.S. You can check this one https://gateoverflow.in/1072/gate2004-78?show=159282#a159282

Similar approach to kind of similar question.

0

@MiNiPanda Sample space will be 2^n which itself gives all different strings. The how come we find favorable cases in this example?

+1 vote

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 vote

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

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

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.

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.

–2 votes

52,223 questions

59,818 answers

201,021 comments

118,091 users