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

My attempt:

So $2$ bit strings will be identical when same sequence of head and tail comes while generating the sequences.

The probability that the two strings are identical is

$(1/2) * (1/2) * ..... * (1/2) (n$ times$)$ which is $=\frac{1}{2^n}$

The probability for not identical is $=1-\frac{1}{2^n}$

Can you please explain in formal way?

  • $\begingroup$ I think your approach is correct. $\endgroup$ – Rajat Nov 20 '15 at 9:08
  • 3
    $\begingroup$ Yep there's nothing formal to add - you nailed it. $\endgroup$ – Benjamin Lindqvist Nov 20 '15 at 9:29
  • $\begingroup$ your approach is better than the answer ! $\endgroup$ – laura Jun 12 '18 at 7:43

Your reasoning is correct. And IMO your reasoning is formal enough.

You find the probability that two strings are the same ($1/2^n$) and so the probability that two strings are different is $1 /2^n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.