-1
$\begingroup$

I'm trying to find a lower bound for the following expression for $q\ge p$: $$f(q,p,n) := \sum_{v=0}^n \sum_{k=v}^n \binom{n}{v} \binom{n}{k}q^v(1-q)^{n-v}p^k(1-p)^{n-k}.$$ It can be thought of as the expectation value of the tail of the binomial distribution with parameter $p$ taken with respect to the binomial distribution with parameter $q$, an expectation value of a p-value.

It is easy to see that $f(q,0,n) = (1-q)^n$ and $f(1,p,n) = p^n$, and with a bit of work one can show that $\lim_{n \to \infty} f(\frac12,\frac12,n) = 1/2$, so I conjecture that the following bound holds: $$f(q,p,n) \ge \frac12(1-(q-p))^n.$$ I have no idea how to prove it, though. Applying the standard lower bounds to the binomial tail leads to a terribly loose bound, and I couldn't use generating functions to get a bound on the overall expression. On the other hand, one can easily prove the upper bound $(1-(q-p)^2)^n$ using generating functions, so perhaps there is also some easy trick that applies to the lower bound.

I don't know if it is helpful, but one can also show that $f(q,p,n) = f(1-p,1-q,n)$.

$\endgroup$
5
  • 1
    $\begingroup$ Isn't it just the probability that a Binomial(p,n) is greater than or equal to an independent binomial(q,n)? This gives immediately the cases you wrote (no need for limits or work...), and a bit of work should give you a decent bound (with actually the correct exponential rate). $\endgroup$ Jun 20, 2020 at 12:02
  • $\begingroup$ Yes, it is. I don't see how that helps, though (I'm a physicist, not a mathematician). For example, the exact expression for $f(\frac12,\frac12,n)$ is $\frac12 + 4^{-n}\binom{2n}{n}/2$. How can one get that without doing work? $\endgroup$ Jun 20, 2020 at 13:54
  • $\begingroup$ By symmetry. You have two identically distributed variables $A,B$ and you ask for $P(A\geq B)$, which equals $1/2+P(A=B)$. The local CLT tells you that the probability that $A=B$ is of order $1/\sqrt{n}$ $\endgroup$ Jun 20, 2020 at 19:12
  • $\begingroup$ As to the actual question you asked - asymptotics then become very easy, it is a large deviations question, since the means are different. Exact computations I will leave to others, although I note that you are asking for $P(B\geq 0)$ where $B=\sum_{i=1}^N W_i$, $W_i$ iid, and $EW_i=p-q$ and variance of $W_i$ equal $2q(1-p)$. Asymptotics now follow... $\endgroup$ Jun 20, 2020 at 19:17
  • $\begingroup$ I still don't see how that helps. For example, I can directly apply the Chernoff bound to $P(B\ge 0)$, which gives me the upper bound $f(q,p,n) \le (\sqrt{pq}+\sqrt{(1-p)(1-q)})^{2n}$, but this is exactly the same bound I got via generating functions. And the difficult is anyway finding a lower bound. Do you have any specific anti-concentration inequality in mind that would work? Also, the variance of $W_i$ is $p(1-p)+q(1-q)$. $\endgroup$ Jun 21, 2020 at 10:36

1 Answer 1

0
$\begingroup$

This answer gives asymptotics as $q-p=\alpha>0$ fixed and $n\to\infty$. Other variants are of course also possible.

As mentioned in the comments, the question can be rephrased as follows. Let $W_i$ be iid random variables so that $P(W_1=1)=p(1-q)$, $P(W_1=-1)=q(1-p)$ and $P(W_1=0)=1-p-q+2pq$. With $B=\sum_{i=1}^n W_i$, the question is to evaluate the probability $P(B\geq 0)$. Now, the log moment generating function of $W_1$ is $$\Lambda(\lambda)=\log E(e^{\lambda W_1})=\log(1-p-q+2pq+p(1-q)e^\lambda+q(1-p)e^{-\lambda}).$$ The Legendre transform $\Lambda^*(x)=\sup_{\lambda}(\lambda x-\Lambda(\lambda))$ satisfies, if I am not mistaken, $$\Lambda^*(0)=-\log\left(\left(\sqrt{pq} + \sqrt{(1-p)(1-q)}\right)^2\right)=:\beta.$$ Now, since $\alpha>0$, $EW_1<0$, and so we are in the large deviations regime. By the Bahadur-Rao theorem, $$P(B\geq 0)\sim \frac{c}{\sqrt{n}}e^{-n\beta},$$ where $$c = \frac{\sqrt{pq} + \sqrt{(1-p)(1-q)}}{\sqrt{4\pi}\left(1-\sqrt{\frac{p(1-q)}{(1-p)q}}\right)\big(pq(1-p)(1-q)\big)^\frac14}. $$

The case $q=p$ is just a local CLT. If $q,p$ depend on $n$, asymptotics can be read from the proof of the BR theorem.

For more details see the original paper of Bahadur-Rao (1960), and the exposition in Dembo-Zeitouni LD textbook (Theorem 3.7.4).

$\endgroup$
10
  • $\begingroup$ It's nice to know the asymptotics, but I still don't see how that helps finding a lower bound. I checked your book, and the theorem doesn't provide a bound, it only talks about the limit. Also, is there any reason you wrote $P(B>0)$ instead of $P(B\ge 0)$? Since you're taking $\Lambda^*(0)$ you must mean the latter, which is indeed what I asked about. $\endgroup$ Jun 22, 2020 at 15:30
  • $\begingroup$ Thanks for pointing out the $>$ vs $\geq$ - the asymptotics is actually the same. The lower bound is quantitative - that is, you can actually write $P(B\geq 0) =ce^{-n\beta}/\sqrt{n}(1+C_1/\sqrt{n})$, and with enough diligence get an upper bound on $C_1$. Note that the lower bound involves computing, under the tilted measure, an upper bound on the complementary event, $\endgroup$ Jun 22, 2020 at 19:58
  • $\begingroup$ Here is a sketch of how to do it quantitative: make a tilt of the law of $W_1$ to have the mean at +ϵ. This will give you a factor$e^{-n\Lambda^*(\epsilon)}$ and then a lower bound is $e^{-n \Lambda^*(\epsilon) - n\lambda \delta} P_\lambda^n ([0,(\epsilon+\delta)n])$ which is greater or equal to $e^{-n(\Lambda^*(\epsilon)+\delta\lambda)} (1-P_\lambda^n([0, (\epsilon+\delta)n]^c)$ $\endgroup$ Jun 22, 2020 at 20:45
  • $\begingroup$ Now, by Chebycheff, $P_\lambda^n([0,(\epsilon+\delta)n]^c)\leq e^{-c'(\epsilon \wedge \delta)n}$ for some $c'$ that is explicit and one can compute. For $n$ such that the RHS is smaller than $1/2$, this completes the lower bound. $\endgroup$ Jun 22, 2020 at 20:47
  • $\begingroup$ I calculated the value of $c$ and added it as an edit to your answer, but some random prick deleted it saying that it does not matter. For the record, it is $c = \frac{\sqrt{pq} + \sqrt{(1-p)(1-q)}}{\sqrt{4\pi}\left(1-\sqrt{\frac{p(1-q)}{(1-p)q}}\right)\big(pq(1-p)(1-q)\big)^\frac14}.$ $\endgroup$ Jun 23, 2020 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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