1

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.

John T
  • 75
  • How does Bob pick his random numbers? – Peter Woolfitt Jan 21 '15 at 18:18
  • What restrictions are there on Bob's "random" sequence? That is, what is the distribution of the numbers that he is selecting? That makes a pretty big difference, and is necessary to give an answer. – KSmarts Jan 21 '15 at 18:19
  • In this case, it is suspicous that Alice got $4$ numbers out of $6$ correct, but as already stated we have to know more precise what Bob does. – Peter Jan 21 '15 at 18:25
  • My bad, cleared it up. – John T Jan 22 '15 at 02:14
  • 1
    There's not enough to go on - is Alice trying to lie, or disguise the fact she knows. Why should she pretend not to know the answer? – JMP Feb 13 '15 at 01:54
  • In my mind, this problem is just about the following: Bob has a random sequence. Alice may or may not have looked at this sequence, and she tries to guess it. Under the hypothesis $H_0$ that Alice randomly tries to guess Bob's sequence (and thus have not seen it beforehand), what is the probability that she gets four terms right? Edit: If this probability is below some threshold, say 5 %, then Bob declares that Alice has cheated. – Mankind Feb 13 '15 at 09:50
  • The motivations of the players of this game aren't specified. What does it mean that Alice tries to guess the random sequence? Is she paid for each correct bit? Why does Bob want to prevent cheating? Is he billed for each correct bit? What prevents Bob from always accusing Alice of cheating and refusing to pay? At the other extreme, what prevents him from deciding not to care? If Alice is so worried about not being accused, what prevents her from throwing away her cheat sheet and guessing each bit at random? At the other extreme, what prevents her from using no randomness at all? – Chris Culter Feb 13 '15 at 10:15

2 Answers2

2

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.

Chris Cooper
  • 320
0

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

Mankind
  • 13,170