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:

Taking influence from this answer:

robjohn (https://math.stackexchange.com/users/13854/robjohn), Probability that two numbers differ by one bit, URL (version: 2015-07-28): https://math.stackexchange.com/q/1376557

, I figured the answer would be:

$\frac {\sum_{i=0}^{39} {{100} \choose {i}} } {2^{100}}$

However, I am not sure if this answer is correct since I did not make use of the given probability for each bit.

  • $\begingroup$ 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. $\endgroup$ – JMoravitz Oct 29 '17 at 22:22
  • $\begingroup$ @JMoravitz if it is not too convoluted an expression, could you add it as a comment for P(1) = 2/3 and P(0) = 1/3 ? I am really curious to know. $\endgroup$ – fornit Oct 29 '17 at 22:34
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Oct 29 '17 at 22:37
  • $\begingroup$ @JMoravitz That expression ended up being shorter than I expected it to be. Thanks for your help. $\endgroup$ – fornit Oct 29 '17 at 22:55

Your Answer

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

Browse other questions tagged or ask your own question.