2
$\begingroup$

Assume that given $n$ i.i.d samples $(X_1, X_2, ..., X_n)$ drawn from $p_X$, an unknown probability mass function defined over a finite alphabet $\mathcal{X}$, one wants to estimate $p_X(x)$ for each $x \in \mathcal{X}$.

Assume that one estimates $(p_X(x))_{x \in \mathcal{X}}$ via the empirical distribution. It is known that the optimal convergence speed is in $1/ \sqrt{n}$ by Edgeworth series.

My question is the following.

Is the convergence rate in $1/ \sqrt{n}$ optimal for any estimate of $(p_X(x))_{x \in \mathcal{X}}$ based on the samples $(X_1, X_2, ..., X_n)$?

Hope it is clear. Thanks

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ The reference you're looking for is the Central Limit Theorem. $\endgroup$ – Anthony Quas Dec 10 '15 at 21:39
  • $\begingroup$ Thank you, maybe I don't understand very well the Central Limit Theorem, but it seems to me that it only provides an upper bound on the optimal convergence speed. I think, however, that Edgeworth series shows optimality of $1/ \sqrt{n}$. Please correct me if I am wrong, I am not very familiar with the topic. $\endgroup$ – user297646 Dec 12 '15 at 3:18
  • $\begingroup$ Also, I am not sure how I can use the CLT for my question on the optimal convergence speed for any estimate $\endgroup$ – user297646 Dec 12 '15 at 3:20
  • $\begingroup$ I don't think CLT quite does the trick, as it assumes a particular type of estimator (max likelihood/empirical mean). See my answer below. $\endgroup$ – Aryeh Kontorovich Dec 16 '15 at 15:27
2
$\begingroup$

The minimax rate (in $\ell_1$) for estimating the empirical distribution on an alphabet of size $d$ is $\Theta(\sqrt{d/n})$, where $n$ is the number of samples. See here for more details: http://arxiv.org/abs/1411.1467

| cite | improve this answer | |
$\endgroup$

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.