sample obtained by appending $T$ to the end of $S$. Define a sequence of distributions ${\mathcal{D}}_k$ for $k\geq 0$ as follows:

[**Distributions ${\mathcal{D}}_k$**]{}\

Let $n$ denote an “auxiliary sample” size (to be fixed later) and let ${\mathcal{D}}$ denote the target realizable distribution over examples. The distributions ${\mathcal{D}}_k = {\mathcal{D}}_k({\mathcal{D}},n)$ are defined by induction on $k$ as follows:

1.  ${\mathcal{D}}_0$: output the empty sample $\emptyset$ with probability 1.

2.  Let $ k\ge 1 $. If there exists a $f$ such that $$\Pr_{S \sim {\mathcal{D}}_{k-1}, T\sim{\mathcal{D}}^n}[{\mathsf{SOA}}(S\circ T) = f] \geq 2^{-d},$$ or if ${\mathcal{D}}_{k-1}$ is undefined then ${\mathcal{D}}_k$ is undefined.

3.  Else, ${\mathcal{D}}_k$ is defined recursively by the following process:

    -   Draw $S_0,S_1\sim {\mathcal{D}}_{k-1}$ and $T_0,T_1\sim{\mathcal{D}}^n$ independently.

    -   Let $f_0={\mathsf{SOA}}(S_0\circ T_0)$, $f_1={\mathsf{SOA}}(S_1\circ T_1)$.

    -   If $f_0=f_1$ then go back to step (i).

    -   Else, pick $x\in \{x: f_0(x)\neq f_1(x)\}$ and sample $y\sim\{\pm 1\}$ uniformly.

    -   If $f_0(x)\neq y$ then output $S_0 \circ T_0\circ \bigl((x,y)\bigr)$ and else output $S_1\circ T_1\circ \bigl((x,y)\bigr)$.

Please see Figure \[fig:Dk\] for an illustration of sampling $S\sim {\mathcal{D}}_k$ for $k=3$.

We next observe some basic facts regarding these distributions. First, note that whenever ${\mathcal{D}}_k$ is well-defined, the process in Item 3 terminates with probability 1.

Let $k$ be such 