\documentclass[twoside,11pt]{article}                   % JMLR
\usepackage{jmlr2eVV,amsmath,amsfonts}         % JMLR
\usepackage{amsmath,amsfonts,stmaryrd,epsfig}          % OCM WP3
\emergencystretch=5mm
\tolerance=400

%\setcounter{tocdepth}{1}               % OCM WP 3

%\newcommand{\coefficient}{0.7}         % OCM WP3
\newcommand{\coefficient}{0.73}         % JMLR

\newcommand{\Vladimir}{Vladimir}
\newcommand{\DOT}{.}

%\input{OT2enc.def}                                                             % OCM WP3
%\newenvironment{cyr}                                                           % OCM WP3
%{\fontencoding{OT2}\fontfamily{wncyr}\fontseries{m}\fontshape{n}\selectfont}   % OCM WP3
%{\fontencoding{OT1}\fontfamily{tir}\selectfont}                                % OCM WP3

\newcommand{\iid}{i.i.d.\ }
\newcommand{\as}{\textrm{-a.s.}}

\newcommand{\st}{\mathop{:}}
\newcommand{\givn}{\mathop{|}}
\newcommand{\binmax}{\mathbin{\vee}}
\newcommand{\Err}{\mathop{{\rm Err}}\nolimits}
\newcommand{\err}{\mathop{{\rm err}}\nolimits}
\newcommand{\Unc}{\mathop{{\rm Unc}}\nolimits}
\newcommand{\unc}{\mathop{{\rm unc}}\nolimits}
\newcommand{\Emp}{\mathop{{\rm Emp}}\nolimits}
\newcommand{\emp}{\mathop{{\rm emp}}\nolimits}
\newcommand{\ErrOver}{\mathop{\overline{\mathstrut\rm Err}}\nolimits}
\newcommand{\errOver}{\mathop{\overline{\rm err}}\nolimits}
\newcommand{\UncOver}{\mathop{\overline{\mathstrut\rm Unc}}\nolimits}
\newcommand{\uncOver}{\mathop{\overline{\rm unc}}\nolimits}
\newcommand{\EmpOver}{\mathop{\overline{\mathstrut\rm Emp}}\nolimits}
\newcommand{\empOver}{\mathop{\overline{\rm emp}}\nolimits}

\newcommand{\bbbr}{{\mathbb{R}}}                % OCM WP3: the real numbers
\newcommand{\bbbp}{{\mathbb{P}}}                % OCM WP3: the underlying probability distribution
\newcommand{\Prob}{\mathop{\bbbp}\nolimits}
\newcommand{\bbbe}{{\mathbb{E}}}                % expected value
\newcommand{\Expect}{\mathop{\bbbe}\nolimits}
\newcommand{\III}{{\mathbb{I}}}                 % indicator

\newcommand{\FFF}{{\mathcal{F}}}                % the underlying sigma-algebra
\newcommand{\GGG}{{\mathcal{G}}}                % generic sigma-algebra
\newcommand{\LLL}{{\mathcal{L}}}                % generic martingale
\newcommand{\NNN}{{\mathcal{N}}}                % the upper tail of the standard normal distribution
\newcommand{\PPP}{{\mathcal{P}}}                % only used in the wrong part

