5
$\begingroup$

I'm currently looking through the proof of this lemma and I am getting stuck at this (trivial!) stage of the proof and I was wondering if someone could help? I've written up the part of the proof that I am stuck on -

Lemma Let X, Y be random variables, let a be a real number and ε > 0. Then

$P(Y\leq{a})\leq P(X\leq a+\epsilon) + P(|Y-X|>\epsilon)$

Proof

$P(Y\leq{a})=P(Y\leq a, X\leq a +\epsilon) + P(Y\leq a, X> a +\epsilon)$

$\leq P(X\leq a +\epsilon) + P(Y-X\leq a-X, a-X< -\epsilon)$

$\leq P(X\leq a +\epsilon) + P(Y-X< -\epsilon)$

$\leq P(X\leq a +\epsilon) + P(Y-X< -\epsilon) + P(Y-X> \epsilon)$

$ = P(X\leq a+\epsilon) + P(|Y-X|>\epsilon)$

The proof seems to imply that $P(Y\leq a, X\leq a +\epsilon) \leq P(X\leq a +\epsilon)$

But I don't understand why this is true?

$\endgroup$
3
  • $\begingroup$ Hint: P(x<=a+ e) is computed over all the domain of y. Try to write both parts in terms of integral and double integrals then it might be more clearer. Sorry, I'm writing using my cell phone. $\endgroup$
    – user9292
    Jan 6, 2017 at 7:36
  • $\begingroup$ Nowhere did it say that X and Y were both continuous. $\endgroup$ Jan 6, 2017 at 7:45
  • $\begingroup$ This what I assume just to help him see the relation. $\endgroup$
    – user9292
    Jan 6, 2017 at 8:13

3 Answers 3

2
$\begingroup$

It's always a good idea to reduce such manipulations to the axioms of probability (and, if needed, simple algebra).

Begin by noting we can decompose the sample space $\Omega$ into the union of any event and its complement:

$$\Omega = \{|X-Y| \gt \epsilon\}\ \bigcup\ \{|X-Y| \le \epsilon\}.$$

This breaks the event $Y \le a$ into two disjoint parts,

$$\{Y \le a\} = \left(\{Y \le a\} \cap \{|X-Y| \gt \epsilon\}\right)\ \bigcup\ \left(\{Y \le a\} \cap\{|X-Y| \le \epsilon\}\right).\tag{1}$$

