# How to combine probability inequalities that are w.r.t. different random variables?

Let $x$ and $z$ be two independent random variables. Suppose I know the following two facts:

$P_z[f(x,z) < g(x)] > 1-\delta$ uniformly for all x;

$P_x[g(x) < h(x)] > 1-\delta_h$

How can I combine these to say something about $P_x[f(x,z) < h(x)] > 1-?$ with high probability ($1-\delta$) w.r.t. $z$?

You can rephrase both of these conditions in terms of the joint distribution $P(x,y)$. The first is more tricky and required the independence assumption. The second is trivial since it does not depend on $z$. Once, you have this you know that they're both true with measure at least $$(1-\delta-\delta_h).$$ Then you should be able to get the condition you desired, with any $(1-\delta-\delta_h)$ in place of both values at the end. If you would like me to clarify or solve it fully I will do that later. Just ask!
• Thanks! I see - so we get that $P_{x,z}[f(x,z)<h(x)] >1-\delta-\delta_h$, which is a bound on the expectation $E_z[P_{x}[f(x,z)<h(x)]]$. I think we didn't need that the first inequality holds uniformly is that? – axk Mar 20 '15 at 0:17