Defensive Forecasting
Vladimir Vovk\footnotemark[1]
http://vovk.net \And Akimichi Takemura\footnotemark[2]
http://www.e.u-tokyo.ac.jp/\~{takemura} \AND Glenn Shafer\footnotemark[3] \footnotemark[1]
http://glennshafer.com
We consider how to make probability forecasts of binary labels. Our main mathematical result is that for any continuous \ifWP(in particular, any computable) \fi gambling strategy used for detecting disagreement between the forecasts and the actual labels, there exists a forecasting strategy whose forecasts are ideal as far as this gambling strategy is concerned. A forecasting strategy obtained in this way from a gambling strategy demonstrating a strong law of large numbers is simplified and studied empirically. \Extra{This working paper is the full version of a paper to be published in the AI \& Statistics 2005 proceedings.}
DF.TEX
% Last changed by Volodya, 30 May 2005
% Spell checked by Volodya, 30 May 2005
\newif\ifAIStats
\AIStatsfalse
\newif\ifarXiv
\arXivfalse
\newif\ifWP
\WPfalse

%\AIStatstrue				% choose WP or AIStats or arXiv
\arXivtrue
%\WPtrue

\ifAIStats
\documentclass{article}
\usepackage{amsmath,amsfonts,latexsym,graphicx,proceed2e}
\newcommand{\Extra}[1]{}
\newcommand{\Case}[1]{\uppercase{#1}}
\fi

\ifarXiv
\documentclass{article}
\usepackage{amsmath,amsfonts,latexsym,graphicx}
\newcommand{\Extra}[1]{}
\newcommand{\Case}[1]{#1}
\fi

\ifWP
\documentclass[toc]{gtarticle}
\usepackage{amsmath,amsfonts,latexsym,graphicx,epsfig}
\renewcommand{\Extra}[1]{#1}
\newcommand{\Case}[1]{#1}
\fi

\newlength{\picturewidth}
\ifAIStats
  \setlength{\picturewidth}{\columnwidth}
\fi
\ifarXiv
  \setlength{\picturewidth}{10cm}
\fi
\ifWP
  \setlength{\picturewidth}{10cm}
\fi

\emergencystretch=5mm
\tolerance=400

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

\newcommand{\st}{\mathop{|}}
\newcommand{\given}{\mathrel{|}}

\newcommand{\bbbr}{\mathbb{R}}		% real numbers
\newcommand{\bbbc}{\mathbb{C}}		% complex numbers
\newcommand{\III}{\mathbb{I}}		% indicator
\newcommand{\bbbp}{\mathbb{P}}		% auxiliary (probability)
\newcommand{\bbbe}{\mathbb{E}}		% auxiliary (expectation)
\newcommand{\K}{\mathcal{K}}		% capital
\newcommand{\FFF}{\mathcal{F}}		% sigma-algebra

\newcommand{\Prob}{\mathop{\bbbp}\nolimits}
\newcommand{\Expect}{\mathop{\bbbe}\nolimits}
\newcommand{\LP}{\mathop{\underline{\bbbp}}\nolimits}
\newcommand{\UP}{\mathop{\overline{\bbbp}}\nolimits}
\newcommand{\ULP}{\mathop{\overline{\underline{\bbbp}}}\nolimits}
\newcommand{\sign}{\mathop{{\rm sign}}\nolimits}

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

\newlength{\IndentI}
\newlength{\IndentII}
\newlength{\IndentIII}
\setlength{\IndentI}{0mm}
\setlength{\IndentII}{7mm}
\setlength{\IndentIII}{14mm}
\newlength{\WidthI}
\newlength{\WidthII}
\newlength{\WidthIII}
\setlength{\WidthI}{\textwidth}
\setlength{\WidthII}{\textwidth}
\setlength{\WidthIII}{\textwidth}
\addtolength{\WidthI}{-\IndentI}
\addtolength{\WidthII}{-\IndentII}
\addtolength{\WidthIII}{-\IndentIII}

\ifAIStats
\title{Defensive Forecasting}

\author{Vladimir Vovk\footnotemark[1]\\
\texttt{vovk{\rm@}cs.rhul.ac.uk}\\
\texttt{http://vovk.net}
\And
Akimichi Takemura\footnotemark[2]\\
\texttt{takemura{\rm@}stat.t.u-tokyo.ac.jp}\\
\texttt{http://www.e.u-tokyo.ac.jp/\~{}takemura}
\AND
Glenn Shafer\footnotemark[3] \footnotemark[1]\\
\texttt{gshafer{\rm@}andromeda.rutgers.edu}\\
\texttt{http://glennshafer.com}}
\fi

\ifarXiv
\title{Defensive Forecasting}

\author{Vladimir Vovk\\
\texttt{vovk{\rm@}cs.rhul.ac.uk}\\
\texttt{http://vovk.net}
\and
Akimichi Takemura\\
\texttt{takemura{\rm@}stat.t.u-tokyo.ac.jp}\\
\texttt{http://www.e.u-tokyo.ac.jp/\~{}takemura}
\and
Glenn Shafer\\
\texttt{gshafer{\rm@}andromeda.rutgers.edu}\\
\texttt{http://glennshafer.com}}
\fi

\ifWP
\title{Defensive Forecasting}

\author{Vladimir Vovk\and Akimichi Takemura\and Glenn Shafer}

\newcommand{\No}{8}
%For the two dates option: uncomment the next 2 lines
\twodatestrue
\newcommand{\firstposted}{September 29, 2004}
\fi

\begin{document}
\maketitle

\ifAIStats
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%\footnotetext[1]{The final text of this article has been written
%  by Vovk and Shafer,
%  who are responsible for expressions such as ``Takemura predictor''.}
\footnotetext[1]{Computer Learning Research Centre,
  Department of Computer Science,
  Royal Holloway, University of London,
  Egham, Surrey TW20 0EX, England.}
\footnotetext[2]{Department of Mathematical Informatics,
  Graduate School of Information Science and Technology,
  University of Tokyo,
  7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan.}
\footnotetext[3]{%Department of Accounting and Information Systems,
  Rutgers Business School---Newark and New Bruns\-wick,
  180 University Avenue, Newark, NJ 07102, USA.}
\renewcommand{\thefootnote}{\arabic{footnote}}
\fi

\begin{abstract}
  We consider how to make probability forecasts of binary labels.
  Our main mathematical result is that for any continuous
  \ifWP(in particular, any computable) \fi
  gambling strategy used for detecting disagreement between the forecasts
  and the actual labels,
  there exists a forecasting strategy
  whose forecasts are ideal
  as far as this gambling strategy is concerned.
  A forecasting strategy obtained in this way
  from a gambling strategy demonstrating a strong law of large numbers
  is simplified and studied empirically.
  \Extra{This working paper is the full version of a paper
  to be published in the AI \& Statistics 2005 proceedings.}
\end{abstract}

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

Probability forecasting can be thought of
as a game between two players, Forecaster and Reality:

\medskip

\Extra{\noindent
\textsc{Basic Binary Forecasting Protocol}

\noindent
\textbf{Players:} Reality, Forecaster}

\parshape=4
\IndentI  \WidthI
\IndentII \WidthII
\IndentII \WidthII
\IndentII \WidthII
\noindent
FOR $n=1,2,\dots$:\\
  Reality announces $x_n\in{\bf X}$.\\
  Forecaster announces $p_n\in[0,1]$.\\
  Reality announces $y_n\in\{0,1\}$.

\medskip

\noindent
On each round,
Forecaster predicts Reality's move $y_n$
chosen from the \emph{label space},
always taken to be $\{0,1\}$ in this paper.
His move, the \emph{probability forecast} $p_n$,
can be interpreted as the probability he attaches to the event $y_n=1$.
To help % (or maybe confuse)
Forecaster,
Reality presents him with an \emph{object} $x_n$
at the beginning of the round;
$x_n$ are chosen from an \emph{object space} ${\bf X}$.

Forecaster's goal is to produce $p_n$ that agree with the observed $y_n$.
Various results of probability theory,
in particular limit theorems
(such as the weak and strong laws of large numbers, the law of the iterated logarithm,
and the central limit theorem)
and large-deviation inequalities
(such as Hoeffding's inequality),
describe different aspects of agreement between $p_n$ and $y_n$.
For example, according to the strong law of large numbers,
we expect that
\begin{equation}\label{eq:SLLN}
  \lim_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  =
  0.
\end{equation}
Such results will be called \emph{laws of probability}
and the existing body of laws of probability
will be called \emph{classical probability theory}.
\Extra{Historically, laws of probability form the core of probability theory.}

In \S\ref{sec:gambling},
following \cite{shafer/vovk:2001},
we formalize Forecaster's goal by adding a third player, Skeptic,
who is allowed to gamble at the odds given by Forecaster's probabilities.
We state a result from \cite{ville:1939} and \cite{shafer/vovk:2001}
suggesting that Skeptic's gambling strategies
can be used as tests of agreement between $p_n$ and $y_n$
and that all tests of agreement between $p_n$ and $y_n$
can be expressed as Skeptic's gambling strategies.
Therefore,
the forecasting protocol with Skeptic
provides an alternative way of stating laws of probability.

As demonstrated in \cite{shafer/vovk:2001},
many standard proof techniques developed in classical probability theory
can be translated into
\ifAIStats continuous strategies for Skeptic. \fi
\ifarXiv continuous strategies for Skeptic. \fi
\ifWP computable strategies for Skeptic; all such strategies are continuous. \fi
In \S\ref{sec:result}
we show that for any continuous strategy ${\cal S}$ for Skeptic
there exists a strategy ${\cal F}$ for Forecaster
such that ${\cal S}$ does not detect any disagreement
between the $y_n$ and the $p_n$ produced
by ${\cal F}$.
This result is a ``meta-theorem''
that allows one to move from laws of probability to forecasting algorithms:
as soon as a law of probability is expressed
as a continuous strategy for Skeptic,
we have a forecasting algorithm
that guarantees that this law will hold;
there are no assumptions about Reality,
who may play adversarially.

Our meta-theorem is of any interest
only if one can find sufficiently interesting laws of probability
(expressed as gambling strategies)
that can serve as its input.
In \S\ref{sec:examples} we apply it
to the important properties of unbiasedness in the large and small
of the forecasts $p_n$
((\ref{eq:SLLN}) is an asymptotic version of the former).
The resulting forecasting strategy is automatically unbiased,
no matter what data $x_1,y_1,x_2,y_2,\dots$ is observed.
% Our discussion will show that many practically interesting
% properties of agreement between $p_n$ and $y_n$ can be encoded
% as strategies for Skeptic.

In \S\ref{sec:experiments} we simplify the algorithm
obtained in \S\ref{sec:examples}
and demonstrate its performance
on some artificially generated data sets.

\section{\Case{The gambling framework for testing probability forecasts}}\label{sec:gambling}

Skeptic is allowed to bet at the odds defined by Forecaster's probabilities,
and he refutes the probabilities
if he multiplies his capital manyfold.
This is formalized as a perfect-information game
in which Skeptic plays against a team composed of Forecaster and Reality:

\medskip

\noindent
\textsc{Binary Forecasting Game I}

\noindent
\textbf{Players:} Reality, Forecaster, Skeptic

\noindent
\textbf{Protocol:}

\parshape=7
\IndentI   \WidthI
\IndentI   \WidthI
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\noindent
$\K_0 := 1$.\\
FOR $n=1,2,\dots$:\\
  Reality announces $x_n\in{\bf X}$.\\
  Forecaster announces $p_n\in[0,1]$.\\
  Skeptic announces $s_n\in\bbbr$.\\
  Reality announces $y_n\in\{0,1\}$.\\
  $\K_n := \K_{n-1} + s_n (y_n-p_n)$.

\noindent
\textbf{Restriction on Skeptic:}
Skeptic must choose the $s_n$
so that his capital is always nonnegative
($\K_n \ge 0$ for all $n$)
no matter how the other players move.

\medskip

\noindent
This is a perfect-information protocol;
the players move in the order indicated,
and each player sees the other player's moves
as they are made.
It specifies
both an initial value for Skeptic's capital ($\K_0 = 1$)
and a lower bound on its subsequent values ($\K_n \ge 0$).

Our interpretation,
which will be called the \emph{testing interpretation},
of Binary Forecasting Game I
is that $\K_n$ measures the degree to which Skeptic
has shown Forecaster to do a bad job of predicting $y_i$, $i=1,\dots,n$.

\subsection{\Case{Validity and universality of the testing interpretation}}

As explained in \cite{shafer/vovk:2001},
the testing interpretation is valid and universal
in an important sense.
Let us assume, for simplicity,
that objects are absent (formally, that $|{\bf X}|=1$).
In the case where Forecaster starts
from a probability measure $P$ on $\{0,1\}^{\infty}$
and obtains his forecasts $p_n\in[0,1]$
as conditional probabilities under $P$ that $y_n=1$
given $y_1,\dots,y_{n-1}$,
we have a standard way of testing $P$ and, therefore, $p_n$:
choose an event $A\subseteq\{0,1\}^{\infty}$
(the \emph{critical region})
with a small $P(A)$ and reject $P$ if $A$ happens.
The testing interpretation satisfies the following two properties:
\begin{description}
\item[Validity]
  Suppose Skeptic's strategy is measurable
  and $p_n$ are obtained from $P$;
  $\K_n$ then form a nonnegative martingale
  w.r.\ to $P$.
  According to Doob's inequality
  \cite{ville:1939,doob:1953},
  for any positive constant $C$,
  $\sup_n\K_n\ge C$ with $P$-probability at most $1/C$.
  (If Forecaster is doing a bad job according to the testing interpretation,
  he is also doing a bad job from the standard point of view.)
\item[Universality]
  According to Ville's theorem
  (\cite{shafer/vovk:2001}, \S8.5),
  for any positive constant $\epsilon$
  and any event $A\subseteq\{0,1\}^{\infty}$
  such that $P(A)<\epsilon$,
  Skeptic has a measurable strategy that ensures
  $\liminf_{n\to\infty}\K_n>1/\epsilon$
  whenever $A$ happens,
  provided $p_n$ are computed from $P$.
  (If Forecaster is doing a bad job according to the standard point of view,
  he is also doing a bad job according to the testing interpretation.)
  In the case $P(A)=0$,
  Skeptic actually has a measurable strategy that ensures
  $\lim_{n\to\infty}\K_n=\infty$ on $A$.
\end{description}
The universality of the gambling scenario
of Binary Forecasting Game I
is its most important advantage over von Mises's gambling scenario
based on subsequence selection;
it was discovered by Ville \cite{ville:1939}.

\ifAIStats\subsection{\Case{Continuity of gambling strategies}}\fi
\ifarXiv\subsection{\Case{Continuity of gambling strategies}}\fi
\ifWP\subsection{\Case{Constructiveness of the gambling framework}}\fi

In \cite{shafer/vovk:2001} we constructed
Skeptic's strategies that made him rich
when the statement of any of several key laws of probability theory
was violated.
The constructions were explicit
and lead to
\ifAIStats continuous \fi\ifarXiv continuous \fi\ifWP computable \fi gambling strategies.
We conjecture that every natural result of classical probability theory
leads to a \ifAIStats continuous \fi\ifarXiv continuous \fi\ifWP computable \fi strategy for Skeptic.

\ifWP Since Brouwer's work on intuitionist mathematics
it is widely accepted that only continuous functions
can be computable
(this is Brouwer's \emph{continuity principle} \cite{brouwer:1918};
for a modern statement, see \cite{martin-lof:1970}, \S22).
There are also idealized definitions of computability
in terms of computational models able to perform operation with real numbers
with infinite accuracy in unit time
(such as \cite{blum/etal:1989}),
and the functions computed in such weaker senses need not be computable.
Our conjecture asserts computability in the stronger Brouwer's sense.\fi

\Extra{\begin{remark*}According to \cite{atten/dalen:2002},
Brouwer introduced his continuity principle in 1916.
The following quote from Borel's 1912 paper \cite{borel:1912} is popular
(see, e.g., \cite{vonplato:2001}, p.~64):
``a function cannot be calculable unless it is continuous'';
Borel, however, was interested only in the values that computable functions
take on the computable values of the argument.\end{remark*}}

\section{\Case{Defeating Skeptic}}
\label{sec:result}

In this section we prove the main (albeit very simple) mathematical result
of this paper:
for any continuous strategy for Skeptic
there exists a strategy for Forecaster
that does not allow Skeptic's capital to grow,
regardless of what Reality is doing.
Actually, our result will be even stronger:
we will have Skeptic announce his strategy
for each round
before Forecaster's move on that round
rather than making him announce his full strategy at the beginning of the game,
and we will drop the restriction on Skeptic.
Therefore,
we consider the following perfect-information game
that pits Forecaster against the two other players:

\medskip

\noindent
\textsc{Binary Forecasting Game II}

\noindent
\textbf{Players:} Reality, Forecaster, Skeptic

\noindent
\textbf{Protocol:}

\parshape=6
\IndentI   \WidthI
\IndentI   \WidthI
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\noindent
$\K_0 := 1$.\\
FOR $n=1,2,\dots$:\\
  Reality announces $x_n\in{\bf X}$.\\
  Skeptic announces continuous $S_n:[0,1]\to\bbbr$.\\
  Forecaster announces $p_n\in[0,1]$.\\
  Reality announces $y_n\in\{0,1\}$.\\
  $\K_n := \K_{n-1} + S_n(p_n) (y_n-p_n)$.

\medskip

\begin{theorem}\label{thm:main}
  Forecaster has a strategy in Binary Forecasting Game II
  that ensures $\K_0\ge\K_1\ge\K_2\ge\cdots$.
\end{theorem}
\begin{proof}
  Forecaster can use the following strategy to ensure $\K_0\ge\K_1\ge\cdots$:
  \begin{itemize}
  \item
    if the function $S_n(p)$ takes the value 0,
    choose $p_n$ so that $S_n(p_n)=0$;
  \item
    if $S_n$ is always positive,
    take $p_n:=1$;
  \item
    if $S_n$ is always negative,
    take $p_n:=0$.
    \qedtext
  \end{itemize}
\end{proof}
\ifWP
\begin{remark*}
  In this paper computability serves only to motivate the assumption of continuity of $S_n$;
  only in this remark we briefly discuss computability issues.
  The proof of Theorem~\ref{thm:main} shows that for computability
  of the constructed strategy for Forecaster
  we need more than the computability of $S_n$;
  namely, we need an oracle
  that for each point $p$ tells us the sign of $S_n(p)$.
  Without such an oracle we can only claim
  that, for an arbitrary accuracy $\epsilon$,
  either we can find, with accuracy $\epsilon$, $p_n$
  ensuring $\K_n\le\K_{n-1}$
  or we can find $p_n$
  ensuring $\K_n\le\K_{n-1}+\epsilon$.
  For an example showing that such an oracle is necessary,
  see \cite{martin-lof:1970} (Figure 5).
\end{remark*}\fi

\section{\Case{Examples of gambling strategies}}
\label{sec:examples}

In this section we discuss strategies for Forecaster
obtained by Theorem~\ref{thm:main}
from different strategies for Skeptic;
the former will be called \emph{defensive forecasting strategies}.
There are many results of classical probability theory
that we could use,
but we will concentrate on the simple strategy
described in \cite{shafer/vovk:2001}, p.~69,
for proving the strong law of large numbers.

If $S_n(p)=S_n$ does not depend on $p$,
the strategy from the proof of Theorem~\ref{thm:main}
makes Forecaster choose
$$
  p_n
  :=
  \begin{cases}
    0 & \text{if $S_n<0$}\\
    1 & \text{if $S_n>0$}\\
    0 \text{ or } 1 & \text{if $S_n=0$}.
  \end{cases}
$$

The basic procedure described in \cite{shafer/vovk:2001} (p.~69)
is as follows.
Let $\epsilon\in(0,0.5]$ be a small number
(expressing our tolerance to violations
of the strong law of large numbers).
In Binary Forecasting Game I, Skeptic can ensure that
\begin{equation}\label{eq:goal}
  \sup_n\K_n<\infty
  \enspace\Longrightarrow\enspace
  \limsup_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  \le
  \epsilon
\end{equation}
using the strategy $s_n=s_n^{\epsilon}:=\epsilon\K_{n-1}$.
Indeed, since
$$
  \K_n
  =
  \prod_{i=1}^n
  (1+\epsilon(y_i-p_i)),
$$
on the paths where $\K_n$ is bounded
we have
$$
  \prod_{i=1}^n
  (1+\epsilon(y_i-p_i))
  \le
  C,
$$$$
  \sum_{i=1}^n
  \ln(1+\epsilon(y_i-p_i))
  \le
  \ln C,
$$$$
  \epsilon
  \sum_{i=1}^n
  (y_i-p_i)
  -
  \epsilon^2
  \sum_{i=1}^n
  (y_i-p_i)^2
  \le
  \ln C,
$$$$
  \epsilon
  \sum_{i=1}^n
  (y_i-p_i)
  \le
  \ln C
  +
  \epsilon^2 n,
$$$$
  \frac1n
  \sum_{i=1}^n
  (y_i-p_i)
  \le
  \frac{\ln C}{\epsilon n}
  +
  \epsilon
$$
(we have used the fact that $\ln(1+t)\ge t-t^2$
when $|t|\le0.5$).
If Skeptic wants to ensure
\begin{multline*}
  \sup_n\K_n<\infty
  \quad\Longrightarrow
\\[-3mm]
  -\epsilon
  \le
  \liminf_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  \le
  \limsup_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  \le
  \epsilon,
\end{multline*}
he can use the strategy $s_n:=(s_n^{\epsilon}+s_n^{-\epsilon})/2$,
and if he wants to ensure
\begin{equation}\label{eq:implication}
  \sup_n\K_n<\infty
  \enspace\Longrightarrow\enspace
  \lim_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  =
  0,
\end{equation}
he can use a convex mixture of $(s_n^{\epsilon}+s_n^{-\epsilon})/2$
over a sequence of $\epsilon$ converging to zero.
There are also standard ways of strengthening (\ref{eq:implication}) to
$$
  \liminf_{n\to\infty}\K_n<\infty
  \enspace\Longrightarrow\enspace
  \lim_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  =
  0;
$$
for details, see \cite{shafer/vovk:2001}.

In the rest of this section we will draw
on the excellent survey \cite{dawid:1986}.
% most references will be recycled from it.
We will see how Forecaster defeats
increasingly sophisticated strategies for Skeptic.

\subsection{\Case{Unbiasedness in the large}}

Following Murphy and Epstein \cite{murphy/epstein:1967},
we say that Forecaster is \emph{unbiased in the large}
if (\ref{eq:SLLN}) holds.
Let us first consider the one-sided relaxed version of this property
\begin{equation}\label{eq:one-sided}
  \limsup_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  \le
  \epsilon.
\end{equation}
The strategy for Skeptic described above, $S_n(p):=\epsilon\K_n$,
leads to Forecaster always choosing $p_n:=1$;
(\ref{eq:one-sided}) is then satisfied in a trivial way.

Forecaster's strategy corresponding to the two-sided version
\ifAIStats
  \begin{multline}\label{eq:two-sided}
\fi
\ifarXiv
  \begin{equation}\label{eq:two-sided}
\fi
\ifWP
  \begin{equation}\label{eq:two-sided}
\fi
  -\epsilon
  \le
  \liminf_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
\ifAIStats\\\fi
  \le
  \limsup_{n\to\infty}
  \frac1n\sum_{i=1}^n(y_i-p_i)
  \le
  \epsilon
\ifAIStats
  \end{multline}
\fi
\ifarXiv
  \end{equation}
\fi
\ifWP
  \end{equation}
\fi
is not much more reasonable.
Indeed, it can be represented as follows.
The initial capital $1$ is split evenly between two accounts,
and Skeptic gambles with the two accounts separately.
If at the outset of round $n$
the capital on the first account is $\K^1_{n-1}$
and the capital on the second account is $\K^2_{n-1}$,
Skeptic plays $s^1_n:=\epsilon\K^1_{n-1}$ with the first account
and $s^2_n:=-\epsilon\K^2_{n-1}$ with the second account;
his total move is
\ifAIStats
  \begin{multline*}
\fi
\ifarXiv
  \begin{equation*}
\fi
\ifWP
  \begin{equation*}
\fi
  S_n(p)
  :=
  \epsilon\K^1_{n-1}
  -
  \epsilon\K^2_{n-1}
\ifAIStats\\\fi
  =
  \epsilon
  \left(
    \prod_{i=1}^{n-1}
    (1+\epsilon(y_i-p_i))
    -
    \prod_{i=1}^{n-1}
    (1+\epsilon(p_i-y_i))
  \right).
\ifAIStats
  \end{multline*}
\fi
\ifarXiv
  \end{equation*}
\fi
\ifWP
  \end{equation*}
\fi
Therefore, Forecaster's move is $p_n:=1$ if
$$
  \sum_{i=1}^{n-1}
  \ln(1+\epsilon(y_i-p_i))
  >
  \sum_{i=1}^{n-1}
  \ln(1+\epsilon(p_i-y_i)),
$$
$p_n:=0$ if
$$
  \sum_{i=1}^{n-1}
  \ln(1+\epsilon(y_i-p_i))
  <
  \sum_{i=1}^{n-1}
  \ln(1+\epsilon(p_i-y_i)),
$$
and $p_n$ can be chosen arbitrarily in the case of equality.
The limiting form of this strategy as $\epsilon\to0$ is:
Forecaster's move is $p_n:=1$ if
$$
  \sum_{i=1}^{n-1}
  (y_i-p_i)
  >
  0,
$$
$p_n:=0$ if
$$
  \sum_{i=1}^{n-1}
  (y_i-p_i)
  <
  0,
$$
and $p_n$ can be chosen arbitrarily in the case of equality.

We can see that unbiasedness in the large does not lead to interesting forecasts:
Forecaster fulfils his task too well.
In the one-sided case (\ref{eq:one-sided}),
he always chooses $p_n:=1$ making
$$
  \sum_{i=1}^n
  (y_i-p_i)
$$
as small as possible.
In the two-sided case (\ref{eq:two-sided}) with $\epsilon\to0$,
he manages to guarantee that
\begin{equation}\label{eq:TooGood1}
  \left|
    \sum_{i=1}^n
    (y_i-p_i)
  \right|
  \le
  1.
\end{equation}
His goals are achieved with categorical forecasts, $p_n\in\{0,1\}$.

In the rest of this section we consider
the more interesting case where $S_n(p)$ depends on $p$.

\subsection{\Case{Unbiasedness in the small}}
\label{subsec:small}

We now consider a subtler requirement that forecasts should satisfy,
which we introduce informally.
We say that the forecasts $p_n$ are \emph{unbiased in the small}
(or reliable, or valid, or well calibrated)
if, for any $p^*\in[0,1]$,
\begin{equation}\label{eq:p}
  \frac
  {\sum_{i=1,\dots,n:p_i\approx p^*} y_i}
  {\sum_{i=1,\dots,n:p_i\approx p^*} 1}
  \approx
  p^*
\end{equation}
provided $\sum_{i=1,\dots,n:p_i\approx p^*} 1$ is not too small.

Let us first consider just one value for $p^*$.
Instead of the ``crisp'' point $p^*$ we will consider a ``fuzzy point''
$I:[0,1]\to[0,1]$ such that $I(p^*)=1$
and $I(p)=0$ for all $p$ outside a small neighborhood of $p^*$.
A standard choice would be something like $I:=\III_{[p_{-},p_{+}]}$,
where $[p_{-},p_{+}]$ is a short interval containing $p^*$
and $\III_{[p_{-},p_{+}]}$ is its indicator function,
but we will want $I$ to be continuous
(it can, however,
be arbitrarily close to $\III_{[p_{-},p_{+}]}$).

The strategy for Skeptic ensuring (\ref{eq:goal})
can be modified as follows.
Let $\epsilon\in(0,0.5]$ be again a small number.
Now we consider the strategy $S_n(p)=S_n^{\epsilon,I}(p):=\epsilon I(p)\K_{n-1}$.
Since
$$
  \K_n
  =
  \prod_{i=1}^n
  (1+\epsilon I(p_i)(y_i-p_i)),
$$
on the paths where $\K_n$ is bounded we have
$$
  \prod_{i=1}^n
  (1+\epsilon I(p_i)(y_i-p_i))
  \le
  C,
$$$$
  \sum_{i=1}^n
  \ln(1+\epsilon I(p_i)(y_i-p_i))
  \le
  \ln C,
$$$$
  \epsilon
  \sum_{i=1}^n
  I(p_i)(y_i-p_i)
  -
  \epsilon^2
  \sum_{i=1}^n
  I^2(p_i)
  (y_i-p_i)^2
  \le
  \ln C,
$$$$
  \epsilon
  \sum_{i=1}^n
  I(p_i)(y_i-p_i)
  -
  \epsilon^2
  \sum_{i=1}^n
  I(p_i)
  \le
  \ln C
$$
(the last step involves replacing $I^2(p_i)$ with $I(p_i)$;
the loss of precision is not great if $I$ is close to $\III_{[p_{-},p_{+}]}$),
$$
  \epsilon
  \sum_{i=1}^n
  I(p_i)(y_i-p_i)
  \le
  \ln C
  +
  \epsilon^2
  \sum_{i=1}^n
  I(p_i),
$$$$
  \frac{\sum_{i=1}^n I(p_i)(y_i-p_i)}{\sum_{i=1}^n I(p_i)}
  \le
  \frac{\ln C}{\epsilon \sum_{i=1}^n I(p_i)}
  +
  \epsilon.
$$
The last inequality shows that the mean of $y_i$ for $p_i$ close to $p^*$
is close to $p^*$
provided we have observed sufficiently many such $p_i$;
its interpretation is especially simple
when $I$ is close to $\III_{[p_{-},p_{+}]}$.

In general, we may consider a mixture of
$S_n^{\epsilon,I}(p)$ and $S_n^{-\epsilon,I}(p)$
for different values of $\epsilon$
and for different $I$ covering all $p^*\in[0,1]$.
If we make sure that the mixture is continuous
(which is always the case for continuous $I$ and finitely many $\epsilon$ and $I$),
Theorem~\ref{thm:main} provides us with forecasts
that are unbiased in the small.

\subsection{\Case{Using the objects}}
\label{subsec:objects}

Unbiasedness, even in the small,
is only a necessary but far from sufficient condition
for good forecasts:
for example, a forecaster who ignores the objects $x_n$
can be perfectly calibrated,
no matter how much useful information $x_n$ contain.
(Cf.\ the discussion of resolution in \cite{dawid:1986};
we prefer not to use the term ``resolution'',
which is too closely connected
with the very special way of probability forecasting
based on sorting and labeling.)
It is easy to make the algorithm of the previous subsection
take the objects into account:
we can allow the test functions $I$ to depend not only on $p$
but also on the current object $x_n$;
$S_n(p)$ then becomes a mixture of
$$
  S_n^{\epsilon,I}(p)
  :=
  \epsilon I(p,x_n)
  \prod_{i=1}^{n-1}
  (1+\epsilon I(p_i,x_i)(y_i-p_i))
$$
and $S_n^{-\epsilon,I}(p)$ (defined analogously)
over $\epsilon$ and $I$.

\Extra{\begin{remark*}Another popular example is:
if the observed sequence of labels is $1,0,1,0,\dots$,
the sequences of forecasts $0.5,0.5,\dots$ and $1,0,1,0,\dots$
are both unbiased in the small,
but the first of them is not as good as the second.
For this example to be covered by our discussion,
the labels $y_n=n\mod2$ should be complemented by objects,
$x_n:=n$.\end{remark*}}

\subsection{\Case{Relation to a standard counter-example}}

Suppose, for simplicity, that objects are absent ($|{\bf X}|=1$).
The standard construction from Dawid \cite{dawid:1985JASA}
showing that no forecasting strategy
produces forecasts $p_n$ that are unbiased in the small for all sequences
is as follows.
Define an infinite sequence $y_1,y_2,\dots$ recursively by
$$
  y_n
  :=
  \begin{cases}
    1 & \text{if $p_n<0.5$}\\
    0 & \text{otherwise},
  \end{cases}
$$
where $p_n$ is the forecast
produced by the forecasting strategy
after seeing $y_1,\dots,y_{n-1}$.
For the forecasts $p_n<0.5$ we always have $y_n=1$
and for the forecasts $p_n\ge0.5$ we always have $y_n=0$;
obviously, we do not have unbiasedness in the small.

Let us see what Dawid's construction gives
% (we will say ``Dawid's'', for terminological convenience)
when applied to the defensive forecasting strategy
constructed from the mixture of $S_n^{\epsilon,I}(p)$ and $S_n^{-\epsilon,I}(p)$,
as described above,
over different $\epsilon$ 
and different $I$;
we will assume not only that the test functions $I$ cover all $[0,1]$
but also that each point $p\in[0,1]$
is covered by arbitrarily narrow
(concentrated in a small neighborhood of $p$)
test functions.
% among them are many kernels of different widths.
It is clear that we will inevitably have $p_n\to0.5$
if $p_n$ are produced by the defensive forecasting strategy
and $y_n$ are produced by Dawid's construction.
On the other hand, since all test functions $I$ are continuous
and so cannot sharply distinguish between the cases $p_n<0.5$ and $p_n\ge0.5$,
we do not have any contradiction:
neither the test functions nor any observer
who can only measure the $p_n$ with a finite precision
can detect the lack of unbiasedness in the small.

In this paper we are only interested in unbiasedness in the small
when the test functions $I$ are required to be continuous.
Dawid's construction shows that unbiasedness in the small
is impossible to achieve
if $I$ are allowed to be indicator functions of intervals
(such as $[0,0.5)$ and $[0.5,1]$).
To achieve unbiasedness in the small in this stronger sense,
randomization appears necessary
(see, e.g., \cite{GTP7}).
It is interesting that already a little bit of randomization suffices,
as explained in \cite{kakade/foster:2004}.

\section{\Case{Simplified algorithm}}
\label{sec:experiments}

Let us assume first that objects are absent, $|{\bf X}|=1$.
It was observed empirically
that the performance of defensive forecasting strategies
with a fixed $\epsilon$ does not depend on $\epsilon$ much
(provided it is not too large;
e.g., in the above calculations we assumed $\epsilon\le0.5$).
This suggests letting $\epsilon\to0$
(in particular, we will assume that $\epsilon\ll n^{-2}$).
As the test functions $I$ we will take Gaussian bells $I_j$
with standard deviation $\sigma>0$
located densely and uniformly in the interval $[0,1]$.
Letting $\approx$ stand for approximate equality
and using the shorthand $\sum_{\pm}f(\pm):=f(+)+f(-)$,
we obtain:
$$
  S_n(p)
  =
  \sum_{\pm}
  \sum_j
  (\pm\epsilon)
  I_j(p)
  \prod_{i=1}^{n-1}
  (1\pm\epsilon I_j(p_i)(y_i-p_i))
$$$$
  {}=
  \sum_{\pm}
  \sum_j
  (\pm\epsilon)
  I_j(p)
  \exp
  \left(
    \sum_{i=1}^{n-1}
    \ln(1\pm\epsilon I_j(p_i)(y_i-p_i))
  \right)
$$$$
  {}\approx
  \sum_{\pm}
  \sum_j
  (\pm\epsilon)
  I_j(p)
  \exp
  \left(
    \pm\epsilon
    \sum_{i=1}^{n-1}
    I_j(p_i)(y_i-p_i)
  \right)
$$$$
  {}\approx
  \sum_{\pm}
  \sum_j
  (\pm\epsilon)
  I_j(p)
  \left(
    1\pm\epsilon
    \sum_{i=1}^{n-1}
    I_j(p_i)(y_i-p_i)
  \right)
$$$$
  {}=
  \sum_{\pm}
  \sum_j
  (\pm\epsilon)
  I_j(p)
  \left(
    \pm\epsilon
    \sum_{i=1}^{n-1}
    I_j(p_i)(y_i-p_i)
  \right)
$$$$
  {}\propto
  \sum_j
  I_j(p)
  \sum_{i=1}^{n-1}
  I_j(p_i)(y_i-p_i)
$$
\begin{equation}\label{eq:expression}
  {}=
  \sum_{i=1}^{n-1}
  K(p,p_i)(y_i-p_i),
\end{equation}
where $K(p,p_i)$ is the Mercer kernel
$$
  K(p,p_i)
  :=
  \sum_j
  I_j(p)
  I_j(p_i).
$$
This Mercer kernel can be approximated by
$$
  \int_0^1
  \frac{1}{\sqrt{2\pi}\sigma}
  \exp
  \left(
    -\frac{(t-p)^2}{2\sigma^2}
  \right)
  \frac{1}{\sqrt{2\pi}\sigma}
  \exp
  \left(
    -\frac{(t-p_i)^2}{2\sigma^2}
  \right)
  dt
$$
\begin{align*}
  &\propto
  \int_0^1
  \exp
  \left(
    -\frac{(t-p)^2+(t-p_i)^2}{2\sigma^2}
  \right)
  dt
\\
  &\approx
  \int_{-\infty}^{\infty}
  \exp
  \left(
    -\frac{(t-p)^2+(t-p_i)^2}{2\sigma^2}
  \right)
  dt.
\end{align*}
As a function of $p$,
the last expression is proportional to the density
of the sum of two Gaussian random variables of variance $\sigma^2$;
therefore, it is proportional to
\iffalse
\begin{align*}
  &=
  \int_{-\infty}^{\infty}
  \exp
  \Biggl(
    -\frac{1}{2\sigma^2}
    \Biggl(
      2 t^2 - 2 (p+p_i)t
      +
      2
      \left(
        \frac{p+p_i}{2}
      \right)^2
\\
      &\quad+
      p^2 + p_i^2
      -
      2
      \left(
        \frac{p+p_i}{2}
      \right)^2
    \Biggr)
  \Biggr)
  dt
\\
  &\propto
  \exp
  \left(
    -\frac{1}{2\sigma^2}
    \left(
      p^2 + p_i^2
      -
      2
      \left(
        \frac{p+p_i}{2}
      \right)^2
    \right)
  \right)
\end{align*}
\fi
$$
  \exp
  \left(
    -\frac{(p-p_i)^2}{4\sigma^2}
  \right).
$$

To get an idea of the properties of this forecasting strategy,
which we call the \emph{K29} strategy (or algorithm),
we run it and the Laplace forecasting strategy
($p_n:=(k+1)/(n+1)$, where $k$ is the number of 1s observed so far)
on a randomly generated bit sequence of length 1000
(with the probability of $1$ equal to $0.5$).
A zero point $p_n$ of $S_n$ was found using the simple bisection procedure
(see, e.g., \cite{press/etal:1992}, \S\S9.2--9.4, for more sophisticated methods):
(a) start with the interval $[0,1]$;
(b) let $p$ be the mid-point of the current interval;
(c) if $S_n(p)>0$, remove the left half of the current interval;
    otherwise, remove its right half;
(d) go to (b).
We did 10 iterations,
after which the mid-point of the remaining interval was output as $p_n$.
Notice that the values $S_n(0)$ and $S_n(1)$
did not have to be tested.
Our program was written in MATLAB, Version 7,
and the initial state of the random number generator was set to 0.

Figure~\ref{fig:1000} shows that the probabilities output
by the K29 ($\sigma=0.01$) and Laplace forecasting strategies
are almost indistinguishable.
% their Brier losses $\sum_{i=1}^{1000}(y_i-p_i)^2$
% are also very close:
% $251.51$ for Laplace and $252.50$ for K29.
To see that these two forecasting strategies can behave very differently,
we complemented the $1000$ bits generated as described above
with $1000$ 0s followed by $1000$ 1s.
The result is shown in Figure~\ref{fig:3000}.
The K29 strategy detects that the probability $p$ of $1$ changes
after the $1000$th round,
and fairly quickly moves down.
When the probability changes again after the $2000$th round,
K29 starts moving toward $p=1$,
but interestingly,
hesitates around the line $p=0.5$,
as if expecting the process to reverse
to the original probability of 1.

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art1000bw.eps}
  \caption{The First $1000$ Probabilities Output
    by the K29 ($\sigma=0.01$) and Laplace Forecasting Strategies
    on a Randomly Generated Bit Sequence
  \label{fig:1000}}
\end{figure}

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art3000bw.eps}
  \caption{The Probabilities Output
    by the K29 ($\sigma=0.01$) and Laplace Forecasting Strategies
    on a Randomly Generated Sequence of $1000$ Bits
    Followed by $1000$ 0s and $1000$ 1s
  \label{fig:3000}}
\end{figure}

The Mercer kernel
$$
  K(p,p_i)
  =
  \exp
  \left(
    -\frac{(p-p_i)^2}{4\sigma^2}
  \right)
$$
used in these experiments is known in machine learning
as the Gaussian kernel
(in the usual parameterization $4\sigma^2$ is replaced by $2\sigma^2$ or $c$);
however, many other Mercer kernels also give reasonable results.

If we start from test functions $I$ depending on the object,
instead of (\ref{eq:expression})
we will arrive at the expression
\begin{equation}\label{eq:S}
  S_n(p)
  =
  \sum_{i=1}^{n-1}
  K((p,x_n),(p_i,x_i))(y_i-p_i),
\end{equation}
where $K$ is a Mercer kernel on the squared product $([0,1]\times{\bf X})^2$.
There are standard ways of constructing such Mercer kernels
from Mercer kernels on $[0,1]^2$ and ${\bf X}^2$
(see, e.g., the description of tensor products and direct sums
in \cite{vapnik:1998,scholkopf/smola:2002}).
For $S_n$ to be continuous,
we have to require that $K$ be \emph{forecast-continuous}
in the following sense:
for all $x\in{\bf X}$ and all $(p',x')\in[0,1]\times{\bf X}$,
$K((p,x),(p',x'))$ is continuous as a function of $p$.
The overall procedure can be summarized as follows.

\medskip

\noindent
\textsc{K29 Algorithm}

\noindent
\textbf{Parameter:} forecast-continuous Mercer kernel $K$ on $([0,1]\times{\bf X})^2$

\parshape=6
\IndentI   \WidthI
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\IndentII  \WidthII
\noindent
FOR $n=1,2,\dots$:\\
  Read $x_n\in{\bf X}$.\\
  Define $S_n(p)$ as per (\ref{eq:S}).\\
  Output any root $p$ of $S_n(p)=0$ as $p_n$;\\
  if there are no roots, $p_n:=(1+\sign(S_n))/2$.\\
  Read $y_n\in\{0,1\}$.

\medskip

\noindent
Computer experiments reported in \cite{GTP9}
show that the K29 algorithm
performs well on a standard benchmark data set.
For a theoretical discussion of the K29 algorithm,
\ifAIStats see \cite{GTP8local} (Appendix) \fi
\ifarXiv see \cite{GTP8local} (Appendix) \fi
\ifWP see the appendix \fi
and \cite{GTP11}.

\section{\Case{Related work and directions of further research}}
\label{sec:conclusion}

This paper's methods connect two areas
that have been developing independently so far:
probability forecasting and classical probability theory.
It appears that, when properly developed,
these methods can benefit both areas:
\begin{itemize}
\item
  the powerful machinery of classical probability theory
  can be used for probability forecasting;
\item
  practical problems of probability forecasting
  may suggest new laws of probability.
\end{itemize}

Classical probability theory started from Bernoulli's weak law of large numbers (1713)
and is the subject of countless monographs and textbooks.
% the first central limit theorem was derived by de Moivre (1733);
% the first strong law of large numbers by Borel (1909);
% the first law of the iterated logarithm by Khinchin (1924);
% Hoeffding published his inequality in 1963.
The original statements of most of its results
were for independent random variables,
but they were later extended to the martingale framework;
the latter was reduced to its game-theoretic core in \cite{shafer/vovk:2001}.
The proof of the strong law of large numbers used in this paper
was extracted from Ville's \cite{ville:1939} martingale proof
of the law of the iterated logarithm (upper half).

The theory of probability forecasting was a topic of intensive research in meteorology
in the 1960s and 1970s;
this research is summarized in \cite{dawid:1986}.
Machine learning is still mainly concerned with categorical prediction,
but the situation appears to be changing.
Probability forecasting using Bayesian networks
is a mature field;
the literature devoted to probability forecasting using decision trees
and to calibrating other algorithms
is also fairly rich.
So far, however, the field of probability forecasting
has been developing without any explicit connections
with classical probability theory.

Defensive forecasting is indirectly related,
in a sense dual,
to prediction with expert advice
(reviewed in \cite{vovk:2001competitive}, \S4)
and its special case, Bayesian prediction.
In prediction with expert advice
one starts with a given loss function
and tries to make predictions that lead to a small loss
as measured by that loss function.
In defensive forecasting,
one starts with a law of probability
and then makes predictions
such that this law of probability is satisfied.
So the choice of the law of probability
when designing the forecasting strategy
plays a role analogous to the choice of the loss function
in prediction with expert advice.

In prediction with expert advice
one combines a pool of potentially promising forecasting strategies
to obtain a forecasting strategy
that performs not much worse than the best strategies in the pool.
In defensive forecasting
one combines strategies for Skeptic
(such as the strategies corresponding to different test functions $I$
and different $\pm\epsilon$ in \S\ref{sec:examples})
to obtain one strategy achieving an interesting goal
(such as unbiasedness in the small);
a strategy for Forecaster
is then obtained using Theorem~\ref{thm:main}.
The possibility of mixing strategies for Skeptic
is as fundamental in defensive forecasting
as the possibility of mixing strategies for Forecaster
in prediction with expert advice.

This paper continues the work
started by Foster and Vohra~\cite{foster/vohra:1998}
and later developed in, e.g., \cite{lehrer:2001,sandroni/etal:2003,GTP7}
(the last paper replaces the von Mises--style framework
of the previous papers with a martingale framework,
as in this paper).
The approach of this paper is similar to that
of the recent paper \cite{kakade/foster:2004},
which also considers deterministic forecasting strategies
and continuous test functions for unbiasedness in the small.

The main difference of this paper's approach
from %\cite{vovk/etal:2004} and 
the bulk of work in learning theory
is that we do not make any assumptions about Reality's strategy.

The following directions of further research
appear to us most important:
\begin{itemize}
\item
  extending Theorem~\ref{thm:main} to other forecasting protocols
  (such as multi-label classification)
  and designing efficient algorithms for finding the corresponding $p_n$;
\item
  exploring forecasting strategies corresponding to:
  (a) Hoeffding's inequality, (b) the central limit theorem,
  (c) the law of the iterated logarithm
  (all we did in this paper was to slightly extend the strong law of large numbers
  and then use it for probability forecasting).
%\item
%  empirically exploring Mercer kernels taking into account the objects,
%  as described at the end of \S\ref{sec:experiments};
%\item
%  formalizing the notion of unbiasedness in the small
%  to state formally the ``strong law of large numbers in the small''
%  proved in \S\ref{subsec:small}
%  (in principle, it might be possible to use one of the available formalizations,
%  as in \cite{kakade/foster:2004},
%  but it is preferable to have a ``point-wise'' definition).
\end{itemize}

\subsection*{Acknowledgments}

We are grateful to the participants of the PASCAL workshop
``Notions of complexity: information-theoretic, computational and statistical approaches''
(October 2004, EURANDOM)
who commented on this work
and to the anonymous referees for useful suggestions.
This work was partially supported
by BBSRC (grant 111/BIO14428),
EPSRC (grant GR/R46670/01),
MRC (grant S505/65),
% European Commission (grant IST-1999-10226),
Royal Society,
and, especially,
the Superrobust Computation Project
(Graduate School of Information Science and Technology,
University of Tokyo).
\ifAIStats
  \bibliographystyle{plain}
\fi
\ifarXiv
%  \bibliographystyle{plain_small}
% start
\begin{thebibliography}{10}{\small

\bibitem{dawid:1985JASA}
A\DOT{}~Philip Dawid.
\newblock Self-calibrating priors do not exist: {C}omment.
\newblock {\em Journal of the American Statistical Association}, 80:340--341,
  1985.
\newblock This is a contribution to the discussion in \cite{oakes:1985}.

\bibitem{dawid:1986}
A\DOT{}~Philip Dawid.
\newblock Probability forecasting.
\newblock In Samuel Kotz, Norman~L\DOT{} Johnson, and Campbell~B\DOT{} Read,
  editors, {\em Encyclopedia of Statistical Sciences}, volume~7, pages
  210--218. Wiley, New York, 1986.

\bibitem{doob:1953}
Joseph~L\DOT{} Doob.
\newblock {\em Stochastic Processes}.
\newblock Wiley, New York, 1953.

\bibitem{foster/vohra:1998}
Dean~P\DOT{} Foster and Rakesh~V\DOT{} Vohra.
\newblock Asymptotic calibration.
\newblock {\em Bio\-met\-rika}, 85:379--390, 1998.

\bibitem{kakade/foster:2004}
Sham~M\DOT{} Kakade and Dean~P\DOT{} Foster.
\newblock Deterministic calibration and {N}ash equilibrium.
\newblock In John Shawe-Taylor and Yoram Singer, editors, {\em Proceedings of
  the Seventeenth Annual Conference on Learning Theory}, volume 3120 of {\em
  Lecture Notes in Computer Science}, pages 33--48, Heidelberg, 2004. Springer.

\bibitem{lehrer:2001}
Ehud Lehrer.
\newblock Any inspection is manipulable.
\newblock {\em Eco\-no\-met\-rica}, 69:1333--1347, 2001.

\bibitem{murphy/epstein:1967}
Allan~H\DOT{} Murphy and Edward~S\DOT{} Epstein.
\newblock Verification of probabilistic predictions: a brief review.
\newblock {\em Journal of Applied Meteorology}, 6:748--755, 1967.

\bibitem{oakes:1985}
David Oakes.
\newblock Self-calibrating priors do not exist (with discussion).
\newblock {\em Journal of the American Statistical Association}, 80:339--342,
  1985.

\bibitem{press/etal:1992}
William~H\DOT{} Press, Brian~P\DOT{} Flannery, Saul~A\DOT{} Teukolsky, and
  William~T\DOT{} Vetterling.
\newblock {\em Numerical Recipes in C}.
\newblock Cambridge University Press, Cambridge, second edition, 1992.

\bibitem{sandroni/etal:2003}
Alvaro Sandroni, Rann Smorodinsky, and Rakesh~V\DOT{} Vohra.
\newblock Calibration with many checking rules.
\newblock {\em Mathematics of Operations Research}, 28:141--153, 2003.

\bibitem{scholkopf/smola:2002}
Bernhard Sch\"olkopf and Alexander~J\DOT{} Smola.
\newblock {\em Learning with Kernels}.
\newblock MIT Press, Cambridge, MA, 2002.

\bibitem{shafer/vovk:2001}
Glenn Shafer and \Vladimir{} Vovk.
\newblock {\em Probability and Finance: It's Only a Game!}
\newblock Wiley, New York, 2001.

\bibitem{vapnik:1998}
Vladimir~N\DOT{} Vapnik.
\newblock {\em Statistical Learning Theory}.
\newblock Wiley, New York, 1998.

\bibitem{ville:1939}
Jean Ville.
\newblock {\em Etude critique de la notion de collectif}.
\newblock Gauthier-Villars, Paris, 1939.

\bibitem{vovk:2001competitive}
Vladimir Vovk.
\newblock Competitive on-line statistics.
\newblock {\em International Statistical Review}, 69:213--248, 2001.

\bibitem{GTP9}
\Vladimir{} Vovk.
\newblock Defensive forecasting for a benchmark data set, {T}he
  {G}ame-{T}he\-o\-ret\-ic {P}robability and {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#9, September 2004.

\bibitem{GTP11}
\Vladimir{} Vovk.
\newblock Non-asymptotic calibration and resolution, {T}he
  {G}ame-{T}he\-o\-ret\-ic {P}robability and {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#11, November 2004.

\bibitem{GTP7}
\Vladimir{} Vovk and Glenn Shafer.
\newblock Good randomized sequential probability forecasting is always
  possible, {T}he {G}ame-{T}heoretic {P}robability and {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#7, June 2003 (revised September 2004).

\bibitem{GTP8local}
\Vladimir{} Vovk, Akimichi Takemura, and Glenn Shafer.
\newblock Defensive forecasting, {T}he {G}ame-{T}heoretic {P}robability and
  {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#8, September 2004 (revised January 2005).
\newblock This is a fuller version of the current paper, with an appendix
  added.

}\end{thebibliography}
% end
\fi
\ifWP
  \bibliographystyle{plain}
\fi
\iffalse
\bibliography{%
  /doc/work/r/bib/math/math,%
  /doc/work/r/bib/prob/prob,%
  /doc/work/r/bib/stat/stat,%
  /doc/work/r/bib/vovk/vovk,%
  local}
\fi
\ifWP
\appendix
\section*{Appendix: Geometry of the K29 algorithm and weak probability theory}
\addcontentsline{toc}{section}{Appendix: Geometry of the K29 algorithm
	and weak probability theory}

In this paper the K29 algorithm was derived,
somewhat informally,
from the requirement that the forecasts should be unbiased in the small.
However, since in this derivation we assumed that $\epsilon$ was very small,
we cannot longer assert that the algorithm obtained (K29)
is unbiased in the small.
In this appendix we will give a direct argument
showing that the K29 algorithm can be expected
to be unbiased in the small.
The figures in this appendix will be given in color
(color is especially important for Figure~\ref{fig:3000A2}).

\subsection*{What K29 accomplishes}

In this subsection we reproduce
a result from~\cite{GTP11}
(Theorem~\ref{thm:K29} below coincides with Theorem~1 of~\cite{GTP11})
and complement it by related results
showing connections with classical probability theory.

Following the K29 algorithm
Forecaster ensures that Skeptic will never increase his capital
with the strategy
\begin{equation}\label{eq:strategy}
  s_n
  :=
  \sum_{i=1}^{n-1}
  K
  \left(
    (p_n,x_n),(p_i,x_i)
  \right)
  (y_i-p_i).
\end{equation}
(This strategy is not necessarily valid in the sense of guaranteeing
Skeptic's solvency;
we will take care of the latter later on.)
The increase in Skeptic's capital when he follows~(\ref{eq:strategy}) is
\begin{multline}\label{eq:increase1}
  \K_N-\K_0
  =
  \sum_{n=1}^N
  s_n(y_n-p_n)\\
  =
  \sum_{n=1}^N
  \sum_{i=1}^{n-1}
  K
  \left(
    (p_n,x_n),(p_i,x_i)
  \right)
  (y_n-p_n)
  (y_i-p_i)\\
  =
  \frac12
  \sum_{n=1}^N
  \sum_{i=1}^N
  K
  \left(
    (p_n,x_n),(p_i,x_i)
  \right)
  (y_n-p_n)
  (y_i-p_i)\\
  -
  \frac12
  \sum_{n=1}^N
  K
  \left(
    (p_n,x_n),(p_n,x_n)
  \right)
  (y_n-p_n)^2
\end{multline}
(we generalize slightly the protocol of \S\ref{sec:gambling}
allowing initial values $\K_0$ of Skeptic's capital different from 1).
According to Mercer's theorem
(a very simple proof of a suitable version
can be found in \cite{doob:1953}, Theorem~II.3.1),
there exists a function $\Phi:[0,1]\times{\bf X}\to H$
(a \emph{feature mapping} taking values in a Hilbert space $H$)
such that
\begin{equation}\label{eq:K}
  K(a,b)
  =
  \Phi(a)\cdot\Phi(b),
  \enspace
  \forall a,b\in[0,1]\times{\bf X}
\end{equation}
($\cdot$ standing for the dot product in $H$).
Therefore, we can rewrite (\ref{eq:increase1}) as
\begin{multline}\label{eq:increase2}
  \K_N-\K_0
  =
  \frac12
  \left\|
    \sum_{n=1}^N
    (y_n-p_n)
    \Phi(p_n,x_n)
  \right\|^2
  -
  \frac12
  \sum_{n=1}^N
  \left\|
    (y_n-p_n)
    \Phi(p_n,x_n)
  \right\|^2.
\end{multline}

To make sure that Skeptic never goes bankrupt,
let us consider a finite-horizon game with $N$ the horizon
(i.e., ``FOR $n=1,2,\dots$'' in the protocol of \S\ref{sec:gambling}
is replaced by ``FOR $n=1,\dots,N$''),
assume that
\begin{equation}\label{eq:C}
  C
  :=
  \sup_{p,x}
  \left\|
    \Phi(p,x)
  \right\|
  <
  \infty
\end{equation}
(it is often a good idea to use Mercer kernels with $C=1$),
and set
$$
  \K_0
  :=
  \frac12 NC^2
$$
(the latter ensuring $\K_n\ge0$, $\forall n$).
With game-theoretic lower probability at least $1-\delta$
we will have $\K_N<\frac{1}{\delta}\K_0$,
which, in combination with (\ref{eq:increase2}), implies
$$
  \frac12
  \left\|
    \sum_{n=1}^N
    (y_n-p_n)
    \Phi(p_n,x_n)
  \right\|^2
  \le
  \K_N
  <
  \frac{1}{\delta}\K_0
  =
  \frac{1}{2\delta} NC^2,
$$
i.e.,
$$
  \left\|
    \sum_{n=1}^N
    (y_n-p_n)
    \Phi(p_n,x_n)
  \right\|^2
  <
  \frac{NC^2}{\delta},
$$
\begin{equation*}
  \left\|
    \frac1N
    \sum_{n=1}^N
    (y_n-p_n)
    \Phi(p_n,x_n)
  \right\|
  <
  \frac{C}{\sqrt{N\delta}}.
\end{equation*}
Therefore, we have proved:
\begin{theorem}\label{thm:WLLN}
  Let $N\in\{1,2,\dots\}$, $\delta>0$,
  $\Phi:[0,1]\times{\bf X}\to H$ for a Hilbert space $H$,
  and $C$ be defined by (\ref{eq:C}).
  Then
  \begin{equation}\label{eq:bound}
    \LP
    \left\{
      \left\|
        \frac1N
        \sum_{n=1}^N
        (y_n-p_n)
        \Phi(p_n,x_n)
      \right\|
      <
      \frac{C}{\sqrt{N\delta}}
    \right\}
    \ge
    1-\delta
  \end{equation}
  in Binary Forecasting Game I with horizon $N$.
\end{theorem}
It is clear that the K29 algorithm ensures the inequality
within the curly braces in (\ref{eq:bound}) for any $\delta>0$;
this is stated in the following theorem,
in which we also remove the assumption of a finite horizon.
\begin{theorem}\label{thm:K29}
  The K29 algorithm with parameter $K$ ensures
  \begin{equation}\label{eq:TooGood2}
    \sup_{N\in\{1,2,\dots\}}
    \left\|
      \frac{1}{\sqrt{N}}
      \sum_{n=1}^N
      (y_n-p_n)
      \Phi(p_n,x_n)
    \right\|
    \le
    C
  \end{equation}
  in Binary Forecasting Game I,
  where $\Phi$ is a mapping taking values in a Hilbert space
  and satisfying~(\ref{eq:K}).
\end{theorem}
In this theorem we can still observe the phenomenon
we saw earlier (cf.\ (\ref{eq:TooGood1})):
the forecasts are calibrated better than in the case
of genuine randomness.
Let us take, for simplicity, $\Phi\equiv1$.
According to the law of the iterated logarithm,
we would expect
$$
  \limsup_{N\to\infty}
  \left|
    \frac{1}{\sqrt{2A_N\ln\ln A_N}}
    \sum_{n=1}^N
    (y_n-p_n)
  \right|
  =
  1,
$$
where
$$
  A_N
  :=
  \sum_{n=1}^N
  p_n(1-p_n),
$$
and so
$$
  \sup_{N\in\{1,2,\dots\}}
  \left\|
    \frac{1}{\sqrt{N}}
    \sum_{n=1}^N
    (y_n-p_n)
    \Phi(p_n,x_n)
  \right\|
$$
to be infinite for $p_n$ not consistently very close to 0 or 1.

\begin{remark*}
  The parameter $K$ of the K29 algorithm
  is required to be forecast-continuous.
  If $K$ satisfies (\ref{eq:K}) with $\Phi(p,x)$ continuous in $p$ (for any $x$),
  $K$ is forecast-continuous;
  moreover,
  in this case $K((p,x),(p',x'))$ is continuous in $(p,p')$ (for any $(x,x')$).
  On the other hand,
  the last property implies that the mapping $\Phi$
  in the representation~(\ref{eq:K}) can be chosen continuous
  (\cite{parthasarathy/schmidt:1972};
  \cite{scholkopf/smola:2002}, Proposition~2.14 on p.~41).
\end{remark*}

\subsection*{Connection with \S\S\ref{subsec:small}--\ref{subsec:objects}}

Let $(p^*,x^*)$ be a point in $[0,1]\times{\bf X}$;
we would like the average of $y_n$, $n=1,\dots,N$,
such that $(p_n,x_n)$ is close to $(p^*,x^*)$
to be close to $p^*$.
(Cf.\ (\ref{eq:p}) and the discussion in \S\ref{subsec:objects}.)
Fix a forecast-continuous Mercer kernel $K:([0,1]\times{\bf X})^2\to\bbbr$
and consider the ``soft neighborhood''
\begin{equation}\label{eq:I}
  I_{(p^*,x^*)}(p,x)
  :=
  K((p^*,x^*),(p,x))
\end{equation}
of the point $(p^*,x^*)$.
The following is an easy corollary of Theorem~\ref{thm:K29}
(we refrain from stating the analogous corollary
for Theorem~\ref{thm:WLLN}).
\begin{corollary}\label{cor:calibration}
  In Binary Forecasting Game I with horizon $N$,
  the K29 algorithm with parameter $K\ge0$ ensures
  \begin{equation}\label{eq:calibration}
    \left|
      \frac
      {
        \sum_{n=1}^N
        (y_n-p_n)
        I_{(p^*,x^*)}(p_n,x_n)
      }
      {
        \sum_{n=1}^N
        I_{(p^*,x^*)}(p_n,x_n)
      }
    \right|
    \le
    \frac
    {
      C^2\sqrt{N}
    }
    {
      \sum_{n=1}^N
      I_{(p^*,x^*)}(p_n,x_n)
    }
  \end{equation}
  for each point $(p^*,x^*)\in([0,1]\times{\bf X})$,
  where $I$ is defined by (\ref{eq:I}).
\end{corollary}
This corollary implies that we can expect unbiasedness
in the ``soft neighborhood'' of $(p^*,x^*)$ when
$$
  \sum_{n=1}^N
  I_{(p^*,x^*)}(p_n,x_n)
  \gg
  \sqrt{N}.
$$
\begin{Proof}{of Corollary~\ref{cor:calibration}}
  Let $\Phi:[0,1]\times{\bf X}\to H$ be a function
  taking values in a Hilbert space $H$
  and satisfying (\ref{eq:K}).
  Theorem~\ref{thm:K29} and the Cauchy--Schwarz inequality imply
  \begin{multline*}
    \left|
      \frac{1}{\sqrt{N}}
      \sum_{n=1}^N
      (y_n-p_n)
      I_{(p^*,x^*)}(p_n,x_n)
    \right|\\
    =
    \left|
      \left(
        \frac{1}{\sqrt{N}}
        \sum_{n=1}^N
        (y_n-p_n)
        \Phi(p_n,x_n)
      \right)
      \cdot
      \Phi(p^*,x^*)
    \right|\\
    \le
    \left\|
      \frac{1}{\sqrt{N}}
      \sum_{n=1}^N
      (y_n-p_n)
      \Phi(p_n,x_n)
    \right\|
    \left\|
      \Phi(p^*,x^*)
    \right\|
    \le
    C^2;
  \end{multline*}
  the inequality between the extreme terms of this chain
  is equivalent to (\ref{eq:calibration}).
  \qedtext
\end{Proof}

\subsection*{Connection with the weak law of large numbers}

Despite the fact that K29 was derived from a proof of the strong law of large numbers,
it is closely connected with the weak law:
indeed, if $\Phi(p,x)\equiv1$,
(\ref{eq:bound}) is a form of Bernoulli's theorem.
To see this, rewrite (\ref{eq:bound}) as
$$
  \UP
  \left\{
    \left\|
      \frac1N
      \sum_{n=1}^N
      (y_n-p_n)
      \Phi(p_n,x_n)
    \right\|
    \ge
    \epsilon
  \right\}
  \le
  \frac{C^2}{N\epsilon^2},
$$
substitute $1$ for $\Phi$ and $1$ for $C$ (see (\ref{eq:C})),
and compare
\begin{equation}\label{eq:Bernoulli}
  \UP
  \left\{
    \left|
      \frac1N
      \sum_{n=1}^N
      (y_n-p_n)
    \right|
    \ge
    \epsilon
  \right\}
  \le
  \frac{1}{N\epsilon^2}
\end{equation}
with the first displayed equation on p.~126 of \cite{shafer/vovk:2001}.

\begin{remark*}
  The measure-theoretic counterpart of (\ref{eq:Bernoulli})
  was first proven by Kolmogorov in 1929;
  this is the origin of the current (provisional) name of the K29 algorithm.
  The combination of equations (3) and (7) in \cite{kolmogorov:1929LLN} gives,
  essentially,
  \begin{equation}\label{eq:Kolmogorov}
    \Prob
    \left\{
      \left|
        \sum_{n=1}^N
        Z_n
      \right|
      \ge
      \epsilon
    \right\}
    \le
    \frac{1}{\epsilon^2}
    \sum_{n=1}^N
    \Expect
    \left(
      Z_n^2
      \given
      \FFF_{n-1}
    \right),
  \end{equation}
  where $Z_1,\dots,Z_n$ is a martingale difference w.r.\ to the filtration $(\FFF_i)_{i=1}^n$
  and $\FFF_0$ is the trivial $\sigma$-algebra;
  (\ref{eq:Kolmogorov}) is more general
  than the measure-theoretic counterpart of (\ref{eq:Bernoulli}).
  (Of course, Kolmogorov did not use this terminology;
  the modern notion of martingale was introduced by Ville \cite{ville:1939}.)
\end{remark*}

\subsection*{Examples}

We can see that, for $\Phi\equiv1$,
(\ref{eq:bound}) is a formalization of unbiasedness in the large.
It is intuitively clear that (\ref{eq:bound}) may express
unbiasedness in the small with good resolution
if $\Phi$ is a sufficiently twisted surface
(assuming, for simplicity, that ${\bf X}$ is a continuous space)
in $H$:
if pairwise distant points $(p_i,x_i)$, $i=1,\dots,m$, in $[0,1]\times{\bf X}$
are mapped by $\Phi$ to vectors $\Phi(p_i,x_i)$
that are far from being dependent
(we will call this the \emph{diversity} property of $\Phi$),
then unbiasedness is required to hold in the neighborhood of each point,
not just in the large.

To consider a simple example,
let us now assume that objects $x_n$ are absent
($|{\bf X}|=1$);
$\Phi=\Phi(p)$ is then a path in the Hilbert space $H$.
The path $\Phi(p):=e^{ip}$ in the complex plane
satisfies, to some (rather weak) degree, the diversity property:
$\Phi(p)$ and $\Phi(p')$ are not collinear
for distant $p$ and $p'$;
the corresponding Mercer kernel is $K(p,p')=\cos(p-p')$.
Figures \ref{fig:1000A0} and \ref{fig:3000A0}
are the analogues of Figures \ref{fig:1000} and \ref{fig:3000}
for this Mercer kernel.
A possible explanation for the rugged shape of the solid line in Figure \ref{fig:1000A0}
is that $\Phi$ is not diverse enough:
the two-dimensional complex plane
simply does not have enough room for much diversity.
If we take $\Phi(p):=e^{cip}$ for $c>1$
in an attempt to increase diversity
for moderately distant points,
we will risk very distant points becoming collinear or nearly collinear;
even the Mercer kernel based on $\Phi(p):=e^{\pi ip}$ occasionally confuses 0 and 1,
which are mapped to collinear vectors
(see Figures \ref{fig:1000A1} and \ref{fig:3000A1}).
The forecasts become very bad for $\Phi(p):=e^{2\pi ip}$
(Figure \ref{fig:1000A2}),
although even in this case the performance can be surprisingly good
for categorical (0 or 1) forecasts
(see Figure \ref{fig:3000A1};
there is only one error after round 2000).

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art1000colA0.eps}
  \caption{Analogue of Figure \ref{fig:1000}
    for the Mercer kernel $K(p,p'):=\cos(p-p')$
  \label{fig:1000A0}}
\end{figure}

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art3000colA0.eps}
  \caption{Analogue of Figure \ref{fig:3000}
    for the Mercer kernel $K(p,p'):=\cos(p-p')$
  \label{fig:3000A0}}
\end{figure}

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art1000colA1.eps}
  \caption{Analogue of Figure \ref{fig:1000}
    for the Mercer kernel $K(p,p'):=\cos(\pi(p-p'))$
  \label{fig:1000A1}}
\end{figure}

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art3000colA1.eps}
  \caption{Analogue of Figure \ref{fig:3000}
    for the Mercer kernel $K(p,p'):=\cos(\pi(p-p'))$
  \label{fig:3000A1}}
\end{figure}

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art1000colA2.eps}
  \caption{Analogue of Figure \ref{fig:1000}
    for the Mercer kernel $K(p,p'):=\cos(2\pi(p-p'))$
  \label{fig:1000A2}}
\end{figure}

\begin{figure}[bt]
  \centering
    \includegraphics[width=\picturewidth]{art3000colA2.eps}
  \caption{Analogue of Figure \ref{fig:3000}
    for the Mercer kernel $K(p,p'):=\cos(2\pi(p-p'))$
  \label{fig:3000A2}}
\end{figure}

Much greater diversity is provided by the Gaussian kernel
$$
  K(p,p')
  :=
  \exp
  \left(
    -\frac{(p-p')^2}{c}
  \right),
$$
where $c$ is a small positive number:
$\Phi(p)$ and $\Phi(p')$ are nearly orthogonal for distant $p$ and $p'$.
It is easy to check that this kernel corresponds to the Fourier feature mapping
\begin{align*}
  \Phi(p): \bbbr&\to\bbbc\\
           \lambda&\mapsto e^{i\lambda p}
\end{align*}
with the following dot product in the feature space:
$$
  f \cdot g
  =
  \frac{1}{\sqrt{2\pi}}
  \int
  f(\lambda) \overline{g}(\lambda)
  e^{-c\lambda^2/4}
  d\lambda.
$$

\subsection*{Weak probability theory}

The research program proposed in this paper
consists in using Theorem~\ref{thm:main}
to transform laws of probability into forecasting strategies.
However, a closer look at Theorem~\ref{thm:main} reveals
that we need much less than a law of probability
to derive a forecasting strategy.
In this subsection we introduce a suitable relaxation
of the game-theoretic probability theory as developed in \cite{shafer/vovk:2001};
we will assume that the reader is familiar with,
or has access to,
the main definitions of \cite{shafer/vovk:2001}
(we will, however, use the words ``weak'' and ``weakly''
in a different sense from \cite{shafer/vovk:2001}).

Let us say that Skeptic can \emph{weakly force} an event $E$
if he has a strategy in Binary Forecasting Game~I
that guarantees the disjunction
\begin{equation*}%\label{eq:disjunction}
  \left(
    \exists n:
    \K_n < \K_{n+1}
  \right)
  \text{ or }
  E.
\end{equation*}
Theorem~\ref{thm:main} shows that if Skeptic can weakly force an event $E$
with a continuous strategy,
Forecaster has s strategy in Basic Binary Forecasting Protocol
that guarantees $E$.

\emph{Weak probability theory} corresponding to the notion of weakly forcing
is radically different from the standard probability theory.
To see this,
remember that the usual results of probability theory
(the strong law of large numbers, the law of the logarithm, etc.;
cf.\ \cite{shafer/vovk:2001})
remain interesting even when we fix Forecaster's strategy;
in fact,
most of these results were first discovered for the fair-coin protocol
(\cite{shafer/vovk:2001}, \S3.1).
It is easy to see that an event $E$ can be weakly forced
when Forecaster follows a fixed strategy producing forecasts in $(0,1)$
if and only if $E$ is non-empty.
It is clear that the situation will not change
if we require Skeptic's strategy to be continuous.

All three of the following closely related properties
of an event $E$ appear to be interesting:
\begin{itemize}
\item
  $E$ can be weakly forced;
\item
  $E$ can be weakly forced with a continuous strategy;
\item
  Forecaster can guarantee $E$ in Basic Binary Forecasting Protocol.
\end{itemize}
We believe that these properties and relations between them
deserve serious study.
\iffalse
In conclusion, we will give a simple example showing that the last property
is different from the fist two:
the event~(\ref{eq:TooGood1}) satisfies all three properties,
but the last property is also satisfied by the event
\begin{equation*}
  \left|
    \sum_{i=1}^n
    (y_i-p_i)
  \right|
  \le
  \frac12
\end{equation*}
(Forecaster starts with $p_1=1/2$ and then predicts $p_n=y_{n-1}$, $n=2,3,\dots$)
whereas the first two properties are not satisfied by
\begin{equation*}
  \left|
    \sum_{i=1}^n
    (y_i-p_i)
  \right|
  \le
  1-\epsilon
\end{equation*}
for any $\epsilon>0$.
\fi
%\lastpageDF
\fi
\end{document}

cs0505083.extracted_bib
\begin{thebibliography}{10}{\small

\bibitem{dawid:1985JASA}
A\DOT{}~Philip Dawid.
\newblock Self-calibrating priors do not exist: {C}omment.
\newblock {\em Journal of the American Statistical Association}, 80:340--341,
  1985.
\newblock This is a contribution to the discussion in \cite{oakes:1985}.

\bibitem{dawid:1986}
A\DOT{}~Philip Dawid.
\newblock Probability forecasting.
\newblock In Samuel Kotz, Norman~L\DOT{} Johnson, and Campbell~B\DOT{} Read,
  editors, {\em Encyclopedia of Statistical Sciences}, volume~7, pages
  210--218. Wiley, New York, 1986.

\bibitem{doob:1953}
Joseph~L\DOT{} Doob.
\newblock {\em Stochastic Processes}.
\newblock Wiley, New York, 1953.

\bibitem{foster/vohra:1998}
Dean~P\DOT{} Foster and Rakesh~V\DOT{} Vohra.
\newblock Asymptotic calibration.
\newblock {\em Bio\-met\-rika}, 85:379--390, 1998.

\bibitem{kakade/foster:2004}
Sham~M\DOT{} Kakade and Dean~P\DOT{} Foster.
\newblock Deterministic calibration and {N}ash equilibrium.
\newblock In John Shawe-Taylor and Yoram Singer, editors, {\em Proceedings of
  the Seventeenth Annual Conference on Learning Theory}, volume 3120 of {\em
  Lecture Notes in Computer Science}, pages 33--48, Heidelberg, 2004. Springer.

\bibitem{lehrer:2001}
Ehud Lehrer.
\newblock Any inspection is manipulable.
\newblock {\em Eco\-no\-met\-rica}, 69:1333--1347, 2001.

\bibitem{murphy/epstein:1967}
Allan~H\DOT{} Murphy and Edward~S\DOT{} Epstein.
\newblock Verification of probabilistic predictions: a brief review.
\newblock {\em Journal of Applied Meteorology}, 6:748--755, 1967.

\bibitem{oakes:1985}
David Oakes.
\newblock Self-calibrating priors do not exist (with discussion).
\newblock {\em Journal of the American Statistical Association}, 80:339--342,
  1985.

\bibitem{press/etal:1992}
William~H\DOT{} Press, Brian~P\DOT{} Flannery, Saul~A\DOT{} Teukolsky, and
  William~T\DOT{} Vetterling.
\newblock {\em Numerical Recipes in C}.
\newblock Cambridge University Press, Cambridge, second edition, 1992.

\bibitem{sandroni/etal:2003}
Alvaro Sandroni, Rann Smorodinsky, and Rakesh~V\DOT{} Vohra.
\newblock Calibration with many checking rules.
\newblock {\em Mathematics of Operations Research}, 28:141--153, 2003.

\bibitem{scholkopf/smola:2002}
Bernhard Sch\"olkopf and Alexander~J\DOT{} Smola.
\newblock {\em Learning with Kernels}.
\newblock MIT Press, Cambridge, MA, 2002.

\bibitem{shafer/vovk:2001}
Glenn Shafer and \Vladimir{} Vovk.
\newblock {\em Probability and Finance: It's Only a Game!}
\newblock Wiley, New York, 2001.

\bibitem{vapnik:1998}
Vladimir~N\DOT{} Vapnik.
\newblock {\em Statistical Learning Theory}.
\newblock Wiley, New York, 1998.

\bibitem{ville:1939}
Jean Ville.
\newblock {\em Etude critique de la notion de collectif}.
\newblock Gauthier-Villars, Paris, 1939.

\bibitem{vovk:2001competitive}
Vladimir Vovk.
\newblock Competitive on-line statistics.
\newblock {\em International Statistical Review}, 69:213--248, 2001.

\bibitem{GTP9}
\Vladimir{} Vovk.
\newblock Defensive forecasting for a benchmark data set, {T}he
  {G}ame-{T}he\-o\-ret\-ic {P}robability and {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#9, September 2004.

\bibitem{GTP11}
\Vladimir{} Vovk.
\newblock Non-asymptotic calibration and resolution, {T}he
  {G}ame-{T}he\-o\-ret\-ic {P}robability and {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#11, November 2004.

\bibitem{GTP7}
\Vladimir{} Vovk and Glenn Shafer.
\newblock Good randomized sequential probability forecasting is always
  possible, {T}he {G}ame-{T}heoretic {P}robability and {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#7, June 2003 (revised September 2004).

\bibitem{GTP8local}
\Vladimir{} Vovk, Akimichi Takemura, and Glenn Shafer.
\newblock Defensive forecasting, {T}he {G}ame-{T}heoretic {P}robability and
  {F}inance project,
  \texttt{http://prob\linebreak[0]a\linebreak[0]bil\linebreak[0]i\linebreak[0]%
ty\linebreak[0]and\linebreak[0]fi\linebreak[0]nance.com}, {W}orking {P}aper
  \#8, September 2004 (revised January 2005).
\newblock This is a fuller version of the current paper, with an appendix
  added.

}\end{thebibliography}