Because these parts are disjoint, their probabilities will add (that's an axiom). Let's tackle the evaluation of the probabilities separately.

Left hand side

Another axiomatic relationship is that the probability of a subset of an event is never greater than the probability of the event itself. This allows us to overestimate the left hand portion of $(1)$:

$$\Pr\left(\{Y \le a\} \cap \{|X-Y| \gt \epsilon\}\right)\le \Pr(|X-Y| \gt \epsilon).\tag{2}$$

This is intuitively clear.

Right hand side

The right hand portion is due to the algebraic fact that inequalities add:

$$Y \le a\text{ and } |X-Y|\le \epsilon\ \text{ implies }\ X= Y + (X-Y) \le a + \epsilon.$$

(This is readily deduced from the triangle inequality.)

Therefore the right side of $(1)$ is a subset of a simpler event $X \le a+\epsilon$. Once again this gives an inequality of probabilities

$$\Pr\left(\{Y \le a\} \cap\{|X-Y| \le \epsilon\}\right) \le \Pr\left(X \le a+\epsilon\right).\tag{3}$$

Intuitively, if $Y$ does not exceed $a$ and $X$ is within $\epsilon$ of $Y$, then $X$ cannot exceed $a+\epsilon$.

Solution

Taking probabilities in $(1)$ by means of the results $(2)$ and $(3)$ yields

$$\Pr(Y \le a) \le \Pr(|X-Y| \gt \epsilon) + \Pr\left(X \le a+\epsilon\right),$$

QED.

Putting this result in words might help the intuition:

The chance of $Y \le a$ cannot be greater than the chance that $X \le a+\epsilon$ (if $X$ is within $\epsilon$ of $Y$) plus the chance that $X$ is more than $\epsilon$ away from $Y$.

$\endgroup$
9
  • $\begingroup$ @whiber Okay you were more thorough so you get credit for that. When the OP concentrates on one issue it is hard to know what aspect of the proof is already clear to him and doesn't need comment. We all worked hard on P(A and B)<=P(B) because the OP gave us a hard time about it. You came in late and cleaned up. I gave you an upvote. I don't know if the OP even cares about your answer. But I know your feeling is that thorough answers are better for the community in general. $\endgroup$ Jan 6, 2017 at 17:53
  • $\begingroup$ I got no credit and I was the first to respond to the OPs main question. $\endgroup$ Jan 6, 2017 at 17:54
  • 2
    $\begingroup$ @Michael When a post is not very readable it's unlikely to get many upvotes. Allow me to give a little advice. First, learn how to apply MathJax markup. It's a useful skill and you can pick up the basics in minutes (by emulating and copying markup from other posts). Second, make a habit of explaining which part or parts of the question you intend to address. Always include a statement summarizing your post's contribution. Third, if there is any outstanding issue concerning what the question is asking, then try to resolve it (via comments) before posting an answer. $\endgroup$
    – whuber
    Jan 6, 2017 at 18:19
  • $\begingroup$ Does MathJax help me make my equations look better like Latex does? I don't know anything about it. Had I done what you suggest it is not clear that i would have gotten credit anyway. Of course people can still give me credit now. I don't think I am alone. ab90hi gave an answer without explaining that he was only answering part of the question. I think we both may have thought we were answering the question completely because we addressed everything the OP asked. $\endgroup$ Jan 6, 2017 at 18:28
  • 1
    $\begingroup$ Isn't the question asking about why $P(Y\leq a, X\leq a +\epsilon) \leq P(X\leq a +\epsilon)$ ? $\endgroup$ Jan 6, 2017 at 18:37
1
$\begingroup$

Let the us define the following events

$A = \{X \leq a+e\}$, $B = \{X \leq a+e,Y\leq a\}$, and $C = \{X \leq a+e,Y>a\} $

Now, \begin{equation} A = B \bigcup C \end{equation} \begin{equation} \implies B \subseteq A \implies P(B) \le P(A) \end{equation}

$\endgroup$
3
  • $\begingroup$ But this is the opposite of what I need to prove right? $\endgroup$ Jan 6, 2017 at 16:44
  • $\begingroup$ $A$ and $B$ appear to have switched in the last row ( $A=B\cup C$ implies $B\subseteq A$, not $A \subseteq B$) $\endgroup$ Jan 6, 2017 at 18:34
  • $\begingroup$ Yes, sorry about that. I have made the edit to correct it. $\endgroup$
    – ab90hi
    Jan 7, 2017 at 7:55
0
$\begingroup$

That part is easy as you suspect. Let the event A={X<=a+e) and B= {Y<=a} then you have P(A and B) <= P(A) simply because the event {A and B} is a subset of A.

$\endgroup$
7
  • $\begingroup$ But shouldn't the fact that they are two different random variables make a difference here? $\endgroup$ Jan 6, 2017 at 7:37
  • $\begingroup$ No They live on the same probability space. $\endgroup$ Jan 6, 2017 at 7:42
  • $\begingroup$ If you assume that x and y are independent, then p(y<=a, x<=a+e) = p(y<=a)p(x<=a+e). Then since probability <=1, the relation holds true. $\endgroup$
    – user9292
    Jan 6, 2017 at 7:44
  • 1
    $\begingroup$ But X and Y are not assumed to be independent and it is still true. There is no need to say P(A and B) = P(A) P(B) where A and B are as I defined in my answer. For any two events U and V if U is a subset of V P(U)<= P(V). $\endgroup$ Jan 6, 2017 at 7:50
  • $\begingroup$ This answer is suspect: why doesn't the event $|X-Y\gt \epsilon|$ ever enter into consideration? $\endgroup$
    – whuber
    Jan 6, 2017 at 16:59

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.