# Convergence of an empirical distribution w.r.t. the Hellinger distance

Let $P$ be a probability distribution on a finite set $\mathcal{X}$ and let $X_1, X_2, \ldots, X_n$ be drawn i.i.d. according to $P$. Define the empirical distribution:

$\hat{P_n}(x) = \frac{1}{n} \sum_{i=1}^{n} 1_{X_i = x}$

Let $d_H(P,Q)$ be the Hellinger distance:

$d_H(P,Q) = \left( \frac{1}{2} \sum_{x \in \mathcal{X}} ( \sqrt{P(x)} - \sqrt{Q(x)} )^2 \right)^{1/2}$

Is there a nice expression for the expected distance between $\hat{P_n}$ and $P$? That is, is there some formula like

$\mathbb{E}[ d_H(P,Q) ] = C \frac{1}{n} - O(\frac{1}{n^2})$

where $C$ can be written out explicitly? Or if the rate of convergence is slower than $1/n$, can we get the exact rate of convergence?

For context, if we consider the KL-divergence or $L_1$ distance then we can get explicit expressions for the first term in the rate of convergence of $\hat{P_n}$ to $P$. Can we do the same for the Hellinger distance?

It would be interesting to know this for densities as well, but maybe the discrete problem is easier.

-
Does it help that the Hellinger-squared provides upper and lower bounds on the Jensen-Shannon divergence? – Suvrit Nov 8 '10 at 20:47
Not really -- what I was hoping for was an exact expression for the first term in the expansion of the expected error. for KL divergence we can get something like (|X| - 1)/2n, and for L1/total variation we can get it exactly from DeMoivre's formula. I wasn't sure if there was an expression for Hellinger as well. – Anand Sarwate Nov 11 '10 at 4:47

it is possible to show that $\mathrm {E}d(P,\hat{P_n})\sim \frac{C}{\sqrt{n}}$ and specify the value of $C$.

let

$$D_n^2 =\sum_{x \in \mathcal{X}} \left( \sqrt{P(x)} - \sqrt{\hat{P_n}(x)} \right)^2 = 2d^2(P,\hat{P_n}).$$

$4nD_n^2$ is known in statistics [for reasons unclear to me] as the freeman-tukey goodness-of-fit [gof] statistic for testing the null hypothesis that $X\sim P$. like the better known pearson chi-squared gof statistic, it also has [under the null hypothesis] an asymptotic chi-squared distribution with $k-1$ df. here $k=|\mathcal{X}|$.

the statistic $D_n^2$ seems to have been first considered by matusita 1. matusita 2 develops some asymptotic [and other] properties of $D_n^2$, including the fact that under the null hypothesis, as $n\to\infty$,

$$\kern-1.9in (1)\kern1.9in 4nD_n^2\ \buildrel{\mathcal L}\over{\to}\ \chi^2_{k-1}.$$

it is also shown there that

$$\kern-.88in (2)\kern.88in 4nD_n^2\ \le\ \mathbb{X}^2_n\ :=\ n\sum_{x \in \mathcal{X}} \frac{\left({\hat P}(x)-P(x)\right)^2}{P(x)}.$$

$\mathbb{X}^2_n$ is, of course, the pearson chi-squared gof statistic, and it is well-known that under the null hypothesis $X\sim P$, as $n\to\infty$,

$$\kern-2in (3)\kern2in \mathbb{X}^2_n\ \buildrel{\mathcal L}\over{\to}\ \chi^2_{k-1}.$$

it is also easily seen that for all $n\ge 1,\ \mathrm {E} \mathbb{X}^2_n\ =\ k-1$. together with (3) [and non-negativity], this entails that $\mathbb{X}^2_n$ is uniformly integrable. in view of (2), so is $4nD_n^2$, so it follows from (1) that

$$\mathrm {E}4nD_n^2\to \mathrm {E}\chi^2_{k-1}\ =\ k-1\ \mathrm{as}\ n\to\infty$$

and

