For the sake of this question I want to focus on an unfair coin.
Assuming we have a number of $i.i.d.$ samples $X_1, ..., X_n$ and a precision level requirement $\tau$. I search for the optimal estimator $\hat{P_n}$ minimizing the expression $P(|\hat{P_n} - {P(X_1 = 1)} |\geq \tau)$. Also I would like to know the convergence rate in this case.
Intiutively the law of large numbers should be the best choice, which gives exponential convergence speed. But that might not be enough for small $\tau$ and little $n$. So I just wanted to check if in this case we could possibly do any better. I guess the answer should not be due to the CLT, but I can't quite prove it.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Use Chernoff bounds + Borel-Cantelli for almost sure convergence. Alternatively, Sanov's theorem gives you the exact convergence rate. $\endgroup$– Aryeh KontorovichCommented Dec 22, 2016 at 21:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
And if you want the exact minimax risk rate, take a look at the recent preprint by Iosif Pinelis and myself: https://arxiv.org/abs/1606.08920
Essentially, the above shows that the optimal estimator is the maximum-likelihood one (i.e., the obvious one obtained by dividing the number of heads by sample size) and the error decays as $c/\sqrt n$, where $c$ is a constant we explicitly compute in the paper.
answered Dec 22, 2016 at 21:15
-
1$\begingroup$ This paper is just what I had been searching for. Thank you very much. $\endgroup$ Commented Dec 22, 2016 at 21:33
-
$\begingroup$ Thinking practically here, the (general) question is most interesting for relatively small n. How big does n need to be for the asymptotic $c/\sqrt(n)$ to hold? $\endgroup$ Commented Dec 22, 2016 at 22:29
-
$\begingroup$ Well, once you know the form of the optimal estimator (empirical mean), you can use Chernoff bounds for sharp finite-sample estimates. $\endgroup$ Commented Dec 22, 2016 at 22:33