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

0 votes
0 votes

 

Take small values for n and then solve it.

 

0 votes
0 votes

Using simple probability concept,

Suppose we take a n-bit string. Now looking into the sample space, if we want the same string again, we only have $1$ possibility.

Now, sample space = $2^n$ [combinations of n-bit strings]

Probability to get same identical string = $\frac{1}{2^n}$

But we want the opposite.

Therefore, $1-\frac{1}{2^n}$

This returns the probability of atleast one character that will be different from the original string. 

–2 votes
–2 votes
Favourable case is 1 and the total sample space is $2^n$ so it must be $1/2^n$
Answer:

Related questions

24 votes
24 votes
3 answers
1
gatecse asked Sep 21, 2014
11,447 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,456 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,282 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...