$$\mathrm {E}2\sqrt{n}D_n\to \mathrm {E}\chi_{k-1}\ \mathrm{as}\ n\to\infty.$$

[for more details on connections between convergence in law, uniform integrability and convergence of expectations, see billingsley 1st ed, p32 theorem 5.4 or billingsley 2nd ed pp31-32 theorems 3.4 and 3.5.]

-
@ronaf: Nice post! But you do not show that the family $(\mathbb{X}_n^2)_n$ is uniformly integrable, do you? Fortunately the boundedness of $\mathrm{E}(\mathbb{X}_n^2)$ proves that $(\mathbb{X}_n)_n$ is uniformly integrable, and this implies the $C/\sqrt{n}$ equivalent of $\mathrm{E}(D_n)$. – Did Jan 19 '11 at 6:51
@ronaf thanks for this answer! I did not know these papers from Matusita. It seems than none of them mention Hellinger (who died in 1950). I did not find informations about Matusita (where did he worked..) do you know more than me (I liked his papers)? – robin girard Jan 19 '11 at 7:37
@robin matusita worked at the institute of statistical mathematics in tokyo. [it is a statistical think tank - something like the IAS in princeton - in concept - if not quite in prestige.] – ronaf Jan 19 '11 at 18:05
@didier thanks for the boost. as for $(\mathbb{X}_n^2)_n$ being ui: it follows from the fact that the expectation is k-1 for all $n$ - so that it [trivially] converges to the expectation of $\chi^2_{k-1}$. given convergence in law, the expectations converge iff the sequence is ui. [i don't think just boundedness of the expectations is enough to guarantee ui for $(\mathbb{X}_n^2)_n$. one needs a bit more, like boundedness of a $1+\delta$ moment, for example. [the best result in that vein is de la Vallée-Poussin's theorem; cf en.wikipedia.org/wiki/Uniform_integrability.] – ronaf Jan 19 '11 at 18:45
@ronaf: Indeed, boundedness in $L^1$ does not imply uniform integrability. Re your answer to my remark: For real valued random variables $Y_n$ and $Y$ such that $E(Y_n)\to E(Y)$, the fact that $Y_n\to Y$ in law does not imply that $(Y_n)$ is uniformly integrable. But this implication holds if, furthermore, every $Y_n$ is almost surely nonnegative. (Proof: Scheffé's lemma + Skorohod representation theorem.) You might want to expand this step of the proof in your answer. – Did Jan 19 '11 at 23:45

Here's a quick argument to get something in the direction of what you want, but rather weaker than you asked for. First of all, using the Cauchy-Schwarz inequality, $$\mathbb{E} d_H(P,\hat{P}_n) \le \sqrt{1-\sum_x \sqrt{P(x)}\mathbb{E} \sqrt{\hat{P}_n(x)}}.$$ For each $x$, $\hat{P}_n(x)$ is distributed as $\frac{1}{n} \mathrm{Bin}(n,P(x))$, which is approximated by the normal distribution $\mathcal{N}(P(x), \frac{1}{n} P(x)(1-P(x))$, with an error (say in Kolmogorov distance) of $O(n^{-1/2})$. Since the variance converges to 0, one can make a linear approximation of $t \mapsto \sqrt{t}$ about $P(x)$ to see $\mathbb{E}\sqrt{\hat{P}_n(x)} = \sqrt{P(x)} + O(n^{-1/2})$, which leads to $$\mathbb{E} d_H(P,\hat{P}_n) = O(n^{-1/4}).$$

-
Doesn't this show that the error is upper bounded by O(n^{-1/4}) only? I had sort of hoped that the error would be O(n^{-1/2}), so that squaring it would give an error of O(n^{-1})... – Anand Sarwate Nov 11 '10 at 4:49
Yes, writing $=O(n^{-1/4})$ means only that the error is upper bounded by $Cn^{-1/4}$ for some constant $C>0$. This was a pretty quick and dirty argument, and I wouldn't be surprised if it could be improved to yield $O(n^{-1/2})$ with a bit more work. – Mark Meckes Nov 11 '10 at 14:29