# Probability that two bit sequences match more than 60%

Assume that there is a random bit sequence generator that each time returns a bit sequence of length 100. Each bit of the sequence can be a 1 or 0 with equal probability.

Question: What is the probability that two bit sequences taken from the generator match in more than 60% of the bits?

Attempted Solution:

$\frac {\sum_{i=0}^{39} {{100} \choose {i}} } {2^{100}}$
• It is correct. You tacitly made use of the fact that each bit is equal probability in using the method of calculating probability by counting. If $1$'s were more likely to occur than $0$'s then the approach would have been different and more complicated. – JMoravitz Oct 29 '17 at 22:22
• For that, we will need to calculate an additional intermediate probability, namely the probability that the $n$'th bits match. They will match with probability $P(0)^2+P(1)^2$ which in your example will simplify as $\frac{5}{9}$. Calling this value $p$ and calling $q=1-p$ we will have final probability for your question $\sum\limits_{i=0}^{39}p^{100-i}q^i\binom{100}{i}$. Note that what happens when $P(0)=P(1)=\frac{1}{2}$ you would have $p=q=\frac{1}{2}$ which explains the $\frac{1}{2^{100}}$ in your original answer. – JMoravitz Oct 29 '17 at 22:37