$\forall{i=1 ... n}, Pr({a_i > 0}) < e^{-d}$, $a_i$ iid, then $Pr({\sum_{i=1}^{i=n}a_i > 0}) \le 1-(1-e^{-d})^n $? can you give a better bound?

Question

I have changed this problem by adding some conditions. giving that $\forall{i=1...n}, Pr(a_i > 0) < e^{-d}$ where $Pr$ is the probability and $d$ is an positive integer, $a_i$ are iid, please give a bound for $Pr(\sum_{i=1}^{i=n}{a_i} > 0) < $ ???.

we can simply use $$Pr(\sum_{i=1}^{i=n}{a_i} > 0) = 1-Pr(\sum_{i=1}^{i=n}{a_i} \le 0) \le 1-Pr(a_1 \le 0, a_2 \le 0, ..., a_n \le 0)=1-(1-e^{-d})^n$$, but is there a better bound? a better bound means it should be less than $1-(1-e^{-d})^n$

Answer 1

Let $n=2$, $d=1$ and $a_i = 1_{H_i}$ where $\{H_n\}_{n \ge 1}$ is independent coin tossing with $Pr(H_n) = p < e^{-1}$

$$Pr(\sum_{i=1}^{i=2}{a_i} > 0) = 1-(1-p)^2 \ge e^{-1}$$

for $p \in [1-\sqrt{\frac{e-1}{e}},\frac1e) $

Generally,

$$Pr(\sum_{i=1}^{i=n}{a_i} > 0) = 1-(1-p)^n \ge e^{-d}$$

for $p \in [1-(\frac{e^d-1}{e^d})^{\frac1n},\frac1{e^d}] $

But $1-(1-p)^n < 1-(1-e^{-d})^n$

That covers the cases where $a_i$'s are those indicators. You can try out different indicators, but I guess we should assume independence of the $a_i$'s. Then you can try $a_i$'s to be simple functions. The inequality holds true for $a_i=-1_{H_i}$, any $n$ and any $d$ obviously. Then you can try nonnegative then integrable.

You may be interested in Chebyshev's inequality.

Answer 2

I have solve this problem. I will give my proving procedure as follows.

By mathematical induction, if we can prove when $n=2$, the bound holds, then the bound would always hold.

That's to say if we can prove:

Giving $Pr(A > 0) > e^{-d}$ and $Pr(B > 0) < e^{-d}$, then $Pr(A + B > 0) < e^{-d}$.

, the problem would be solved. Actually we can prove this, since:

$$Pr(A + B > 0) = Pr(A > 0, B > 0) + Pr(A + B > 0, A > 0, B < 0) + Pr(A + B > 0 ,A < 0 , B > 0)$$

and $Pr(A > 0,B > 0) = e^{-d} \times e^{-d}$.

and $$Pr(A + B > 0,A > 0, B < 0) = Pr( (A + B > 0) | (A > 0, B < 0)) \times Pr(A > 0, B < 0) = Pr( (A + B > 0) | (A > 0, B < 0)) \times e^{-d} \times (1-e^{-d})$$

observing that $$Pr(A+B>0|A>0,B<0) + Pr(A+B\le0|A>0,B<0) = 1\tag{1}\label{1}$$ and $$Pr(A+B>0|A>0,B>0)\le Pr(A+B\le0|A>0,B>0)\tag{2}\label{2}$$ since for each $A$ and $B$ meets $Pr(A + B > 0)$, that exists another tuple where $(B_1=-A,A_1=-B)$ meet $Pr(A_1 + B_1) < 0$.

so we can obtain $$Pr(A+B>0|A>0,B>0) \le 1/2$$

then $$Pr(A + B > 0,A > 0, B < 0) \le \frac{1}{2} \times e^{-d} \times {1-e^{-d}}$$

so $$Pr(A + B > 0) = Pr(A > 0, B > 0) + Pr(A + B > 0, A > 0, B < 0) + Pr(A + B > 0 ,A < 0 , B > 0) \le e^{-d} \times e^{-d} + 2 \times \frac{1}{2} \times e^{-d} \times ({1-e^{-d}})=e^{-d}$$

Thank @herb steinberg again.