# The probability of random strings matching at more than X locations

I have a problem related to the significance of experimental results, but I will frame it this way:

Suppose I have two binary strings of length A+B. The first contains exactly A 0s and B 1s. The second can be any pattern. Assuming all strings are equiprobable, what is the probability that my two strings match in at least x% of the positions?

• Isn't $A+B = 100$? – maverick Oct 11 '16 at 20:28
• Also question is not clear. Will you continue removing balls till the bag is empty and then we need to tell the probability that your answer was correct for exactly $X%$ of them.? – maverick Oct 11 '16 at 20:29
• I will continue until the bag is empty. No, the answer is not 100%, but yes A+B = 100. I have to make a vector of [blue, red, blue, blue...], and then pull from the bag to generate an other vector like that, and then compare to see my accuracy. What is the probability my accuracy is at least X%? – Pavel Komarov Oct 11 '16 at 20:31
• It is not clear to me exactly how I should generate the first vector, but at the moment I am considering just generating "red" with probability A and "blue" with probability B. – Pavel Komarov Oct 11 '16 at 20:33
• If you know how many are red and you plan to draw them all, then with 100% confidence you know how many red balls you will draw. Or, do you intend to adjust your guess as you draw and the ratios in the bag are changing? – Doug M Oct 11 '16 at 20:34

## 1 Answer

As long as all strings are equiprobable for the second one, the first doesn't matter. You are taking the bitwise XOR of the strings and asking if you have $x\%\ 0$'s in the result with each bit having equal chance to be $1$ or $0$. So just look at the chance you have at least $\frac x{100}(A+B)\ 0$'s in a string of $A+B$ bits. This is a cumulative binomial distribution. You can use the normal approximation to ease the calculation.

• I think this will work. – Pavel Komarov Oct 11 '16 at 21:16
• 68%*244 = 166. sum n = 166 to 244 (244 choose n)*(0.5^244) = 9.03586 * 10^-9. integral from 0.68 to infinity (1/(2*61*pi) * exp(-(x-122)^2/(2*61))) dx – Pavel Komarov Oct 11 '16 at 21:40
• Using the normal approximation, $$np = \mu = 122$$ and $$np(1-p) = 61 = \sigma^{2}$$. Integrating from 0.68 to infinity yields 0.051. That's very different from 10^-8. What have I done wrong? – Pavel Komarov Oct 11 '16 at 21:44
• Ah. I see. I had it wrong. $$integral from 166 to infinity (1/sqrt(2*61*pi) * exp(-(x-122)^2/(2*61))) dx = 8.8*10^-9$$ Evidently my result is significant. My classifier is better than random in a more rigorous sense; there is some signal left in the noise. – Pavel Komarov Oct 11 '16 at 21:48