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

  • 1
    $\begingroup$ The reference you're looking for is the Central Limit Theorem. $\endgroup$ Commented Dec 10, 2015 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$
    – user83947
    Commented Dec 12, 2015 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$
    – user83947
    Commented Dec 12, 2015 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$ Commented Dec 16, 2015 at 15:27

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.