1
$\begingroup$

Imagine $n > 100$ participants in a (toy) casino. In one round each of the $n$ participants simultaneously toss a different independent coin. If a participant gets a head he/she gets a $\$1$ profit and otherwise he/she suffers a $\$1$ loss in that round. The expected profit/loss if the coins are all unbiased is $\$0$.

Now imagine that $1 \leq m \leq n/2$ players are cheats and working together. They each have independent coins with probability $1/2+\epsilon$ of getting a head. This subgroup of players has an expected positive profit from this game. The casino would like to detect this and expel the cheats.

Assuming all the players play in every round, after $r$ rounds how confident can the casino be that:

  • That some people are cheating?
  • They can identify which people are cheating?

Note that $\epsilon$ is the same for all the cheaters.

Half-baked thoughts The two simplest strategies for the casino are: a) The casino could just count the number of heads in all the rounds so far and see it is far $rn/2$ b) The casino could look at each individual person and count how many heads they have so far and see if it is far $r/2$.

$\endgroup$
  • $\begingroup$ You need to set a confidence level. The casino can never be 100% positive that anyone is cheating; they could just be really lucky. $\endgroup$ – Nuclear Wang May 30 '19 at 20:48
  • $\begingroup$ @NuclearWang I am interested in the best possible confidence level as a function of the number of rounds. $\endgroup$ – marylou May 30 '19 at 20:49
  • 2
    $\begingroup$ Why the downvote? $\endgroup$ – marylou May 30 '19 at 20:52
  • $\begingroup$ Quite a few moving parts here... this will be a function of the number of players, number of cheats, number of rounds, and epsilon. If there's 10 people in your casino, someone who gets 10 heads in a row is almost certainly a cheat, but if there's 1M people in your casino, it's pretty well guaranteed that at least one fair player will get 10 heads in a row. $\endgroup$ – Nuclear Wang May 30 '19 at 20:56
  • 1
    $\begingroup$ @HagenvonEitzen Yes it is. $\endgroup$ – Anush May 30 '19 at 21:18
2
$\begingroup$

First, think about one player. We can use the normal approximation, which says that after $r$ rounds you expect $\frac r2$ heads with a standard deviation of $\frac 12\sqrt {r}$. If the coin is unfair, we expect $r(\frac 12+\epsilon)$ heads. As the excess number of heads over $\frac r2$ grows linearly and the standard deviation only grows as the square root, we expect the excess of heads to eventually become greater than any number of standard deviations we want to set. We can choose the number of standard deviations to make the chance of incorrect identification of cheaters as small as we want. This will postpone the detection of cheaters.

If there are $m$ cheaters the excess heads will pile up faster, but the dilution of them among the crowd makes the standard deviation larger as well.

To make an example, suppose each person plays $10,000$ rounds and let $\epsilon=0.005$. The expected number of heads is $5,000$ with a standard deviation of $50$. The cheaters have an expected number of heads of $5,050$ and their standard deviation is very close to $50$ as well. If there are $10,000$ players and $1,000$ cheaters among them, the total number of heads (without considering the cheaters) is expected to be $5\cdot 10^7$ with a standard deviation of $5,000$. The cheaters raise the expected number of heads to $5.05\cdot 10^7$, an increase of $50,000$. That total is $10\sigma$ high, which never happens. With $1,000$ cheaters, you expect one to be about $3\sigma$ high, which means that one would get $5,200$ heads. If that were random, it is $4\sigma$ high, which happens three times in $100,000$. You wouldn't expect that every night, but you should get one a month. You wouldn't want to call that person a cheater on this basis. In this example the casino would be quite certain that cheating is going on but unable to clearly identify any individual cheaters.

On the other hand, the cheaters are getting paid $\$50$ for the effort of flipping a coin $10,000$ times, which is probably worse than minimum wage.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Could you expand on the case where there is only one cheater and $n=1000$ say? Do we detect cheating more quickly by looking at each individual player or by counting the overall number of heads? $\endgroup$ – Anush May 31 '19 at 6:17
  • $\begingroup$ One issue that is confusing me is the question of multiple testing. The casino can look at each participant individually but then it needs to take into account that there are $n$ participants when testing for statistical significance. If it looks at pairs of participants, this problem is even worse. $\endgroup$ – marylou May 31 '19 at 9:26
  • $\begingroup$ @marylou Yes, you'll need to do multiple hypothesis correction to avoid kicking out lucky winners alongside cheaters. With just one person, being 2 s.d. above the mean is very unlikely, with p<0.05, but you need a much more stringent threshold if you have 1000 players - a conservative Bonferroni correction would require p< 0.05/1000, or about 4 s.d. above the mean. Why do you need to look at pairs of participants? You mention in the question that the cheaters are "working together", but there is no interaction among them. They are all cheating independently. $\endgroup$ – Nuclear Wang May 31 '19 at 14:09
  • $\begingroup$ If there is just one cheater it is better to look at each individual. The standard deviation is smaller and the expected excess is just as large. A better way to look at the crowd is to fit the observed distribution to a binomial distribution and do a chi-squared test. That will be more sensitive than just the number of heads. I think that will cover all the subgroups together. You can compare the fits with all the coins fair and with two batches of coins. $\endgroup$ – Ross Millikan May 31 '19 at 14:09
  • $\begingroup$ That sounds interesting. The casino doesn't know the number of cheaters of course (it could be zero) so when comparing fits (as you suggested) does it need to try all possible numbers of cheaters? $\endgroup$ – marylou May 31 '19 at 14:17

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.