Chance versus Skill

Suppose $p\in[0,1]$ is the probability that the coin lands heads up. Let $q\in[0,1]$ be the probability that a candidate successfully lands heads. Then, the skill ratio is given by $\chi_q:=\frac{q-p}{1-p}$. The candidate throws the coin $N$ times and successfully lands heads $M$ times out of $N$. We use the following estimator $\hat{q}:=\frac{M}{N}$ of $q$, assuming that $q$ is uniformly distributed on $[0,1]$. (The last assumption is the most dubious one. It may be better to assume that $q$ is uniformly distributed on $[p,1]$. However, I do not want to deal with difficult calculations.)

Assume that the measurement yields $\hat{q}=\hat{r}$ for some $\hat{r}\in[0,1]$. Therefore, we need to calculate $$\text{E}\Big(\chi_q\,\Big|\,\hat{q}=\hat{r}\Big)=\int_{0}^1\,\left(\frac{r-p}{1-p}\right)\,f(r,\hat{r})\,\text{d}r\,,$$ where $$f\left(r,\hat{r}\right):=\binom{N}{\hat{r}N}r^{\hat{r}N}(1-r)^{\left(1-\hat{r}\right)N}$$ for all $r\in[0,1]$ and $\hat{r}\in\left\{0,\frac{1}{N},\frac{2}{N},\ldots,\frac{N-1}{N},1\right\}$. This means $$\text{E}\Big(\chi_q\,\Big|\,\hat{q}=\hat{r}\Big)=\frac{1}{1-p}\,\binom{N}{\hat{r}N}\,\left(\frac{\big(\hat{r}N+1\big)!\,\big((1-\hat{r})N\big)!}{(N+2)!}-p\,\left(\frac{\left(\hat{r}N\right)!\,\big((1-\hat{r})N\big)!}{(N+1)!}\right)\right)\,.$$ That is, $$\mu:=\text{E}\Big(\chi_q\,\Big|\,\hat{q}=\hat{r}\Big)=\frac{\left(\hat{r}-p\right)N+1-2p}{(N+1)(N+2)(1-p)}\,.$$ For $p=\frac{1}{2}$, we get $$\mu=\frac{\left(2\hat{r}-1\right)N}{(N+1)(N+2)}\,.$$

Now, $$\text{E}\Big(\chi_q^2\,\big|\,\hat{q}=\hat{r}\Big)=\,\int_0^1\,\left(\frac{r-p}{1-p}\right)^2\,f\left(r,\hat{r}\right)\,\text{d}r\,,$$ or $$\text{E}\Big(\chi_q^2\,\big|\,\hat{q}=\hat{r}\Big)=\frac{\left(\hat{r}-p\right)^2N^2+\left(3\hat{r}(1-2p)-2p+5p^2\right)+\left(2-6p+6p^2\right)}{(N+1)(N+2)(N+3)(1-p)^2}\,.$$ Ergo, $$ \begin{align}\sigma:=\sqrt{\text{Var}\Big(\chi_q^2\,\big|\,\hat{q} =\hat{r}\Big)}=\frac{\sqrt{\tau}}{(N+1)(N+2)\sqrt{N+3}(1-p)}\,,\end{align}$$ where $$ \begin{align}\tau&:=(\hat{r}-p)^2N^4+\left(2\hat{r}^2+(3-10)p\hat{r}-2p+7p^2\right)N^3 \\&\phantom{abcdef}-\left(\hat{r}^2+(7-12p)\hat{r}+2-10p+16p^2\right)N^2+\left(5-12p+12p^2\right)N+1\,. \end{align}$$ If $p=\frac{1}{2}$, we have $$\sigma=\frac{\sqrt{(2\hat{r}-1)^2N^4+\left(8\hat{r}^2-8\hat{r}+3\right)N^3-\left(\hat{r}^2-\hat{r}-1\right)N^2+8N+4}}{(N+1)(N+2)\sqrt{N+3}}\,.$$

If the estimated skill ratio is $\hat{\chi}=\frac{\hat{r}-p}{1-p}$, then the skillfulness can be defined by $$\hat{S}:=\frac{\hat{\chi}-\mu}{\sigma}\,.$$ Fix $p=\frac{1}{2}$.
(1) When $N=10^2$ and $\hat{r}=1$, then $\hat{S}\approx 10.2$.

(2) When $N=10^4$ and $\hat{r}=\frac{9}{10}$, then $\hat{S}\approx 100.02$.
(3) When $N=10^6$ and $\hat{r}=\frac{8}{10}$, then $\hat{S}\approx 1000$.
(4) When $N=10^9$ and $\hat{r}=\frac{7}{10}$, then $\hat{S}\approx 31623$.
(5) When $N=10^{10}$ and $\hat{r}=\frac{6}{10}$, then $\hat{S}\approx 100000$.
It seems like $\hat{S}$ goes to $\sqrt{N}$ very quickly when $\hat{r}$ starts to exceed $p$. See the plot of $\hat{S}$ versus $\hat{r}$ for $p=\frac{1}{2}$ and $N=100$ below.

