I came across a claim in a paper Trace reconstruction revisited (in Lemma 11), which is basically that the squared Hellinger distance between Binomial$(n,p)$ and Binomial$(n+1,p)$ grows as $O(1/n)$. $p$ is a small positive number less than $\frac{1}{2}$.

I've been trying to prove it but have not been able to see this. Is there an easy way to see this?

  • $\begingroup$ If $p=1$, the statement is false. So what's the constraint on $p$? $\endgroup$
    – Thomas
    Oct 8 '15 at 18:08
  • $\begingroup$ $p$ is some constant less than $\frac{1}{2}$. $\endgroup$
    – Devil
    Oct 8 '15 at 19:06
  • 1
    $\begingroup$ Please edit the question to include that information (and any other relevant information) in the question. We expect questions to be self-contained. People shouldn't have to read the comments to understand the question. Thank you! $\endgroup$
    – D.W.
    Oct 9 '15 at 4:59

Write $$\begin{align} h^2(B(n,p), B(n+1,p))& = 2 \left(1 - \sum_{i=0}^{n+1}\sqrt{{n \choose i}p^i(1-p)^{n-i}{n+1 \choose i} p^i (1-p)^{n+1-i}}\right)\\ &=2\left(1 - \sum_{i=0}^{n+1}\sqrt{\left({n+1 \choose i}p^i(1-p)^{n+1-i}\right)^2 \frac{n+1-i}{(n+1)(1-p)}} \right)\\ &=2 \left(1 - \sum_{i=0}^{n+1}{n+1 \choose i}p^i(1-p)^{n+1-i}\sqrt{ \frac{n+1-i}{(n+1)(1-p)}} \right)\\ &=2\left(1-\frac{1}{\sqrt{(n+1)(1-p)}} \mathbb{E}(\sqrt{Z})\right),\\ \end{align}$$ where $Z \sim B(n+1, 1-p)$. By Taylor approximation (see this), we have $$\mathbb{E}(\sqrt{Z}) \ge \sqrt{(n+1)(1-p)} - \frac{p}{2 \sqrt{(n+1)(1-p)}}. $$ Combining with the above, we get $$ h^2(B(n,p), B(n+1,p)) \le 2 \left(1 - \left(1 - \frac{p}{2 (n+1)(1-p)}\right)\right) = \frac{p}{(n+1)(1-p)}.$$


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.