0
$\begingroup$

I read the following lemma in one of the recent engineering publications, and I hope someone can help me understand this Lemma. The lemma as stated in the paper is:

Lemma 1 (Difference Lemma). Let R1, R2 and R3 represent the events defined in some probability distribution. If R1 ^ -R3 <=> R2 ^ -R3 , we have |Pr[R1] - Pr[R2]| <= Pr[R3].

I was able to read it as, If R1 AND (NOT R3) if and only if R2 AND (NOT R#), the probability of event R1 minus the probability of R2 is less or equal the probability of R3.

But I don't understand it. How is the event R1 and NOT R3 if and only if event R2 and NOT R3 leads to probability of R1-R2 is less than probability of R3?

$\endgroup$
7
  • $\begingroup$ Intuitively (think of a Venn diagram in the sample space): If outside of $R3$, $R1$ and $R2$ are equivalent, then they can only be inequivalent inside $R3$, so their maximum possible inequivalence is bounded by the size of $R3$. $\endgroup$
    – Steve Kass
    Jul 5, 2020 at 19:56
  • $\begingroup$ Do you mean the first part says R1 and R2 are equivalent? but why the difference in their probability is less than probability of R3? $\endgroup$
    – Mona
    Jul 5, 2020 at 20:07
  • $\begingroup$ The first part says that $R1$ and $R2$ are equivalent when $R3$ is false. So the difference in their probabilities is only when $R3$ is true, so the difference between $p(R1)$ and $p(R2)$ is bounded by the probability of $R3$ $\endgroup$
    – Steve Kass
    Jul 5, 2020 at 20:18
  • $\begingroup$ So if R3 is false, then R1 and R2 are equivalent, then the p(R1)-p(R2) should be equal to zero. Is this correct? Also, if R3 is true, then why the p(R1)-p(R2) is <= p(R3) ? $\endgroup$
    – Mona
    Jul 5, 2020 at 20:38
  • $\begingroup$ I’m trying to give intuition. Draw a Venn diagram. The portions of $R1$ and $R2$ that lie outside of $R3$ have equal area. So the difference in areas of (all of) $R1$ and $R2$ is entirely due to how much they differ inside $R3$. Two things within $R3$ can’t differ in size by more that the size of $R3$. $\endgroup$
    – Steve Kass
    Jul 5, 2020 at 20:46

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.