# Probability inequality for sum of non-negative independent random variables

Suppose $$X_i$$, $$i \in \mathbb{N}$$ are independent binary random variables with $$P(X_i = 1) = p_i = 1-P(X_i = 0)$$ and define $$S_n \equiv \sum_{i=1}^n X_i$$. I want to prove that for every $$x > 0$$, we have $$P(S_n \ge x) \leq \left(\frac{\mu e}{x}\right)^x$$

I can do this for $$x \in (0,1]$$ by noting that the function $$f(y) \equiv y^x, y \ge 0$$ is concave for $$x$$ in this range, hence we have $$P(S_n \ge x) \leq P(eS_n \ge x) \leq P(e^x S_n^x \ge x^x) \leq \frac{e^x E(S_n^x)}{x^x}\leq \frac{e^x E(S_n)^x}{x^x} = \left(\frac{\mu e}{x} \right)^x$$

where we apply Jensen's inequality to get the last inequality. I am lost about trying to get this right for $$x > 1$$. We can't apply Jensen's again because the function $$f(y)$$ is now convex on $$x \in (1, \infty)$$ so we need a different strategy entirely. I'm not sure if this is the right idea, but we can write down an expression for the probability exactly as being $$P(S_n \ge x) = \sum_{J \subseteq \{1, ... n\}, |J| \ge x} \prod_{i \in J} p_i \prod_{i \not \in J} (1-p_i)$$ I can't see anything fruitful from this though. Any help would be much appreciated!

• If I were given this problem, I would start with the binomial formula. Perhaps use simpler versions of Stirling's formula. Aug 16, 2020 at 21:49
• Incidentally, the only way $S_n < 1$ is if $S_n = 0$. So the inequality for $x \in (0,1)$ isn't that useful. Aug 16, 2020 at 21:50
• How would we apply the binomial formula or Stirling's formula when the $p_i$ may vary with $i$? We are not simply choosing the ceiling of $x$ out of the $n$ $X_i's$ to be equal to $1$. Perhaps I'm misinterpreting what you're suggesting Aug 16, 2020 at 21:59
• No, it was my mistake. I didn't see that the $p_i$ are changing. Aug 16, 2020 at 22:00
• Using your approach, it does seem to me that you could show $P(S_n \ge m) \le \sum_{k=m}^\infty \frac{\mu^k}{k!}$. This gives a nice upper bound, but not the one you want. Aug 16, 2020 at 22:27

Suppose $$x > \mu$$, because if $$x \le \mu$$, then the right hand side is bigger than $$1$$.
For any $$\theta > 0$$, we have $$P(S \ge x) = P(\exp(\theta(S-x)) \ge 1) \le E(\exp(\theta(S-x))) = e^{-\theta x} \prod_k E(\exp(\theta X_k)) .$$ Now $$E(\exp(\theta X_k)) = 1-p_k + p_k e^{\theta} \le \exp((e^{\theta} - 1) p_k ) .$$ So $$P(S \ge x) \le \exp(-\theta x + (e^\theta -1) \mu ) \le \exp(-\theta x + e^\theta \mu ) .$$ Set $$\theta = \log (x/\mu)$$.