Probability that an individual cheated and knows a random sequence.

Question

Bob writes down a sequence of coin flips on a piece of paper and hides it away. He uses a coin flip to determine if he uses a 1 or a 0. Alice tries to guess the random sequence and may have looked at this paper. It is Bob's job to determine if she has looked at the numbers.

Bob's secret paper says:

0, 1, 1, 0, 0, 1

Alice says:

0, 1, 1, 0, 1, 0

Alice knows about Bob's suspicion and throws in actual random numbers once in a while. Alice would like Bob not to know if she knows. Is it possible to know with a reasonable degree of certainty of Alice's cheating?

I simplified it down to an easy to understand explanation, in reality my problem features potentially thousands of bits.

Answer 1

This comes down to hypothesis testing.

If we make the hypothesis that Alice is not cheating, then she has a 50% chance of correctly guessing the correct value with each bit guessed.

Using this information we can look at the using a normal distribution to see how likely it is that Alice's submission is the result of cheating.

Given $n$ bits of data, and $m$ incorrect guesses then the $p$-value (probability of $m$ or fewer incorrect guesses from $n$ guesses) is: $$p = \sum_{i=0}^m {^n \text{C} _i \times \left ( \frac{1}{2} \right ) ^n}$$

Now you need to interpret $p$-value, in order to determine whether the results are so unlikely that the hypothesis (not cheating) appears unlikely and thus tampering appears evident.

Typical (though arbitrary) values for $p$-value interpretation are:

• $p > 0.1$ - Little evidence against
• $0.10 \ge p \gt 0.05$ - Weak evidence against
• $0.05 \ge p \gt 0.01$ - Moderate evidence against
• $0.01 \ge p \gt 0.001$ - Strong evidence against
• $0.001 \ge p$ - Very strong evidence against

So for example if $p < 0.01$ you should be looking closely at Alice, if $p < 0.001$ then its a pretty safe bet that Alice is cheating, as the number of incorrect guess are so low as to be highly unlikely.

A final caveat: This is a statistical likelihood of cheating rather then outright proof, using this method, someone who was extraordinarily lucky would be assumed to be cheating. Or course as $n$ becomes larger the chances of being so lucky become smaller.

Answer 2

Given that you agree with what I wrote in the comments above, I believe a solution would run like this. Let $X$ be the number of terms that Alice guesses correctly. Under the hypothesis that Alice is not cheating, and is thus guessing randomly, we have that $X$ follows a binomial distribution $\text{Bin}(6,1/2)$.

So you have calculate the probability that Alice gets at least 4 terms correct in this Binomial distribution, which is

$P(X\geq 4) = \binom{6}{4}\left(\frac{1}{2}\right)^4\left(\frac{1}{2}\right)^2 + \binom{6}{5}\left(\frac{1}{2}\right)^5\left(\frac{1}{2}\right)^1 + \binom{6}{6}\left(\frac{1}{2}\right)^6\left(\frac{1}{2}\right)^0.$

EDIT: Numbers included.

According to Wolfram Alpha, this is about 34 %, which is not significant at any reasonable level.

http://www.wolframalpha.com/input/?i=%28binom%286%2C4%29%2Bbinom%286%2C5%29%2Bbinom%286%2C6%29%29%281%2F2%29%5E6