# Literature question on the convergence rate of the empirical distribution

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

• The reference you're looking for is the Central Limit Theorem. – Anthony Quas Dec 10 '15 at 21:39
• 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. – user297646 Dec 12 '15 at 3:18
• Also, I am not sure how I can use the CLT for my question on the optimal convergence speed for any estimate – user297646 Dec 12 '15 at 3:20
• 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. – Aryeh Kontorovich Dec 16 '15 at 15:27

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