Probability for heads from an experiment 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!
 A: 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. 
A: 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$.
A: 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. :-)
