# Non-asymptotic tail bounds for $D_{\text{Hellinger}}(P\|\hat{P}_N)$

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.$$

# Question

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).$$