As mentioned in the first paragraph, it should be better if $q$ is assumed to be uniformly distributed on $[p,1]$. Here are some calculations with the modified distribution of $q$ under $p=\frac{1}{2}$:
(1) $N=10^2$ and $\hat{r}=1$ yield $\hat{S}\approx 7.178$;
(2) $N=10^4$ and $\hat{r}=\frac{9}{10}$ yield $\hat{S}\approx 70.79$;
(3) $N=10^6$ and $\hat{r}=\frac{8}{10}$ yield $\hat{S}\approx 707.1$;
(4) $N=10^{9}$ and $\hat{r}=\frac{7}{10}$ yield $\hat{S}\approx 22361$;
(5) $N=10^{10}$ and $\hat{r}=\frac{6}{10}$ yield $\hat{S}\approx 70711$.
Note that $\hat{S}$ goes to $\sqrt{\frac{N}{2}}$ very quickly. See the plots of $\hat{S}$ against $\hat{r}$ for $p=\frac{1}{2}$ and $N=100$ (on top) as well as $N=1000$ (at the bottom) below.

One other reasonable approach is to accept the "statistics dogma", which is, roughly speaking, that "the predefined events of probability more than $\alpha$ may be due to chance and the rest is due to cause". It is traditional to set $\alpha=0.05$, but this value is in no way sacred. So, if the coin flipping skill is measured by the probability $p$ of landing heads, to convince you that his head landing skill is at least $q$, the person needs to announce and then achieve the result that would have probability less than $\alpha$ for any flipper with skill $q$ and below. From this point of view, the perfect result in $100$ tosses (if announced beforehand) convinces you only of the skill $\alpha^{1/100}$, which for $\alpha=0.05$ is about $0.97$. The pre-announced perfect result in $10$ tosses convinces you only of skill $0.74$, etc.

The second question should come first :

SECOND SCENARIO : When do we go from thinking "He's lucky!" to "He's good!"?

Since you deal with probabilities, any number of results could be explained by luck. The most general way to sort this out is to compute what would be the odds of such a result happening by pure luck. The statistical approach is to choose a metric (here the success rate is pretty easy to choose), and then to compute the probability of the hypothesis "the result is due to luck". This probability is the p-value. Below a certain treshold, you will state the result is due to skills.

In the case of a coinflip, you would look at the probability that the guy lands all these heads with a 1/2 probability of landing heads.

The p-value is widely used, with varying values that depend on how sure you want to be not to select false positives.

Because that's the trick : Whatever your method of selecting "truly good" coinflippers is, you will always be wrong some times. What's even worse is that if you want to know your actual probability to be wrong, you need to make extra asumptions, because to do this (by using bayesian inference), you need to the actual probability of your hypothesis to be true.

You can increase as much as you want your ability to find "truly good" coinflippers from "lucky frauds", but you cannot know how likely your guy is to be in the first group (which is the question you want to answer), unless you assume the actual repartition of people between the two groups. p-value only gives you the probability for you to be wrong in the case the contestant is a fraud. If you already knew how many skilled coinflippers there were and how their skill is distributed, you wouldn't be holding this giant coinflipping contest.

This sheds a light on the difficulty to answer your second question in the general case.

FIRST SCENARIO : The contest

It all boils down to the definition of what is "being a good coinflipper" ?

• Is it showing that you can actually throw a fair coin with a probability to land heads different of 1/2 ? In that case you would use the p-value of the hypothesis "p(heads)=1/2". The last contestant would win in this framework, but all of them have incredibly low p-values.

• You can estimate the actual skill, but you need to make asumptions on the actual distribution of skills. For instance, if you assume it is possible to achieve a 60% success rate by knowing how to throw the coin, you would set different expectations. But for this, you need additional hypothesis, I won't go into the details of all the possibilities

I think a good way to organize such a contest would be to request people to show the highest Lower bound of confidence interval for a Bernoulli parameter, as suggested here.

In nearly plain english, is to define some (very low) confidence level alpha, and to set the score of each person that participated as "The lowest possible actual probability of success of the coinflipper that would have given such a good record with a probability higher than alpha"

I like this solution because any contestant will eventually converge towards it's actual success rate, but will very rarely (with a small probability of your choosing) be above during its convergence process. Thus any contestant patient enough can hope to overcome any opponent in the end, knowing that this opponent is very unlikely to have been ranked to high out of luck.

Let's choose alpha as 0.01%

This method enables us to select a winner for your contest : Person 2 wins !! with a score of 88.8%

Note that with a p-value of 1%, Person 1 wins, and that my poor Excel overflows before I reach a probability that will make person 3 wins, probably around the event of a 27 sigma variation in a normal distribution.

My solution is not perfect, because as small as I can chose my alpha, there is always the possibility that some contestant gets lucky enough to get a lower-bound estimate too generous, which would allow him an advantage that could not be overcome by other contestants that can only hope to converge towards their true success rate. Depending on the hypothesis you are ready to take, and what you want to achieve, you will choose one or the other