1
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – axk Mar 20 '15 at 0:17
  • $\begingroup$ I agree, if the first bound w's in terms of (x,z), the same result would hold. Do you have any more questions, or would you like to accept the answer? $\endgroup$ – jlimahaverford Mar 20 '15 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.