I have three independent nonnegative random variables $X_1$, $X_2$, and $X_3$, and I do not have their density functions, but I do have a decent upper bound for their cdfs. In other words, I have functions $G_1$, $G_2$, $G_3$ such that $\Pr(X_i\leq x) \leq G_i(x)$ for all $i$ and $x$. Each $G_i$ is of the form $G_i(x) = c_i x^{n_i}$. Is there any way at all that I could use these functions to bound the cdf of the sum, $\Pr(X_1+X_2+X_3\leq x)$, from above? This seems hopeless but I figured I'd give it a shot.

2$\begingroup$ Of course some things are possible. For example, the probability that the sum is greater than $x$ is at most the sum of the probabilities that the summands are greater than $x/3$. What types of bounds do you have on the CDFs and what type of bound do you want to get on the sum? $\endgroup$ – Douglas Zare Apr 11 '16 at 8:32

$\begingroup$ @DouglasZare: I just added a description of the $G_i$ functions. I'm looking for an upper bound of $\Pr(X_1+X_2+X_3\leq x)$. $\endgroup$ – Tom Solberg Apr 11 '16 at 16:02

$\begingroup$ I just realized this is really a question about stochastic dominance...I'm going to post a new question that phrases things better. $\endgroup$ – Tom Solberg Apr 11 '16 at 19:20
The obvious bound is $$\text{Pr}(X_1 + X_2 + X_3 \le x) \le \text{Pr}(X_1 \le x) \text{Pr}(X_2 \le x) \text{Pr}(X_3 \le x) \le G_1(x) G_2(x) G_3(x)$$ For something that might be slightly better, take $a_1, a_2, a_3 \ge 0$ with $a_1 + a_2 + a_3 \ge x$. Then $$\text{Pr}(X_1 + X_2 + X_3 \le x) \le G_1(a_1) G_2(x) G_3(x) + G_1(x) G_2(a_2) G_3(x) + G_1(x) G_2(x) G_3(a_3)$$ In any particular application, you might optimize this over $a_1, a_2, a_3$.
EDIT: Alternatively, take $b_1, b_2, b_3 \ge 0$ with $b_1 + b_2 \ge x$, $b_1 + b_3 \ge x$, $b_2 + b_3 \ge x$. Then $$ \text{Pr}(X_1 + X_2 + X_3 \le x) \le G_1(b_1) G_2(b_2) G_3(x) + G_1(b_1) G_2(x) G_3(b_3) + G_1(x) G_2(b_2) G_3(b_3)$$