that ${\mathcal{D}}_k$ is well-defined and consider a sample $S$ drawn from ${\mathcal{D}}_k$. The size of $S$ is $\lvert S\rvert = k\cdot(n + 1)$. Among these $k\cdot(n+1)$ examples there are $k\cdot n$ examples drawn from ${\mathcal{D}}$ and $k$ examples which are generated in Item 3(iv). We will refer to these $k$ examples as . Note that during the generation of $S\sim {\mathcal{D}}_k$ there are examples drawn from ${\mathcal{D}}$ which do not actually appear in $S$. In fact, the number of such examples may be unbounded, depending on how many times Items 3(i)-3(iii) were repeated. In Section \[sec:monte\] we will define a “Monte-Carlo” variant of ${\mathcal{D}}_k$ in which the number of examples drawn from ${\mathcal{D}}$ is always bounded. This Monte-Carlo variant is what we actually use to define our globally-stable learning algorithm, but we introduce the simpler distributions ${\mathcal{D}}_k$ to clarify our analysis.

The $k$ tournament examples satisfy the following important properties.

\[obs:mistakebound\] Let $k$ be such that ${\mathcal{D}}_k$ is well-defined and consider running the ${\mathsf{SOA}}$ on the concatenated sample $S\circ T$, where $S\sim {\mathcal{D}}_k$ and $T\sim {\mathcal{D}}^n$. Then

1.  Each tournament example forces a mistake on the ${\mathsf{SOA}}$. Consequently, the number of mistakes made by the ${\mathsf{SOA}}$ when run on $S\circ 