Probability for heads from an experiment

Question

You are given a (perhaps biased) coin with probability for heads $p$ for some unknown $p$. Construct a random experiment such that with probability at least $0.99$ you can determine the value of $p$ with an error of at most $\frac{1}{1000}$.

I guess some ingenuity and perhaps the use of a well-known inequality could work, but I really have no idea from where to start. Any help appreciated!

Answer 1

You can use Chebyshev's inequality. Toss the coin independently $n$ times. Let $S_n$ be the total number of heads. Then $$ \mathbb P\left(\Bigl|\frac{S_n}{n}-p\,\Bigr|\leq \frac{1}{1000}\right)\geq 1-\frac{\text{Var}(S_n/n)}{\frac{1}{1000^2}} =1- \frac{1000^2 p(1-p)}{n} $$ For any $0<p<1$, the following inequality is valid: $p(1-p)\leq \frac14$. Therefore right-hand side of Chebyshev's inequality is $$ 1- \frac{1000^2 p(1-p)}{n} \geq 1- \frac{1000^2}{4n} $$ Equate it to $0.99$ and find $n=25\,000\,000$. This is a very huge number of tosses since Chebyshev's inequality is very rough and the requested error $0.001$ is very small.

If you will use central limit theorem instead, you will find a smaller value of $n$: $$ \mathbb P\left(\Bigl|\frac{S_n}{n}-p\,\Bigr|\leq 0.001\right)\approx 1-2\Phi\left(-\frac{0.001\sqrt{n}}{\sqrt{p(1-p)}}\right)\geq 1-2\Phi(-0.002\sqrt{n})=0.99 $$ gives $n=1\,658\,725$.

Answer 2

I would use the Chebysheff's inequality:

$${Pr}\left(\left|\hat p-p\right| < k\right) \geq 1 - \frac{\sigma^2}{k^2}=0.99$$

with $\sigma^2=\frac{p\cdot (1-p)}{n},k=\frac{1}{1000}$

To make the upper bound as small as possible you should set $p=0.5$. Now the minimum number of coin flips can be calculated.

Answer 3

Obviously, you need to flip the coin $n$ times and then estimate $p$ by the proportion $\hat p = \frac{n_h}{n}$ where $n_h$ is the number of heads which occurred during the $n$ trials.

Now, the remaining part is just some standard calculations based on a normal approximation of the error of the proportion:

• $\color{blue}{99\%}$-confidence interval for $\hat p$: $\hat p \pm z_{\color{blue}{0.995}}\sqrt{\frac{\hat p (1-\hat p)}{n}}$
• $z_{\color{blue}{0.995}} \approx 2.58$ is the $z$-score of the standard normal distribution for the $\color{blue}{99\%}$-confidence interval.
• You want $2.58\sqrt{\frac{\hat p (1-\hat p)}{n}}\stackrel{!}{\leq}\frac 1{1000}$.
• Since $\hat p$ is unknown between $0$ and $1$, you may estimate $\hat p (1-\hat p) \leq \frac 14$. (Note that $\hat p (1-\hat p)$ describes a downwards open parabola with vertex at $\hat p=\frac 12$.)
• Now, calculate $n$:

$$2.58\sqrt{\frac{\hat p (1-\hat p)}{n}}\leq \frac{2.58}{2\sqrt n}\stackrel{!}{\leq}\frac 1{1000} \Leftrightarrow \boxed{n \geq 1664100}$$

Now, have fun throwing the coin. :-)