Bounding the probability that two binomials are equal

Question

Note: This question was migrated from this earlier post, where it initially appeared. Following suggestions, I moved this into its own question.

Let $B_{n,p}$ denote the usual binomial random variable (i.e., the probability that it equals $k$ is given by ${n \choose k} p^k (1-p)^{n-k}$). I would like some reference (or proof) for the following:

• For all integers $0 \leq t < n$ and all $0 < p < 1$, we have $t \cdot \mathbb{P}(B_{n+t,p} = B_{n-t,p}) \leq \dfrac{100}{p}$, where the variables $B_{n+t,p}$ and $B_{n-t,p}$ are independent binomials.

---

I believe this could be done as follows, but I didn’t work it out fully...

Let $f(t)$ denote the quantity in question (thinking of $n$ and $p$ as fixed). I imagine that $f(t)$ is unimodal with a maximum taken at some relatively small $t$. If we replace the difference of Binomials with their normal approximations, this suggests the maximum should occur when $t = C \sqrt{np(1-p)} /p$. And values of $t$ this small, it is easy to see the desired bound on $f(t)$ simply because that probability is always at most $C/\sqrt{np(1-p)}$.

So we’d just need to argue that if $t \geq C \sqrt{np(1-p)}/p$, then $f(t)$ is decreasing [note that if convenient, we can safely throw in an extra constant here without any concern].

---

I can also prove a weaker bound involving some extra $\log(np(1-p))$ factor (there about) via a naive approach that wastefully bounds the probability in question using some concentration results such as Bernstein’s inequality. But that’s not the way to go about it, and it gives us the wrong answer.

Hoping for a nice argument or (perhaps better?) a reference.

Thanks!

Added remark: I’m really just asking about the probability that two independent binomials $B_{m,p}$ and $B_{k,p}$ are equal, so one might reasonably hope this is already known.

Answer 1

$$\mathbb{P}(B_{n+t,p}=B_{n-t,p})=\sum_{k=0}^{n-t}\frac{(n+t)!(n-t)!}{(n+t-k)!(n-t-k)!(k!)^2}p^{2k}(1-p)^{2n-2k}. $$ We write $a_k$ the terms in this sum. We have $$ \frac{a_{k+1}}{a_k}=\frac{p^2(n+t-k)(n-t-k)}{(1-p)^2(k+1)^2}$$ The formal function $f(k)=\frac{a_{k+1}}{a_k}$ is decreasing in $k$. And there is a $k^*$ such that $f(k^*)\approx 1$. It corresponds to a $a_{k^*}=\max_k a_k$ .There we have $f'(k^*)< - \frac{1}{k^*}$. Therefore for $k$ not too far from $k^*$ $$ a_k = a_{k^*}\prod_{k^*\leq i < k}f(i)\approx a_{k^*}\prod_{k^*\leq i < k} (1+(i-k^{*})f'(k^*)) \leq a_{k^*} \exp(-\sum_{l=0}^{k-k^*}\frac{l}{k^*})\approx a_{k^*}e^{-\frac{(k-k^*)^2}{2k^*}}$$ So one should get $$\sum_{k}a_k \leq C\sqrt{k^*} a_{k^*}.$$Moreover using the TCL we have $$a_{k^*}= \mathbb{P}(B_{n+t,p}=B_{n-t,p}=k^*) \approx \frac{1}{\sqrt{\sigma^2}}e^{-\frac{1}{\sigma^2}(k^*-(n+t)p)^2)}\times \frac{1}{\sqrt{\sigma^2}}e^{-\frac{1}{\sigma^2}(k^*-(n-t)p)^2}\leq \frac{1}{\sigma^2} e^{-\frac{2(tp)^2}{\sigma^2}}$$ where $\sigma^2 = Cnp(1-p)\approx k^*$. Finally $$pt\sqrt{k^*}a_{k^*}\leq \frac{pt}{\sigma} e^{-\frac{2(tp)^2}{\sigma^2}}\leq \sup_{x\geq0} x e^{-2x^2}\leq C $$