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



Literature question on the convergence rate of the empirical distribution
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>


