Basic adaptive composition

Put $H_0=\{\ast \}$ and $H_i={\mathcal{Y}}_1\times \cdots \times {\mathcal{Y}}_i$. For fixed $D$ and $i$, define $T_i^D(h,B)={\int }_{{\mathcal{Y}}_i}{\mathbf{1}}_B(h,y)K_i(D,h,dy)$ for measurable $B\subseteq H_i$. By [F4], $B_h$ is measurable; taking sections preserves the whole space, complements, and countable disjoint unions, so $B\mapsto T_i^D(h,B)=K_i(D,h,B_h)$ is a probability measure by [F2]. By [F5], $h\mapsto T_i^D(h,B)$ is measurable, so $T_i^D$ is a probability kernel. Starting with the point mass on $H_0$, compose these kernels using [F7]–[F8] to obtain transcript laws ${\mu }_i^D$ with ${\mu }_i^D(B)={\int }_{H_{i-1}}{K}_i(D,h,B_h){\mu }_{i-1}^D(dh)$. Every transcript-event evaluation is measurable in the database because its sigma-algebra is the power set by [F1]. No choice is used in these finite compositions.

Write $E_i={\sum }_{j\le i}{\epsilon }_j$ and $D_i={\sum }_{j\le i}{\delta }_j$, with $E_0=D_0=0$. We prove by induction that ${\mu }_i^D(B)\le e^{E_i}{\mu }_i^{D^{\mathrm{\prime }}}(B)+D_i$ for every measurable $B\subseteq H_i$; it is equality at the one-point prefix $i=0$. Suppose it holds at $i-1$, fix an event $B\subseteq H_i$, and put $p(h)=K_i(D,h,B_h)$ and $q(h)=K_i(D^{\mathrm{\prime }},h,B_h)$. By [F2], [F4], and [F5], these are measurable and lie in $[0,1]$. The round-$i$ event inequality and $p\le 1$ imply $p(h)\le \min \{1,e^{{\epsilon }_i}q(h)\}+{\delta }_i$, because $\min \{1,x+{\delta }_i\}\le \min \{1,x\}+{\delta }_i$ for $x\ge 0$. Let $g(h)=\min \{1,e^{{\epsilon }_i}q(h)\}$; it is measurable and $[0,1]$-valued. Integrating first against ${\mu }_{i-1}^D$, applying [F6] to the induction hypothesis, then using $g\le e^{{\epsilon }_i}q$ and [F9] with $E_i=E_{i-1}+{\epsilon }_i$, gives ${\mu }_i^D(B)\le e^{E_{i-1}}{e}^{{\epsilon }_i}\int qd{\mu }_{i-1}^{D^{\mathrm{\prime }}}+D_{i-1}+{\delta }_i=e^{E_i}{\mu }_i^{D^{\mathrm{\prime }}}(B)+D_i$. The same argument with $D,D^{\mathrm{\prime }}$ interchanged proves the reverse ordered inequality. At $i=k$, [F1] gives the asserted differential-privacy guarantee.