Differential privacy inequality for bounded measurable functions

For each integer $m\ge 0$, put $n=2^m$ and define $g_m=\frac{1}{n}{\sum }_{j=1}^n{\mathbf{1}}_{\{g\ge j\mathrm{/}n\}}$. Each $g_m$ is a measurable simple function and $0\le g_m\le g$. Every level $j\mathrm{/}n$ counted at stage $m$ contributes the two levels $(2j-1)\mathrm{/}(2n)$ and $2j\mathrm{/}(2n)$ at stage $m+1$, so $g_{m+1}\ge g_m$. The largest dyadic level not exceeding any fixed $g(x)$ differs from $g(x)$ by less than $2^{-m}$, so $g_m(x)\uparrow g(x)$.

Apply the given event inequality to the $n$ level sets in step 1.1 and use [F3] on disjoint simple representations. Partition the range into $B_k=\{k\mathrm{/}n\le g<(k+1)\mathrm{/}n\}$ for $0\le k<n$ and $B_n=\{g=1\}$. Then $g_m={\sum }_{k=1}^{n-1}(k\mathrm{/}n){\mathbf{1}}_{B_k}+{\mathbf{1}}_{B_n}$, while each level set $\{g\ge j\mathrm{/}n\}$ is the disjoint union of $B_j,\dots ,B_n$. Rearranging these finite sums gives $\int g_{m}dP=\frac{1}{n}{\sum }_{j=1}^{n}P(g\ge j\mathrm{/}n)\le \frac{1}{n}{\sum }_{j=1}^n(e^{\epsilon }Q(g\ge j\mathrm{/}n)+\delta )=e^{\epsilon }\int g_{m}dQ+\delta$. This holds for every $m$.

Let $m\to \mathrm{\infty }$ in step 2.1. By [F4] and step 1.1, both nonnegative integrals converge to the corresponding integrals of $g$, so $\int gdP\le e^{\epsilon }\int gdQ+\delta$.