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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.