Lemma KL-Divergence (Differential Privacy)

Question

I am studying differential privacy and I got stuck again in proof of a lemma. Which is:

• $D_{\infty}^\delta(Y||Z) \leq \epsilon$ if and only if there exists a random variable $Y'$ such that $\Delta(Y,Y') \leq \delta$ and $D_\infty(Y||Z) \leq \epsilon $.

I have a problem understanding the reverse proof.

Definitions:

Be $Y, Z$ two random variables.

1. $\Delta (Y,Z) \overset{def}{=} \underset{S}{max} \ \ \ | \Pr[Y\in S]-\Pr[Z\in S]|$
2. $D_{\infty}(Y||Z)=\underset{S\subseteq Supp(Y)}{max}\Big[ln\frac{\Pr[Y\in S]}{\Pr[Z \in S]}\Big]$, which is the KL-Divergence between two distributions $Y,Z$
3. $D_{\infty}^\delta(Y||Z)=\underset{S\subseteq Supp(Y):\Pr[Y\in S]\geq \delta}{max}\Big[ln\frac{\Pr[Y\in S]-\delta}{\Pr[Z \in S]}\Big]$

Proof:

Suppose that $D_{\infty}^\delta(Y||Z) \leq \epsilon$. Sea $S=\{y:\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y]\}$. Then

\begin{equation*} \sum_{y \in S}(\Pr[Y=y]-e^\epsilon \cdot \Pr[Z=y]) = \Pr[Y \in S]-e^\epsilon \cdot \Pr[Z \in S] \leq \delta \end{equation*}

(I understand until here)

Moreover, if we let $T=\{y:\Pr[Y=y] \leq \Pr[Z=y]\}$, then :

\begin{equation*} \begin{split} \sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) &= \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y]) \ \ \ \text{//I got stuck here} \\ & \geq \sum _{y \in S}(\Pr[Y=y]-\Pr[Z=Y])\\ & \geq \sum _{y \in S}(\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y]) \end{split} \end{equation*}

I don't' understand why: $$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y])$$

Thus we can obtain $Y'$ from $Y$ by lowering the probabilities on $S$ and raising the probabilities on $T$ To satisfy:

1. For all $y\in S$, $\Pr[Y'=y]=e^\epsilon \cdot \Pr[Z=y] < \Pr[Y=y]]$
2. For all $y \in T$, $\Pr[Y=y]\leq \Pr[Y'=y]\leq \Pr[Z=y]$
3. For all $y\notin S \cup T$, $\Pr[Y'=y]=\Pr[Y=y] \leq e^{\epsilon} \cdot \Pr[Z=y]$

Then $D_{\infty}^\delta(Y'||Z) \leq \epsilon$ by inspection

Reference: Dwork, C. & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, page 45.

Answer 1

I don't understand why:

$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=y])$$

Well the domain is partitioned into $T$ and its complement. So the sum over the full domain of the difference of the two probability distributions is zero.

$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) +\sum _{y \notin T}(\Pr[Z=y]-\Pr[Y=y])=0,$$ but now you can just move the second term to the right hand side and get the claimed equation.