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?

  • $\begingroup$ Isn't $A+B = 100$? $\endgroup$ – maverick Oct 11 '16 at 20:28
  • $\begingroup$ 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.? $\endgroup$ – maverick Oct 11 '16 at 20:29
  • $\begingroup$ 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%? $\endgroup$ – Pavel Komarov Oct 11 '16 at 20:31
  • $\begingroup$ 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. $\endgroup$ – Pavel Komarov Oct 11 '16 at 20:33
  • $\begingroup$ 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? $\endgroup$ – Doug M Oct 11 '16 at 20:34

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.

  • $\begingroup$ I think this will work. $\endgroup$ – Pavel Komarov Oct 11 '16 at 21:16
  • $\begingroup$ 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 $\endgroup$ – Pavel Komarov Oct 11 '16 at 21:40
  • $\begingroup$ 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? $\endgroup$ – Pavel Komarov Oct 11 '16 at 21:44
  • $\begingroup$ 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. $\endgroup$ – Pavel Komarov Oct 11 '16 at 21:48

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.