7
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Does it help that the Hellinger-squared provides upper and lower bounds on the Jensen-Shannon divergence? $\endgroup$ – Suvrit Nov 8 '10 at 20:47
  • $\begingroup$ 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. $\endgroup$ – Anand Sarwate Nov 11 '10 at 4:47
5
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Did Jan 19 '11 at 6:51
  • $\begingroup$ @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)? $\endgroup$ – robin girard Jan 19 '11 at 7:37
  • $\begingroup$ @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.] $\endgroup$ – ronaf Jan 19 '11 at 18:05
  • $\begingroup$ @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.] $\endgroup$ – ronaf Jan 19 '11 at 18:45
  • $\begingroup$ @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. $\endgroup$ – Did Jan 19 '11 at 23:45
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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})... $\endgroup$ – Anand Sarwate Nov 11 '10 at 4:49
  • $\begingroup$ 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. $\endgroup$ – Mark Meckes Nov 11 '10 at 14:29

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.