-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)$.

Improve this question
$\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$
    – ofer zeitouni
    Commented 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$
    – Mateus Araújo
    Commented 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$
    – ofer zeitouni
    Commented 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$
    – ofer zeitouni
    Commented 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$
    – Mateus Araújo
    Commented Jun 21, 2020 at 10:36

1 Answer 1

Reset to default
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).

Improve this answer
$\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$
    – Mateus Araújo
    Commented 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$
    – ofer zeitouni
    Commented 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$
    – ofer zeitouni
    Commented 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$
    – ofer zeitouni
    Commented 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$
    – Mateus Araújo
    Commented Jun 23, 2020 at 13:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .