Let P be a distribution on a finite set of size $k$ and let $\hat{P}_N=(N_1/N,\ldots,N_k/N)$ be the empirical distribution (frequencies) from a samples of size $N$. Consider the Hellinger distance between $P$ and $\hat{P}_N$, namely

$$ D_{\text{Hell}}(P\|\hat{P}_N) := \left(\sum_{i=1}^k\left(\sqrt{p_i}-\sqrt{N_i/N}\right)^2 \right)^{1/2}=2\left(1-\sum_{i=1}^k\sqrt{p_i}\sqrt{N_i/N}\right)^{1/2}. $$

Using the Markov inequality, (Matusita 1995) showed the non-asymptotic bound

Theorem I. For all $t>0$, it holds that $$ P\left(D_{\text{Hellinger}}\left(P\|\hat{P}_N\right)^2 \ge (k-1)t/N\right) \le 1/t. $$

The author also proved the convergence in law

Theorem II. $$4ND_{\text{Hellinger}}(P\|\hat{P}_N)^2 \overset{\mathcal L}{\longrightarrow}\chi_{(k-1)}^2. $$


Can the non-asymptotic tail bound in Theorem I above be improved ? Maybe something like the sub-exponential tail bound for the chi-squared distribution.


This is what I've come up with. It's too long to be a comment, so I decided to post it as an answer.

So, it was proven in LeCam, L. M. (1969). Théorie Asymptotique de la Décision Statistique, p35 that $D_{\text{Hell}}(\cdot\|\cdot)^2/2 \le TV(\cdot, \cdot) \le D_{\text{Hell}}(\cdot\|\cdot)$. On the other hand, Theorem 2 of this paper proves a powerful nonasymptotic tail bound on the $TV(P\|\hat{P}_N)$, namely

For every $\epsilon \ge \sqrt{k/N}$, one has $$ P(TV(P\|\hat{P}_N) > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon-\sqrt{k/N})^2\right). $$

Putting things together, we have

For every $\epsilon \ge 2\sqrt{k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N)^2 > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon/2-\sqrt{k/N})^2\right). $$

from which one may immediate recover a nonasymptotic sub-exponential tail bound for $D_{\text{Hell}}(P\|\hat{P}_N)$, as dreamed, for example

For every $\epsilon \ge 4\sqrt{5k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N) > \sqrt{\epsilon}) \le \exp(-0.075N\epsilon^2). $$


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.