3
$\begingroup$

Let $H$ denote the Hellinger distance; i.e., for two discrete distributions $p,q$ (identified with their pmf) over $\mathbb{N}$, $$ H(p,q)^2 = \frac{1}{2}\sum_{n=0}^\infty \left(\sqrt{p(n)}-\sqrt{q(n)}\right)^2 = 1-\sum_{n=0}^\infty \sqrt{p(n)q(n)} $$ and $\operatorname{Poi}(\lambda)$ for the Poisson distribution with parameter $\lambda$.

I would like to know whether there exists a simple proof of the following result:

Let $\lambda>0$, and $\alpha\in[0,1]$. Define $Q= \frac{1}{2}(\operatorname{Poi}((1+\alpha)\lambda) +\operatorname{Poi}((1-\alpha)\lambda) )$. Then $H(\operatorname{Poi}(\lambda),Q) \lesssim \alpha^2\lambda$.

I can easily prove that the square Hellinger distance satisfies $H(\operatorname{Poi}(\lambda),Q)^2 \lesssim \alpha^2\lambda$, but the only proof I know for the correct (and tight) statement above is Lemma 4.1 of [VV17]; and I feel there should (?) be a neater and more generalizable argument to establish this seemingly simple bound.

As far as I can tell, the crux of the difficulty (at least in my attempts) is to tightly (upper) bound the quantity $$ \sum_{n=0}^\infty \frac{\lambda^n}{n!}\sqrt{\frac{e^{\lambda\alpha}(1-\alpha)^n+e^{-\lambda\alpha}(1+\alpha)^n}{2}} $$ where the obvious attempts (e.g., AM-GM) only yield the loose bound mentioned above.


[VV17] Valiant, Gregory; Valiant, Paul. An automatic inequality prover and instance optimal identity testing. SIAM J. Comput. 46 (2017), no. 1, 429--455. https://theory.stanford.edu/~valiant/papers/instanceOptFull.pdf

$\endgroup$
0

1 Answer 1

1
$\begingroup$

I have an indirect (but simple) proof, which relies on the chi-squared distance $\chi^2(p,q) = \sum_n \frac{(p(n)-q(n))^2}{q(n)}$ as a proxy, along with the fact that $H(p,q)^2 \leq 1\land \chi^2(p,q)$ for all discrete distributions $p,q$.

Lemma. Let $\lambda>0$, and $\alpha\in[0,1]$. Define $Q= \frac{1}{2}(\operatorname{Poi}((1+\alpha)\lambda) +\operatorname{Poi}((1-\alpha)\lambda) )$. Then $1\land \chi^2(\operatorname{Poi}(\lambda),Q) \leq \alpha^2\lambda$.

Proof. We can assume in the rest of the proof that $\alpha^2\lambda \leq 1$, as otherwise there is nothing to prove. For convenience, write $P:= \operatorname{Poi}(\lambda)$. We can express the pmf of $Q$ as \begin{equation} Q(n) = P(n)\cdot\frac{e^{-\lambda\alpha}(1+\alpha)^n + e^{\lambda\alpha}(1-\alpha)^n}{2} \tag{1} \end{equation} for $n\in \mathbb{N}$. It follows that $$\begin{align*} \chi^2( Q , P ) &= -1 + \sum_{n\in\mathbb{N}} \frac{Q(n)^2}{P(n)} \\ &= -1 + e^{-\lambda}\sum_{n\in\mathbb{N}} \frac{\lambda^n}{n!}\left( \frac{e^{-\lambda\alpha}(1+\alpha)^n + e^{\lambda\alpha}(1-\alpha)^n}{2}\right)^2 \tag{2} \end{align*}$$ Focusing on the last sum, we expand the square and compute it explicitly: \begin{align*} \sum_{n\in\mathbb{N}} &\frac{\lambda^n}{n!}\left( \frac{e^{-\lambda\alpha}(1+\alpha)^n + e^{\lambda\alpha}(1-\alpha)^n}{2}\right)^2\\ &= \sum_{n\in\mathbb{N}} \frac{\lambda^n}{n!} \frac{e^{-2\lambda\alpha}(1+\alpha)^{2n} + e^{2\lambda\alpha}(1-\alpha)^{2n} + 2(1-\alpha^2)^n}{4}\\ &= e^{\lambda}\cdot\frac{e^{\lambda\alpha^2} + e^{-\lambda\alpha^2}}{2} \tag{3}\,. \end{align*} Plugging this in (2), we get $$ \chi^2( Q , P ) = -1 + \frac{e^{\lambda\alpha^2} + e^{-\lambda\alpha^2}}{2} \leq \lambda^2\alpha^4 \tag{4} $$ where for the last inequality we used our bound $\lambda\alpha^2\leq 1$, and the fact that $\cosh x \leq 1+x^2$ for $|x|\leq 1$ (I didn't try to optimize the constant).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .