# Difference Lemma and the probability of three events

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?

• 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$. Jul 5, 2020 at 19:56
• 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?
– Mona
Jul 5, 2020 at 20:07
• 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$ Jul 5, 2020 at 20:18
• 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) ?
– Mona
Jul 5, 2020 at 20:38
• 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$. Jul 5, 2020 at 20:46