Defensive Forecasting

Vladimir Vovk∗
vovk@cs.rhul.ac.uk
http://vovk.net

Akimichi Takemura†takemura@stat.t.u-tokyo.ac.jp
http://www.e.u-tokyo.ac.jp/~takemura

Glenn Shafer‡∗
gshafer@andromeda.rutgers.edu
http://glennshafer.com

Abstract
We consider how to make probability forecasts of binary labels. Our main mathematical result is that for any continuous gamblingstrategy 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.

1

INTRODUCTION

Probability forecasting can be thought of as a gamebetween two players, Forecaster and Reality:
FOR n = 1, 2, . . . :Reality announces xn ∈ X.
Forecaster announces pn ∈ [0, 1].
Reality announces yn ∈ {0, 1}.
On each round, Forecaster predicts Reality’s move ynchosen from the label space, always taken to be {0, 1}
in this paper. His move, the probability forecast pn ,can be interpreted as the probability he attaches tothe event yn = 1. To help Forecaster, Reality presents
him with an object xn at the beginning of the round;
xn are chosen from an object space X.
Forecaster’s goal is to produce pn that agree with theobserved yn . Various results of probability theory,∗

Computer Learning Research Centre, Department ofComputer Science, Royal Holloway, University of London,
Egham, Surrey TW20 0EX, England.
†
Department of Mathematical Informatics, Graduate
School of Information Science and Technology, Universityof Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan.
‡
Rutgers Business School—Newark and New Brunswick, 180 University Avenue, Newark, NJ 07102, USA.

in particular limit theorems (such as the weak andstrong laws of large numbers, the law of the iterated
logarithm, and the central limit theorem) and largedeviation inequalities (such as Hoeffding’s inequality),
describe different aspects of agreement between pn andyn . For example, according to the strong law of large
numbers, we expect thatn1X(yi − pi ) = 0.
n→∞ n
i=1
lim

(1)

Such results will be called laws of probability and theexisting body of laws of probability will be called classical probability theory.
In §2, following [12], we formalize Forecaster’s goal byadding a third player, Skeptic, who is allowed to gamble at the odds given by Forecaster’s probabilities. We
state a result from [14] and [12] suggesting that Skeptic’s gambling strategies can be used as tests of agreement between pn and yn and that all tests of agreement between pn and yn can be expressed as Skeptic’s
gambling strategies. Therefore, the forecasting protocol with Skeptic provides an alternative way of statinglaws of probability.
As demonstrated in [12], many standard proof techniques developed in classical probability theory can betranslated into continuous strategies for Skeptic. In §3
we show that for any continuous strategy S for Skeptic there exists a strategy F for Forecaster such that S
does not detect any disagreement between the yn andthe pn produced by F. This result is a “meta-theorem”
that allows one to move from laws of probability toforecasting algorithms: as soon as a law of probability
is expressed as a continuous strategy for Skeptic, wehave a forecasting algorithm that guarantees that thislaw will hold; there are no assumptions about Reality,
who may play adversarially.
Our meta-theorem is of any interest only if one can findsufficiently interesting laws of probability (expressed asgambling strategies) that can serve as its input. In §4we apply it to the important properties of unbiasedness in the large and small of the forecasts pn ((1) is an
asymptotic version of the former). The resulting forecasting strategy is automatically unbiased, no matter
what data x1 , y1 , x2 , y2 , . . . is observed.
In §5 we simplify the algorithm obtained in §4 anddemonstrate its performance on some artificially generated data sets.

2

