Before revision:  In particular, we show that the PML distribution is an optimal estimator of the sorted true distribution: it is \varepsilon-close in sorted \ell_1 distance to the true distribution with support size k for any n=\Omega(k/(\varepsilon^2 \log k)) and \varepsilon \gg n^{-1/3}, which are the information-theoretically optimal sample complexity and the largest error regime where the classical empirical distribution is sub-optimal, respectively.
After revision:  In particular, we show that the PML distribution is an optimal estimator of the sorted distribution: it is \varepsilon-close in sorted \ell_1 distance to the true distribution with support size k for any n=\Omega(k/(\varepsilon^2 \log k)) and \varepsilon \gg n^{-1/3}, which are the information-theoretically optimal sample complexity and the largest error regime where the classical empirical distribution is sub-optimal, respectively.