%\newtheorem{theorem}{Theorem}                                  % OCM WP3
%\newtheorem{proposition}{Proposition}                          % OCM WP3
%\newtheorem{lemma}{Lemma}                                      % OCM WP3
%\newtheorem{corollary}{Corollary}                              % OCM WP3
%\newenvironment{remark}                                        % OCM WP3
%  {\trivlist\item[\hskip\labelsep\textbf{Remark}]}             % OCM WP3
%  {\endtrivlist}                                               % OCM WP3
%\newenvironment{proof}                                         % OCM WP3
%  {\trivlist\item[\hskip\labelsep\textbf{Proof}]}              % OCM WP3
%  {\endtrivlist}                                               % OCM WP3
%\newenvironment{proofsketch}                                   % OCM WP3
%  {\trivlist\item[\hskip\labelsep\textbf{Proof sketch}]}       % OCM WP3
%  {\endtrivlist}                                               % OCM WP3
%\newenvironment{Proof}[1]                                      % OCM WP3
%  {\trivlist\item[\hskip\labelsep\textbf{Proof #1}]}           % OCM WP3
%  {\endtrivlist}                                               % OCM WP3
%\newcommand{\boxforqed}{\rule{.3em}{1.5ex}}                    % OCM WP3
%\newcommand{\qedtext}{\unskip\nobreak\hfil                     % OCM WP3
%  \penalty50\hskip1em\null\nobreak\hfil\boxforqed              % OCM WP3
%  \parfillskip=0pt\finalhyphendemerits=0\endgraf}              % OCM WP3
%\newcommand{\qedmath}{\eqno\boxforqed}                         % OCM WP3

%\newenvironment{theorem*}[1]
%  {\trivlist \item[\hskip \labelsep{\bfseries #1}]\itshape}
%  {\endtrivlist}

\newlength{\IndentI}
\newlength{\IndentII}
\newlength{\IndentIII}
\newlength{\IndentIV}
\setlength{\IndentI}{1cm}
\setlength{\IndentII}{2cm}
\setlength{\IndentIII}{3cm}
\setlength{\IndentIV}{4cm}
\newlength{\WidthI}
\newlength{\WidthII}
\newlength{\WidthIII}
\newlength{\WidthIV}
\setlength{\WidthI}{\textwidth}
\setlength{\WidthII}{\textwidth}
\setlength{\WidthIII}{\textwidth}
\setlength{\WidthIV}{\textwidth}
\addtolength{\WidthI}{-\IndentI}
\addtolength{\WidthII}{-\IndentII}
\addtolength{\WidthIII}{-\IndentIII}
\addtolength{\WidthIV}{-\IndentIV}

%\title{A Universal Well-Calibrated Algorithm\\for On-line Classification}        % OCM WP3
%\author{Vladimir Vovk}                                                         % OCM WP3
\title{A Universal Well-Calibrated Algorithm\\for On-line Classification}
\author{\name Vladimir Vovk \email vovk@cs.rhul.ac.uk\\
        \addr Computer Learning Research Centre\\
%       Department of Computer Science\\
        Royal Holloway, University of London\\
        Egham, Surrey TW20 0EX, UK}

\editor{Kristin Bennett and Nicol\`o Cesa-Bianchi}

%\newcommand{\No}{3}                                    % OCM WP3
%\date{November 7, 2002}                                % OCM WP3

% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

\jmlrheading{5}{2004}{575-604}{1/04}{6/04}{Vladimir Vovk}

% Short headings should be running head and authors last names

\ShortHeadings{Universal Well-Calibrated Classification}{Vovk}
\firstpageno{575}

\begin{document}
\maketitle
\begin{abstract}%
  We study the problem of on-line classification in which the
  prediction algorithm, for each ``significance level'' $\delta$, is
  required to output as its prediction a range of labels (intuitively,
  those labels deemed compatible with the available data at the level
  $\delta$) 
rather than just one label; as usual, the examples are
  assumed to be generated independently from the same probability
  distribution $P$.  The prediction algorithm is said to be
  ``well-calibrated'' for $P$ and $\delta$ if the long-run relative
  frequency of errors does not exceed $\delta$ almost surely w.r.\ to
  $P$.  For well-calibrated algorithms we take the number of
  ``uncertain'' predictions (i.e., those containing more than one
  label) as the principal measure of predictive performance.  The main
  result of this paper is the construction of a prediction algorithm
  which, for any (unknown) $P$ and any $\delta$: (a) makes errors
  independently and with probability $\delta$ at every trial (in
  particular, is well-calibrated for $P$ and $\delta$); (b) makes in
  the long run no more uncertain predictions than any other prediction
  algorithm that is well-calibrated for $P$ and $\delta$; (c)
  processes example $n$ in time $O(\log n)$.
\end{abstract}


\begin{keywords}
  Transductive Confidence Machine, on-line prediction
\end{keywords}

\section{Introduction}\label{sec:introduction}

Typical machine learning algorithms output a point prediction
for the label of an unknown object.
This paper continues study of an algorithm
called the Transductive Confidence Machine (TCM),
introduced by \cite{saunders/etal:1999} and \cite{vovk/etal:1999},
that complements its predictions with some measures of confidence.
There are different ways of presenting TCM's output;
in this paper \citep[as in the related][]{vovk:2002FOCSforJMLR,vovk:2002ALTforJMLR}    % JMLR
%in this paper (as in the related~\cite{OCM1,OCM2})                                     % OCM WP3
we use TCM as a ``region predictor'',
in the sense that it outputs a nested family of prediction regions
(indexed by the significance level $\delta$)
rather than a point prediction.

Any TCM is well-calibrated when used in the on-line mode: for any
significance level $\delta$ the long-run relative frequency of
erroneous predictions does not exceed $\delta$.  What makes this
feature of TCM especially appealing is that it is far from being just
an asymptotic phenomenon: a slight modification of TCM called
randomized\footnote{Randomization is needed to break ties and deal
  efficiently with borderline cases.} TCM (rTCM) makes errors
independently at different trials and with probability $\delta$ at
each trial. The property of being well-calibrated then immediately
follows by the Borel strong law of large numbers.
Figure~\ref{fig:TCM_ERR} shows the cumulative numbers of errors at the
significance levels 1\%--5\% made on the well-known USPS data set of
hand-written digits (randomly permuted); as expected, these are
straight lines with the slope approximately equal to the significance
level.  For proofs and further information, see
%\cite{OCM1}.                                                           % OCM WP3
\cite{vovk:2002FOCSforJMLR}.                                           % JMLR

\begin{figure}[tb]
\centerline{\psfig{file=TCM0err.eps,width=\coefficient\textwidth}}
  \caption{TCM's cumulative errors at the significance levels 1\%--5\% on the USPS data set%
  \label{fig:TCM_ERR}}
\end{figure}

The justification of the study of TCM given
by~\cite{vovk:2002FOCSforJMLR}                                         % JMLR
%in~\cite{OCM1}                                                         % OCM WP3
was its good performance on real-world and standard benchmark data sets.
For example, Figure~\ref{fig:TCM_UNC} shows
that for the significance levels between 1\% and 5\% most examples
in the USPS data set can be predicted categorically
(by a simple 1-Nearest Neighbour TCM, used in all experiments reported in this paper):
the prediction region contains only one label.

\begin{figure}[tb]
\centerline{\psfig{file=TCM0unc.eps,width=\coefficient\textwidth}}
  \caption{Cumulative number of ``uncertain'' predictions
    (i.e., prediction regions containing more than one label)
    made by the 1-Nearest Neighbour TCM
    at the significance levels 1\%--5\% on the USPS data set%
  \label{fig:TCM_UNC}}
\end{figure}

This paper presents theoretical results about TCM's performance
in the problem of classification,
where the number of possible labels is finite;
we show that there exists a \emph{universal} rTCM, which,
for any significance level $\delta$ and
without knowing the true distribution $P$ generating the examples:
\begin{itemize}
\item
  produces, asymptotically, no more uncertain predictions
  than any other prediction algorithm that is well-calibrated for $P$ and $\delta$;
\item
  produces, asymptotically, at least as many empty predictions
  as any other prediction algorithm that is well-calibrated for $P$ and $\delta$
  and whose percentage of uncertain predictions
  is optimal (in the sense of the previous item).
\end{itemize}
The importance of the first item is obvious:
we want to minimize the number of uncertain predictions.
This asymptotic criterion ceases to work, however, when the number of uncertain predictions
stabilizes, as in Figure~\ref{fig:TCM_UNC} for significance levels 3\%--5\%.
In such cases the number of empty predictions becomes important:
empty predictions (automatically leading to an error)
provide a warning that the object is atypical
(looks very different from the previous objects),
and one would like to be warned as often as possible,
taking into account that the relative frequency of errors
(including empty predictions)
is guaranteed not to exceed $\delta$ in the long run.
Remember that TCM outputs a whole family of prediction regions,
so the fact that at some significance level the prediction region
becomes empty does not mean that all potential labels
for a new object become equally likely:
we should just shift our attention to other significance levels.
Figure~\ref{fig:TCM_EMP} shows the cumulative numbers of empty predictions
for the USPS data set.

\begin{figure}[tb]
\centerline{\psfig{file=TCM0emp.eps,width=\coefficient\textwidth}}
  \caption{Cumulative number of empty predictions made by the 1-Nearest Neighbour TCM
    at the significance levels 1\%--5\% on the USPS data set
    (there are no empty predictions for 1\% and 2\%)%
  \label{fig:TCM_EMP}}
\end{figure}

The full prediction output by a TCM
is a complicated mathematical object:
for each significance level $\delta$ we have a prediction region.
In practice, a good starting point might be
first to look at the prediction regions
corresponding to two or three conventional significance levels,
such as 1\% and 5\%
(afterwards, of course, the prediction regions
at other significance levels should be looked at).
For example,
denoting $\Gamma^{\delta}$ the prediction region
at significance level $\delta$,
we could say that the prediction is ``highly certain'' if $|\Gamma^{1\%}|\le1$
and ``certain'' if $|\Gamma^{5\%}|\le1$;
similarly, we could say that the new object
(whose label is being predicted)
is ``highly atypical'' if $|\Gamma^{1\%}|=0$
and ``atypical'' if $|\Gamma^{5\%}|=0$.
In the case of classification,
the family of prediction regions $\Gamma^{\delta}$
can be summarized by reporting the \emph{confidence}
$$
  \sup\{1-\delta\st|\Gamma^{\delta}|\le1\},
$$
the \emph{credibility}
$$
  \inf\{\delta\st|\Gamma^{\delta}|=0\},
$$
and the \emph{prediction} $\Gamma^{\delta}$,
where $1-\delta$ is the confidence
(in the case of TCM,
$|\Gamma^{\delta}|\le1$ and usually $|\Gamma^{\delta}|=1$
when $1-\delta$ is the confidence).
Reporting the prediction, confidence, and credibility,
as in \cite{saunders/etal:1999} and \cite{vovk/etal:1999},
is analogous to reporting the observed level of significance
\citep[p.~66]{cox/hinkley:1974} in statistics.

This paper's result elaborates on \cite{vovk:2002ALTforJMLR},          % JMLR
%This paper's result elaborates on \cite{OCM2},                         % OCM WP3
where it was shown that an optimal randomized TCM exists
when the distribution $P$ generating the examples is known.
In the rest of this paper we consider only randomized TCM,
so we drop the adjective ``randomized''.

The two areas of mainstream machine learning
that are most closely connected with this paper
are PAC learning theory and Bayesian learning theory.
Whereas we often use the rich arsenal of mathematical tools
developed in these fields,
they do not provide the same kind of guarantees
(the right probability of error at each significance level,
with errors at different trials independent)
under unknown $P$;
for more details,
see~\cite{vovk:2002FOCSforJMLR}                                        % JMLR
%see~\cite{OCM1}                                                        % OCM WP3
and references therein.
Several papers \citep[such as][]{rivest/sloan:1988,freund/etal:2004}    % JMLR
extend the standard PAC framework by allowing the prediction algorithm
to abstain from making a prediction at some trials.
Our results show that for any significance level $\delta$
there exists a prediction algorithm that:
(a) makes a wrong prediction with relative frequency at most $\delta$;
(b) has an optimal frequency of abstentions among the prediction algorithms
that satisfy property~(a)
(for details, see Remark~\ref{rem:abstentions} on p.~\pageref{rem:abstentions}).
The paper by \cite{freund/etal:2004} is especially close to the approach of this paper,       % JMLR
defining a very natural TCM in the situation where a hypothesis class is given
(the ``empirical log ratio'' of \citet{freund/etal:2004},                               % JMLR
taken with appropriate sign,
can be used as an ``individual strangeness measure'',
as defined in \S\ref{sec:construction}).

\section{Main Result}\label{sec:result}

In our learning protocol, Reality outputs pairs
$
  (x_1,y_1),(x_2,y_2),\dots
$
called \emph{examples}.
Each example $(x_i,y_i)$ consists of an \emph{object} $x_i$ and its
\emph{label} $y_i$. The objects are chosen from a measurable space ${\bf X}$ called the \emph{object space}
and the labels are elements of a measurable space ${\bf Y}$ called the \emph{label space}.
In this paper we assume that ${\bf Y}$ is finite
(and endowed with the $\sigma$-algebra of all subsets).
The protocol includes variables $\Err^{\delta}_n$
(the total number of errors made up to and including trial $n$
at significance level $\delta$)
and $\err^{\delta}_n$ (the binary variable showing whether an error is
made at trial $n$). It also includes analogous variables
$\Unc^{\delta}_n$, $\unc^{\delta}_n$, $\Emp^{\delta}_n$, $\emp^{\delta}_n$
for uncertain and empty predictions:

\medskip

\parshape=9
\IndentI  \WidthI
\IndentI  \WidthI
\IndentII \WidthII
\IndentII \WidthII
\IndentII \WidthII
\IndentII \WidthII
\IndentII \WidthII
\IndentII \WidthII
\IndentI  \WidthI
\noindent
$\Err^{\delta}_0:=0$, $\Unc^{\delta}_0:=0$, $\Emp^{\delta}_0:=0$ for all $\delta\in(0,1)$;\\
FOR $n=1,2,\dots$:\\
  Reality outputs $x_n\in{\bf X}$;\\
  Predictor outputs $\Gamma^{\delta}_n\subseteq{\bf Y}$ for all $\delta\in(0,1)$;\\
  Reality outputs $y_n\in{\bf Y}$;\\
  $\err^{\delta}_n
  :=
  \begin{cases}
    1 & \text{if $y_n \notin \Gamma^{\delta}_n$}\\
    0 & \text{otherwise}
  \end{cases}$,
  $\Err^{\delta}_n:=\Err^{\delta}_{n-1}+\err^{\delta}_n$
  for all $\delta\in(0,1)$;\\
  $\unc^{\delta}_n
  :=
  \begin{cases}
    1 & \text{if $|\Gamma^{\delta}_n|>1$}\\
    0 & \text{otherwise}
  \end{cases}$,
  $\Unc^{\delta}_n:=\Unc^{\delta}_{n-1}+\unc^{\delta}_n$
  for all $\delta\in(0,1)$;\\
  $\emp^{\delta}_n
  :=
  \begin{cases}
    1 & \text{if $|\Gamma^{\delta}_n|=0$}\\
    0 & \text{otherwise}
  \end{cases}$,
  $\Emp^{\delta}_n:=\Emp^{\delta}_{n-1}+\emp^{\delta}_n$
  for all $\delta\in(0,1)$\\
END FOR.

\medskip

\noindent
We will use the notation ${\bf Z}:={\bf X}\times{\bf Y}$
for the \emph{example space};
$\Gamma^{\delta}_n$ will be called the \emph{prediction region}
(or just \emph{prediction}).

We will assume that each example $z_n=(x_n,y_n)$, $n=1,2,\dots$,
is output according to a probability distribution $P$ in ${\bf Z}$
and the examples are independent of each other
(so the sequence $z_1z_2\dots$ is output by the power distribution $P^{\infty}$).
This is Reality's randomized strategy.

A \emph{region predictor} is a measurable function
\begin{equation}\label{eq:function}
  \Gamma^{\delta}(x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x_n,\tau_n),
\end{equation}
where $\delta\in(0,1)$, $n=1,2,\dots$,
the $(x_i,y_i)\in{\bf Z}$, $i=1,\dots,n-1$, are examples,
$x_n\in{\bf X}$ is an object, and $\tau_i\in[0,1]$ ($i=1,\dots,n$),
which satisfies
\begin{equation*}
  \Gamma^{\delta_1}
  \left(
    x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x_n,\tau_n
  \right)
%\\
  \subseteq
  \Gamma^{\delta_2}
  \left(
    x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x_n,\tau_n
  \right)
\end{equation*}
whenever $\delta_1\ge\delta_2$.
The measurability of (\ref{eq:function}) means
that for each $n$ the set
\begin{multline*}
  \left\{
    (\delta,x_1,\tau_1,y_1,\dots,x_{n},\tau_{n},y_{n})
    \st
    y_n
    \in
    \Gamma^{\delta}(x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x_n,\tau_n)
  \right\}
  \\
  \subseteq
  (0,1) \times ({\bf X}\times[0,1]\times{\bf Y})^n
\end{multline*}
is measurable.

Since we are interested in prediction with confidence,
the region predictor (\ref{eq:function})
is given an extra input $\delta\in(0,1)$,
which we call the \emph{significance level}
(typically it is close to $0$, standard values being $1\%$ and $5\%$);
the complementary value $1-\delta$ is called the \emph{confidence level}.
We will always assume that $\tau_n$ are independent random variables
uniformly distributed in $[0,1]$. This makes a region predictor a family (indexed by $\delta\in(0,1)$)
of Predictor's randomized strategies.

We will often use the notation $\err^{\delta}_n$, $\unc^{\delta}_n$, etc.,
in the case where Reality and Predictor are using given randomized
strategies. For example, $\err^{\delta}_n(P^{\infty},\Gamma)$ is the random variable
equal to 0 if Predictor is right at trial~$n$ and at significance level $\delta$
and equal to 1 otherwise.
It is always assumed that the random numbers $\tau_n$ used by $\Gamma$
and the random examples $z_n$ chosen by Reality are independent.

We say that a region predictor $\Gamma$ is (conservatively) \emph{well-calibrated}
for a probability distribution $P$ in ${\bf Z}$
and a significance level $\delta\in(0,1)$ if
$$
  \limsup_{n\to\infty}
  \frac{\Err^{\delta}_n(P^{\infty},\Gamma)}{n}
  \le
  \delta
  \quad
  \text{a.s.}
$$
We say \cite[as in][]{vovk:2002ALTforJMLR}                      % JMLR
%We say (as in \cite{OCM2})                                     % OCM WP3
that $\Gamma$ is \emph{optimal} for $P$ and $\delta$ if,
for any region predictor $\Gamma^{\dagger}$ which is well-calibrated for $P$ and $\delta$,
\begin{equation}\label{eq:sense}
  \limsup_{n\to\infty}
  \frac{\Unc^{\delta}_n(P^{\infty},\Gamma)}{n}
  \le
  \liminf_{n\to\infty}
  \frac{\Unc^{\delta}_n(P^{\infty},\Gamma^{\dagger})}{n}
  \quad
  \text{a.s.}
\end{equation}
(It is natural to assume in this and other similar definitions
that the random numbers used by $\Gamma$ and $\Gamma^{\dagger}$
are independent,
but this assumption is not needed for our mathematical results
and we do not make it.)
Of course, the definition of optimality is natural only for well-calibrated $\Gamma$.

A region predictor $\Gamma$ is \emph{universal well-calibrated} if:
\begin{itemize}
\item
  it is well-calibrated for any $P$ and $\delta$;
\item
  it is optimal for any $P$ and $\delta$;
\item
  for any $P$, any $\delta$, and any region predictor $\Gamma^{\dagger}$
  which is well-calibrated and optimal for $P$ and $\delta$,
  $$
    \liminf_{n\to\infty}
    \frac{\Emp^{\delta}_n(P^{\infty},\Gamma)}{n}
    \ge
    \limsup_{n\to\infty}
    \frac{\Emp^{\delta}_n(P^{\infty},\Gamma^{\dagger})}{n}
    \quad
    \text{a.s.}
  $$
\end{itemize}

Recall that a measurable space ${\bf X}$ is \emph{Borel}
if it is isomorphic to a measurable subset of the interval $[0,1]$.
The class of Borel spaces is very rich;
for example, all Polish spaces (such as finite-dimensional Euclidean spaces $\bbbr^n$,
$\bbbr^{\infty}$, functional spaces $C$ and $D$) are Borel.
%(see \cite{schervish:1995}, B.3.2).
\begin{theorem}\label{thm:universal}
  Suppose the object space ${\bf X}$ is Borel.
  There exists a universal well-calibrated region predictor.
\end{theorem}
This is the main result of the paper. In \S\ref{sec:construction} we construct a universal well-calibrated region predictor
(processing example $n$ in time $O(\log n)$)
and in \S\ref{sec:fine} outline the idea of the proof
that it indeed satisfies the required properties. Technical details will be given in \S\ref{sec:proofs}.
\begin{remark}\label{rem:abstentions}
  The protocol of \cite{rivest/sloan:1988} and \cite{freund/etal:2004}
  is in fact a restriction of our protocol,
  in which Predictor is only allowed to output a one-element set or the whole of ${\bf Y}$;
  the latter is interpreted as abstention.
  (And in the situation where the numbers of errors and uncertain predictions are of primary interest,
  as in this paper,
  the difference between these two protocols is not significant.)
  The universal well-calibrated region predictor
  can be adapted to the restricted protocol
  by replacing an uncertain prediction with ${\bf Y}$
  and replacing an empty prediction with a randomly chosen label.
  In this way we obtain a prediction algorithm in the restricted protocol
  which is well-calibrated and has an optimal frequency of abstentions,
  in the sense of~(\ref{eq:sense}),
  among the well-calibrated algorithms.
\end{remark}

\section{Construction of a Universal Well-Calibrated Region Predictor}
\label{sec:construction}
In this section we first define the general notion of Transductive
Confidence Machine, and then we specialize it using a nearest
neighbours procedure to obtain a universal well-calibrated region
predictor.

\subsection{Preliminaries}\label{subsec:prel}

%As we already mentioned,
%our prediction algorithm is given a sequence of random numbers $\tau_n$, $n=1,2,\dots$,
%independent and distributed uniformly in $[0,1]$.
%These random numbers can have different uses,
%and first of all we define a way of ``splitting'' a random number.
If $\tau$ is a number in $[0,1]$,
we split it into two numbers $\tau',\tau''\in[0,1]$ as follows:
if the binary expansion of $\tau$ is $0.a_1 a_2 \dots$
(redefine the binary expansion of $1$ to be $0.11\dots$), set
$
  \tau' := 0.a_1 a_3 a_5 \dots
$
and
$
  \tau'' := 0.a_2 a_4 a_6 \dots
$\,.
If $\tau$ is distributed uniformly in $[0,1]$,
then both $\tau'$ and $\tau''$ are, and they are independent of each other.
%therefore,
%this gives us a way of ``splitting'' a random number.
%We will let $\tau^{(i,j)}$ stand for $\left(\tau^{(i)}\right)^{(j)}$.

We will often apply our procedures
(e.g., the ``individual strangeness measure'' in \S\ref{subsec:TCM},
the Nearest Neighbours rule in \S\ref{subsec:univTCM}) not to the original objects $x\in{\bf X}$
but to \emph{extended objects} $(x,\sigma)\in\tilde{{\bf X}}:={\bf X}\times[0,1]$,
where $x$ is complemented by a random number $\sigma$
(to be extracted from one of the $\tau_n$).
In other words, along with examples $(x,y)$ we will also consider \emph{extended examples}
$(x,\sigma,y)\in\tilde{{\bf Z}}:={\bf X}\times[0,1]\times{\bf Y}$.

Let us set ${\bf X} := [0,1]$;
we can do this without loss of generality since ${\bf X}$ is Borel.
This makes the extended object space $\tilde{{\bf X}}=[0,1]^2$
a linearly ordered set with the \emph{lexicographic order}\label{p:lex}:
$(x_1,\sigma_1)<(x_2,\sigma_2)$ means that either $x_1=x_2$ and $\sigma_1<\sigma_2$
or $x_1<x_2$.
We say that $(x_1,\sigma_1)$ is \emph{nearer} to $(x_3,\sigma_3)$ than $(x_2,\sigma_2)$ is
if
\begin{equation}\label{eq:closeness}
  |x_1-x_3,\sigma_1-\sigma_3|
  <
  |x_2-x_3,\sigma_2-\sigma_3|,
\end{equation}
where
\begin{equation}\label{eq:abs}
  |x,\sigma|
  :=
  \begin{cases}
    (x,\sigma) & \text{if $(x,\sigma)\ge(0,0)$}\\
    (-x,-\sigma) & \text{otherwise}.
  \end{cases}
\end{equation}
The value $|x_1-x_2,\sigma_1-\sigma_2|$ plays the role of the distance
between extended objects $(x_1,\sigma_1)$ and $(x_2,\sigma_2)$.
Despite such distances being two-dimensional,
they are still always comparable
using the lexicographic order.

Our construction will be based on the Nearest Neighbours algorithm,
which is known to be strongly universally consistent
in the traditional theory of pattern recognition
%(see, e.g., \cite{devroye/etal:1996}, Chapter~11);             % OCM WP3
\citep[see, e.g.,][Chapter~11]{devroye/etal:1996};              % JMLR
the random components $\sigma$ are needed for tie-breaking.

\subsection{Transductive Confidence Machines}\label{subsec:TCM}

Transductive Confidence Machine, or TCM,
is a way of transition
from what we call an ``individual strangeness measure'' to a region predictor.
A family of measurable functions $\{A_n\st n=1,2,\dots\}$,
where $A_n:{\tilde{\bf Z}}^n\to\bbbr^n$ for all $n$,
%and $R$ is a linearly ordered measurable space
%(with the relation $<$ measurable),
is called an \emph{individual strangeness measure} if,
for any $n=1,2,\dots$,
each $\alpha_i$ in
\begin{equation}\label{eq:ism}
  A_n:
  (w_1,\dots,w_n)
  \mapsto
  (\alpha_1,\dots,\alpha_n)
\end{equation}
is determined by $w_i$ and the multiset 
$\lbag w_1,\dots,w_n\rbag$.
(The difference between a multiset 
$\lbag w_1,\dots,w_n\rbag$
and a set $\{w_1,\dots,w_n\}$
is that the former can contain several copies of the same element.)

The \emph{TCM associated with an individual strangeness measure $A_n$}
is the following %randomized 
region predictor
$\Gamma^{\delta}(x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x_n,\tau_n)$:
at any trial $n$ and for any label $y\in{\bf Y}$, define
$$
  (\alpha_1,\dots,\alpha_n)
  :=
  A_n((x_1,\tau'_1,y_1),\dots,(x_{n-1},\tau'_{n-1},y_{n-1}),(x_n,\tau'_n,y)),
$$
and include $y$ in~$\Gamma^{\delta}$ if and only if
\begin{equation}\label{eq:prob}
  \tau''_n
  <
  \frac
    {\#\{i=1,\dots,n\st\alpha_i\ge\alpha_n\}-n\delta}
    {\#\{i=1,\dots,n\st\alpha_i=\alpha_n\}}
\end{equation}
(in particular,
include $y$ in~$\Gamma^{\delta}$ if
$
  \#\{i=1,\dots,n\st\alpha_i>\alpha_n\}/n
  >
  \delta
$
and do not include $y$ in~$\Gamma^{\delta}$ if
$
  \#\{i=1,\dots,n\st\alpha_i\ge\alpha_n\}/n
  \le
  \delta
$).

A \emph{TCM} is the TCM associated with some individual strangeness measure.
It was shown in~\cite{vovk:2002FOCSforJMLR} that               % JMLR
%It was shown in~\cite{OCM1} that                               % OCM WP3
\begin{proposition}\label{prop:calibration}
  Every TCM is well-calibrated for every $P$ and $\delta$.
\end{proposition}
%(This proposition goes slightly beyond what is proved in~\citep{vovk:2002FOCSforJMLR},
%since in this paper we consider randomized individual strangeness measures
%and allow $\alpha_i$ to take values in an arbitrary linearly ordered measurable space.)

The definition of TCM can be illustrated
by the following simple example of an individual strangeness measure,
the one used in producing Figures~\ref{fig:TCM_ERR}--\ref{fig:TCM_EMP}:
mapping~(\ref{eq:ism}) can be defined,
in the spirit of the 1-Nearest Neighbour Algorithm,
as (assuming the objects are vectors in a Euclidean space)
\begin{equation*}
  \alpha_i
  :=
  \frac
  {
    \min_{j\ne i: y_j = y_i}
    d(x_i,x_j)
  }
  {
    \min_{j\ne i: y_j \ne y_i}
    d(x_i,x_j)
  },
\end{equation*}
where $d$ is the Euclidean distance
(i.e., an object is considered strange if it is in the middle
of objects labelled in a different way
and is far from the objects labelled in the same way).

\subsection{Universal TCM}\label{subsec:univTCM}

Fix a monotonically non-decreasing sequence of integer numbers $K_n$,
$n=1,2,\dots$,
such that
\begin{equation}\label{eq:K}
  K_n \to \infty,
  \;
  K_n
  =
  o
  \left(
    \sqrt{n/\ln n}
  \right)
\end{equation}
as $n\to\infty$.
The \emph{Nearest Neighbours TCM} is defined as follows.
Let $w_1,\dots,w_n$ be a sequence of extended examples $w_i=(x_i,\sigma_i,y_i)$.
To define the corresponding $\alpha$s , as seen in~(\ref{eq:ism}),
we first define Nearest Neighbours approximations $P^{\ne}_n(y\givn x_i,\sigma_i)$
to the true (but unknown) conditional probabilities $P(y\givn x_i)$:
for every extended example $(x_i,\sigma_i,y_i)$ in the sequence,
\begin{equation}\label{eq:cond}
  P^{\ne}_n(y\givn x_i,\sigma_i)
  :=
  N^{\ne}(x_i,\sigma_i,y) / K_n,
\end{equation}
where $N^{\ne}(x_i,\sigma_i,y)$ is the number of $j=1,\dots,n$
such that $y_j=y$ and
$(x_j,\sigma_j)$ is one of the $K_n$ nearest neighbours,
in the sense of (\ref{eq:closeness}),
of $(x_i,\sigma_i)$
in the sequence
%$((x_1,\sigma_1),\dots,(x_{i-1},\sigma_{i-1}),         % OCM WP3
%(x_{i+1},\sigma_{i+1}),\dots,(x_n,\sigma_n))$.         % OCM WP3
$$((x_1,\sigma_1),\dots,(x_{i-1},\sigma_{i-1}),
(x_{i+1},\sigma_{i+1}),\dots,(x_n,\sigma_n)).$$
(The upper index ${}^{\ne}$ reminds us of the fact that $(x_i,\sigma_i)$
is not counted as one of its own nearest neighbours in this definition.)
If $K_n\ge n$ or $K_n\le0$,
this definition does not work,
so set, e.g.,  $P^{\ne}_n(y\givn x_i,\sigma_i):=1/|{\bf Y}|$
for all $y$ and $i$
(this particular convention is not essential since, by~(\ref{eq:K}),
$0<K_n<n$ from some $n$ on).
If the expression ``$K_n$ nearest neighbours'' is not defined
because of distance ties,
we again set $P^{\ne}_n(y\givn x_i,\sigma_i):=1/|{\bf Y}|$
for all $y$ and $i$
(this convention is not essential
since distance ties happen with probability zero).

Define the ``empirical predictability function'' $f^{\ne}_n$ by
\begin{equation}\label{eq:fne_n}
  f^{\ne}_n(x_i,\sigma_i)
  :=
  \max_{y\in{\bf Y}}
  P^{\ne}_n(y\givn x_i,\sigma_i).
\end{equation}
For each $(x_i,\sigma_i)$ fix some
\begin{equation}\label{eq:max}
  \hat{y}_n(x_i,\sigma_i) \in \arg\max_y P^{\ne}_n(y\givn x_i,\sigma_i)
\end{equation}
(e.g., take the first element of $\arg\max_y P^{\ne}_n(y\givn x_i,\sigma_i)$
in a fixed ordering of ${\bf Y}$)
and define the mapping~(\ref{eq:ism})
(where $w_i=(x_i,\sigma_i,y_i)$, $i=1,\dots,n$)
setting
\begin{equation}\label{eq:univ_alpha}
  \alpha_i
  :=
  \begin{cases}
    -f_n^{\ne}(x_i,\sigma_i) & \text{if $y_i=\hat{y}_n(x_i,\sigma_i)$}\\
    f_n^{\ne}(x_i,\sigma_i) & \text{otherwise}.
  \end{cases}
\end{equation}
This completes the definition of the Nearest Neighbours TCM,
which will later be shown to be universal.
\begin{proposition}\label{prop:time}
  Let $\Delta\subseteq(0,1)$ be finite.
  If ${\bf X}=[0,1]$ and $K_n\to\infty$ sufficiently slowly,
  the Nearest Neighbours TCM
  can be implemented for significance levels $\delta\in\Delta$
  so that the computations at trial $n$ are performed in time $O(\log n)$.
\end{proposition}
Proposition~\ref{prop:time} assumes a computational model
that allows operations (such as comparison) with real numbers.
If ${\bf X}$ is an arbitrary Borel space,
for this proposition to be applicable
${\bf X}$ should be embedded in $[0,1]$ first;
e.g., if ${\bf X}\subseteq[0,1]^n$,
an $x=(x_1,\dots,x_n)\in{\bf X}$ can be represented as
$$
  \left(
    x_{1,1}, x_{2,1}, \dots, x_{n,1},
    x_{1,2}, x_{2,2}, \dots, x_{n,2},
    \dots
  \right)
  \in
  [0,1],
$$
where $0.x_{i,1}x_{i,2}\dots$ is the binary expansion of $x_i$.
We use the expression ``can be implemented'' in a wide sense,
only requiring that the implementation should give the correct results
almost surely.

\section{Fine Details of Region Prediction}
\label{sec:fine}

In this section we make first steps
towards the proof of Theorem~\ref{thm:universal}.
Let $P$ be the true distribution in ${\bf Z}$ generating the examples.
We denote by $P_{{\bf X}}$ the marginal distribution of $P$ in ${\bf X}$
(i.e., $P_{{\bf X}}(E):=P(E\times{\bf Y})$)
and by $P_{{\bf Y}\givn{\bf X}}(y\givn x)$ the conditional probability
that, for a random example $(X,Y)$ chosen from $P$,
$Y=y$ provided $X=x$
(we fix arbitrarily a regular version of this conditional probability).
We will often omit lower indices ${}_{{\bf X}}$ and ${}_{{\bf Y}\givn{\bf X}}$
and $P$ itself from our notation.

The \emph{predictability} of an object $x\in{\bf X}$ is
$$
  f(x)
  :=
  \max_{y\in{\bf Y}}
  P(y\givn x)
$$
and the \emph{predictability distribution function}
is the function $F:[0,1]\to[0,1]$ defined by
$$
  F(\beta)
  :=
  P\{x\st f(x)\le\beta\}.
$$
%(essentially, it is the distribution function of the image $P\circ f^{-1}$
%of the probability distribution $P$ under the mapping $f$).
An example of such a function $F$ is given in Figure~\ref{fig:PredDF} (left),
where the graph of $F$ is the thick line.
%and the unit box is also shown.

\begin{figure}
  \centering
  \unitlength=0.5mm
  \begin{picture}(120,120)
    \put(10,20){\vector(1,0){110}}              % x axis
    \put(20,10){\vector(0,1){110}}              % y axis
    \put(20,100){\line(1,0){80}}                % bounding box
    \put(100,20){\line(0,1){80}}                % bounding box
    \put(120,18){\makebox(0,0)[ct]{$\beta$}}            % x axis label
    \put(18,120){\makebox(0,0)[rc]{$F(\beta)$}}         % y axis label
    \put(100,60){\line(-1,0){13}}               % finish the triangle
    \put(100,100){\circle*{2}}                  % A
    \put(100,102){\makebox(0,0)[cb]{A}}         % A
    \put(100,60){\circle*{1}}                   % B
    \put(102,60){\makebox(0,0)[lc]{B}}          % B
    \put(86.86,60){\circle*{2}}                 % C
    \put(86,61.5){\makebox(0,0)[rb]{C}}         % C
    \put(100,20){\circle*{1}}                   % Z
    \put(100,18){\makebox(0,0)[ct]{Z}}          % Z
    \put(94.5,65){$\delta$}                     % delta
    \multiput(20,60)(2,0){34}{\line(1,0){1}}                    % the dashed line from S(delta) to B
    \put(18,60){\makebox(0,0)[rc]{${\bf S}(\delta)$}}           % S(delta)
    \put(74,38){\makebox(0,0)[rb]{$F$}}                         % F
%    \thicklines
%    \linethickness{1mm}
    \linethickness{0.5mm}
    \qbezier[2000](40,20)(80,20)(99.5,100)      % F's graph
    \put(20,20){\line(1,0){20}}                 % F's graph
  \end{picture}
  \qquad
  \unitlength=0.5mm
  \begin{picture}(120,120)
    \put(10,20){\vector(1,0){110}}              % x axis
    \put(20,10){\vector(0,1){110}}              % y axis
    \put(20,100){\line(1,0){80}}                % bounding box
    \put(100,20){\line(0,1){80}}                % bounding box
    \put(120,18){\makebox(0,0)[ct]{$\beta$}}            % x axis label
    \put(18,120){\makebox(0,0)[rc]{$F(\beta)$}}         % y axis label
    \put(100,100){\circle*{2}}                  % A
    \put(100,102){\makebox(0,0)[cb]{A}}         % A
%    \put(100,40){\circle*{1}}                  % B
%    \put(102,40){\makebox(0,0)[lc]{B}}         % B
    \put(20,100){\circle*{1}}                   % D
    \put(18,100){\makebox(0,0)[rc]{D}}          % D
    \put(100,20){\circle*{1}}                   % Z
    \put(100,18){\makebox(0,0)[ct]{Z}}          % Z
    \put(20,20){\circle*{1}}                    % O
    \put(18,18){\makebox(0,0)[rt]{O}}           % O
    \put(40,30){\makebox(0,0)[cc]{$\delta-\delta_0$}}           % delta - delta_0
    \put(90,40){\makebox(0,0)[cc]{$\delta_0$}}                  % delta_0
%    \multiput(20,40)(2,0){40}{\line(1,0){1}}                   % the solid line from C(delta) to B
    \put(18,40){\makebox(0,0)[rc]{${\bf C}(\delta)$}}           % C(delta)
    \put(89,60){\makebox(0,0)[rb]{$F$}}                         % F
    \qbezier[2000](40,20)(61,20)(76,40)         % F's graph (lower half)
%    \thicklines
%    \linethickness{1mm}
    \linethickness{0.5mm}
    \qbezier[2000](75.5,40)(100,74)(99.5,100)   % F's graph (upper half)
    \put(20,40){\line(1,0){56}}                 % thick horizontal line
  \end{picture}
  \caption{The predictability distribution function $F$
     and the success curve ${\bf S}(\delta)$ (left);
     the complementary success curve ${\bf C}(\delta)$ (right)
  \label{fig:PredDF}}
\end{figure}
% It is clear that the predictability distribution function $F$
% satisfies these properties:
% $F(\epsilon)=0$ for some $\epsilon>0$ and $F(1)=1$;
% $F$ is non-decreasing;
% $F$ is continuous on the right.

The \emph{success curve} ${\bf S}_P$ of $P$ is defined by the equality
\begin{equation}\label{eq:success}
  {\bf S}_P(\delta)
  =
  \inf
  \left\{
    B\in[0,1]
    \st
    \int_0^1
      (F(\beta)-B)^{+}
    d\beta
    \le
    \delta
  \right\},
\end{equation}
where $t^{+}$ stands for $\max(t,0)$;
the function ${\bf S}_P$ is also of the type $[0,1]\to[0,1]$.
Geometrically,
${\bf S}_P(\delta)$ is defined from the graph of $F$ as follows
(see Figure~\ref{fig:PredDF}, left;
we often drop the lower index ${}_P$):
move the point B from A to Z
until the area of the curvilinear triangle ABC becomes $\delta$
or B reaches Z;
% (assuming this area does become $\delta$ eventually,
% i.e., $\delta$ is not too large);
the ordinate of B is then ${\bf S}(\delta)$.

The \emph{complementary success curve} ${\bf C}_P$ of $P$ is defined by
\begin{equation}\label{eq:compl}
  {\bf C}_P(\delta)
  =
  \sup
  \left\{
    B\in[0,1]
    \st
    B
    +
    \int_0^1
      (F(\beta)-B)^{+}
    d\beta
    \le
    \delta
  \right\},
\end{equation}
where $\sup\emptyset$ is interpreted as $0$.
Similarly to the case of ${\bf S}(\delta)$,
${\bf C}(\delta)$ is defined
as the value such that the area of the part of the box AZOD below the thick line
in Figure~\ref{fig:PredDF} (right)
is $\delta$
(${\bf C}(\delta)=0$ if such a value does not exist).

Define the \emph{critical significance level} $\delta_0$ as
\begin{equation}\label{eq:critical}
  \delta_0
  :=
  \int_0^1
  F(\beta)
  d\beta.
\end{equation}
It is clear that
\begin{align*}
  \delta\le\delta_0
  &\Longrightarrow
  \int_0^1
    (F(\beta)-{\bf S}(\delta))^{+}
  d\beta
  =
  \delta
  \;\&\;
  {\bf C}(\delta)=0
\\
  \delta\ge\delta_0
  &\Longrightarrow
  {\bf S}(\delta)=0
  \;\&\;
  {\bf C}(\delta)
  +
  \int_0^1
    (F(\beta)-{\bf C}(\delta))^{+}
  d\beta
  =
  \delta.
\end{align*}

The following result is proved in \cite{vovk:2002ALTforJMLR}.          % JMLR
%The following result is proved in \cite{OCM2}.                         % OCM WP 3
\begin{proposition}\label{prop:lower}
  Let $P$ be a probability distribution in ${\bf Z}$
% with success curve ${\bf S}$
  and $\delta\in(0,1)$ be a significance level.
  If a region predictor $\Gamma$ is well-calibrated for $P$ and $\delta$,
  then
  \begin{equation}\label{eq:lower}
    \liminf_{n\to\infty}
    \frac{\Unc^{\delta}_n(P^{\infty},\Gamma)}{n}
    \ge
    {\bf S}_P(\delta)
    \quad
    \text{a.s.}
  \end{equation}
\end{proposition}
%The ``a.s.''\ in this proposition
%(and in the next one)
%refers to the probability distribution $(P\times{\bf U})^{\infty}$
%generating the sequence $x_1,\tau_1,y_1,x_2,\tau_2,y_2,\dots$ of examples
%and random numbers,
%with ${\bf U}$ standing for the uniform distribution in $[0,1]$.
In this paper we complement Proposition~\ref{prop:lower} with
\begin{proposition}\label{prop:lower_compl}
  Let $P$ be a probability distribution in ${\bf Z}$
% with success curve ${\bf S}$ and complementary success curve ${\bf C}$
  and $\delta\in(0,1)$ be a significance level.
  If a region predictor $\Gamma$ is well-calibrated for $P$ and $\delta$
  and satisfies
  \begin{equation}\label{eq:opt}
    \limsup_{n\to\infty}
    \frac{\Unc^{\delta}_n(P^{\infty},\Gamma)}{n}
    \le
    {\bf S}_P(\delta)
    \quad
    \text{a.s.},
  \end{equation}
  then
  $$
    \limsup_{n\to\infty}
    \frac{\Emp^{\delta}_n(P^{\infty},\Gamma)}{n}
    \le
    {\bf C}_P(\delta)
    \quad
    \text{a.s.}
  $$
\end{proposition}

Theorem~\ref{thm:universal} immediately follows
from Propositions~\ref{prop:calibration}, \ref{prop:lower}, \ref{prop:lower_compl}
and the following proposition.
\begin{proposition}\label{prop:upper}
  Suppose ${\bf X}$ is Borel.
  The Nearest Neighbours TCM constructed in \S\ref{subsec:univTCM} satisfies,
  for any $P$ and any significance level $\delta$,
  \begin{equation}\label{eq:main}
    \limsup_{n\to\infty}
    \frac{\Unc^{\delta}_n(P^{\infty},\Gamma)}{n}
    \le
    {\bf S}_P(\delta)
    \quad
    \text{a.s.}
  \end{equation}
  and
  \begin{equation}\label{eq:mainEmp}
    \liminf_{n\to\infty}
    \frac{\Emp^{\delta}_n(P^{\infty},\Gamma)}{n}
    \ge
    {\bf C}_P(\delta)
    \quad
    \text{a.s.}
  \end{equation}
\end{proposition}

\section{Proofs}\label{sec:proofs}

%To simplify notation,
%in this section we will deal with the ``regularized'' classification problem,
%in which each observed object $x_n$
%is complemented by adding the random number $\tau'_n$;
%${\bf X}$ and ${\bf Z}$ will always stand for the object and example spaces
%(earlier denoted by $\tilde{\bf X}$ and $\tilde{\bf Z}$) of the regularized problem
%and $P$ will be the probability distribution
%($P\times{\bf U}$ in the earlier notation)
%generating the examples in the regularized problem.

In this section we will assume
that all extended objects $(x_i,\tau'_i)\in[0,1]^2$,
where $x_i$ are output by Reality and $\tau_i$ are the random numbers used,
are different
and that all pairwise distances between them
are also different
(this is true with probability one,
since $\tau'_i$ are independent random numbers
uniformly distributed in $[0,1]$).

\subsection{Proof Sketch of Proposition~\ref{prop:time}}

%Remember that the extended examples form a linearly ordered set
%(with the lexicographic order).
Without loss of generality we assume that $\Delta$ contains
only one significance level $\delta$,
which will be omitted from our notation.
%The size $L:=|{\bf Y}|$ of the label space ${\bf Y}$ is fixed;
%we fix some ordering $y_{[1]},\dots,y_{[L]}$ of the elements of ${\bf Y}$.
Our computational model has an operation of splitting $\tau\in[0,1]$
into $\tau'$ and $\tau''$
(or is allowed to generate both $\tau'_n$ and $\tau''_n$
at every trial $n$).

We will use two main data structures in our implementation
of the Nearest Neighbours TCM:
\begin{itemize}
\item a red-black binary \emph{search tree};\footnote{See,
    e.g., \cite{cormen/etal:2001}, Chapters~12--14. The only two operations
    on red-black trees we need in this paper are the query
    \textsc{Search} and the modifying operation \textsc{Insert}.}
%\item
%  a growing array (called \emph{big array}) of nonnegative integer numbers
%  indexed by sequences $(y,k_1,\dots,k_L)$,
%  where $y\in{\bf Y}$ ranges over all possible labels
%  and $k_1,\dots,k_L$ are integers ranging between $0$ and $K_n$
%  (where $n$ is the ordinal number of the example being processed);
\item
  a growing \emph{array}
% (called \emph{summary array})
  of nonnegative integers
  indexed by $k\in\{-K_n,-K_n+1,\dots,K_n\}$
  (where $n$ is the ordinal number of the example being processed).
\end{itemize}
Immediately after processing the $n$th extended example $(x_n,\tau_n,y_n)$
the contents of these data structures are as follows:
\begin{itemize}
\item
  The search tree contains $n$ vertices,
  corresponding to the extended examples $(x_i,\tau_i,y_i)$ seen so far.
  The key of vertex $i$ is the extended object $(x_i,\tau'_i)\in[0,1]^2$;
  the linear order on the keys is the lexicographic order.
%  (and the expression ``nearest neighbour'' is understood in terms of this order).
  The other information contained in vertex $i$ is
  the random number $\tau''_i$,
  the label $y_i$,
  the set $\{P^{\ne}_n(y\givn x_i,\tau'_i)\st y\in{\bf Y}\}$
  of conditional probability estimates~(\ref{eq:cond}),
  the pointer to the following vertex
  (i.e., the vertex that has the smallest key greater than $(x_i,\tau'_i)$;
  if there is no greater key, the pointer is \textsc{nil}),
  and the pointer to the previous vertex
  (i.e., the vertex that has the greatest key smaller than $(x_i,\tau_i')$;
  if $(x_i,\tau'_i)$ is the smallest key, the pointer is \textsc{nil}).
%  The system of pointers to the following and previous vertices
%  will sometimes be called the \emph{thread}.
%\item
%  The big array contains the numbers
%  \begin{gather*}
%    N(y,k_1,\dots,k_L)
%    :=
%    \#
%    \Bigl\{
%      i=1,\dots,n
%      \st{}
%  \\
%      y_i=y,
%      k_1=K_nP^{\ne}_n(y_{[1]}\givn x_i,\tau'_i),
%      \dots,
%      k_L=K_nP^{\ne}_n(y_{[L]}\givn x_i,\tau'_i)
%    \Bigr\}.
%  \end{gather*}
\item
  The array contains the numbers
  $$
    N(k)
    :=
    \#
    \left\{
      i=1,\dots,n
      \st
      \alpha_i = k/K_n
    \right\}
  $$
  ($\alpha_i$ are defined by (\ref{eq:univ_alpha})
  with $\sigma_i:=\tau'_i$).
\end{itemize}
Notice that the information
contained in vertex $i$ of the search tree
is sufficient to find $\hat{y}_n(x_i,\tau'_i)$ and $\alpha_i$ in time $O(1)$.
%and the information contained in each index structure of the array
%is sufficient to find the $\alpha_i$ in time $O(1)$.

We will say that an extended object $(x_j,\tau'_j)$
is in the \emph{vicinity} of an extended object $(x_i,\tau'_i)$,
$i\ne j$,
%at the end of step $n$ of the protocol, $n\ge i$,
if there are less than $K_n$ extended objects $(x_k,\tau'_k)$
(strictly) between $(x_i,\tau'_i)$ and $(x_j,\tau'_j)$.

When a new object $x_n$ becomes known, the algorithm does the following:
\begin{itemize}
\item
  Generates $\tau'_n$ and $\tau''_n$.
\item
  Locates the successor and predecessor of $(x_n,\tau'_n)$ in the search tree
  (using the query \textsc{Search} and the pointers to the following and previous vertices);
  this requires time $O(\log n)$.
\item
  Computes the estimated conditional probabilities
  $\{P^{\ne}_n(y\givn x_n,\tau'_n)\st y\in{\bf Y}\}$;
  this also gives $\hat y_n(x_n,\tau'_n)$.
% and $\alpha_n(y)$
% (the value of $\alpha_n$ that obtains if $y$ is the true label of $x_n$)
% for all $y\in{\bf Y}$.
  This involves scanning the vicinity of $(x_n,\tau'_n)$
  for the $K_n$ nearest neighbours of $(x_n,\tau'_n)$,
  which can be done in time $O(K_n)$:
  the $K_n$ nearest neighbours can be extracted
  from the vicinity of $(x_n,\tau'_n)$
  sorted in the order of increasing distances from $(x_n,\tau'_n)$;
  since initially the vicinity consists of two sorted lists
  (to the left and to the right of $(x_n,\tau'_n)$),
  the procedure \textsc{Merge} used in the merge sort algorithm
  (see, e.g., \citealt{cormen/etal:2001}, \S2.3.1)
  will sort the whole vicinity in time $O(K_n)$.
  Therefore, the required time is $O(K_n)=O(\log n)$.
%\item
%  Updates the big array,
%  changing
%  $$
%    N(y_i,K_nP_n(y_{[1]}\givn x_i,\tau'_i),\dots,K_nP_n(y_{[L]}\givn x_i,\tau'_i))
%  $$
%  for the $(x_i,\tau'_i)$ in the vicinity of $(x_n,\tau_n)$
%  (time $O(K_n)=O(\log n)$).
\item
  For each $y\in{\bf Y}$ looks at what happens
  if the $n$th example is $(x_n,\tau_n,y_n)=(x_n,\tau_n,y)$:
  computes $\alpha_n$ and updates (if necessary) $\alpha_i$ for $(x_i,\tau'_i)$
  in the vicinity of $(x_n,\tau'_n)$;
  using the array and $\tau''_n$, finds whether $y\in\Gamma_n$.
  This requires time $O(K^2_n) = O(\log n)$,
  since there are $O(K_n)$ $\alpha_i$'s in the vicinity of $(x_n,\tau'_n)$
  and each of them can be computed in time $O(K_n)$.
\item
  Outputs the prediction region $\Gamma_n$
  (time $O(1)$).
\end{itemize}
When the label $y_n$ arrives, the algorithm:
\begin{itemize}
\item
  Inserts the new vertex
  $(x_n,\tau'_n,\tau''_n,y_n,\{P^{\ne}_n(y\givn x_n,\tau'_n)\st y\in{\bf Y}\})$
  in the search tree,
  repairs the pointers to the following and previous elements
  for $(x_n,\tau'_n)$'s left and right neighbours,
  initializes the pointers to the following and previous elements
  for $(x_n,\tau'_n)$ itself,
  and rebalances the tree (time $O(\log n)$).
\item
  Updates (if necessary) the conditional probabilities
  $$
    \{P^{\ne}_{n-1}(y\givn x_i,\tau'_i)\st y\in{\bf Y}\}
    \mapsto
    \{P^{\ne}_n(y\givn x_i,\tau'_i)\st y\in{\bf Y}\}
  $$
  for the $2K_n$ existing vertices $(x_i,\tau'_i)$ in the vicinity of $(x_n,\tau'_n)$;
%  (using the query \textsc{Search} and the pointers to the following and previous vertices);
  this requires time $O(K^2_n) = O(\log n)$.
  The conditional probabilities for other $(x_i,\tau'_i)$, $i=1,\dots,n-1$,
  do not change.
\item
  Updates the array,
  changing $N(K_n\alpha_i)$ for the $(x_i,\tau'_i)\ne(x_n,\tau'_n)$
  in the vicinity of $(x_n,\tau'_n)$
  and for both old and new values of $\alpha_i$
  and changing $N(K_n\alpha_n)$
  (time $O(K_n)=O(\log n)$).
%\item
%  Updates the big array.
%\item
%  Updates the summary array, namely 
%  (time $O(1)$).
\end{itemize}

In conclusion we discuss how to do the updates
required when $K_n$ changes.
At the critical trials $n$ when $K_n$ changes
the array and the estimated conditional probabilities
$P^{\ne}_n(y\givn x_i,\tau'_i)$ have to be recomputed,
which, if done naively,
would require time $\Theta(nK_n)$.

The assumption we have made about $K_n$ so far is that $K_n=O(\sqrt{\log n})$.
We now also assume that $K_n$ is monotonic non-decreasing and
\begin{equation}\label{eq:O}
  \#\{n\st K_n<c\}
  =
  O
  \left(
    \#\{n\st K_n=c\}
  \right)
\end{equation}
as $c\to\infty$.
This is the full explication of the ``$K_n\to\infty$ sufficiently slowly''
in the statement of the lemma,
as used in this proof.

An \emph{epoch} is defined to be a maximal sequence of $n$s
with the same $K_n$.
%in other words,
%epochs are sequences of the form
%\begin{equation}\label{eq:epoch}
%  2^k,2^{k+1},\dots,2^{k+1}-1.
%\end{equation}
Since the changes that need to be done
when a new epoch starts are substantial,
they will be spread over the whole preceding epoch;
we will only discuss  updating the estimated conditional probabilities
$P^{\ne}_n(y\givn x_i,\tau'_i)$:
the array is treated similarly.
An epoch is \emph{odd} if the corresponding $K_n$ is odd
and \emph{even} if $K_n$ is even.
At every step in an epoch we prepare the ground for the next epoch.
By the end of epoch~$n=A+1,A+2,\dots,B$
we need to change $B$ sets
$\{P^{\ne}_n(y\givn x_i,\tau'_i)\st y\in{\bf Y}\}$ in $B-A$ steps
(the duration of the epoch).
Therefore, each vertex of the search tree
should contain not only $\{P^{\ne}_n(y\givn x_i,\tau'_i)\}$ for the current epoch
but also $\{P^{\ne}_n(y\givn x_i,\tau'_i)\}$ for the next epoch
(two structures for holding $\{P^{\ne}_n(y\givn x_i,\tau'_i)\}$ will suffice,
one for even epochs and one for odd epochs).
Our assumptions of the slow growth of $K_n$, as seen in \ref{eq:O}),
imply that $B=O(B-A)$.
This means that at each step
$O(1)$ sets $\{P^{\ne}_n(y\givn x_i,\tau'_i)\}$
for the next epoch should be added.
%namely, at step $i$ of the epoch, $i=1,\dots,2^k$,
%sets for extended examples $2^k+2i-2$ and $2^k+2i-1$ are added.
This will take time $O(K_n)=O(\log n)$.
As soon as a set $\{P^{\ne}_n(y\givn x_i,\tau'_i)\st y\in{\bf Y}\}$
for the next epoch is added
at some trial,
both sets (for the current and next epoch)
will have to be updated for each new example.
% In a similar way the array for the next epoch is gradually built up.

\subsection{Proof Sketch of Proposition~\ref{prop:lower_compl}}

The proof of Proposition~\ref{prop:lower_compl}
is similar to (but more complicated than)
the proof of Theorems~1 and~1r in~\cite{vovk:2002ALTforJMLR};  % JMLR
%the proof of Theorems~1 and~1r in~\cite{OCM2};                 % OCM WP3
this proof sketch can be made rigorous using the Neyman--Pearson lemma,
as in~\cite{vovk:2002ALTforJMLR}.                              % JMLR
%as in~\cite{OCM2}.                                             % OCM WP3

We will use the notations $g'_{{\rm left}}$ and $g'_{{\rm right}}$
for the left and right derivatives, respectively, of a function $g$.
The following lemma parallels Lemma~2 in \cite{vovk:2002ALTforJMLR},   % JMLR
%The following lemma parallels Lemma~2 in \cite{OCM2},                  % OCM WP3
which deals with ${\bf S}(\delta)$.
\begin{lemma}\label{lem:compl_success}
  The complementary success curve ${\bf C}:[0,1]\to[0,1]$
  always satisfies these properties:
  \begin{enumerate}
  \item\label{it:S1}
    There is a point $\delta_0\in[0,1]$
    (namely, the critical significance level)
    such that ${\bf C}(\delta)=0$ for $\delta\le\delta_0$
    and ${\bf C}(\delta)$ is concave for $\delta\ge\delta_0$.
  \item\label{it:S2}
    ${\bf C}'_{{\rm right}}(\delta_0)< \infty$ and ${\bf C}'_{{\rm left}}(1)\ge1$;
    therefore, for $\delta\in(\delta_0,1)$,
    $1\le{\bf C}'_{{\rm right}}(\delta)\le{\bf C}'_{{\rm left}}(\delta)<\infty$
    and the function ${\bf C}(\delta)$ is increasing.
  \item\label{it:S3}
    ${\bf C}(\delta)$ is continuous at $\delta=\delta_0$;
    therefore, it is continuous everywhere in $[0,1]$.
  \end{enumerate}
  If a function ${\bf C}:[0,1]\to[0,1]$ satisfies these properties,
  there exist a measurable space ${\bf X}$, a finite set ${\bf Y}$,
  and a probability distribution $P$ in ${\bf X}\times{\bf Y}$
  for which ${\bf C}$ is the complementary success curve.
\end{lemma}
\begin{proofsketch}
  The statement of the lemma follows from the fact
  that the complementary success curve ${\bf C}$
  can be obtained from the predictability distribution function $F$
  using these steps
  (labelling the horizontal and vertical axes as $x$ and $y$ respectively):
  \begin{enumerate}
  \item
    Invert $F$: $F_1:=F^{-1}$.
  \item
    Integrate $F_1$: $F_2(x):=\int_0^xF_1(t)dt$.
  \item
    Increase $F_2$: $F_3(x):=F_2(x)+\delta_0$, where $\delta_0:=\int_0^1F(x)dx$.
  \item
    Invert $F_3$: $F_4:=F_3^{-1}$.
%   (defining $F_4(x):=0$ for $x<\delta_0$).
  \end{enumerate}
  It can be shown that ${\bf C}=F_4$,
  if we define
  $
    g^{-1}(y)
    :=
    \sup\{x\st g(x)\le y\}
  $
  for non-decreasing $g$ (so that $g^{-1}$ is continuous on the right).
% \qedtext              % OCM WP3
\end{proofsketch}

Complement the protocol of \S\ref{sec:result}
in which Reality plays $P^{\infty}$ and Predictor plays $\Gamma$
with the following variables:
\begin{align*}
  \!\errOver_n
  &:=
  (P\times{\bf U})
  \bigl\{
    (x,y,\tau)
    \st
    y\notin\Gamma^{\delta}(x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x,\tau)
  \bigr\},
\\
  \!\uncOver_n
  &:=
  (P_{{\bf X}}\times{\bf U})
  \bigl\{
    (x,\tau)
    \st
    |\Gamma^{\delta}(x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x,\tau)|>1
  \bigr\},
\\
  \!\empOver_n
  &:=
  (P_{{\bf X}}\times{\bf U})
  \bigl\{
    (x,\tau)
    \st
    |\Gamma^{\delta}(x_1,\tau_1,y_1,\dots,x_{n-1},\tau_{n-1},y_{n-1},x,\tau)|=0
  \bigr\},
\end{align*}
\label{p:over}$\delta$ being fixed
and ${\bf U}$ standing for the uniform distribution in $[0,1]$,
and
$$
  \ErrOver_n
  :=
  \sum_{i=1}^n
  \errOver_i,
  \;\;\;\;
  \UncOver_n
  :=
  \sum_{i=1}^n
  \uncOver_i,
  \;\;\;\;
  \EmpOver_n
  :=
  \sum_{i=1}^n
  \empOver_i.
$$
%(we are not always consistent in the order of arguments of the function $\Gamma^{\delta}$).
By the martingale strong law of large numbers,
to prove the proposition it suffices to consider only these ``predictable'' versions
of $\Err_n$, $\Unc_n$, and $\Emp_n$:
indeed,
since $\Err_n-\ErrOver_n$, $\Unc_n-\UncOver_n$, and $\Emp_n-\EmpOver_n$
are martingales
(with increments bounded by 1 in absolute value)
with respect to the filtration $\FFF_n$, $n=0,1,\dots$,
where each $\FFF_n$ is generated by $(x_1,\tau_1,y_1),\dots,(x_n,\tau_n,y_n)$,
we have
\begin{align*}
  \lim_{n\to\infty}
  \frac{\Err_n-\ErrOver_n}{n}
  &=
  0
  \qquad
  \text{a.s.},\\
%$$%\quad\quad
%\mbox{and}
%\quad\quad
%$$
  \lim_{n\to\infty}
  \frac{\Unc_n-\UncOver_n}{n}
  &=
  0
  \qquad
  \text{a.s.},\\
%$$
\intertext{and}
%\quad\quad
%$$
  \lim_{n\to\infty}
  \frac{\Emp_n-\EmpOver_n}{n}
  &=
  0
  \qquad
  \text{a.s.}
\end{align*}
%(see, e.g., \cite{shiryaev:1996}, Theorem~VII.5.4).            % OCM WP3
\citep[See, e.g.,][Theorem~VII.5.4.]{shiryaev:1996}             % JMLR

\begin{figure}
  \centering
  \unitlength=0.5mm
  \begin{picture}(120,120)
    \put(10,20){\vector(1,0){110}}              % x axis
    \put(20,10){\vector(0,1){110}}              % y axis
    \put(20,100){\line(1,0){80}}                % bounding box
    \put(100,20){\line(0,1){80}}                % bounding box
    \put(120,18){\makebox(0,0)[ct]{$\beta$}}            % x axis label
    \put(18,120){\makebox(0,0)[rc]{$F(\beta)$}}         % y axis label
    \put(100,60){\line(-1,0){13}}               % finish the triangle
    \put(20,40){\line(1,0){80}}                 % line GD (via E)
    \put(100,100){\circle*{2}}                  % A
    \put(100,102){\makebox(0,0)[cb]{A}}         % A
    \put(100,60){\circle*{2}}                   % B
    \put(102,60){\makebox(0,0)[lc]{B}}          % B
    \put(86.86,60){\circle*{2}}                 % C
    \put(86,61.5){\makebox(0,0)[rb]{C}}         % C
    \put(100,40){\circle*{2}}                   % D
    \put(102,40){\makebox(0,0)[lc]{D}}          % D
    \put(20,40){\circle*{2}}                    % G
    \put(18,40){\makebox(0,0)[rc]{G}}           % G
    \put(75.5,40){\circle*{2}}                  % E
    \put(75,41.5){\makebox(0,0)[rb]{E}}         % E
    \put(100,20){\circle*{1}}                   % Z
    \put(100,18){\makebox(0,0)[ct]{Z}}          % Z
    \put(20,20){\circle*{1}}                    % O
    \put(18,18){\makebox(0,0)[rt]{O}}           % O
    \put(91,50){\makebox(0,0)[cc]{$\epsilon_n$}}                % \epsilon_n
    \multiput(20,60)(2,0){34}{\line(1,0){1}}                    % the dashed line from S(delta) to B
    \put(18,60){\makebox(0,0)[rc]{${\bf S}(\errOver_n-\empOver_n)$}}            % S(...)
%    \thicklines
%    \linethickness{1mm}
    \linethickness{0.5mm}
    \qbezier[2000](40,20)(80,20)(99.5,100)      % F's graph
    \put(20,20){\line(1,0){20}}                 % F's graph
  \end{picture}
  \caption{An admissible region predictor.
     The thick line is the predictability distribution function $F$;
     the area of the curvilinear triangle ABC is $\errOver_n-\empOver_n$;
     the area of the rectangle DZOG is $\empOver_n$;
     the (non-negative) area of the curvilinear quadrangle BDEC is denoted $\epsilon_n$
  \label{fig:Proof}}
\end{figure}

Without loss of generality we can assume that Predictor's move $\Gamma_n$ at trial $n$
is $\{\hat{y}(x_n)\}$
(where $x\mapsto\hat{y}(x)\in\arg\max_y P(y\givn x)$ is a fixed ``choice function'')
or the empty set $\emptyset$ or the whole label space ${\bf Y}$.
Furthermore, we can assume that, at every trial, the predictions are certain for the new objects
above the straight line BC in Figure~\ref{fig:Proof},\footnote{
More formally, predictions are certain for new extended objects $(x,\tau)$ satisfying
$$
  F(x,\tau)
  :=
  F(f(x)-)
  +
  \tau
  \left(
    F(f(x)+)
    -
    F(f(x)-)
  \right)
  \ge
  {\bf S}(\errOver_n-\empOver_n).
$$
Intuitively, considering extended objects makes the vertical axis ``infinitely divisible''.}
and that the predictions are empty for the objects below the straight line DG
in Figure~\ref{fig:Proof}.\footnote{Indeed, predictions of this kind are admissible in the sense
that we cannot improve $\uncOver_n$ and $\empOver_n$ simultaneously,
and all admissible predictions are equivalent to predictions of this kind.
A formal argument for the case where $\emp_n$ are omitted is given
in~\cite{vovk:2002ALTforJMLR}.}                      % JMLR
%in~\cite{OCM2}.)                                       % OCM WP3
It is clear that for the region predictor to satisfy (\ref{eq:opt})
it must hold that
$$
  \lim_{n\to\infty}
  \frac1n
  \sum_{i=1}^n
  (\epsilon_i\wedge\empOver_i)
  =
  0
$$
(otherwise $\UncOver_n$ can be decreased substantially,
which contradicts (\ref{eq:lower});
$\epsilon_i$ are defined in the caption of Figure \ref{fig:Proof}),
and so we can assume, without loss of generality, that
either $\epsilon_n=0$ or $\empOver_n=0$ at every trial $n$,
i.e., that
%\begin{equation}\label{eq:hole}
$$
  \uncOver_n = {\bf S}(\errOver_n),
  \quad
  \empOver_n = {\bf C}(\errOver_n)
$$
%\end{equation}
at every trial.

Let us check that to achieve~(\ref{eq:opt})
the region predictor must satisfy
\begin{align}
  \delta<\delta_0
  &\Longrightarrow
  \limsup_{n\to\infty}
  \frac1n
  \sum_{i=1}^n
  \left(
    \errOver_i - \delta_0
  \right)^{+}
  =
  0
  \label{eq:less}
\\
  \delta\ge\delta_0
  &\Longrightarrow
  \limsup_{n\to\infty}
  \frac1n
  \sum_{i=1}^n
  \left(
    \delta_0 - \errOver_i
  \right)^{+}
  =
  0,
  \label{eq:more}
\end{align}
where the convergence is, as usual, almost certain.
It was shown in \cite{vovk:2002ALTforJMLR}     % JMLR
(Lemma~2) that the success curve ${\bf S}$
is convex, non-increasing, continuous,
and has slope at most $-1$ before it hits the $x$ axis at $\delta=\delta_0$.
The second implication, (\ref{eq:more}), now immediately follows
from the fact that, under $\delta\ge\delta_0$ and (\ref{eq:opt}),
$$
  0
  =
  \limsup_{n\to\infty}
  \frac{\UncOver_n}{n}
  =
  \limsup_{n\to\infty}
  \frac1n
  \sum_{i=1}^n
  {\bf S}(\errOver_i)
  \ge
  \limsup_{n\to\infty}
  \frac1n
  \sum_{i=1}^n
  \left(
    \delta_0
    -
    \errOver_i
  \right)^{+}.
$$
The first implication, (\ref{eq:less}),
can be extracted from the chain
\begin{equation}\label{eq:chain}
  \frac{\UncOver_n}{n}
  =
  \frac{1}{n}
  \sum_{i=1}^n \uncOver_i
  =
  \frac{1}{n}
  \sum_{i=1}^n {\bf S}(\errOver_i)
  \ge
  {\bf S}
  \left(
    \frac{1}{n}
    \sum_{i=1}^n \errOver_i
  \right)
  =
  {\bf S}
  \left(
    \frac{\ErrOver_n}{n}
  \right)
  \ge
  {\bf S}(\delta) - \epsilon
\end{equation}
(with the last inequality holding almost surely
for an arbitrary $\epsilon>0$ from some $n$ on)
%used in~\cite{OCM2}                                    % OCM WP3
%(Proof of Theorems~1 and~1r)                           % OCM WP3
used by Vovk (2002b, in the proof of Theorems~1 and~1r).                                  % JMLR
Indeed, it can be seen from (\ref{eq:chain}) that,
assuming the predictor is well-calibrated and optimal and $\delta<\delta_0$,
$$
  \ErrOver_n/n\to\delta
  \quad
  \text{a.s.}
$$
and, therefore,
\begin{multline*}
  {\bf S}(\delta)
  \ge
  \limsup_{n\to\infty}
  \frac{\UncOver_n}{n}
  =
  \limsup_{n\to\infty}
  \frac{1}{n}
  \sum_{i=1}^n {\bf S}(\errOver_i)
  =
  \limsup_{n\to\infty}
  \frac{1}{n}
  \sum_{i=1}^n {\bf S}(\errOver_i \wedge \delta_0)
\\
  \ge
  \limsup_{n\to\infty}
  {\bf S}
  \left(
    \frac{1}{n}
    \sum_{i=1}^n (\errOver_i \wedge \delta_0)
  \right)
  =
  \limsup_{n\to\infty}
  {\bf S}
  \left(
    \frac{\ErrOver_n}{n}
    -
    \frac1n
    \sum_{i=1}^n
    \left(
      \errOver_i - \delta_0
    \right)^{+}
  \right)
\\
  =
  \limsup_{n\to\infty}
  {\bf S}
  \left(
    \delta
    -
    \frac1n
    \sum_{i=1}^n
    \left(
      \errOver_i - \delta_0
    \right)^{+}
  \right)
  =
  {\bf S}
  \left(
    \delta
    -
    \limsup_{n\to\infty}
    \frac1n
    \sum_{i=1}^n
    \left(
      \errOver_i - \delta_0
    \right)^{+}
  \right)
\end{multline*}
almost surely.
This proves (\ref{eq:less}).

Using (\ref{eq:less}), (\ref{eq:more}),
and the fact that the complementary success curve ${\bf C}$
is concave, increasing, and (uniformly) continuous
for $\delta\ge\delta_0$
(see Lemma~\ref{lem:compl_success}),
we obtain:
if $\delta<\delta_0$,
\begin{align*}
  \frac{\EmpOver_n}{n}
  &=
  \frac{1}{n}
  \sum_{i=1}^n \empOver_i
  =
  \frac{1}{n}
  \sum_{i=1}^n {\bf C}(\errOver_i)
\\
  &\le
  \frac1n
  {\bf C}'_{{\rm right}}(\delta_0)
  \sum_{i=1}^n
  \left(
    \errOver_i - \delta_0
  \right)^{+}
  \to
  0
  \quad
  (n\to\infty);
\end{align*}
if $\delta\ge\delta_0$,
\begin{align*}
  \frac{\EmpOver_n}{n}
  &=
  \frac{1}{n}
  \sum_{i=1}^n {\bf C}(\errOver_i)
  =
  \frac{1}{n}
  \sum_{i=1}^n {\bf C}(\errOver_i \binmax \delta_0)
\\
  &\le
  {\bf C}
  \left(
    \frac{1}{n}
    \sum_{i=1}^n (\errOver_i \binmax \delta_0)
  \right)
  =
  {\bf C}
  \left(
    \frac{1}{n}
    \sum_{i=1}^n \errOver_i
    +
    \frac{1}{n}
    \sum_{i=1}^n (\delta_0 - \errOver_i)^{+}
  \right)
\\
  &\le
  {\bf C}
  \left(
    \frac{1}{n}
    \sum_{i=1}^n \errOver_i
  \right)
  +
  o(1)
  \le
  {\bf C}(\delta) + \epsilon,
\end{align*}
the last inequality holding almost surely for an arbitrary $\epsilon>0$ from some $n$ on
and $\delta$ being the significance level used.

\subsection{Proof Sketch of Proposition~\ref{prop:upper}}

Let us first modify and extend the notation $P^{\ne}_n(y\givn x_i,\sigma_i)$
introduced in~(\ref{eq:cond}).
Consider the sequence of extended examples $w_i=(x_i,\tau'_i,y_i)$,
$i=1,\dots,n$
($(x_i,y_i)$ are the first $n$ examples chosen by Reality
and $\tau_i$ are the random numbers used by Predictor).
We define the Nearest Neighbours approximations $P_n(y\givn x,\sigma)$
to the conditional probabilities $P(y\givn x)$ as follows:
for every $(x,\sigma,y)\in\tilde{{\bf Z}}$,
\begin{equation}\label{eq:P_n}
  P_n(y\givn x,\sigma)
  :=
  N(x,\sigma,y) / K_n,
\end{equation}
where
$N(x,\sigma,y)$ is the number of $i=1,\dots,n$
such that $(x_i,\tau'_i)$ is among the $K_n$ nearest neighbours of $(x,\sigma)$ and $y_i=y$
(this time $(x_i,\tau'_i)$ is not prevented from being counted
as one of the $K_n$ nearest neighbours of $(x,\sigma)$
if $(x_i,\tau'_i)=(x,\sigma)$).
We define the empirical predictability function $f_n$ by
\begin{equation}\label{eq:f_n}
  f_n(x,\sigma)
  :=
  \max_{y\in{\bf Y}}
  P_n(y\givn x,\sigma).
\end{equation}

%Our first goal is to prove~(\ref{eq:main}).
The proof will be based on the following version
of a well-known fundamental result.
\begin{lemma}\label{lem:DGKL}
  Suppose $K_n\to\infty$, $K_n=o(n)$, and ${\bf Y}=\{0,1\}$.
  For any $\epsilon>0$ and large enough $n$,
  $$
    \Prob
    \left\{
      \int
      \left|
        P(1\givn x)-P_n(1\givn x,\sigma)
      \right|
      P_{{\bf X}}(dx)
      {\bf U}(d\sigma)
      >
      \epsilon
    \right\}
    \le
    e^{-n\epsilon^2/40},
  $$
  where the outermost probability distribution $\Prob$
  (essentially $(P\times{\bf U})^{\infty}$)
  generates the extended examples $(x_i,\tau_i,y_i)$,
  which determine the empirical distributions $P_n$.
\end{lemma}
\begin{proof}
  This is almost a special case of
% Devroye et al.'s \cite{devroye/etal:1994}                             % OCM WP3
  \citeauthor{devroye/etal:1994}'s (\citeyear{devroye/etal:1994})       % JMLR
  Theorem~1.
% (replace ${\bf Y}=\{0,1\}$ by ${\bf Y}=\{-1/2,1/2\}$
% and set $M=1/2$ and $\gamma_d=\gamma_1=2$).
  There is, however, an important difference
  between the way we break distance ties
% and the way Devroye et al.~\cite{devroye/etal:1994} do this:          % OCM WP3
  and the way \cite{devroye/etal:1994} do this. In that work, instead of our~(\ref{eq:closeness}),    % JMLR
  $$
    \left(
      |x_1-x_3|,
      |\sigma_1-\sigma_3|
    \right)
    <
    \left(
      |x_2-x_3|,
      |\sigma_2-\sigma_3|
    \right)
  $$
  is used.
  (Our way of breaking ties better agrees with the lexicographic order
  on $[0,1]^2$,
  which is useful in the proof of Proposition~\ref{prop:time} and,
  less importantly,
  in the proof of Lemma~\ref{lem:Mc}.)
  It is easy to check that the proof given by~\cite{devroye/etal:1994}         % JMLR
  also works (and becomes simpler)
  for our way of breaking distance ties.
% \qedtext              % OCM WP3
\end{proof}
\begin{lemma}\label{lem:basic}
  Suppose $K_n\to\infty$ and $K_n=o(n)$.
  For any $\epsilon>0$ there exists an $\epsilon^*>0$ such that,
  for large enough $n$,
  $$
    \Prob
    \left\{
      (P_{{\bf X}}\times{\bf U})
      \left\{
        (x,\sigma)
        \st
        \max_{y\in{\bf Y}}
        |P_n(y\givn x,\sigma)-P(y\givn x)|>\epsilon
      \right\}
      >
      \epsilon
    \right\}
    \le
    e^{-\epsilon^* n};
  $$
  in particular,
  $$
    \Prob
    \bigl\{
      (P_{{\bf X}}\times{\bf U})
      \left\{
        (x,\sigma)
        \st
        |f_n(x,\sigma)-f(x)|>\epsilon
      \right\}
      >
      \epsilon
    \bigr\}
    \le
    e^{-\epsilon^* n}.
  $$
\end{lemma}
\begin{proof}
  We apply Lemma~\ref{lem:DGKL} to the binary classification problem
  obtained from our classification problem
  by replacing label $y\in{\bf Y}$ with 1 and replacing all other labels with 0:
%  \begin{equation}\label{eq:aux1}
  $$
    \Prob
    \left\{
      \int
      \left|
        P(y\givn x)-P_n(y\givn x,\sigma)
      \right|
      P_{{\bf X}}(dx)
      {\bf U}(d\sigma)
      >
      \epsilon
    \right\}
    \le
    e^{-n\epsilon^2/40}.
  $$
%  \end{equation}
  By Markov's inequality this implies
  $$
    \Prob
    \left\{
      (P_{{\bf X}}\times{\bf U})
      \{
        |P(y\givn x)-P_n(y\givn x,\sigma)| > \sqrt{\epsilon}
      \}
      >
      \sqrt{\epsilon}
    \right\}
    \le
    e^{-n\epsilon^2/40},
  $$
  which, in turn, implies
  $$
    \Prob
    \left\{
      (P_{{\bf X}}\times{\bf U})
      \left\{
        \max_{y\in{\bf Y}} |P(y\givn x)-P_n(y\givn x,\sigma)| > \sqrt{\epsilon}
      \right\}
      >
      |{\bf Y}| \sqrt{\epsilon}
    \right\}
    \le
    e^{-n\epsilon^2/40}.
  $$
  This completes the proof, since we can take the $\epsilon$ in the last equation
  arbitrarily small as compared to the $\epsilon$ in the statement of the lemma.
% \qedtext              % OCM WP3
\end{proof}

We will use the shorthand ``$\forall^{\infty}n$'' for ``from some $n$ on''.
\begin{lemma}\label{lem:Mc}
  Suppose $K_n\to\infty$ and $K_n=o(n)$.
  For any $\epsilon>0$ there exists an $\epsilon^*>0$ such that,
  for large enough $n$,
  $$
    \Prob
    \left\{
      \frac
      {
        \#
        \left\{
          i
          \st
          \max_y
          \left|
            P(y\givn x_i) - P^{\ne}_n(y\givn x_i,\tau'_i)
          \right|
          >
          \epsilon
        \right\}
      }
      {n}
      >
      \epsilon
    \right\}
    \le
    e^{-\epsilon^* n}.
  $$
  In particular,
  $$
    \forall^{\infty}n:
    \Prob
    \left\{
      \frac
      {
        \#
        \left\{
          i
          \st
          \left|
            f(x_i) - f^{\ne}_n(x_i,\tau'_i)
          \right|
          >
          \epsilon
        \right\}
      }
      {n}
      >
      \epsilon
    \right\}
    \le
    e^{-\epsilon^* n}.
  $$
\end{lemma}
\begin{proof}
  Since
  $$
    \left|
      P^{\ne}_n(y\givn x_i,\tau'_i)
      -
      P_n(y\givn x_i,\tau'_i)
    \right|
    \le
    \frac{1}{K_n}
    =
    o(1),
  $$
  we can, and will, ignore the upper indices ${}^{\ne}$ in the statement of the lemma.

  Define
  $$
    I_n(x,\sigma)
    :=
    \begin{cases}
      0 \quad\quad\quad \text{if $\max_y |P(y\givn x)-P_n(y\givn x,\sigma)| \le \epsilon$}\\
      1 \quad\quad\quad \text{if $\max_y |P(y\givn x)-P_n(y\givn x,\sigma)| \ge 2\epsilon$}\\
      (\max_y |P(y\givn x)-P_n(y\givn x,\sigma)| - \epsilon) / \epsilon \quad \text{otherwise}
    \end{cases}
  $$
  (intuitively, $I_n(x,\sigma)$ is a ``soft version''
  of $\III_{\{\max_y |P(y\givn x)-P_n(y\givn x,\sigma)|>\epsilon\}}$).

  The main tool in this proof
  (and several other proofs in this section)
  will be McDiarmid's theorem
%  (see, e.g., \cite{devroye/etal:1996}, Theorem~9.2).          % OCM WP3
  \cite[see, e.g.,][Theorem~9.2]{devroye/etal:1996}.            % JMLR
  First we check the possibility of its application.
  If we replace an extended object $(x_j,\tau'_j)$
  by another extended object $(x_j^*,\tau^*_j)$,
  the expression
  $$
    \sum_{i=1}^n
    I_n(x_i,\tau'_i)
  $$
  will change as follows:
  \begin{itemize}
  \item
    the addend $I_n(x_i,\tau'_i)$ for $i=j$ changes by $1$ at most;
  \item
    the addends $I_n(x_i,\tau'_i)$ for $i\ne j$ such that
    neither $(x_j,\tau'_j)$ nor $(x_j^*,\tau_j^*)$
    are among the $K_n$ nearest neighbours of $(x_i,\tau'_i)$
    do not change at all;
  \item
    the sum over the at most $4K_n$ (see below) addends $I_n(x_i,\tau'_i)$
    for $i\ne j$ such that
    either $(x_j,\tau'_j)$ or $(x_j^*,\tau_j^*)$ (or both)
    are among the $K_n$ nearest neighbours of $(x_i,\tau'_i)$
    can change by at most
    \begin{equation}\label{eq:change}
      4 K_n \frac{1}{\epsilon} \frac{1}{K_n}
      =
      \frac{4}{\epsilon}.
    \end{equation}
  \end{itemize}
  The left-hand side of~(\ref{eq:change}) reflects the following facts:
  the change in $P_n(y\givn x_i,\tau'_i)$ for $i\ne j$ is at most $1/K_n$;
  the number of $i\ne j$ such that
  $(x_j,\tau'_j)$ is among the $K_n$ nearest neighbours of $(x_i,\tau'_i)$
  does not exceed $2K_n$
  (since the extended objects are linearly ordered
  and~(\ref{eq:closeness}) is used for breaking distance ties);
  analogously, the number of $i\ne j$ such that
  $(x^*_j,\tau^*_j)$ is among the $K_n$ nearest neighbours of $(x_i,\tau'_i)$
  does not exceed $2K_n$.

  Therefore, by McDiarmid's theorem,
  \begin{multline}\label{eq:Mc}
    \Prob
    \left\{
      \frac1n
      \sum_{i=1}^n
      I_n(x_i,\tau'_i)
      -
      \Expect
      \left(
        \frac1n
        \sum_{i=1}^n
        I_n(x_i,\tau'_i)
      \right)
      >
      \epsilon
    \right\}
  \\
    {}\le
    \exp
    \left(
      -2\epsilon^2n
      /
      \left(
        1 + 4/\epsilon
      \right)^2
    \right)
    =
    \exp
    \left(
      -
      \frac{2\epsilon^4}{(4+\epsilon)^2}
      n
    \right).
  \end{multline}
  Next we find:
  \begin{align*}
    &\Expect
    \left(
      \frac1n
      \sum_{i=1}^n
      I_n(x_i,\tau'_i)
    \right)
    =
    \Expect
    \left(
      I_n(x_n,\tau'_n)
    \right)
    \le
    \Expect
    \left(
      I_{n-1}(x_n,\tau'_n)
    \right)
    +
%    \frac{1}{\epsilon K_n}
    o(1)
  \\
    &\le
    \Expect
    (P_{{\bf X}}\times{\bf U})
    \{
      (x,\sigma)
      \st
      \max_y |P(y\givn x)-P_{n-1}(y\givn x,\sigma)|>\epsilon
    \}
    +
%    \frac{1}{\epsilon K_n}
    o(1)
  \\
    &\le
    e^{-\epsilon^*n}
    +
    \epsilon
    +
%    \frac{1}{\epsilon K_n}
    o(1)
    \le
    2\epsilon
  \end{align*}
  (the penultimate inequality follows from Lemma~\ref{lem:basic})
  from some $n$ on.
  In combination with (\ref{eq:Mc}) this implies
  $$
    \forall^{\infty}n:
    \Prob
    \left\{
      \frac1n
      \sum_{i=1}^n
      I_n(x_i,\tau'_i)
      >
      3\epsilon
    \right\}
    \le
    \exp
    \left(
      -
      \frac{2\epsilon^4}{(4+\epsilon)^2}
      n
    \right),
  $$
  in particular
  $$
    \Prob
    \left\{
      \frac
      {
        \#
        \left\{
          i
          \st
          \max_y
          \left|
            P(y\givn x_i)-P_n(y\givn x_i,\tau'_i)
          \right|
          \ge
          2\epsilon
        \right\}
      }
      {n}
      >
      3\epsilon
    \right\}
    \le
    \exp
    \left(
      -
      \frac{2\epsilon^4}{(4+\epsilon)^2}
      n
    \right).
  $$
  Replacing $3\epsilon$ by $\epsilon$, we obtain that, from some $n$ on,
  $$
    \Prob
    \left\{
      \frac
      {
        \#
        \left\{
          i
          \st
          \max_y
          \left|
            P(y\givn x_i)-P_n(y\givn x_i,\tau'_i)
          \right|
          >
          \epsilon
        \right\}
      }
      {n}
      >
      \epsilon
    \right\}
    \le
    \exp
    \left(
      -
      \frac{2(\epsilon/3)^4}{(4+\epsilon/3)^2}
      n
    \right),
  $$
  which completes the proof.
% \qedtext              % OCM WP3
\end{proof}

We say that an extended example $(x_i,\tau_i,y_i)$,
$i=1,\dots,n$, is \emph{$n$-strange} if $y_i\ne\hat{y}_n(x_i,\tau'_i)$;
otherwise, $(x_i,\tau_i,y_i)$ will be called \emph{$n$-ordinary}.
We will assume that
$(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$, $i=1,\dots,n$,
are all different for all $n$;
even more than that,
we will assume that $\tau''_i$ are all different
(we can do so since the probability of this event is one).
\begin{lemma}\label{lem:main1}
  Suppose~(\ref{eq:K}) is satisfied and $\delta\le\delta_0$.
  With probability one,
  the $\lfloor(1-{\bf S}(\delta))n\rfloor$ extended examples with the largest
  (in the sense of the lexicographic order) $(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$
  among $(x_1,\tau_1,y_1),\dots,(x_n,\tau_n,y_n)$
  contain at most $n\delta+o(n)$ $n$-strange extended examples as $n\to\infty$.
\end{lemma}
\begin{proof}
  Define
  $$
    c
    :=
    \sup\{\beta\st F(\beta)\le{\bf S}(\delta)\}.
  $$
  It is clear that $0<c<1$.
%  our assumption $\delta<\delta_0$ implies $c>0$.
  Our proof will work both in the case
  where $F(c)={\bf S}(\delta)$
  and in the case where $F(c)>{\bf S}(\delta)$,
  as illustrated in Figure~\ref{fig:cases}.

  \begin{figure}[bt]
    \unitlength=0.5mm
    \centering
    \begin{picture}(120,120)
      \put(10,20){\vector(1,0){110}}                            % x axis
      \put(20,10){\vector(0,1){110}}                            % y axis
      \put(20,100){\line(1,0){80}}                              % bounding box
      \put(100,20){\line(0,1){80}}                              % bounding box
      \put(118,18){\makebox(0,0)[ct]{$\beta$}}                  % x axis label
      \put(19,116){\makebox(0,0)[rc]{$F(\beta)$}}               % y axis label
      \put(100,60){\line(-1,0){13}}                             % finish the triangle
      \put(100,100){\circle*{2}}                                % A
      \put(20,20){\circle*{2}}                                  % O
      \put(86.86,60){\circle*{2}}                               % C
      \multiput(20,60)(2,0){34}{\line(1,0){1}}                          % the dashed line from S(delta)
      \put(18,60){\makebox(0,0)[rc]{${\bf S}(\delta)$}}                 % S(delta)
      \multiput(86.86,20)(0,2){40}{\line(0,1){1}}               % the dashed line from c up
      \put(86.86,20){\circle*{1.6}}                             % c
      \multiput(78.86,20)(0,2){40}{\line(0,1){1}}                       % the dashed line from c-2epsilon up
      \multiput(82.86,20)(0,2){40}{\line(0,1){1}}                       % the dashed line from c-epsilon up
      \multiput(90.86,20)(0,2){40}{\line(0,1){1}}                       % the dashed line from c+epsilon up
      \multiput(94.86,20)(0,2){40}{\line(0,1){1}}                       % the dashed line from c+2epsilon up
      \put(86.86,18){\makebox(0,0)[ct]{$c$}}                    % c
      \put(80.86,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}            % epsilon
      \put(84.86,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}            % epsilon
      \put(88.86,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}            % epsilon
      \put(92.86,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}            % epsilon
%      \linethickness{1mm}
      \linethickness{0.5mm}
      \qbezier[2000](40,20)(80,20)(99.5,100)                    % F's graph
      \put(20,20){\line(1,0){20}}                               % F's graph
    \end{picture}
    \qquad
    \unitlength=0.5mm
    \begin{picture}(120,120)
      \put(10,20){\vector(1,0){110}}                            % x axis
      \put(20,10){\vector(0,1){110}}                            % y axis
      \put(20,100){\line(1,0){80}}                              % bounding box
      \put(100,20){\line(0,1){80}}                              % bounding box
      \put(118,18){\makebox(0,0)[ct]{$\beta$}}                  % x axis label
      \put(19,116){\makebox(0,0)[rc]{$F(\beta)$}}               % y axis label
      \put(100,100){\circle*{2}}                                % A
      \put(20,20){\circle*{2}}                                  % O
      \multiput(20,60)(2,0){40}{\line(1,0){1}}                          % the dashed line from S(delta)
      \put(18,60){\makebox(0,0)[rc]{${\bf S}(\delta)$}}                 % S(delta)
      \put(80,60){\circle*{1}}                                          % dot
      \put(80,70){\circle*{1}}                          % dot
      \multiput(80,20)(0,2){40}{\line(0,1){1}}          % the dashed line from c up
      \put(80,50){\line(0,1){30}}                       % the solid part of the line from c up
      \put(80,20){\circle*{1.6}}                        % c
      \multiput(72,20)(0,2){40}{\line(0,1){1}}          % the dashed line from c-2epsilon up
      \multiput(76,20)(0,2){40}{\line(0,1){1}}          % the dashed line from c-epsilon up
      \multiput(84,20)(0,2){40}{\line(0,1){1}}          % the dashed line from c+epsilon up
      \multiput(88,20)(0,2){40}{\line(0,1){1}}          % the dashed line from c+2epsilon up
      \put(80,18){\makebox(0,0)[ct]{$c$}}               % c
      \put(74,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}       % epsilon
      \put(78,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}       % epsilon
      \put(82,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}       % epsilon
      \put(86,28){\makebox(0,0)[cc]{{\small $\epsilon$}}}       % epsilon
%      \linethickness{1mm}
      \linethickness{0.5mm}
      \put(20,20){\line(1,0){20}}                       % F's graph
      \qbezier[2000](40,20)(60,20)(79.5,50)             % F's graph
      \qbezier[2000](80,80.5)(90,90.5)(99.5,100)        % F's graph
      \put(80,80){\circle*{2}}                          % end-point
    \end{picture}
    \caption{Cases $F(c)={\bf S}(\delta)$ (left) and $F(c)>{\bf S}(\delta)$ (right).
        The vertical bands of width $\epsilon$ determine
        the division of the first $n$ extended examples
        into five classes
    \label{fig:cases}}
  \end{figure}

  Let $\epsilon>0$ be a small constant (we will let $\epsilon\to0$ eventually).
  Define a ``threshold'' $(c'_n,c''_n)\in[0,1]^2$ requiring that
  \begin{equation}\label{eq:def}
    \Prob
    \left\{
      f(x_n)=c,
      (f_{n-1}(x_n,\tau'_n),\tau''_n) > (c'_n,c''_n)
    \right\}
    =
    F(c) - {\bf S}(\delta) - \epsilon
  \end{equation}
  if $F(c)>{\bf S}(\delta)$;
  we assume that $\epsilon$ is small enough for
  \begin{equation}\label{eq:epsilon}
    2\epsilon
    <
    F(c) - {\bf S}(\delta)
  \end{equation}
  to hold
  . Among other things this will ensure the validity of the definition~(\ref{eq:def}).
  If $F(c)={\bf S}(\delta)$,
  we set $(c'_n,c''_n):=(c+\epsilon,0)$;
  in any case, we will have
  \begin{equation}\label{eq:defA}
    \Prob
    \left\{
      f(x_n)=c,
      (f_{n-1}(x_n,\tau'_n),\tau''_n) > (c'_n,c''_n)
    \right\}
    \ge
    F(c) - {\bf S}(\delta) - \epsilon.
  \end{equation}

  Let us say that an extended example $(x_i,\tau_i,y_i)$ is
  \emph{above the threshold} if
  $$
    (f^{\ne}_n(x_i,\tau'_i),\tau''_i)
    >
    (c'_n,c''_n);
  $$
  otherwise,
  we say it is \emph{below the threshold}.
  Divide the first $n$ extended examples $(x_i,\tau_i,y_i)$, $i=1,\dots,n$,
  into five classes:
  \begin{description}
  \item[Class I:]
    Those satisfying $f(x_i) \le c-2\epsilon$.
  \item[Class II:]
    Those that satisfy $f(x_i)=c$ and are below the threshold.
  \item[Class III:]
    Those satisfying $c-2\epsilon < f(x_i) \le c+2\epsilon$
    but not $f(x_i)=c$.
  \item[Class IV:]
    Those that satisfy $f(x_i)=c$ and are above the threshold.
  \item[Class V:]
    Those satisfying $f(x_i) > c+2\epsilon$.
  \end{description}
  First we explain the general idea of the proof.
  The threshold $(c',c'')$ was chosen so that
  approximately $\lfloor(1-{\bf S}(\delta))n\rfloor$
  of the available extended examples
  will be above the threshold.
  Because of this,
  the extended examples above the threshold will essentially be
  the $\lfloor(1-{\bf S}(\delta))n\rfloor$ extended examples
  with the largest $(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$
  referred to in the statement of the lemma.
  For each of the five classes
  we will be interested in the following questions:
  \begin{itemize}
  \item
    How many extended examples are there in the class?
  \item
    How many of those are above the threshold?
  \item
    How many of those above the threshold are $n$-strange?
  \end{itemize}
  If the sum of the answers to the last question does not exceed $n\delta$
  by too much, we are done.

  With this plan in mind, we start the formal proof.
  (Of course, we will not be following the plan literally:
  for example, if a class is very small,
  we do not need to answer the second and third questions.)
  The first step is to show that
  \begin{equation}\label{eq:separation}
    c-\epsilon
    \le
    c'_n
    \le
    c+\epsilon
  \end{equation}
  from some $n$ on;
  this will ensure that the classes are conveniently separated from each other.
  We only need to consider the case $F(c) > {\bf S}(\delta)$.
  The inequality $c'_n\le c+\epsilon$ follows from
  $$
    \forall^{\infty}n:
    \Prob
    \left\{
      f(x_n)=c,
      f_{n-1}(x_n,\tau'_n) > c+\epsilon
    \right\}
    <
    \epsilon
    <
    F(c) - {\bf S}(\delta) - \epsilon
  $$
  Simply combine Lemma~\ref{lem:basic} with~(\ref{eq:epsilon}).
  The inequality $c-\epsilon\le c'_n$ follows in a similar way from
  \begin{align*}
    \forall^{\infty}n:{}\quad&
    \Prob
    \left\{
      f(x_n)=c,
      f_{n-1}(x_n,\tau'_n) \ge c-\epsilon
    \right\}
  \\
    &{}=
    \Prob\{f(x_n)=c\}
    -
    \Prob
    \left\{
      f(x_n)=c,
      f_{n-1}(x_n,\tau'_n) < c-\epsilon
    \right\}
  \\
    &>
    F(c) - F(c-) - \epsilon
    \ge
    F(c) - {\bf S}(\delta) - \epsilon.
  \end{align*}

  Now we are ready to analyze the composition of our five classes.
  Among the Class~I extended examples at most
  \begin{equation}\label{eq:Cl1Q2}
    \epsilon n
  \end{equation}
  will be above the threshold from some $n$ on almost surely
  (by Lemma~\ref{lem:Mc} and the Borel--Cantelli lemma).
  None of the Class~II extended examples will be above the threshold, by definition.
  The fraction of Class~III extended examples
  among the first $n$ extended examples
  will tend to
  \begin{equation}\label{eq:Cl3Q1}
    F(c+2\epsilon)-F(c)
    +F(c-)-F(c-2\epsilon)
  \end{equation}
  as $n\to\infty$ almost surely.

  To estimate the number $N_n^{{\rm IV}}$ of Class~IV extended examples
  among the first $n$ extended examples,
  we use McDiarmid's theorem.
  If one extended example is replaced by another,
  $N_n^{{\rm IV}}$ will change by at most $2K_n+1$
  (since this extended example can affect $f_n^{\ne}(x_i,\tau'_i)$
  for at most $2K_n$ other extended examples $(x_i,\tau_i,y_i)$).
  Therefore,
  $$
    \Prob
    \left\{
      \left|
        \frac1n N_n^{{\rm IV}}
        -
        \frac1n \Expect N_n^{{\rm IV}}
      \right|
      \ge
      \epsilon
    \right\}
    \le
    2 e^{-2\epsilon^2n/(2K_n+1)^2};
  $$
  the assumption $K_n = o\left(\sqrt{n/\ln n}\right)$
  and the Borel--Cantelli lemma imply that
  $$
    \left|
      \frac1n N_n^{{\rm IV}}
      -
      \frac1n \Expect N_n^{{\rm IV}}
    \right|
    <
    \epsilon
  $$
  from some $n$ on almost surely.
  Since
  $$
    \frac1n \Expect N_n^{{\rm IV}}
    =
    \Prob
    \left\{
      f(x_n)=c,
      (f_{n-1}(x_n,\tau'_n),\tau''_n) > (c'_n,c''_n)
    \right\}
    \ge
    F(c) - {\bf S}(\delta) - \epsilon,
  $$
  as in~(\ref{eq:defA}),
  we have
  \begin{equation}\label{eq:Cl4Q2}
    N_n^{{\rm IV}}
    >
    (F(c) - {\bf S}(\delta) - 2\epsilon) n
  \end{equation}
  from some $n$ on almost surely.
  Of course, all these examples are above the threshold.

  Now we estimate the number $N_n^{{\rm IV,str}}$
  of $n$-strange extended examples of Class~IV.
  Again McDiarmid's theorem implies that
  $$
    \left|
      \frac1n N_n^{{\rm IV,str}}
      -
      \frac1n \Expect N_n^{{\rm IV,str}}
    \right|
    <
    \epsilon
  $$
  from some $n$ on almost surely.
  Now, from some $n$ on,
  \begin{align}
    \frac1n \Expect N_n^{{\rm IV,str}}
    &=
    \Prob
    \left\{
      f(x_n)=c,
      (f_{n-1}(x_n,\tau'_n),\tau''_n) > (c'_n,c''_n),
      \hat y_n(x_n,\tau'_n) \ne y_n
    \right\}
    \nonumber
  \\
    &=
    \Expect
    \left(
      \left(
        1
        -
        P_{{\bf Y}\givn{\bf X}}
        \left(
          \hat y_n(x_n,\tau'_n) \givn x_n
        \right)
      \right)
      \III_{\{f(x_n)=c,(f_{n-1}(x_n,\tau'_n),\tau''_n) > (c'_n,c''_n)\}}
    \right)
    \nonumber
  \\
    &\le
    e^{-\epsilon^* n} + \epsilon
    +
    (1 - c + 2\epsilon)
    \nonumber
  \\
    &\quad\times
    \Prob\{f(x_n)=c,(f_{n-1}(x_n,\tau'_n),\tau''_n) > (c'_n,c''_n)\}
    \nonumber
  \\
    &=
    e^{-\epsilon^* n} + \epsilon
    +
    (1 - c + 2\epsilon)
    (F(c) - {\bf S}(\delta) - \epsilon)
    \label{eq:L1}
  \\
    &\le
    (F(c) - {\bf S}(\delta))
    (1 - c)
    +
    4\epsilon
    \label{eq:L2}
  \end{align}
  in the case $F(c) > {\bf S}(\delta)$;
  the first inequality in this chain
  follows from Lemma~\ref{lem:basic}:
  indeed,
  this lemma implies that,
  unless an event of the small probability $e^{-\epsilon^{*}n}+\epsilon$ happens,
  \begin{equation}\label{eq:explan}
    P
    \left(
      \hat y_n(x_n,\tau'_n) \givn x_n
    \right)
    \ge
    P_{n-1}
    \left(
      \hat y_n(x_n,\tau'_n) \givn x_n,\tau'_n
    \right)
    -
    \epsilon
    =
    f_{n-1}
    \left(
      x_n,\tau'_n
    \right)
    -
    \epsilon
    \ge
    f(x_n)-2\epsilon.
  \end{equation}
  If $F(c) = {\bf S}(\delta)$,
  the lines~(\ref{eq:L1}) and~(\ref{eq:L2}) of that chain
  have to be changed to
  \begin{align*}
    &\le
    e^{-\epsilon^* n} + \epsilon
    +
    (1 - c + 2\epsilon)
% \\
%   &\quad\times
    \Prob\{f(x_n)=c,f_{n-1}(x_n,\tau'_n) \ge c+\epsilon\}
  \\
    &\le
    e^{-\epsilon^* n} + \epsilon
    +
    (1 - c + 2\epsilon)
    \left(
      e^{-\epsilon^* n} + \epsilon
    \right)
% \\
%   &
    <
    4\epsilon
  \end{align*}
  (where the obvious modification of Lemma~\ref{lem:basic}
  with all ``$>\epsilon$'' changed to ``$\ge\epsilon$'' is used),
  but the inequality between the extreme terms of the chain still holds.
  Therefore,
  the number of $n$-strange Class~IV extended examples
  does not exceed
  \begin{equation}\label{eq:Cl4Q3}
    \left(
      (F(c) - {\bf S}(\delta)) (1-c) + 5\epsilon
    \right)
    n
  \end{equation}
  from some $n$ on almost surely.

  By the Borel strong law of large numbers,
  the fraction of Class~V extended examples among the first $n$ extended examples
  will tend to
  \begin{equation}\label{eq:Cl5Q1}
    1-F(c+2\epsilon)
  \end{equation}
  as $n\to\infty$ almost surely.
  By Lemma~\ref{lem:Mc}, the Borel--Cantelli lemma, and~(\ref{eq:separation}),
  almost surely from some $n$ on at least
  \begin{equation}\label{eq:Cl5Q2}
    (1-F(c+2\epsilon)-2\epsilon) n
  \end{equation}
  extended examples in Class~V will be above the threshold.

  Finally, we estimate the number $N_n^{{\rm V,str}}$
  of $n$-strange extended examples of Class~V
  among the first $n$ extended examples.
  By McDiarmid's theorem,
  $$
    \left|
      \frac1n N_n^{{\rm V,str}}
      -
      \frac1n \Expect N_n^{{\rm V,str}}
    \right|
    <
    \epsilon
  $$
  from some $n$ on almost surely.
  Now
  \begin{align*}
    \frac1n \Expect N_n^{{\rm V,str}}
    &=
    \Prob
    \left\{
      f(x_n) > c+2\epsilon,
      \hat y_n(x_n,\tau'_n) \ne y_n
    \right\}
  \\
    &=
    \Expect
    \left(
      \left(
        1
        -
        P_{{\bf Y}\givn{\bf X}}
        \left(
          \hat y_n(x_n,\tau'_n) \givn x_n
        \right)
      \right)
      \III_{\{f(x_n) > c+2\epsilon\}}
    \right)
  \\
    &\le
    e^{-\epsilon^* n} + \epsilon
    +
    \Expect
    \left(
      \left(
        1 - f(x_n) + 2\epsilon
      \right)
      \III_{\{f(x_n) > c+2\epsilon\}}
    \right)
  \\
    &\le
    e^{-\epsilon^* n} + 3\epsilon
    +
    \Expect
    \left(
      \left(
        1 - f(x_n)
      \right)
      \III_{\{f(x_n) > c+2\epsilon\}}
    \right)
  \\
    &=
    e^{-\epsilon^* n} + 3\epsilon
    +
    \int_0^1
      (F(\beta) - F(c+2\epsilon))^{+}
    d\beta
  \\
    &<
    \int_0^1
      (F(\beta) - F(c))^{+}
    d\beta
    +
    4\epsilon
  \end{align*}
  from some $n$ on. The first inequality follows from Lemma~\ref{lem:basic},
  as in (\ref{eq:explan}).
  Therefore,
  \begin{equation}\label{eq:Cl5Q3}
    \frac1n
    N^{{\rm V,str}}_n
    <
    \int_0^1
      (F(\beta) - F(c))^{+}
    d\beta
    +
    5\epsilon
  \end{equation}
  from some $n$ on almost surely.

  Summarizing,
  we can see that the total number of extended examples above the threshold
  among the first $n$ extended examples
  will be at least
%  \begin{multline}\label{eq:above}             % OCM WP3
  \begin{equation}\label{eq:above}              % JMLR
    \left(
      F(c) - {\bf S}(\delta) - 2\epsilon
      +
      1 - F(c+2\epsilon) - 2\epsilon
    \right)
    n
%  \\                                           % OCM WP3
    =
    \left(
      1 - {\bf S}(\delta) + F(c) - F(c+2\epsilon) - 4\epsilon
    \right)
    n
  \end{equation}                                % JMLR
%  \end{multline}                               % OCM WP3
  (see~(\ref{eq:Cl4Q2}) and~(\ref{eq:Cl5Q2}))
  from some $n$ on almost surely.
  The number of $n$-strange extended examples among them will not exceed
  \begin{multline}\label{eq:above_strange}
    \biggl(
      \epsilon
      +
      F(c+2\epsilon)-F(c)+F(c-)-F(c-2\epsilon)+\epsilon
  \\
      {}+
      (F(c) - {\bf S}(\delta)) (1-c) + 5\epsilon
      +
      \int_0^1
        (F(\beta) - F(c))^{+}
      d\beta
      +
      5\epsilon
    \biggr)
    n
  \\
    {}=
    \biggl(
      F(c+2\epsilon)-F(c)+F(c-)-F(c-2\epsilon)
  \\
      {}+
      (F(c) - {\bf S}(\delta)) (1-c)
      +
      \int_0^1
        (F(\beta) - F(c))^{+}
      d\beta
      +
      12\epsilon
    \biggr)
    n
  \end{multline}
  (see~(\ref{eq:Cl1Q2}), (\ref{eq:Cl3Q1}), (\ref{eq:Cl4Q3}), and~(\ref{eq:Cl5Q3}))
  from some $n$ on almost surely.
  Combining~(\ref{eq:above}) and~(\ref{eq:above_strange}),
  we can see that the number of $n$-strange extended examples
  among the $\lfloor(1-{\bf S}(\delta))n\rfloor$ extended examples
  with the largest $(f_n^{\ne}(x_i,\tau'_i),\tau''_i)$ does not exceed
  \begin{multline*}
    \biggl(
      F(c+2\epsilon)-F(c)+F(c-)-F(c-2\epsilon)
      +
      (F(c) - {\bf S}(\delta)) (1-c)
  \\
      {}+
      \int_0^1
        (F(\beta) - F(c))^{+}
      d\beta
      +
      12\epsilon
    \biggr)
    n
    +
    \left(
      F(c+2\epsilon) - F(c) + 4\epsilon
    \right)
    n
  \\
    {}=
    \biggl(
      2 (F(c+2\epsilon)-F(c)) + (F(c-)-F(c-2\epsilon))
      +
      (F(c) - {\bf S}(\delta)) (1-c)
  \\
      {}+
      \int_0^1
        (F(\beta) - F(c))^{+}
      d\beta
      +
      16\epsilon
    \biggr)
    n
  \end{multline*}
  from some $n$ on almost surely.
  Since $\epsilon$ can be arbitrarily small,
  the coefficient in front of $n$ in the last expression can be made arbitrarily close to
  $$
    (F(c) - {\bf S}(\delta)) (1-c)
    +
    \int_0^1
      (F(\beta) - F(c))^{+}
    d\beta
    =
    \int_0^1
      (F(\beta) - {\bf S}(\delta))^{+}
    d\beta
    =\delta,
  $$
  which completes the proof.
% \qedtext              % OCM WP3
\end{proof}
\begin{lemma}\label{lem:delta_0}
  Suppose~(\ref{eq:K}) is satisfied.
  The fraction of $n$-strange extended examples
  among the first $n$ extended examples $(x_i,\tau_i,y_i)$
  approaches $\delta_0$ asymptotically
  with probability one.
\end{lemma}
\begin{proofsketch}
  The lemma is not difficult to prove using
  McDiarmid's theorem and the fact that, by Lemma~\ref{lem:Mc},
  $P(\hat{y}_n(x_i,\tau'_i)\givn x_i)$ will typically differ little from $f(x_i)$.
  Notice, however, that the part that we really need in this paper
  (that the fraction of $n$-strange extended examples
  does not exceed $\delta_0+o(1)$ as $n\to\infty$ with probability one)
  is just a special case of Lemma~\ref{lem:main1},
  corresponding to $\delta=\delta_0$.
% \qedtext              % OCM WP3
\end{proofsketch}
\begin{lemma}\label{lem:main2}
  Suppose~(\ref{eq:K}) is satisfied and $\delta>\delta_0$.
  The fraction of $n$-ordinary extended examples
  among the $\lfloor {\bf C}(\delta)n\rfloor$ extended examples $(x_i,\tau_i,y_i)$,
  $i=1,\dots,n$,
  with the lowest $(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$
  does not exceed $\delta-\delta_0+o(1)$ as $n\to\infty$
  with probability one.
\end{lemma}
Lemma~\ref{lem:main2} can be proved analogously to Lemma~\ref{lem:main1}.
\begin{lemma}\label{lem:SLLN}
  Let $\FFF_1\supseteq\FFF_2\supseteq\cdots$
  be a decreasing sequence of $\sigma$-algebras
  and $\xi_1,\xi_2\dots$ be a bounded adapted
  (in the sense that $\xi_n$ is $\FFF_n$-measurable for all $n$)
  sequence of random variables such that
  $$
    \limsup_{n\to\infty}
    \Expect(\xi_n\givn\FFF_{n+1})
    \le
    0
    \quad
    \text{a.s.}
  $$
  Then
  $$
    \limsup_{n\to\infty}
    \frac1n
    \sum_{i=1}^n
    \xi_i
    \le
    0
    \quad
    \text{a.s.}
  $$
\end{lemma}
\begin{proof}
  Replacing, if necessary,
  $\xi_n$ by $\xi_n-\Expect(\xi_n\givn\FFF_{n+1})$,
  we reduce our task to the following special case
  (a reverse Borel strong law of large numbers):
  if $\xi_1,\xi_2,\dots$ is a bounded \emph{reverse martingale difference},
  in the sense of being adapted and satisfying
  $\forall n:\Expect(\xi_n\givn\FFF_{n+1})=0$,
  then
  \begin{equation}\label{eq:goal}
    \lim_{n\to\infty}
    \frac1n
    \sum_{i=1}^n
    \xi_i
    =
    0
    \quad
    \text{a.s.}
  \end{equation}
  Fix a bounded reverse martingale difference $\xi_1,\xi_2,\dots$;
  our goal is to prove~(\ref{eq:goal}).
  By the martingale version of Hoeffding's inequality
%  (\cite{devroye/etal:1996}, Theorem~9.1)              % OCM WP3
  \cite[Theorem~9.1]{devroye/etal:1996}                 % JMLR
  applied to the martingale difference
  $(\xi_i,\FFF_i)$, $i=n,\dots,1$,
  \begin{equation}\label{eq:bound}
    \Prob
    \left\{
      \left|
        \frac1n
        \sum_{i=1}^n
        \xi_i
      \right|
      \ge
      \epsilon
    \right\}
    \le
    2
    e^{-2\epsilon^2n/(2C)^2},
  \end{equation}
  where $C$ is an upper bound on $\sup_n|\xi_n|$.
  Combined with the Borel--Cantelli--L\'evy lemma,
  (\ref{eq:bound}) implies~(\ref{eq:goal}).
% \qedtext              % OCM WP3
\end{proof}

Now we can sketch the proof of Proposition~\ref{prop:upper}.
Define $\FFF_n$, $n=1,2,\dots$,
to be the $\sigma$-algebra on $\tilde{\bf Z}^{\infty}$
generated by the multiset of the first $n-1$ extended examples
$(x_i,\tau_i,y_i)$, $i=1,\dots,n-1$,
and the sequence of extended examples
$(x_i,\tau_i,y_i)$, $i=n,n+1,\dots$
(starting from the $n$th extended example).

Suppose first that $\delta<\delta_0$.
Consider the $\lfloor(1-{\bf S}(\delta-\epsilon))n\rfloor$ extended examples
with the largest $(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$
among $(x_1,\tau_1,y_1),\dots,(x_n,\tau_n,y_n)$,
where $\epsilon\in(0,\delta)$ is a small constant.
Let us show that each of these examples
will be predicted with certainty from the other extended examples
in the sequence $(x_1,\tau_1,y_1),\dots,(x_n,\tau_n,y_n)$,
from some $n$ on.
We will be assuming $n$ large enough.

Let $(x_k,\tau_k,y_k)$ be the extended example
with the $(\lfloor(\delta-\epsilon/2)n\rfloor+1)$th largest
(in the sense of the lexicographic order)
$(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$
among all $n$-strange extended examples
$(x_i,\tau_i,y_i)$, $i=1,\dots,n$.
(Remember that all $\tau''_i$ are assumed to be different.)
Let $(x_j,\tau_j,y_j)$ be
one of the $\lfloor(1-{\bf S}(\delta-\epsilon))n\rfloor$ extended examples
with the largest $(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$
and let $y\in{\bf Y}$
be a label different from $\hat{y}_n(x_j,\tau'_j)$.
It suffices to prove that
\begin{equation}\label{eq:B}
  \tau''_j
  \ge
  \frac
    {\#\{i=1,\dots,n\st\alpha^y_i\ge\alpha^y_j\}-n\delta}
    {\#\{i=1,\dots,n\st\alpha^y_i=\alpha^y_j\}}
\end{equation}
(cf.~(\ref{eq:prob}) on p.~\pageref{eq:prob}),
where all $\alpha^y$ are computed as $\alpha$ in~(\ref{eq:univ_alpha})
from the sequence
%$(x_1,\tau_1,y_1),\dots,(x_n,\tau_n,y_n)$              % OCM WP3
$$(x_1,\tau_1,y_1),\dots,(x_n,\tau_n,y_n)$$             % JMLR
with $y_j$ replaced by $y$.
It will be more convenient to write~(\ref{eq:B}) in the form
$$
  \#\{i\st\alpha^y_i>\alpha^y_j\}
  +
  (1-\tau''_j)
  \#\{i\st\alpha^y_i=\alpha^y_j\}
  \le
  n\delta.
$$
Since $\alpha^y_j=f^{\ne}_n(x_j,\tau'_j)$ and $\alpha_i^y\ne\alpha_i$
for at most $2K_n+1$ values of $i$
(indeed, changing $y_j$ will affect at most $2K_n+1$ $\alpha$s),
it suffices to prove
\begin{equation}\label{eq:C}
  \#\{i\st\alpha_i>f^{\ne}_n(x_j,\tau'_j)\}
  +
  (1-\tau''_j)
  \#\{i\st\alpha_i=f^{\ne}_n(x_j,\tau'_j)\}
  \le
  n(\delta-\epsilon^*),
\end{equation}
where $\epsilon^*\ll\epsilon$ is a positive constant.

Since $(f^{\ne}_n(x_j,\tau'_j),\tau''_j)\ge(\alpha_k,\tau''_k)$
(indeed, by Lemma~\ref{lem:main1},
there are less than $(\delta-\epsilon/2)n$ $n$-strange extended examples
among the $\lfloor(1-{\bf S}(\delta-\epsilon))n\rfloor$ extended examples
with the largest $(f^{\ne}_n(x_i,\tau'_i),\tau''_i)$),
(\ref{eq:C}) will follow from
\begin{equation}\label{eq:D}
  \#\{i\st\alpha_i>\alpha_k\}
  +
  (1-\tau''_k)
  \#\{i\st\alpha_i=\alpha_k\}
  \le
  n(\delta-\epsilon^*).
\end{equation}
If
$
  \#\{i\st\alpha_i=\alpha_k\}
  \le
  \frac{\epsilon}{3}
  n
$,
the left-hand side of~(\ref{eq:D}) does not exceed
$$
  \left(
    \delta - \frac{\epsilon}{2}
  \right)
  n
  +
  \frac{\epsilon}{3}
  n
  <
  n(\delta-\epsilon^*),
$$
so we can, and will, assume without loss of generality that
\begin{equation}\label{eq:ass}
  \#\{i\st\alpha_i=\alpha_k\}
  >
  \frac{\epsilon}{3}
  n.
\end{equation}
Since $\tau''_i$ for the extended examples satisfying $\alpha_i=\alpha_k$
are output according to the uniform distribution ${\bf U}$,
the expected value of $1-\tau''_k$ is about
$$
  \frac
  {
    (\delta-\epsilon/2)n
    -
    \#\{i\st\alpha_i>\alpha_k\}
  }
  {
    \#\{i\st\alpha_i=\alpha_k\}
  },
$$
and so by Hoeffding's inequality and the Borel--Cantelli lemma we will have
(from some $n$ on)
\begin{equation}\label{eq:ineq}
  1-\tau''_k
  \le
  \frac
  {
    (\delta-\epsilon/2)n
    -
    \#\{i\st\alpha_i>\alpha_k\}
  }
  {
    \#\{i\st\alpha_i=\alpha_k\}
  }
  +
  \epsilon^*, 
\end{equation}
remembering~(\ref{eq:ass}).
Equation~(\ref{eq:D}) will hold
because its left-hand side can be transformed using~(\ref{eq:ineq}) as
\begin{align*}
  \#\{i\st\alpha_i>\alpha_k\}
  +
  (1-\tau''_k)
  \#\{i\st\alpha_i=\alpha_k\}
  &\le
  (\delta-\epsilon/2)n
  +
  \epsilon^*
  \#\{i\st\alpha_i=\alpha_k\}
\\
  &\le
  (\delta-\epsilon/2+\epsilon^*)n
  \le
  (\delta-\epsilon^*)n.
\end{align*}

The assertion we have just proved means that, almost surely from some $n$ on,
$$
  \Prob(\{\unc_n=0\}\givn\FFF_{n+1})
  \ge
  \frac{\lfloor(1-{\bf S}(\delta-\epsilon))n\rfloor}{n}
  \ge
  1-{\bf S}(\delta-\epsilon) - \frac1n.
$$
Since $\epsilon$ can be arbitrarily small and ${\bf S}$ is continuous
\citep[Lemma~2]{vovk:2002ALTforJMLR},                   % JMLR
%(\cite{OCM2}, Lemma~2),                                % OCM WP3
this implies
$$
  \limsup_{n\to\infty}
  \Expect(\unc_n\givn\FFF_{n+1})
  \le
  {\bf S}(\delta)
  \quad
  \text{a.s.}
$$
By Lemma~\ref{lem:SLLN} this implies, in turn,
$$
  \limsup_{n\to\infty}
  \frac1n
  \sum_{i=1}^n
  \unc_i
  \le
  {\bf S}(\delta)
  \quad
  \text{a.s.},
$$
which coincides with~(\ref{eq:main}).

If $\delta\ge\delta_0$,
Lemma~\ref{lem:delta_0} implies that
$$
  \lim_{n\to\infty}
  \Expect(\unc_n\givn\FFF_{n+1})
  =
  0
  \quad
  \text{a.s.}
$$
(and actually $\Expect(\unc_n\givn\FFF_{n+1})=0$ from some $n$ on
if $\delta>\delta_0$);
in combination with Lemma~\ref{lem:SLLN} this again implies~(\ref{eq:main}).

Inequality~(\ref{eq:mainEmp}) is treated
in a similar way to (\ref{eq:main}).
Lemmas~\ref{lem:delta_0} and~\ref{lem:main2} imply that
\begin{equation}\label{eq:star}
  \liminf_{n\to\infty}
  \Expect(\emp_n\givn\FFF_{n+1})
  \ge
  {\bf C}(\delta)
  \quad
  \text{a.s.}
\end{equation}
(this inequality is vacuously true when $\delta\le\delta_0$).
Another application of Lemma~\ref{lem:SLLN} gives
$$
  \liminf_{n\to\infty}
  \frac1n
  \sum_{i=1}^n
  \emp_i
  \ge
  {\bf C}(\delta)
  \quad
  \text{a.s.},
$$
i.e.,~(\ref{eq:mainEmp}).
\begin{remark}
  The derivation of Proposition~\ref{prop:upper}
  from Lemmas~\ref{lem:main1}--\ref{lem:SLLN}
  would be very simple if we defined the individual strangeness measure by, say,
  $$
    \alpha_i
    :=
    \begin{cases}
      (-f_n^{\ne}(x_i,\sigma_i),\sigma_i) & \text{if $y_i=\hat{y}_n(x_i,\sigma_i)$}\\
      (f_n^{\ne}(x_i,\sigma_i),\sigma_i) & \text{otherwise}
    \end{cases}
  $$
  (with the lexicographic order on the $\alpha$'s)
  instead of~(\ref{eq:univ_alpha})
  (in which case the denominator of~(\ref{eq:prob})
  would be~$1$ almost surely).
  Our definition~(\ref{eq:univ_alpha}), however,
  is simpler and, most importantly, facilitates the proof of Proposition~\ref{prop:time}.
  Another simplification would be to use Lemma~\ref{lem:main1}
  (applied to $\delta:=\delta-{\bf C}(\delta)$)
  instead of Lemma~\ref{lem:main2}
  in the derivation of (\ref{eq:star});
  we preferred a more symmetric picture.
\end{remark}

\section{Conclusion}

We have shown that there exist universal well-calibrated region predictors,
thus satisfying, to some degree, the desiderata mentioned in \S\ref{sec:introduction}:
well-calibratedness and optimal performance.
Notice, however, that the ways in which these two desiderata are satisfied
are very different:
the well-calibratedness holds in a very specific finitary sense,
since the errors have probability $\delta$ and are independent,
whereas the optimal performance is achieved only asymptotically.

An important direction of further research
is to obtain non-asymptotic results about TCM's optimality.
A natural setting is where we have a Bayesian model
for Reality's strategy,
$\{P_{\theta}\st\theta\in\Theta\}$ with a prior $\mu(d\theta)$ on $\Theta$,
and our goal is to minimize $\Unc_n^{\delta}$ under this model.
The intuition behind this setting
is that we do not really believe
that the data is generated from our model
and so prefer a predictor
that is well-calibrated regardless the correctness of the model;
but if the model is correct,
we would like to have an optimal performance.
A special case of this setting,
with $\mu(d\theta)$ concentrated at one point,
was considered in \cite{vovk:2002ALTforJMLR};
however, all results in that paper are asymptotic.

\acks{This is a full version of the conference paper~\citep{vovk:2003COLT};
I am grateful to both sets of anonymous referees
(for the conference and journal versions),
whose comments and suggestions
helped to improve the quality of presentation
and correct several mistakes.
This work was partially supported by EPSRC
(grant GR/R46670/01),
% ``Complexity Approximation Principle and Predictive Complexity:
% Analysis and Applications''),
BBSRC
(grant 111/BIO14428),
% ``Pattern Recognition Techniques
% for Gene and Promoter Identification and Classification
% in Plant Genomic Sequences''),
and EU
(grant IST-1999-10226).}
% ``EurEdit:
% The Development and Evaluation of New Methods for Editing and Imputation'').

\appendix
\section{Notation}

The following table contains, strictly speaking,
not only the notation used in this paper
but also the preferred use of symbols.

\begin{tabbing}
  LongggNotation \= LongExplanation\kill
  ${\bf X}$ \> object space\\
  ${\bf Y}$ \> label space\\
  ${\bf Z}$ \> example space (${\bf Z}={\bf X}\times{\bf Y}$)\\
  $P$ \> the probability distribution in ${\bf Z}$ generating individual examples\\
        \> $z_1=(x_1,y_1),z_2=(x_2,y_2),\dots$\\
  $\delta$ \> significance level\\
  $\Gamma_n^{\delta}$ \> prediction region\\
  $\err_n^{\delta}$ \> indicator of error at trial $n$\\
  $\unc_n^{\delta}$ \> indicator of uncertain prediction at trial $n$\\
  $\emp_n^{\delta}$ \> indicator of empty prediction at trial $n$\\
  $\Err_n^{\delta}$ \> cumulative number of errors up to trial $n$\\
  $\Unc_n^{\delta}$ \> cumulative number of uncertain predictions up to trial $n$\\
  $\Emp_n^{\delta}$ \> cumulative number of empty predictions up to trial $n$\\
  $\tau_n$ \> the $n$th random number used by a region predictor\\
  $\tau'_n$, $\tau''_n$ \> two components of $\tau_n$, as defined in \S\ref{subsec:prel}\\
  $\tilde{{\bf X}}$ \> the extended object space ${\bf X}\times[0,1]$\\
  $\tilde{{\bf Z}}$ \> the extended example space ${\bf X}\times[0,1]\times{\bf Y}$\\
  $<$, $\le$ \> may refer to the lexicographic order on $[0,1]^2$, as defined on p.~\pageref{p:lex}\\
  $|x,\sigma|$ \> the absolute value of $(x,\sigma)\in[0,1]^2$, as defined in (\ref{eq:abs})\\
  $A_n$ \> individual strangeness measure\\
  $\alpha_i$ \> values taken by an individual strangeness measure\\
  $\#E$ \> the size of set $E$\\
  $K_n$ \> the number of nearest neighbours taken into account at trial $n$\\
  $P_n^{\ne}(y\givn x_i,\sigma_i)$ \> empirical estimate of $P(y\givn x_i)$
        without taking $y_i$ into account,\\
        \> as defined in (\ref{eq:cond})\\
  $f_n^{\ne}(x_i,\sigma_i)$ \> corresponding empirical predictability function, (\ref{eq:fne_n})\\
  $\hat y_n(x_i,\sigma_i)$ \> ``choice function'', as defined in (\ref{eq:max})\\
  $\Delta$ \> finite set of significance levels\\
  $P_{{\bf X}}$ \> the marginal distribution of $P$ in ${\bf X}$\\
  $P_{{\bf Y}\givn{\bf X}}$ \> the regular conditional distribution
        of $y\in{\bf Y}$ given $x\in{\bf X}$,\\
        \> where $(x,y)$ is distributed as $P$\\
  $f(x)$ \> predictability of object $x$\\
  $F(\beta)$ \> predictability distribution function\\
  ${\bf S}(\delta)$ \> success curve, defined in (\ref{eq:success})\\
  ${\bf C}(\delta)$ \> complementary success curve, defined in (\ref{eq:compl})\\
  $\delta_0$ \> critical significance level, defined in (\ref{eq:critical})\\
  $\errOver$, $\uncOver$, $\empOver$ \>
    ``predictable'' versions of $\err$, $\unc$, $\emp$,
    as defined on p.~\pageref{p:over}\\
  $\ErrOver$, $\UncOver$, $\EmpOver$ \>
    ``predictable'' versions of $\Err$, $\Unc$, $\Emp$\\
  $F(t-)$ \> the limit of $F(u)$ as $u$ approaches $t$ from below\\
  $F(t+)$ \> the limit of $F(u)$ as $u$ approaches $t$ from above\\
  $u\vee v$ \> the maximum of $u$ and $v$, also denoted $\max(u,v)$\\
  $u\wedge v$ \> the minimum of $u$ and $v$, also denoted $\min(u,v)$\\
  $t^+$ \> $t\vee 0$\\
  $t^-$ \> $(-t)\vee 0$\\
  ${\bf U}$ \> the uniform probability distribution in $[0,1]$\\
  $P_n(y\givn x,\sigma)$ \> empirical estimate of $P(y\givn x)$, defined by (\ref{eq:P_n})\\
  $f_n(x,\sigma)$ \> corresponding empirical predictability function, defined by (\ref{eq:f_n})\\
  $\Prob$ \> probability\\
  $\Expect$ \> expectation\\
  $\forall^{\infty}n$ \> from some $n$ on\\
  $\III_E$ \> the indicator function of set $E$
\end{tabbing}

%\bibliographystyle{plain}      % OCM WP3

\vskip 0.2in
\bibliography{%
  math,%
  prob,%
  stat,%
  vovk}
%\lastpage                      % OCM WP3
\end{document}

% Any additional packages needed should be included after jmlr2e.
% Note that jmlr2e.sty includes epsfig, amssymb, natbib and graphicx,
% and defines many common macros, such as 'proof' and 'example'.
%
% It also sets the bibliographystyle to plainnat; for more information on
% natbib citation styles, see the natbib documentation, a copy of which
% is archived at http://www.jmlr.org/format/natbib.pdf
