0
$\begingroup$

Let $X_1\sim Bin(k,p_1)$ and $X_2\sim Bin(k,p_2)$ be independent r.v. such that $p_1\neq p_2$, and w.l.o.g. let $p_1>p_2$. I wish to upper bound $\Pr(X_2 \geq X_1)$, i.e. finding as tight as possible $B=B(k,p_1,p_2)$ such that $$ \Pr(X_2 \geq X_1)\leq B. $$ According to Total Probability we have $$ \Pr(X_2 \geq X_1) = \sum_{i=0}^k\Pr(X_1=i)\Pr(X_2\geq i)=\sum_{i=0}^k{k \choose i}p_1^i(1-p_1)^{k-i}\Pr(X_2\geq i). $$ Expending the cdf did not produce anything interesting, therefore I tried using this bound on the cdf, but did not get anywhere.

Ideas?


Update: see my answer below.

$\endgroup$
4
  • $\begingroup$ why does the $k$ suddenly turn into an $m$ in the second $=$ ? $\endgroup$
    – Joker123
    Mar 2 '18 at 16:08
  • $\begingroup$ You could try to use Tschebyscheffs inequality for the expression $\Pr(X_2 \geq i)$. $\endgroup$
    – Joker123
    Mar 2 '18 at 16:34
  • 1
    $\begingroup$ Are you assuming independence? $\endgroup$
    – Did
    Mar 3 '18 at 20:21
  • $\begingroup$ @Joker123 Thank, it was a typo. I wrote an answer below using Hoeffding's inequality, inspired by your answer. Thanks! $\endgroup$
    – omerbp
    Mar 4 '18 at 8:27
1
$\begingroup$

Too long for a comment:

You could get an approximation (at least for reasonable $k$ and probabilities not close to $0$ and $1$) with $$\Phi\left(\dfrac{k(p_2-p_1)+\frac12}{\sqrt{k (p_1(1-p_1)+p_2(1-p_2))}}\right)$$

As an example, with $k=10$, $p_1=0.4$ and $p_2=0.2$, you have $P(X_2 \ge X_1) \approx 0.2244$ while the approximation gives about $0.2266$

You be even more likely to exceed the true probability by changing the $\frac12$ in the approximation to $1$. The example would then suggest $0.3085$

$\endgroup$
1
  • $\begingroup$ Thanks for your suggestion! Normal approximation is indeed valuable. I ended up using concentration inequalities, see my answer below. $\endgroup$
    – omerbp
    Mar 4 '18 at 8:40
1
$\begingroup$

Inspired by Joker123's comment above:

Define a series of i.i.d. r.v. $B_1,\dots,B_k$ such that $$ B_i= \begin{cases} 1 & \text{w.p. } (1-p_1)p_2\\ 0 & \text{w.p. } p_1p_2 + (1-p_1)(1-p_2)\\ -1 & \text{w.p. } p_1(1-p_2)\\ \end{cases}. $$ Thus, \begin{align} \Pr(X_2 \geq X_1)&=\Pr(X_2-X_1\geq 0)=\Pr\left(\sum_{i=1}^k B_i \geq 0 \right) \\ & = \Pr\left(\frac{1}{k}\sum_{i=1}^k B_i - (p_2-p_1) \geq (p_1-p_2) \right). \end{align} Notice that $\mathbb E(B_i)=p_2-p_1$ for all $i\in\{1,\dots,k\}$, and that $B_i$ is bounded in the interval $[-1,1]$. Finally, using Hoeffding's Inequality we obtain $$ \leq \exp\left( -\frac{2k^2(p_1-p_2)^2}{4k} \right). $$

$\endgroup$
3
  • $\begingroup$ Do you really intend to have a $\frac{2k^2}{4k}$ term rather than $\frac{k}{2}$ or is there an typo? $\endgroup$
    – Henry
    Mar 4 '18 at 11:02
  • $\begingroup$ @Henry In favor of those who are not familiar with Hoeffding's Inequality, I presented it as appears in here - en.wikipedia.org/wiki/Hoeffding%27s_inequality . If you think it confuses readers, I'll change it. $\endgroup$
    – omerbp
    Mar 4 '18 at 11:14
  • $\begingroup$ Very nice idea! $\endgroup$
    – Joker123
    Mar 4 '18 at 14:32

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