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?

  • $\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


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.