I have a perfectly fair coin, and my goal is to prove that it is unfair with a confidence level of 95%. In order to accomplish this, I will cheat. Whenever I fail to have enough evidence, I will simply increase the sample size by continuing to flip the coin.

To be specific, I will flip the coin until the proportion of heads is either small enough or large enough to be able to say that the coin is unfair. Let's say that, for any given sample size $N$, there is at least a $95\%$ chance that the proportion of heads is within the confidence interval

$$0.5 ± f(N)$$

where $f(N)$ is some function. If I have flipped the coin a grand total of $N$ times, and the proportion of heads is outside of this interval, then I "conclude" that the fair coin is unfair and stop the process. If the proportion is within the interval, then I flip the coin one more time and repeat the process with $N+1$. One important detail is that I never "throw out" data.

What is the expected number of flips that I would have to make until I receive the "statistically significant" result I seek?

I've run a few simulations with my calculator, and it seems that either it takes a reasonable number of flips (like 44) or it takes a huge amount of time. Why is this, assuming it's not programmer error?

Edit: More simulations

I ran some more simulations (on an actual PC, rather than a calculator). I used two criteria for determining whether or not a result is significant. First, I required that there be at least $20$ flips performed. Second, I used this value for the function:

$$f(N) = 1.9600 * \sqrt{\frac{0.5 * 0.5}N} = \frac{0.98}{\sqrt{N}}$$

More edits: this formula comes from the normal approximation for the binomial distribution, where $1.96$ is the required z-score and other part is the standard deviation of the proportion.

My plan for running the simulations was to set an upper limit for the number of flips, preform a huge number of trials, and see what proportion of trials exceeded the limit. This way, I could gather data in a reasonable time limit. After running a large number of simulations, I acquired this data:

# of flips      proportion > this number      sample size
100000          0.298                         n=1000
10000           0.41                          n=1000
1000            0.5516                        n=10000
100             0.7637                        n=10000
32              0.8726                        n=10000
64              0.8029                        n=10000
128             0.738                         n=10000
256             0.6768                        n=10000
512             0.6252                        n=10000
1024            0.563                         n=10000
2048            0.5126                        n=5000
  • $\begingroup$ Where do the constants $1.96$ and $0.98$ come from? When working with small probabilities (like 5%) you need accuracy and two digits don't look like nearly enough. That said, it is an interesting question. $\endgroup$ – Ross Millikan Jun 19 '13 at 4:16
  • $\begingroup$ You need to think about the cases of $n$ heads and $m$ tails such that that probability is in the 95% range, but $n+1$ vs $m$ or $n$ vs $m+1$ (which are the same by symmetry) is outside the 95% limit. $\endgroup$ – Ross Millikan Jun 19 '13 at 4:24
  • $\begingroup$ Sorry if I wasn't clear, but the value 1.96 comes from here: measuringusability.com/zcalcp.php. It is actually accurate to 4 decimal places. I am using the normal approximation for the binomial distribution, and 1.96 is the required z-score for a significant result. $\endgroup$ – PhiNotPi Jun 19 '13 at 4:37
  • $\begingroup$ This is the expected stopping time of a random walk Markov chain with moving barriers; since random walks move $~\sqrt N$ and your barriers are moving at (roughly the same) $~\sqrt N$ it's possible the expectation diverges (there is a finite probability that you never encounter such a result, for instance - seems unlikely if the variance is exactly matched). I haven't thought about it in detail, but that's what comes to mind. $\endgroup$ – Sharkos Jul 9 '13 at 20:57
  • $\begingroup$ I believe the "cheating' strategy you are employing here is a martingale betting strategy (en.wikipedia.org/wiki/Martingale_(betting_system)). Essentially, the idea is to keep tripling your bet until you come out ahead then quit. Although it's counter intuitive there exists no expected number of plays until this happens, that is, this strategy cannot actually be used to make a profit even with an infinite pile of money to wager. $\endgroup$ – fairidox Jul 9 '13 at 22:33

Edited Note: From David Speyer's answer the below reaches the correct conclusion -- divergence in the expectation value -- though I haven't verified the intermediate observation about the actual asymptotics. (There was a bit of confusion at one point.)

I ran 10000000 simulations (up to 100000 max tosses each) while watching TV and collected a histogram of where I stopped. I got slightly different numbers to you, but sufficiently similar that I think this is a combination of statistical errors, rounding errors and coding errors! I suspect the basic behaviour is the same, but it's possible there is some extreme sensitivity in the tails. I haven't checked my code for bugs at all.

Haven't thought about why this behaviour arises, but it for $M$ the number of tosses required, the probability looks like it behaves as $$\mathbb{P}(M \ge m) \sim \frac C {m^k}\qquad C\approx 1.41,k\approx 0.13$$ Graph

Of course, this might just be a completely misleading line, it's very difficult to tell. This is definitely empirical.

If this holds up to further scrutiny, then we certainly have $$\mathbb{E}(M)=\sum_m^\infty \mathbb P(M\ge m) = \infty$$ If someone else fancies a bit of fun, I think seeing this is the correct behaviour and deriving an expression for $k$ might be a nice challenge!

Edit: Updated with slightly better data.

Also, as I said in the comment above,

This is the expected stopping time of a random walk Markov chain with moving barriers; since random walks move $\sim \sqrt N$ and your barriers are moving at (roughly the same) $\sim \sqrt N$ it's possible the expectation diverges.

You can probably come up with a decent argument as to why this sort of behaviour is to be expected, but I haven't taken taken the time to try it yet, so that might be overly optimistic. If I get round to thinking about this I'll post!


According to Blackwell and Freedman, A Remark on the Coin Tossing Game, the expected time for the number of heads to get outside $n/2 \pm a \sqrt{n}$ is finite for $a<0.5$ and infinite for $a \geq 0.5$. (As Henry points out below, they use $\pm 1$ instead of $(0,1)$ counting, so their boundary is $0 \pm \sqrt{n}$.) I'm afraid I don't understand their proof, but this means that the expectation time should be infinite, as Sharkos finds.

  • $\begingroup$ That's interesting! So the behavior I saw is probably transient but because 0.98 comes close to 1 (purely by fluke) the scale is large. $\endgroup$ – Sharkos Jul 10 '13 at 21:45
  • 1
    $\begingroup$ I think your linked Blackwell and Freedman paper uses outcomes of $\{-1,+1\}$ rather than the $\{0,+1\}$ here, with the finite/infinite expectation boundary at $1$ standard deviation while this question asks about $1.96$ standard deviations. $\endgroup$ – Henry Jul 25 '16 at 15:10
  • $\begingroup$ @Henry Thank you so much, you are right! $\endgroup$ – David E Speyer Jul 25 '16 at 15:55
  • $\begingroup$ @Sharkos Henry points out that I missed a factor of $2$, and you trusted me in your answer. I've fixed mine; you might want to do the same. $\endgroup$ – David E Speyer Jul 25 '16 at 15:57
  • $\begingroup$ @DavidSpeyer Updated! Cheers for the ping. I'd totally forgotten about this, but this is much more satisfying! $\endgroup$ – Sharkos Jul 25 '16 at 18:40

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.