<p>Write $$\begin{align}
h^2(B(n,p), B(n+1,p))&amp; = 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)\\
&amp;=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)\\
&amp;=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)\\
&amp;=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 <a href="https://mathoverflow.net/questions/121411/expectation-of-square-root-of-binomial-r-v">this</a>), 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)}.$$</p>

CC BY-SA 3.0
2015-10-09T22:28:08.703Z
2015-10-09T22:28:08.703Z
2017-04-13T12:57:54.777Z
Denis Pankratov
<p>I came across a claim in a paper <a href="https://people.cs.umass.edu/~mcgregor/papers/14-esa.pdf" rel="nofollow" title="Trace Reconstruction Revisited">Trace reconstruction revisited</a> (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}$.</p>

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

CC BY-SA 3.0
2015-10-08T18:08:19.483Z
If $p=1$, the statement is false. So what's the constraint on $p$?
Thomas Steinke
CC BY-SA 3.0
2015-10-08T19:06:01.390Z
$p$ is some constant less than $\frac{1}{2}$.
Devil
CC BY-SA 3.0
2015-10-09T04:59:36.740Z
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!
D.W.
<pr.probability>
Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p)
Devil
# Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p)

(Asked by: username_0 on 2015-10-08)

I came across a claim in a paper [Trace reconstruction revisited](https://people.cs.umass.edu/~mcgregor/papers/14-esa.pdf "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?

**Tags:** pr.probability

> **Comments:**
> **username_1**: If $p=1$, the statement is false. So what's the constraint on $p$?  
> **username_0**: $p$ is some constant less than $\frac{1}{2}$.  
> **username_2**: 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!  

---

## 1 answers

### Answer by username_3 on 2015-10-09. Score: 5 | Accepted answer

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](https://mathoverflow.net/questions/121411/expectation-of-square-root-of-binomial-r-v)), 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)}.$$


---

