Advanced adaptive composition on arbitrary measurable output spaces

Fix an ordered neighboring pair $D,D^{\mathrm{\prime }}$, and abbreviate the two round kernels by $K_i,L_i$. Let $H_0=\{\ast \}$ and $H_i=H_{i-1}\times Y_i$. For any probability $\lambda$ on $H_{i-1}$, the formula $(\lambda \otimes K_i)(B)=\int K_i(h,B_h)\lambda (dh)$ defines a probability on $H_i$: sections and their evaluations are measurable, and countable additivity follows by monotone convergence for disjoint sections. Its history marginal is $\lambda$. Starting at the point mass on $H_0$, finite recursion constructs the original prefix laws $P_i=P_{i-1}\otimes K_i$ and $Q_i=Q_{i-1}\otimes L_i$. Integrals of product-measurable nonnegative functions have the corresponding iterated-integral formula, first for indicators and then by [F2]. No countable-generation hypothesis enters this construction.

Set $T_0=P_0=Q_0$. Given $T_{i-1}$, form $R_i=T_{i-1}\otimes K_i$ and $S_i=T_{i-1}\otimes L_i$. Apply [F3] with history law $T_{i-1}$ to obtain a probability $T_i$ on $H_i$ with marginal $T_{i-1}$, $S_i\mathrm{/}a\le T_i\le a{S}_i$, and $\mathrm{TV}(R_i,T_i)\le \delta$, where $a=\exp (\epsilon )\ge 1$ by [F9]. The hypotheses hold at every history, hence also under the modified history law. These are measures only; no conditional kernel for $T_i$ is required. Finite iteration yields consistent prefix marginals of the final probability $T_k$. Moreover [F5], applied to $h\mapsto K_i(h,B_h)\in [0,1]$, gives $\mathrm{TV}(P_i,R_i)\le \mathrm{TV}(P_{i-1},T_{i-1})$. Thus the triangle inequality and induction give $\mathrm{TV}(P_i,T_i)\le i\delta$.

By [A1] choose a product-measurable density $r_i=d{T}_i\mathrm{/}d{S}_i$. The measure bounds in step 2.1 force $a^{-1}\le r_i\le a$ almost everywhere, since otherwise a level set separated from one bound contradicts that bound after integration. Clip the representative into this positive interval everywhere. Write $Z_i={\prod }_{j\le i}{r}_j$ as a function on $H_i$, with $Z_0=1$. We prove $d{T}_i\mathrm{/}d{Q}_i=Z_i$ by induction. If $d{T}_{i-1}\mathrm{/}d{Q}_{i-1}=Z_{i-1}$, then for any nonnegative measurable $g$ on $H_i$, [F2] and [F4] give $\int gd{T}_i=\int g{r}_{i}d{S}_i=\int T_{i-1}(dh)\int g(h,y)r_i(h,y)L_i(h,dy)=\int Q_{i-1}(dh)Z_{i-1}(h)\int g(h,y)r_i(h,y)L_i(h,dy)=\int g{Z}_{i-1}{r}_{i}d{Q}_i$. The base is the common point mass. Hence $Z_i$ is the asserted density and is everywhere positive and finite. In particular $\log Z_k={\sum }_i{X}_i$ for the measurable prefix variables $X_i=\log r_i$, each in $[-\epsilon ,\epsilon ]$.

Define measurable functions on $H_{i-1}$ by $u_i(h)=\int r_i(h,y)L_i(h,dy)$ and $m_i(h)=\int r_i(h,y)\log r_i(h,y)L_i(h,dy)$. They are finite by the bounds in step 3.1. Because $T_i$ and $S_i$ have the same history marginal $T_{i-1}$, their density identity on $C\times Y_i$ gives ${\int }_C{u}_{i}d{T}_{i-1}=T_{i-1}(C)$ for every $C$, so $u_i=1$ almost everywhere under $T_{i-1}$. On this conull set, $\log r_i\le r_i-1$ gives $\int \log r_{i}d{L}_i\le 0$. Therefore $m_i\le \int (r_i-1)\log r_{i}d{L}_i\le \epsilon \int \mathrm{\mid }{r}_i-1\mathrm{\mid }d{L}_i$. For every $a^{-1}\le r\le a$, $\mathrm{\mid }r-1\mathrm{\mid }\le (a-1)\min \{r,1\}$, by separately checking $r\ge 1$ and $r\le 1$. Thus $m_i\le \epsilon (a-1)=:b$ almost everywhere. This scalar conditional calculation supplies the entropy bound without a fiberwise RN identity.

Work on $(H_k,T_k)$ with the filtration ${\mathcal{F}}_i$ generated by the first $i$ coordinates. For any measurable history event $C$, consistency of marginals, the density identity for $T_i$ relative to $S_i$, and the iterated-integral formula give ${\int }_{\{H_{i-1}\in C\}}{X}_{i}d{T}_k={\int }_C{m}_i(h)T_{i-1}(dh)$. Hence $m_i(H_{i-1})$ is a version of ${\mathbb{E}}_{T_k}[X_i\mid {\mathcal{F}}_{i-1}]$ by [F6]. It is bounded, as are the $X_i$, so $M_j={\sum }_{i\le j}(X_i-m_i(H_{i-1}))$ is an integrable martingale. Its $i$th increment lies in the ${\mathcal{F}}_{i-1}$-measurable interval $[-\epsilon -m_i,\epsilon -m_i]$, whose length is $2\epsilon$.

If $\epsilon =0$, all $r_i=1$, so $T_k=Q_k$ and the desired one-sided bound follows from step 2.1 with error $k\delta$. If $\epsilon >0$, put $t=\epsilon \sqrt{2k\ln (1\mathrm{/}{\delta }^{\mathrm{\prime }})}>0$. Applying [F7] with interval lengths $2\epsilon$ gives $T_k(M_k\ge t)\le \exp (-t^2\mathrm{/}(2k{\epsilon }^2))={\delta }^{\mathrm{\prime }}$. Step 4.1 bounds ${\sum }_i{m}_i\le kb$, so $T_k(\log Z_k>kb+t)\le {\delta }^{\mathrm{\prime }}$. Set ${\epsilon }^{\mathrm{\prime }}=kb+t$. For every transcript event $B$, split at $\log Z_k\le {\epsilon }^{\mathrm{\prime }}$ and use the density from step 3.1 to obtain $T_k(B)\le e^{{\epsilon }^{\mathrm{\prime }}}{Q}_k(B)+{\delta }^{\mathrm{\prime }}$. Then step 2.1 gives $P_k(B)\le e^{{\epsilon }^{\mathrm{\prime }}}{Q}_k(B)+k\delta +{\delta }^{\mathrm{\prime }}$.

The preceding construction applies to every ordered neighboring pair. In particular repeat it with $D,D^{\mathrm{\prime }}$ interchanged, constructing a new modified measure on that side, to get $Q_k(B)\le e^{{\epsilon }^{\mathrm{\prime }}}{P}_k(B)+k\delta +{\delta }^{\mathrm{\prime }}$. This proves differential privacy by [F1]. The proof includes $k=1$, $\delta =0$, and equality $k\delta +{\delta }^{\mathrm{\prime }}=1$; $0<{\delta }^{\mathrm{\prime }}<1$ makes the logarithm finite and positive. All database event evaluations are measurable by the power-set database convention in [F1]. No modified law, density, or exceptional set needs to be selected measurably in the database pair: the event inequality has been proved for each pair separately.