in Probability
8,315 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}$
in Probability
by
8.3k views

2 Comments

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

7
7

tot prob

= 1st bits mismatch + 1st bits match and 2nd bits mismatch + ….+ first n-1 bits match and nth bits mismatch

=½ + (½ )^2 + …. + (½) ^n 

= 1 – (½ )^2

0
0

11 Answers

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

edited by

4 Comments

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.
4
4
great way to see it as binomial form , cause i was looking it as complemented method where only one possible way a string can match to other is to be exact same copy and other than that is mismatched .and to get that

we need probability of (1/2)^n. then take its compliment 1-(1/2)^n..
0
0
edited by

extending the answer to a bit more random variable approach : 

the random variable here would be let’s say X = number of mismatches in n-bit string and Probability of success is assumed to get a mismatch at a particular bit-position so, $p = \frac{1}{2}$ & $q=1-p = \frac{1}{2}$

the n trials are independent bernoulli trials 

then $P(X=k)= \binom{n}{k}p^{k}q^{n-k}$

after summing all the cases $(\sum_{k=1}^{n}P(X=k))$ , we get the required ans.

0
0
94 votes
94 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.

4 Comments

nice explanation ....
3
3
This is very easy to understand than the selected answer. Thanks !
3
3
can you please explain the numerator part .. i didn’t get why we are subracting -1
0
0

@P SHANMUKHA SHARMA 

out of $2^{n}$ strings possible , after generating 1 string we take it out so that favourable strings now become $2^{n}-1$ (so that there’s no chance of generating that string again)

0
0
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.

4 Comments

hahahaha :D :D @MiNiPanda well said :P

0
0

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

0
0
Literally the best explanation I could get on this question. You gave a very nice intuition on this question
0
0
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

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