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, 2015 at 9:08
  • 3
    $\begingroup$ Yep there's nothing formal to add - you nailed it. $\endgroup$ Nov 20, 2015 at 9:29
  • $\begingroup$ your approach is better than the answer ! $\endgroup$
    – laura
    Jun 12, 2018 at 7:43

1 Answer 1


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.