THE GAMBLING FRAMEWORKFOR TESTING PROBABILITYFORECASTS

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:
Binary Forecasting Game I
Players: Reality, Forecaster, Skeptic
Protocol:K0 := 1.
FOR n = 1, 2, . . . :Reality announces xn ∈ X.
Forecaster announces pn ∈ [0, 1].
Skeptic announces sn ∈ R.
Reality announces yn ∈ {0, 1}.
Kn := Kn−1 + sn (yn − pn ).
Restriction on Skeptic: Skeptic must choose the sn
so that his capital is always nonnegative (Kn ≥ 0 for
all n) no matter how the other players move.
This is a perfect-information protocol; the players
move in the order indicated, and each player sees theother player’s moves as they are made. It specifies
both an initial value for Skeptic’s capital (K0 = 1)
and a lower bound on its subsequent values (Kn ≥ 0).
Our interpretation, which will be called the testing interpretation, of Binary Forecasting Game I is that Kn
measures the degree to which Skeptic has shown Forecaster to do a bad job of predicting yi , i = 1, . . . , n.
2.1

VALIDITY AND UNIVERSALITY OF
THE TESTING INTERPRETATIONAs explained in [12], the testing interpretation is valid
and universal in an important sense. Let us assume,for simplicity, that objects are absent (formally, that
|X| = 1). In the case where Forecaster starts froma probability measure P on {0, 1}∞ and obtains his
forecasts pn ∈ [0, 1] as conditional probabilities under

