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.


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.

  • $\begingroup$ You are dividing by $t$ to obtain the upper bound on probability but $100/p$ is already huge, so something is wrong in your right hand side. Is it 100 p/t? $\endgroup$ – kodlu Jun 20 '20 at 1:34
  • 1
    $\begingroup$ No, this is what I want. It’s immediate unless $t$ is sort of just the right size. Consider for instance $t=f(n) \sqrt{np(1-p)}/p$. If $f(n)$ is bounded, then we’re fine simply because the probability is always at most $C/\sqrt{np(1-p)}$ (anticoncentration of the binomial). On the other hand, if $f(n)$ is too big (e.g., if $f(n) \geq C *\sqrt{\log(np)}$ [and assuming $np(1-p) \geq 10$ or something]), then by Bernstein’s inequality the probability is at most $C / np$, so we’re also fine. So! We really only care about $100 \leq t p/\sqrt{np(1-p)} \leq 100 \sqrt{\log(np)}$. $\endgroup$ – Pat Devlin Jun 20 '20 at 16:25
  • $\begingroup$ Isn't it just the central limit theorem? $\endgroup$ – RaphaelB4 Jun 25 '20 at 11:43
  • $\begingroup$ A local limit theorem is all fine and good, but as I recall the error terms would be bigger than I can tolerate. I could be wrong though, and I’m certainly not an expert in the existing local limit theorems. $\endgroup$ – Pat Devlin Jun 25 '20 at 12:43

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

  • $\begingroup$ Do you have a reference for the local limit theorem you’re using? In general, I’d be concerned about the error terms involved. $\endgroup$ – Pat Devlin Jun 25 '20 at 23:38

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.