# Lower bound on probability of sum of random variables

Suppose that the random variables $X_i, i = 1,2,\ldots,n$ are i.i.d. Suppose $0 \leq X_i \leq 4n^2$ with probability 1 for all $i$. Suppose that $\mathbb{E}(X_i) \geq n$ for all $i$. Show that $$\mathbb{P}(X_1 + X_2 + \cdots + X_n \geq n^2/2) \geq \frac{1}{20}.$$

Hint: Is there a lower bound inequality that you might try here? What do you need to compute? How can you use the hypotheses?

I tried something that seemed like it was working at first, but didn't get me anywhere. Here's what I did, considering only the case where $n$ is even:

Define $S := X_1 + X_2 + \cdots + X_n$. Then $\mathbb{E}(S) \geq n^2$. We have \begin{align*} n^2 \leq \mathbb{E}(S) &\leq \mathbb{P}(0 \leq S) + \mathbb{P}(1 \leq S) + \cdots + \mathbb{P}(4n^3 - 1 \leq S)\\ &= \left(\mathbb{P}(0 \leq S) + \cdots + \mathbb{P}(n^2/2 - 1 \leq S) \right) \\ &\qquad {}+ \left(\mathbb{P}(n^2/2 \leq S) + \cdots + \mathbb{P}(4n^3 - 1 \leq S) \right) \\ &= n^2 + (4n^3 - n^2/2)\mathbb{P}(n^2/2 \leq S) \end{align*} This yields $$\frac{1}{8n-1} \leq \mathbb{P}(n^2/2 \leq S)$$

Which is a pretty nice result, but isn't what the problem asks for. Any help would be greatly appreciated.

• Is is $4n^2$ or just $4n$ for the upper bound of the $X_i$ – user76844 Jan 12 '15 at 20:32
• $4n^2$, unfortunately. I think if it were $4n$ then the answer would pop out using second moment method in addition to Bhatia-Davis Inequality. – user165388 Jan 12 '15 at 20:37
• yep...that's what I was hoping :-\ – user76844 Jan 12 '15 at 20:49
• I think I found a counterexample to the theorem, see my answer. – user76844 Jan 16 '15 at 2:00

I am at a loss for an inequality that ends up being free of $n$. However, in my attempts I came up with what appears to be a counterexample to what you are trying to prove.

Assuming that $0\leq X_i\leq 4n^2$ is not a typo:

Let $\mu_n=E[S],p_n:=P(S\geq n^2/2), \;U:=E[S|S\geq n^2/2,\mu_n>n^2],\; L:=E[S|S<n^2/2,\mu_n>n^2]$

We know that: $E[S_n]=pU+(1-p)L\geq n^2$ for any distribution by simple linearity of expectation.

This implies:

$p_n\geq\frac{n^2-L}{U-L}:U\in[n^2,4n^3],L\in[0,n^2/2)$

If we try to minimize wrt $U,L$, the lower bound on $p_n$ is achieved when $U=4n^3,L\to n^2/2$

Thus (forcing $E[S]=n^2$, $U=4n^3$ and letting $L\to n^2/2$):

$p_n\to\frac{n^2}{8n^3-n^2}\xrightarrow{n\uparrow}0 \implies \exists(c,L,U):p_n<\frac{1}{20}\forall n>c$

Note that the above solution is consistent with the hypotheses of the theorem:

$H_1:E[X_i]=n\geq n$

$H_2:X_i \in [0,4n^2]$

...yet we've arrived at a solution that violates the theorem. It appears something is amiss with either the assumptions and/or the theorem.

In particular, it seems that $E[S]\geq n^2$ is not a strong enough constraint to ensure that the lowest possible probability is $\frac{1}{20}$.

Now, if $E[X_i]\geq n^2$, then you have something, since $E[S] \to 1/8 > 1/20$

• Wow, that's extremely solid. Thanks for taking the time to figure this out and writing it up. If I had to guess, I'd say that it's likely supposed to be $0 \leq X_i \leq 4n$ since the solution just pops out perfectly with those assumptions. Thanks again (and enjoy your well-earned bounty)! – user165388 Jan 18 '15 at 18:26
• @prrulz Thanks...and I totally agree...the second moment method works just too well with $X\leq 4n$ for that to be coincidence. – user76844 Jan 18 '15 at 18:32