P that yn = 1 given y1 , . . . , yn−1 , we have a standard
way of testing P and, therefore, pn : choose an eventA ⊆ {0, 1}∞ (the critical region) with a small P (A)and reject P if A happens. The testing interpretation
satisfies the following two properties:
Validity Suppose Skeptic’s strategy is measurable
and pn are obtained from P ; Kn then form anonnegative martingale w.r. to P . According to
Doob’s inequality [14, 3], for any positive constant C, supn Kn ≥ 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.)
Universality According to Ville’s theorem ([12],§8.5), for any positive constant ² and any
event A ⊆ {0, 1}∞ such that P (A) < ², Skeptic has a measurable strategy that ensures
lim inf n→∞ Kn > 1/² whenever A happens, provided pn are computed from P . (If Forecaster isdoing a bad job according to the standard pointof 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 limn→∞ Kn = ∞ on A.
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 [14].
2.2

CONTINUITY OF GAMBLINGSTRATEGIESIn [12] we constructed Skeptic’s strategies that madehim rich when the statement of any of several key lawsof probability theory was violated. The constructions
were explicit and lead to continuous gambling strategies. We conjecture that every natural result of classical probability theory leads to a continuous strategy
for Skeptic.

3

DEFEATING SKEPTIC

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 wewill drop the restriction on Skeptic. Therefore, we con-sider the following perfect-information game that pits
Forecaster against the two other players:

using the strategy sn = s²n := ²Kn−1 . Indeed, sinceKn =Binary Forecasting Game IInY(1 + ²(yi − pi )),i=1

Players: Reality, Forecaster, Skeptic

on the paths where Kn is bounded we have

Protocol:nY

K0 := 1.
FOR n = 1, 2, . . . :Reality announces xn ∈ X.
Skeptic announces continuous Sn : [0, 1] → R.
Forecaster announces pn ∈ [0, 1].
Reality announces yn ∈ {0, 1}.
Kn := Kn−1 + Sn (pn )(yn − pn ).

(1 + ²(yi − pi )) ≤ C,

i=1
n
X

ln(1 + ²(yi − pi )) ≤ ln C,

i=1

²

n
n
X
X
(yi − pi ) − ²2
(yi − pi )2 ≤ ln C,
i=1

Theorem 1 Forecaster has a strategy in Binary Forecasting Game II that ensures K0 ≥ K1 ≥ K2 ≥ · · · .

i=1

²

n
X

(yi − pi ) ≤ ln C + ²2 n,

i=1
n

ln C
1X
(yi − pi ) ≤
+²
n i=1
²n

Proof Forecaster can use the following strategy to ensure K0 ≥ K1 ≥ · · · :• if the function Sn (p) takes the value 0, choose pn
so that Sn (pn ) = 0;

(we have used the fact that ln(1 + t) ≥ t − t2 when|t| ≤ 0.5). If Skeptic wants to ensuren1X(yi − pi )
n→∞ n
i=1

sup Kn < ∞ =⇒ −² ≤ lim inf• if Sn is always positive, take pn := 1;

n

n

1X
(yi − pi ) ≤ ²,
≤ lim sup
n→∞ n
i=1

• if Sn is always negative, take pn := 0.

4

EXAMPLES OF GAMBLINGSTRATEGIES

he can use the strategy sn := (s²n + s−²n )/2, and if hewants to ensure

In this section we discuss strategies for Forecasterobtained by Theorem 1 from different strategies for
Skeptic; the former will be called 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 [12], p. 69,
for proving the strong law of large numbers.
If Sn (p) = Sn does not depend on p, the strategy fromthe proof of Theorem 1 makes Forecaster choose
if Sn < 0
0
pn := 1
if Sn > 0
0 or 1 if Sn = 0.
The basic procedure described in [12] (p. 69) is as follows. Let ² ∈ (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 canensure thatn

sup Kn < ∞ =⇒
n

n

n→∞

1X
(yi − pi ) ≤ ²
n i=1

(3)

he can use a convex mixture of (s²n + s−²n )/2 over a sequence of ² converging to zero. There are also standard
ways of strengthening (3) ton

1X(yi − pi ) = 0;
n→∞ n
i=1

lim inf Kn < ∞ =⇒

lim

n→∞

for details, see [12].
In the rest of this section we will draw on the excellent
survey [2]. We will see how Forecaster defeats increasingly sophisticated strategies for Skeptic.
4.1

UNBIASEDNESS IN THE LARGE

Following Murphy and Epstein [7], we say that Forecaster is unbiased in the large if (1) holds. Let us firstconsider the one-sided relaxed version of this propertyn

sup Kn < ∞ =⇒ lim sup

1X(yi − pi ) = 0,
n→∞ n
i=1
lim

n

(2)

lim supn→∞

1X(yi − pi ) ≤ ².
n i=1

(4)

The strategy for Skeptic described above, Sn (p) :=²Kn , leads to Forecaster always choosing pn := 1; (4)is then satisfied in a trivial way.
Forecaster’s strategy corresponding to the two-sided
version

n→∞

n
1X

n i=1

(yi − pi ) ≤ ² (5)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 thetwo accounts separately. If at the outset of round n the1capital on the first account is Kn−1
and the capital on
2
1
the second account is Kn−1 , Skeptic plays s1n := ²Kn−122with the first account and sn := −²Kn−1 with the second account; his total move is12
Sn (p) := ²Kn−1− ²Kn−1
Ãn−1
!
n−1
Y
Y
=²
(1 + ²(yi − pi )) −(1 + ²(pi − yi )) .
i=1

i=1

Therefore, Forecaster’s move is pn := 1 ifn−1Xln(1 + ²(yi − pi )) >

i=1

n−1
X

ln(1 + ²(pi − yi )),i=1

pn := 0 ifn−1Xln(1 + ²(yi − pi )) <

i=1

i=1

His goals are achieved with categorical forecasts, pn ∈{0, 1}.

n

1X− ² ≤ lim inf(yi − pi )
n→∞ n
i=1
≤ lim supas small as possible. In the two-sided case (5) with
² → 0, he manages to guarantee that
¯ n
¯
¯X
¯
¯
¯
(6)
¯ (yi − pi )¯ ≤ 1.
¯
¯

n−1
X

ln(1 + ²(pi − yi )),In the rest of this section we consider the more interesting case where Sn (p) depends on p.
4.2

UNBIASEDNESS IN THE SMALL

We now consider a subtler requirement that forecasts
should satisfy, which we introduce informally. We saythat the forecasts pn are unbiased in the small (or reliable, or valid, or well calibrated) if, for any p∗ ∈ [0, 1],P∗ yi
Pi=1,...,n:pi ≈p≈ p∗(7)
i=1,...,n:pi ≈p∗ 1
P
provided i=1,...,n:pi ≈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] → [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 := I[p− ,p+ ] , where [p− , p+ ] isa short interval containing p and I[p− ,p+ ] is its indicatorfunction, but we will want I to be continuous (it can,however, be arbitrarily close to I[p− ,p+ ] ).
The strategy for Skeptic ensuring (2) can be modified
as follows. Let ² ∈ (0, 0.5] be again a small number. Now we consider the strategy Sn (p) = Sn²,I (p) :=²I(p)Kn−1 . Since

i=1

and pn can be chosen arbitrarily in the case of equality. The limiting form of this strategy as ² → 0 is:
Forecaster’s move is pn := 1 if
n−1
X

Kn =

n
Y

(1 + ²I(pi )(yi − pi )),i=1

on the paths where Kn is bounded we havenY

(1 + ²I(pi )(yi − pi )) ≤ C,

i=1

(yi − pi ) > 0,

n
X

i=1

pn := 0 ifln(1 + ²I(pi )(yi − pi )) ≤ ln C,

i=1
n−1
X

(yi − pi ) < 0,i=1

and pn can be chosen arbitrarily in the case of equality.
We can see that unbiasedness in the large does notlead to interesting forecasts: Forecaster fulfils his task
too well. In the one-sided case (4), he always chooses
pn := 1 makingnX(yi − pi )
i=1

²

n
X

I(pi )(yi − pi ) − ²2

i=1

n
X

I 2 (pi )(yi − pi )2 ≤ ln C,

i=1

²

n
X
i=1

I(pi )(yi − pi ) − ²2nXI(pi ) ≤ ln C

i=1
2(the last step involves replacing I (pi ) with I(pi ); theloss of precision is not great if I is close to I[p− ,p+ ] ),
²

n
X
i=1

I(pi )(yi − pi ) ≤ ln C + ²2

n
X
i=1

I(pi ),

Pn

I(p )(y − pi )ln C
i=1
Pn i i
≤ Pn
+ ².
I(p
)
²
i
i=1
i=1 I(pi )The last inequality shows that the mean of yi for pi
close to p∗ is close to p∗ provided we have observed sufficiently many such pi ; its interpretation is especiallysimple when I is close to I[p− ,p+ ] .
In general, we may consider a mixture of Sn²,I (p) andSn−²,I (p) for different values of ² and for different I covering all p∗ ∈ [0, 1]. If we make sure that the mixture
is continuous (which is always the case for continuous
I and finitely many ² and I), Theorem 1 provides us
with forecasts that are unbiased in the small.
4.3

USING THE 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 xn can beperfectly calibrated, no matter how much useful information xn contain. (Cf. the discussion of resolution in[2]; we prefer not to use the term “resolution”, whichis too closely connected with the very special way ofprobability 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 thetest functions I to depend not only on p but also on
the current object xn ; Sn (p) then becomes a mixtureof
Sn²,I (p) := ²I(p, xn )n−1Y(1 + ²I(pi , xi )(yi − pi ))i=1

and Sn−²,I (p) (defined analogously) over ² and I.
4.4

RELATION TO A STANDARD
COUNTER-EXAMPLE

Suppose, for simplicity, that objects are absent (|X| =1). The standard construction from Dawid [1] showingthat no forecasting strategy produces forecasts pn thatare unbiased in the small for all sequences is as follows.
Define an infinite sequence y1 , y2 , . . . recursively by(
1 if pn < 0.5yn :=0 otherwise,
where pn is the forecast produced by the forecasting
strategy after seeing y1 , . . . , yn−1 . For the forecasts
pn < 0.5 we always have yn = 1 and for the forecasts
pn ≥ 0.5 we always have yn = 0; obviously, we do nothave unbiasedness in the small.
Let us see what Dawid’s construction gives when applied to the defensive forecasting strategy constructedfrom the mixture of Sn²,I (p) and Sn−²,I (p), as describedabove, over different ² and different I; we will assume
not only that the test functions I cover all [0, 1] but
also that each point p ∈ [0, 1] is covered by arbitrarily narrow (concentrated in a small neighborhood ofp) test functions. It is clear that we will inevitably
have pn → 0.5 if pn are produced by the defensive
forecasting strategy and yn 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 pn < 0.5 and pn ≥ 0.5, we do
not have any contradiction: neither the test functions
nor any observer who can only measure the pn with afinite precision can detect the lack of unbiasedness inthe 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 thatunbiasedness in the small is impossible to achieve if I
are allowed to be indicator functions of intervals (suchas [0, 0.5) and [0.5, 1]). To achieve unbiasedness in thesmall in this stronger sense, randomization appears
necessary (see, e.g., [18]). It is interesting that alreadya little bit of randomization suffices, as explained in[5].

5

SIMPLIFIED ALGORITHM

Let us assume first that objects are absent, |X| = 1.
It was observed empirically that the performance ofdefensive forecasting strategies with a fixed ² does notdepend on ² much (provided it is not too large; e.g., in
the above calculations we assumed ² ≤ 0.5). This suggests letting ² → 0 (in particular, we will assume that² ¿ n−2 ). As the test functions I we will take Gaussian bells Ij with standard deviation σ > 0 locateddensely and uniformly in the interval [0, 1]. Letting ≈stand P
for approximate equality and using the shorthand ± f (±) := f (+) + f (−), we obtain:n−1
XXY
Sn (p) =(±²)Ij (p)(1 ± ²Ij (pi )(yi − pi ))
±

j

i=1

Ãn−1
!
XX
X
=
(±²)Ij (p) exp
ln(1 ± ²Ij (pi )(yi − pi ))
±

j

i=1

Ã n−1
!
XX
X
≈
(±²)Ij (p) exp ±²
Ij (pi )(yi − pi )
±

≈

j

i=1

XX
±

j

Ã
(±²)Ij (p) 1 ± ²

n−1
X

!
Ij (pi )(yi − pi )

i=1

Ã n−1
!
XX
X
=
(±²)Ij (p) ±²
Ij (pi )(yi − pi )
±

j

i=1

∝

X

Ij (p)

j

=

n−1
X

1

Ij (pi )(yi − pi )n−1
XK29 forecasting strategy
Laplace forecasting strategy

0.9

i=1

0.8

K(p, pi )(yi − pi ),

(8)

0.7

i=1

where K(p, pi ) is the Mercer kernelX
K(p, pi ) :=Ij (p)Ij (pi ).

0.6
0.5
0.4

j
0.3

This Mercer kernel can be approximated by
µ
¶
µ
¶
Z 1
(t − p)2(t − pi )2
1
1
√
√
exp −
exp
−
dt
2σ 2
2σ 2
2πσ
2πσ
0
µ
¶
(t − p)2 + (t − pi )2
∝
exp −
dt
2σ 2
0
µ
¶
Z ∞
(t − p)2 + (t − pi )2
≈
exp −
dt.
2σ 2
−∞
Z 1

As a function of p, the last expression is proportional
to the density of the sum of two Gaussian randomvariables of variance σ 2 ; therefore, it is proportionaltoµ¶(p − pi )2
exp −
.
4σ 2
To get an idea of the properties of this forecasting
strategy, which we call the K29 strategy (or algorithm), we run it and the Laplace forecasting strategy(pn := (k + 1)/(n + 1), where k is the number of 1s
observed so far) on a randomly generated bit sequenceof length 1000 (with the probability of 1 equal to 0.5).
A zero point pn of Sn was found using the simple bisection procedure (see, e.g., [9], §§9.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 Sn (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 theremaining interval was output as pn . Notice that thevalues Sn (0) and Sn (1) did not have to be tested. Our
program was written in MATLAB, Version 7, and theinitial state of the random number generator was set
to 0.
Figure 1 shows that the probabilities output by theK29 (σ = 0.01) and Laplace forecasting strategies arealmost indistinguishable. 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 shownin Figure 2. The K29 strategy detects that the probability p of 1 changes after the 1000th round, and fairly
quickly moves down. When the probability changes

0.2
0.1
0

0

100

200

300

400

500

600

700

800

900

1000

Figure 1: The First 1000 Probabilities Output by theK29 (σ = 0.01) and Laplace Forecasting Strategies ona Randomly Generated Bit Sequenceagain after the 2000th round, K29 starts moving toward p = 1, but interestingly, hesitates around the linep = 0.5, as if expecting the process to reverse to theoriginal probability of 1.
The Mercer kernelµ¶(p − pi )2K(p, pi ) = exp −4σ 2used in these experiments is known in machine learningas the Gaussian kernel (in the usual parameterization
4σ 2 is replaced by 2σ 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 (8) we will arrive at the expression
Sn (p) =n−1
X

K((p, xn ), (pi , xi ))(yi − pi ),

(9)

i=1

where K is a Mercer kernel on the squared product([0, 1] × X)2 . There are standard ways of constructing
such Mercer kernels from Mercer kernels on [0, 1]2 andX2 (see, e.g., the description of tensor products anddirect sums in [13, 11]). For Sn to be continuous, wehave to require that K be forecast-continuous in thefollowing sense: for all x ∈ X and all (p0 , x0 ) ∈ [0, 1] ×
X, K((p, x), (p0 , x0 )) is continuous as a function of p.
The overall procedure can be summarized as follows.
K29 Algorithm
Parameter: forecast-continuous Mercer kernel K on([0, 1] × X)2
FOR n = 1, 2, . . . :Read xn ∈ X.

law of large numbers used in this paper was extracted
from Ville’s [14] martingale proof of the law of theiterated logarithm (upper half).

1
K29 forecasting strategy
Laplace forecasting strategy

0.9
0.8

The theory of probability forecasting was a topic of intensive research in meteorology in the 1960s and 1970s;
this research is summarized in [2]. 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; theliterature 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.

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0

500

1000

1500

2000

2500

3000

Figure 2: The Probabilities Output by the K29 (σ =0.01) and Laplace Forecasting Strategies on a Randomly Generated Sequence of 1000 Bits Followed by1000 0s and 1000 1s
Define Sn (p) as per (9).
Output any root p of Sn (p) = 0 as pn ;if there are no roots, pn := (1 + sign(Sn ))/2.
Read yn ∈ {0, 1}.
Computer experiments reported in [16] show that theK29 algorithm performs well on a standard benchmark
data set. For a theoretical discussion of the K29 algorithm, see [19] (Appendix) and [17].

6

RELATED WORK AND
DIRECTIONS OF FURTHERRESEARCH

This paper’s methods connect two areas that havebeen developing independently so far: probability forecasting and classical probability theory. It appears
that, when properly developed, these methods canbenefit both areas:• the powerful machinery of classical probability
theory can be used for probability forecasting;• practical problems of probability forecasting may
suggest new laws of probability.
Classical probability theory started from Bernoulli’s
weak law of large numbers (1713) and is the subjectof countless monographs and textbooks. The originalstatements of most of its results were for independent
random variables, but they were later extended to themartingale framework; the latter was reduced to its
game-theoretic core in [12]. The proof of the strong

Defensive forecasting is indirectly related, in a sensedual, to prediction with expert advice (reviewed in[15], §4) and its special case, Bayesian prediction. In
prediction with expert advice one starts with a given
loss function and tries to make predictions that leadto 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 lawof probability is satisfied. So the choice of the lawof probability when designing the forecasting strategy
plays a role analogous to the choice of the loss functionin prediction with expert advice.
In prediction with expert advice one combines a pool ofpotentially promising forecasting strategies to obtaina 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 ±² in §4) to obtain one strategy achieving an interesting goal (such as unbiasedness in thesmall); a strategy for Forecaster is then obtained using Theorem 1. The possibility of mixing strategies
for Skeptic is as fundamental in defensive forecasting
as the possibility of mixing strategies for Forecaster inprediction with expert advice.
This paper continues the work started by Foster andVohra [4] and later developed in, e.g., [6, 10, 18] (thelast paper replaces the von Mises–style framework of
the previous papers with a martingale framework, asin this paper). The approach of this paper is similar tothat of the recent paper [5], which also considers deterministic forecasting strategies and continuous test
functions for unbiasedness in the small.
The main difference of this paper’s approach from thebulk of work in learning theory is that we do not makeany assumptions about Reality’s strategy.
The following directions of further research appear to
us most important:• extending Theorem 1 to other forecasting protocols (such as multi-label classification) and designing efficient algorithms for finding the corresponding pn ;• exploring forecasting strategies corresponding to:(a) Hoeffding’s inequality, (b) the central limit
theorem, (c) the law of the iterated logarithm (allwe did in this paper was to slightly extend thestrong law of large numbers and then use it for
probability forecasting).
Acknowledgments[8] David Oakes. Self-calibrating priors do not exist(with discussion). Journal of the American Statistical Association, 80:339–342, 1985.
[9] William H. Press, Brian P. Flannery, Saul A.
Teukolsky, and William T. Vetterling. Numerical Recipes in C. Cambridge University Press,
Cambridge, second edition, 1992.
[10] Alvaro Sandroni, Rann Smorodinsky, andRakesh V. Vohra. Calibration with many checking rules. Mathematics of Operations Research,
28:141–153, 2003.

We are grateful to the participants of the PASCAL workshop “Notions of complexity: informationtheoretic, 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), Royal Society, and, especially, the Superrobust Computation
Project (Graduate School of Information Science andTechnology, University of Tokyo).

[11] Bernhard Schölkopf and Alexander J. Smola.
Learning with Kernels. MIT Press, Cambridge,
MA, 2002.

References[15] Vladimir Vovk. Competitive on-line statistics. International Statistical Review, 69:213–248, 2001.

[1] A. Philip Dawid. Self-calibrating priors do notexist: Comment. Journal of the American Statistical Association, 80:340–341, 1985. This is acontribution to the discussion in [8].
[2] A. Philip Dawid. Probability forecasting. In
Samuel Kotz, Norman L. Johnson, and Campbell B. Read, editors, Encyclopedia of Statistical
Sciences, volume 7, pages 210–218. Wiley, New
York, 1986.
[3] Joseph L. Doob. Stochastic Processes. Wiley, New
York, 1953.
[4] Dean P. Foster and Rakesh V. Vohra. Asymptotic
calibration. Biometrika, 85:379–390, 1998.
[5] Sham M. Kakade and Dean P. Foster. Deterministic calibration and Nash equilibrium. In John
Shawe-Taylor and Yoram Singer, editors, Proceedings of the Seventeenth Annual Conference on
Learning Theory, volume 3120 of Lecture Notes in
Computer Science, pages 33–48, Heidelberg, 2004.
Springer.
[6] Ehud Lehrer. Any inspection is manipulable. Econometrica, 69:1333–1347, 2001.
[7] Allan H. Murphy and Edward S. Epstein. Verification of probabilistic predictions: a brief review.
Journal of Applied Meteorology, 6:748–755, 1967.

[12] Glenn Shafer and Vladimir Vovk. Probability and
Finance: It’s Only a Game! Wiley, New York,
2001.
[13] Vladimir N. Vapnik. Statistical Learning Theory.
Wiley, New York, 1998.
[14] Jean Ville. Etude critique de la notion de collectif.
Gauthier-Villars, Paris, 1939.

[16] Vladimir Vovk. Defensive forecasting for a benchmark data set, The Game-Theoretic Probability
and Finance project, http://probabilityandfi
nance.com, Working Paper #9, September 2004.
[17] Vladimir Vovk. Non-asymptotic calibration
and resolution, The Game-Theoretic Probability
and Finance project, http://probabilityandfi
nance.com, Working Paper #11, November 2004.
[18] Vladimir Vovk and Glenn Shafer. Good randomized sequential probability forecasting is always possible, The Game-Theoretic Probability
and Finance project, http://probabilityandfi
nance.com, Working Paper #7, June 2003 (revised September 2004).
[19] Vladimir
Vovk, Akimichi Takemura, andGlenn Shafer.
Defensive forecasting, The
Game-Theoretic Probability and Finance project,
http://probabilityandfinance.com, Working
Paper #8, September 2004. This is a fuller versionof the current paper, with an appendix added.