Convergence of an empirical distribution w.r.t. the Hellinger distance - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T22:30:01Z http://mathoverflow.net/feeds/question/45320 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45320/convergence-of-an-empirical-distribution-w-r-t-the-hellinger-distance Convergence of an empirical distribution w.r.t. the Hellinger distance Anand Sarwate 2010-11-08T16:24:11Z 2011-01-22T03:59:17Z <p>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:</p> <p>$\hat{P_n}(x) = \frac{1}{n} \sum_{i=1}^{n} 1_{X_i = x}$</p> <p>Let $d_H(P,Q)$ be the Hellinger distance:</p> <p>$d_H(P,Q) = \left( \frac{1}{2} \sum_{x \in \mathcal{X}} ( \sqrt{P(x)} - \sqrt{Q(x)} )^2 \right)^{1/2}$</p> <p>Is there a nice expression for the expected distance between $\hat{P_n}$ and $P$? That is, is there some formula like</p> <p>$\mathbb{E}[ d_H(P,Q) ] = C \frac{1}{n} - O(\frac{1}{n^2})$</p> <p>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?</p> <p>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?</p> <p>It would be interesting to know this for densities as well, but maybe the discrete problem is easier.</p> http://mathoverflow.net/questions/45320/convergence-of-an-empirical-distribution-w-r-t-the-hellinger-distance/45360#45360 Answer by Mark Meckes for Convergence of an empirical distribution w.r.t. the Hellinger distance Mark Meckes 2010-11-08T20:37:42Z 2010-11-08T20:37:42Z <p>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}).$$</p> http://mathoverflow.net/questions/45320/convergence-of-an-empirical-distribution-w-r-t-the-hellinger-distance/52474#52474 Answer by ronaf for Convergence of an empirical distribution w.r.t. the Hellinger distance ronaf 2011-01-19T04:51:01Z 2011-01-22T03:59:17Z <p>it is possible to show that $\mathrm {E}d(P,\hat{P_n})\sim \frac{C}{\sqrt{n}}$ and specify the value of $C$.</p> <p>let</p> <p>$$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}).$$</p> <p>$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}|$.</p> <p>the statistic $D_n^2$ seems to have been first considered by <a href="http://www.ism.ac.jp/editsec/aism/pdf/005_2_0059.pdf" rel="nofollow"><em>matusita</em> 1</a>. <a href="http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?handle=euclid.aoms/1177728422&amp;view=body&amp;content-type=pdf_1" rel="nofollow"><em>matusita</em> 2</a> develops some asymptotic [and other] properties of $D_n^2$, including the fact that under the null hypothesis, as $n\to\infty$,</p> <p>$$\kern-1.9in (1)\kern1.9in 4nD_n^2\ \buildrel{\mathcal L}\over{\to}\ \chi^2_{k-1}.$$</p> <p>it is also shown there that</p> <p>$$\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)}.$$</p> <p>$\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$,</p> <p>$$\kern-2in (3)\kern2in \mathbb{X}^2_n\ \buildrel{\mathcal L}\over{\to}\ \chi^2_{k-1}.$$</p> <p>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 </p> <p>$$\mathrm {E}4nD_n^2\to \mathrm {E}\chi^2_{k-1}\ =\ k-1\ \mathrm{as}\ n\to\infty$$</p> <p>and</p> <p>$$\mathrm {E}2\sqrt{n}D_n\to \mathrm {E}\chi_{k-1}\ \mathrm{as}\ n\to\infty.$$ </p> <p>[for more details on connections between convergence in law, uniform integrability and convergence of expectations, see <a href="http://www.amazon.com/Convergence-Probability-probability-mathematical-statistics/dp/0471072427%3FSubscriptionId%3D1E2MCMDX6VVV67W7T882%26tag%3Dabs-bookcompareapi-20%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D0471072427" rel="nofollow"><em>billingsley 1st ed</em></a>, p32 theorem 5.4 or <a href="http://books.google.com/books?id=GzjbezrsrFcC&amp;printsec=frontcover&amp;dq=billingsley+%22convergence+of+probability+measures%22&amp;source=bl&amp;ots=jNHmITd6tv&amp;sig=4WRvY0wqYH1-Hd3BwOA9g9DQch4&amp;hl=en&amp;ei=H-s5Td7SO8P6lwfi2dXrBQ&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=7&amp;ved=0CFMQ6AEwBg#v=onepage&amp;q&amp;f=false" rel="nofollow"><em>billingsley 2nd ed</em></a> pp31-32 theorems 3.4 and 3.5.]</p>