Pure differential privacy bounds relative entropy

The standard-Borel hypotheses are explicit as required by [F1]. Since $P(A)\le aQ(A)$ for every measurable $A$, $P\ll Q$. Choose a Radon–Nikodym density $r=dP\mathrm{/}dQ$ using [A1] and [F2].

By [F6], $a=e^{\epsilon }\ge 1$ and $a^{-1}>0$. The inequality $P(A)\le aQ(A)$ forces $r\le a$ $Q$-almost everywhere: otherwise some set $E_n=\{r\ge a+1\mathrm{/}n\}$ has positive $Q$-measure and violates the inequality after integration. Similarly $Q(A)\le aP(A)=a{\int }_{A}rdQ$ forces $r\ge a^{-1}$ $Q$-almost everywhere, since any positive-measure set where $r\le a^{-1}-1\mathrm{/}n$ violates that inequality. Thus $a^{-1}\le r\le a$ almost everywhere.

Let $E=\{r\ge 1\}$, $p=P(E)$, $q=Q(E)$, and $t=p-q$. Since $P(A)-Q(A)={\int }_A(r-1)dQ$, the set $E$ maximizes this difference and $E^c$ gives its negative. Hence $t={\sup }_A\mathrm{\mid }P(A)-Q(A)\mathrm{\mid }=\frac{1}{2}\int \mathrm{\mid }r-1\mathrm{\mid }dQ$. The event inequalities on $E$ and $E^c$ give $t\le (a-1)q$ and $at\le (a-1)(1-q)$, respectively. Adding yields $(a+1)t\le a-1$, so $t\le (a-1)\mathrm{/}(a+1)$.

The lower bound in step 2.1 makes $P$ and $Q$ equivalent. Define $s=1\mathrm{/}r$ on $\{r>0\}$ and $s=0$ on its null complement; [F7] makes it measurable. By [F3], ${\int }_{A}sdP={\int }_{A}srdQ=Q(A)$ for every measurable $A$, so $s=dQ\mathrm{/}dP$. The logarithm reciprocal identity in [F6] gives $\log s=-\log r$ almost everywhere, and both log densities are bounded in absolute value by $\epsilon$; [F4] therefore gives finite divergences and $D(P\mathrm{\parallel }Q)+D(Q\mathrm{\parallel }P)=\int (r-1)\log rdQ\le \epsilon \int \mathrm{\mid }r-1\mathrm{\mid }dQ=2\epsilon t$. By [F5], $D(Q\mathrm{\parallel }P)\ge 0$, and step 3.1 gives $2\epsilon t\le 2\epsilon (a-1)\mathrm{/}(a+1)\le \epsilon (a-1)$. Therefore $D(P\mathrm{\parallel }Q)\le \epsilon (a-1)=\epsilon (e^{\epsilon }-1)$.