Game-theoretic versions of Kolmogorov’s strong law of large

numbers

V. G. Vovk

Technical Report CLRC-TR-99-05 June 1995

����� ����� �����

Department of Computer Science Egham, Surrey TW20 0EX, England

Abstract

We prove two variants of Kolmogorov’s strong law of large numbers in a completely worst-case framework, eschewing any probabilistic assumptions. The first variant is an assertion about a game involving the Bookmaker predicting the values of unprobabilized random variables; in an intuitive sense it is much stronger than the usual strong law of large numbers for martingales. The second variant is an assertion about a security market.

The final version of this paper was prepared for the seminar on the foundations of probability (Aalborg University, June 1995) organized by Steffen Lauritzen.

Predictive strong law of large numbers 1

1 Predictive strong law of large numbers

In this section we consider the following perfect-information game between 3 players, the Bookmaker, the Statistician, and the Nature. The game proceeds in trials. At each trial i, i = 1, 2, …, the Bookmaker tries to predict the real number X_{i} the Nature is to produce at the end of the trial. His prediction consists of two numbers, E_{i} and D_{i} ≥ 0; roughly, E_{i} is the Bookmaker’s expectation of X_{i}, and D_{i} is his expectation of the accuracy L_{i} := (X_{i} − E_{i})^{2} (measured by the Brier scoring rule, see Dawid [1]) of the prediction E_{i}.

Along the lines of Chapter 3 of de Finetti [2] we give an operative interpretation to the numbers E_{i} and D_{i} as follows. Before X_{i} is disclosed, the Bookmaker lets the Statistician buy any amount, positive or negative, of X_{i}-tickets for $E_{i} each and L_{i}-tickets for $D_{i} each. An X_{i}-ticket (resp. L_{i}-ticket) is a contract which obliges the Bookmaker to pay the Statistician $X_{i} (resp. $(X_{i} − E_{i})^{2}) after X_{i} is disclosed. We will use the notation e_{i} and d_{i} for the number of X_{i}-tickets and L_{i}-tickets, respectively, bought by the Statistician at trial i. We describe the unfolding of the game, including the evolution of the Statistician’s capital K_{i}, as follows:

FOR i = 1, 2, …:

Bookmaker selects E_{i} ∈ IR and D_{i} ≥ 0

Statistician selects e_{i}, d_{i} ∈ IR

K_{i} := K_{i−1} − e_{i}E_{i} − d_{i}D_{i} (1) Nature selects X_{i} ∈ IR K_{i} := K_{i} + e_{i}X_{i} + d_{i}(X_{i} − E_{i})^{2}. (2)

Initially, the Statistician’s capital is K_{0} := 1. We call the pair (e_{i}, d_{i}) the portfolio held by the Statistician at trial i. Equation (1) shows how the Statistician’s capital decreases when he buys the new portfolio and (2) describes the proceeds from holding the portfolio. We can summarize (1) and (2) as follows:

K_{i} := K_{i−1} + e_{i}(X_{i} − E_{i}) + d_{i} ((X_{i} − E_{i})^{2} − D_{i}) .  (3)

An important difference between our framework and de Finetti’s is that de Finetti assumes that the Bookmaker can directly price any ticket of interest, and we try to minimize the quantity of tickets priced by the Bookmaker. In particular, for discussing Kolmogorov’s strong law of large numbers it suffices to assume that the Bookmaker can price only the X_{i}-tickets and L_{i}-tickets.

To complete the description of our game, which will be denoted by G, it remains to specify the rule for determining who won the game given its path

E_{1}D_{1}e_{1}d_{1}X_{1}E_{2}D_{2}e_{2}d_{2}X_{2} ….  (4)

We say that this path satisfies SLLN if

lim_{n→∞} \frac{1}{n} ∑_{i=1}^{n}(X_{i} − E_{i}) = 0.  (5)

Intuitively,

⋄ the aim of the Statistician is to demonstrate that the realized path (4) satisfies SLLN; however, even if the path does not satisfy SLLN, the Statistician will be consoled if his capital increases infinitely:

K_{i} → ∞ (i → ∞);  (6)

the Statistician is prohibited to borrow: he is declared to lose the game as soon as K_{i} becomes negative;

⋄ the aim of the Nature is to prevent the Statistician from attaining his goal;

⋄ the Bookmaker does not have his own goals and can cooperate with either the Statistician or the Nature.

Formally, G is won by the Statistician if (5) or (6) holds and his capital K_{i} ≥ 0, ∀i; otherwise, G is won by the Nature. (Thus the Bookmaker never wins the game.)

Now we can state the “predictive version” of Kolmogorov’s strong law of large numbers.

Theorem 1 Let G^{<∞} (resp. G^{=∞}) be the game G with the additional requirement that the Bookmaker should ensure

∑_{i=1}^{∞} \frac{D_{i}}{i^{2}} < ∞  (7)

(resp.

∑_{i=1}^{∞} \frac{D_{i}}{i^{2}} = ∞).  (8)

The Statistician has a winning strategy in G^{<∞}, and the Nature has a winning strategy in G^{=∞}.

Let \overline{G} be the game whose only difference from G is that the Statistician is required to select d_{i} ≥ 0. Intuitively, this means that D_{i} is the Bookmaker’s upper estimate on the variance of X_{i}. We can state for \overline{G} an analogue of Theorem 1.

Theorem 2 Let \overline{G}^{<∞} (resp. \overline{G}^{=∞}) be the game \overline{G} with the additional requirement that the Bookmaker should ensure (7) (resp. (8)). The Statistician (resp. the Nature) has a winning strategy in \overline{G}^{<∞} (resp. \overline{G}^{=∞}).

Financial-theoreticstrong law of large numbers 3

2 Financial-theoretic strong law of large numbers

In this section we consider a security market where K securities are traded; its working is described by the following game G_{K}:

FOR i = 1, 2, …:

Market selects μ_{i} ∈ ]0, 1]^{K} such that ∑_{k=1}^{K} μ_{i}(k) = 1 Gambler selects σ_{i} ∈ IR^{K} Statistician selects p_{i} ∈ IR^{K} Nature selects π_{i} ∈ [−1, ∞[^{K} such that μ_{i} · π_{i} = 0 K_{i} := K_{i−1} + p_{i} · π_{i}.

The initial capital K_{0} is 1; “·” stands for the dot product. Each μ_{i} = (μ_{i}(1), …, μ_{i}(K)) is interpreted as the “market portfolio” at trial i: say, μ_{i}(k) can be the total value (according to the current prices) of all the shares outstanding of security k; we normalize μ_{i} so that ∑_{k} μ_{i}(k) = 1. Each π_{i} = (π_{i}(1), …, π_{i}(K)) is interpreted as the return on the securities at trial i: say, π_{i}(k) = −1 means that security k became worthless; π_{i}(k) = 0 means that k’s price did not change; π_{i}(k) = 0.07 means that k’s price was 7% up. Each σ_{i} = (σ_{i}(1), …, σ_{i}(K)) is the portfolio held by the Gambler at trial i: σ_{i}(k) is the capital he invested into security k (it is possible that σ_{i}(k) < 0; in other words, unlimited short selling is allowed). Analogously, each p_{i} is the Statistician’s portfolio at trial i.

The requirement μ_{i} · π_{i} = 0 means that the market portfolio does not change its value; in other words, we are using the value of the market portfolio as the numeraire. (So saying that p_{i} is the Statistician’s portfolio at trial i, we mean that the Statistician invests p_{i}(k) into security k, k = 1, …, K, and invests the remaining K_{i−1} − ∑_{k} p_{i}(k) into the market portfolio^{1}.)

The Statistician’s goal is to enforce his favorite strong law of large numbers, which says here that on the average the Gambler will neither profit nor lose:

lim_{n→∞} \frac{1}{n} ∑_{i=1}^{n} σ_{i} · π_{i} = 0.  (9)

If he is unable to do it, the only thing that can comfort him is his becoming infinitely rich; as before, he does not tolerate any chance of getting into a position of debt. Formally, the Statistician wins the game if K_{i} ≥ 0, ∀i, and also (9) or (6) holds.

Since everything happens “modulo the market portfolio”, it is natural to consider the “reduced portfolio”

\overline{σ}_{i}(k) := σ_{i}(k) − c_{i}μ_{i}(k),

1To allow the investors to keep part of their capital in cash, we can formally add money to the list of securities traded in the market.

Proofs 4

where c_{i} is the constant that makes ∑_{k} \overline{σ}_{i}(k) = 0 (namely, c_{i} = ∑_{k} σ_{i}(k)). We will say that \overline{σ}_{i} is an arbitrage portfolio.

Theorem 3 Let G_{K}^{<∞} be the game G_{K} where the Gambler is required to ensure that

∑_{i=1}^{∞} i^{−2} ∑_{k=1}^{K} \frac{\overline{σ}_{i}^{2}(k)}{μ_{i}(k)} < ∞.

The Statistician has a winning strategy in G_{K}^{<∞}.

3 Proofs

3.1 Martingale-theoretic strong law of large numbers

First we introduce a generalization of the games G, \overline{G}, and G_{K} considered in Sections 1 and 2. Fix some sets M_{B}, M_{S}, and M_{N} from which the Bookmaker, the Statistician, and the Nature, respectively, will select their moves. Let

λ: M_{B} × M_{S} × M_{N} → IR

be the reward function for the Statistician. The game G_{λ}(K_{0}), where K_{0} ∈ IR is the Statistician’s initial capital, is defined as follows:

FOR i = 1, 2, …:
Bookmaker selects b_{i} ∈ M_{B}
Statistician selects p_{i} ∈ M_{S}
Nature selects x_{i} ∈ M_{N}
K_{i} := K_{i−1} + λ(b_{i}, p_{i}, x_{i}).

A situation in our game is a finite sequence b_{1}x_{1} … b_{n}x_{n} with all b_{i} ∈ M_{B} and all x_{i} ∈ M_{N}; that is, it is a record of the Statistician’s opponents’ moves during the first n trials. To n = 0 corresponds the empty sequence □. A path is an infinite sequence b_{1}x_{1}b_{2}x_{2} …; the sample space of the game is the set of all paths. If ω is a path b_{1}x_{1}b_{2}x_{2} … and n is a nonnegative integer, ω^{n} stands for the situation b_{1}x_{1} … b_{n}x_{n}. A variable^{2} is a real-valued function defined on the sample space. A process is a real-valued (if not explicitly stated otherwise) function defined on the set of all situations. As usual in probability theory, we identify a process S with the sequence S_{0}, S_{1}, … of variables defined by

S_{n}(ω) := S(ω^{n}).

(Thus S_{0} is constant.)

A process A is predictable if, for all n, A_{n}(b_{1}x_{1}b_{2}x_{2} …) does not depend on x_{n}. A martingale is a process S for which there exists the Statistician’s strategy p = p_{n}(ω) (note that the Statistician’s strategy is a predictable M_{S}-valued process) ensuring

2Following Shafer [5], we shorten “random variable” and “stochastic process” to “variable”

and “process”, respectively. (There is nothing random or stochastic in our framework.)

K_{n} = S(b_{1}x_{1} … b_{n}x_{n}), ∀n,

in the game G_{λ}(S_{0}). We will say that p gives rise to S in G_{λ}(S_{0}). A process A is increasing if A_{0} = 0 and A_{n} ≤ A_{n+1}, ∀n, on all paths. A submartingale is a process of the form T = S + A, where S is a martingale and A is an increasing predictable process; any such A will be called a compensator for T. A supermartingale is a process T for which there exists a martingale S such that everywhere

T_{n+1} − T_{n} ≤ S_{n+1} − S_{n}, ∀n;  (10)

in other words, a supermartingale is a process T of the form T = S − A with S a martingale and A an increasing (but not necessarily predictable) process. (Therefore, the difference between the notions of supermartingale and martingale is that in the case of supermartingale the Statistician is allowed to throw away part of his money at every trial.) A semimartingale is a process of the form T = S+A, where S is a supermartingale and A is an increasing predictable process; any such A will be called a supercompensator for T. Any strategy p which gives rise to a martingale S satisfying (10) will be said to bound the supermartingale T.

Now we impose some restrictions on the reward function λ (it is instructive to compare them with the restrictions in [7]):

1. M_{S} is a closed convex cone in a Euclidean space with norm ∥ · ∥.

2. For every fixed b ∈ M_{B} and x ∈ M_{N}, the function p ↦ λ(b, p, x) is linear on M_{S}.

In the case of the games G and \overline{G}, M_{S} is a cone in IR^{2}, and in the case of the games G_{K} (where the Market and the Gambler are aggregated into the Bookmaker), M_{S} is a cone in (in fact, the whole of) IR^{K}.

In this section we will consider supermartingales and semimartingales, but to prove the assertions in Section 1 it would be sufficient to consider only the supermartingales which are martingales and semimartingales which are submartingales.

Our assumptions immediately imply

Lemma 1 The space of supermartingales is a convex cone: if S^{1}, …, S^{m} are supermartingales and t_{1} ≥ 0, …, t_{m} ≥ 0, then t_{1}S^{1} + … + t_{m}S^{m} is a supermartingale as well.

Proof If S^{j} is bounded by the Statistician’s strategy p^{j} in G_{λ}(S_{0}^{j}), j = 1, …, m, then t_{1}S^{1} + … + t_{m}S^{m} is bounded by the strategy t_{1}p^{1} + … + t_{m}p^{m} in G_{λ}(S_{0}^{1} + … + S_{0}^{m}). ⊓ ⊔ With each supermartingale S we associate the predictable process ∥S∥ defined by

\begin{matrix}∥S∥_{n}(ω) := inf\{∥p∥ : \\ S(ω^{n−1} ∗ b ∗ x) − S(ω^{n−1}) ≤ λ(b, p, x), ∀ b ∈ M_{B}, x ∈ M_{N}\} \end{matrix}  (11)

(s ∗ a stands for finite sequence s extended by adding one more element a on the right). We say that the Statistician’s strategy p in G_{λ}(S_{0}) is a minimal bounding strategy for S if p bounds S and ∥S∥_{n} = ∥p_{n}∥ everywhere for all n.

Lemma 2 For each supermartingale S there exists a minimal bounding strategy.

Proof We are only required to prove that the inf in (11) is attained. Fix n and ω and denote by P (b, x) the set of all p ∈ M_{S} which satisfy the inequality in (11). Each P (b, x) is closed; therefore, their intersection P is also closed. We are required to prove that inf_{p∈P} ∥p∥ is attained; this follows from the compactness of every closed ball in a Euclidean space. ⊓ ⊔

Lemma 3 Let S^{1}, S^{2},… be a sequence of nonnegative supermartingales and t_{1}, t_{2},… be a sequence of nonnegative numbers such that

∑_{j=1}^{∞} t_{j}S_{0}^{j} < ∞

and, for any situation s,

∑_{j=1}^{∞} t_{j}∥S^{j}∥(s) < ∞.

Then the sum

S := ∑_{j=1}^{∞} t_{j}S^{j}

is a nonnegative supermartingale and

∥S∥ ≤ ∑_{j=1}^{∞} t_{j}∥S^{j}∥.

Proof It suffices to fix for each S^{j} a minimal bounding strategy p^{j} and put

p := ∑_{j=1}^{∞} t_{j}p^{j};

it is easy to prove by simultaneous induction in n that S_{n} < ∞, ∀n, and p bounds S. ⊓ ⊔

Now our argument will follow [8], which, in its turn, follows Liptser’s proof of Kolmogorov’s strong law of large numbers. The following assertion is an analog of Doob’s martingale convergence theorem for nonnegative supermartingales; by ∃ lim_{n→∞} S_{n} we mean that the limit exists and is finite.

Lemma 4 For any nonnegative supermartingale S there exists a nonnegative martingale S^{∗} such that

S_{0}^{∗} = S_{0}, ∥S^{∗}∥ ≤ ∥S∥,

and always

∃ lim_{n→∞} S_{n} or lim_{n→∞} S_{n}^{∗} = ∞.  (12)

Proof (Doob) Fix the Statistician’s strategy p which bounds the supermartingale S in the game G_{λ}(S_{0}). Let a, b be positive rational numbers such that a < b. Define τ_{0} := 0 and, for m = 1, 2, …,

σ_{m} := min{i > τ_{m−1} : S_{i} > b}, τ_{m} = min{i > σ_{m} : S_{i} < a}.

Let p^{(a,b)} be the Statistician’s strategy

p_{i}^{(a,b)} := \{ \begin{matrix}p_{i}, if ∃m: τ_{m−1} < i ≤ σ_{m}, \\ 0, otherwise, \end{matrix}

in the game G_{λ}(S_{0}), and S^{a,b} be the martingale p^{a,b} gives rise to. It is easy to see that

S_{0}^{(a,b)} = S_{0}, ∥S^{(a,b)}∥ ≤ ∥S∥,

and always

\begin{matrix}\underline{lim}_{n→∞} S_{n} < a \\ \overline{lim}_{n→∞} S_{n} > b \end{matrix} \} ⟹ lim_{n→∞} S_{n}^{(a,b)} = ∞.  (13)

Arrange all such pairs (a, b) in a sequence (a_{1}, b_{1}), (a_{2}, b_{2}), … and put

S^{∗} := \frac{1}{2}S + ∑_{m=1}^{∞} 2^{−m−1}S^{(a_{m},b_{m})}.

By Lemma 3, S^{∗} is a supermartingale with

∥S^{∗}∥ ≤ \frac{1}{2}∥S∥ + ∑_{m=1}^{∞} 2^{−m−1}∥S^{(a_{m},b_{m})}∥ ≤ ∥S∥.

To prove (12), it suffices to rewrite it as

(¬∃ lim_{n→∞} S_{n}) ⟹ lim_{n→∞} S_{n}^{∗} = ∞,

notice that the antecedent is equivalent to

∃(a, b): \underline{lim}_{n→∞} S_{n} < a & \overline{lim}_{n→∞} S_{n} > b,

and make use of (13). (Now S^{∗} is guaranteed to be only a supermartingale, but it is easy to make it into a martingale.) ⊓ ⊔

Let us introduce some new terminology. We say that a property E of a path holds almost surely (a.s.) if there exists a nonnegative martingale S such that S_{n} → ∞ on the paths outside E; without loss of generality we can assume S_{0} = 1. (We will say that S witnesses that E holds a.s.) In other words, E holds a.s. if the Statistician can, without risking to go bankrupt, either ensure E or become infinitely rich. We can see that Lemma 4 implies that each nonnegative supermartingale is convergent a.s. (this is a more familiar formulation of Doob’s theorem).

Lemma 5 If T is a nonnegative semimartingale and A is its supercompensator, then, almost surely,

A_{∞} < ∞ ⇒ ∃ lim_{n→∞} T_{n}.  (14)

Proof Let S := T − A; S is a supermartingale. For C = 1, 2, …, define the nonnegative supermartingales S^{C} by the requirements S_{0}^{C} = C and

ΔS_{i}^{C} = \{ \begin{matrix}ΔS_{i}, if A_{i} ≤ C, \\ 0, otherwise, \end{matrix} i = 1, 2, …,

(Δa_{i} stands for a_{i} − a_{i−1}). Since ∥S^{C}∥ ≤ ∥S∥, Lemma 3 implies that

R := ∑_{C=1}^{∞} 2^{−C}(S^{C})^{∗},

where ^{∗} is the transformation from Lemma 4, witnesses that (14) holds a.s. ⊓ ⊔

We say that a process A is a quadratic supervariation of a martingale S if S^{2} is a semimartingale and A is a supercompensator of S^{2}.

Lemma 6 If S is a martingale and A is its quadratic supervariation, then, almost surely,

A_{∞} < ∞ ⇒ ∃ lim_{n→∞} S_{n}.

Proof If A is a supercompensator of S^{2}, then A is a supercompensator of (S + 1)^{2} as well. By Lemma 5, S_{n}^{2} and (S_{n} + 1)^{2} converge when A_{∞} < ∞, almost surely. It remains to note that

S_{n} = \frac{1}{2}((S_{n} + 1)^{2} − S_{n}^{2} − 1).

⊓ ⊔

Now we can formulate the main result of this section.

Theorem 4 If A is a quadratic supervariation of a martingale S, then, almost surely,

∑_{i=1}^{∞} \frac{ΔA_{i}}{i^{2}} < ∞ ⟹ lim_{n→∞} \frac{S_{n}}{n} = 0.

Proof Noticing that

A′_{n} := ∑_{i=1}^{n} \frac{ΔA_{i}}{i^{2}}

is a quadratic supervariation of the martingale

S′_{n} := ∑_{i=1}^{n} \frac{ΔS_{i}}{i}

and applying Lemma 6, we deduce that, almost surely,

∑_{i=1}^{∞} \frac{ΔA_{i}}{i^{2}} < ∞ ⇒ ∃ ∑_{i=1}^{∞} \frac{ΔS_{i}}{i} .

It remains to apply Kronecker’s lemma (see, e.g., [6], Lemma 3.2.3), which implies that, for any sequence t_{1}, t_{2}, … of real numbers,

∃ ∑_{i=1}^{∞} \frac{t_{i}}{i} ⇒ lim_{n→∞} \frac{1}{n} ∑_{i=1}^{n} t_{i} = 0.

⊓ ⊔

3.2 Statistician’s strategy

It is easy to deduce from Theorem 4 the existence of the Statistician’s strategies required in Theorems 1, 2, and 3. The case of Theorem 1 reduces to the case of Theorem 2, so we are only required to prove that the Statistician has winning strategies in \overline{G}^{<∞} and G_{K}^{<∞}. The case of \overline{G}^{<∞} is easy: it suffices to note that

S_{n} := ∑_{i=1}^{n}(X_{i} − E_{i})

is a martingale and

A_{n} := ∑_{i=1}^{n} D_{i}

is its quadratic supervariation.

It remains to consider the game G_{K}^{<∞}. In this case, it suffices to apply Theorem 4 to the martingale

S_{n} := ∑_{i=1}^{n} σ_{i} · π_{i};  (15)

the next lemma ensures that

A_{n} := ∑_{i=1}^{n} ∑_{k=1}^{K} \frac{\overline{σ}_{i}^{2}(k)}{μ_{i}(k)}  (16)

is a quadratic supervariation of S_{n}.

Lemma 7 (16) is a quadratic supervariation of (15).

Proof We are required to prove that there exists the Statistician’s strategy p such that, for all i ≥ 1,

(S_{i}^{2} − A_{i}) − (S_{i−1}^{2} − A_{i−1}) ≤ p_{i} · π_{i},

i.e.,

(σ_{i} · π_{i})^{2} + 2S_{i−1}(σ_{i} · π_{i}) − ∑_{k} \frac{\overline{σ}_{i}^{2}(k)}{μ_{i}(k)} ≤ p_{i} · π_{i}.

It is easy to see that the existence of such p is equivalent to the existence of p such that

(σ_{i} · π_{i})^{2} − ∑_{k} \frac{\overline{σ}_{i}^{2}(k)}{μ_{i}(k)} ≤ p_{i} · π_{i},

i.e., dropping the indices i,

(σ · π)^{2} − p · π ≤ ∑_{k} \frac{\overline{σ}^{2}(k)}{μ(k)}.  (17)

Let us see how the Statistician can choose such p ∈ IR^{K}. Recall that π ∈ IR^{K} must satisfy

π(k) ≥ −1, ∀k, μ · π = 0.  (18)

In the left-hand side of (17) we have a convex function of π, so it suffices for the Statistician to ensure that (17) holds for π the vertices of the polygon (18). These vertices are π^{j}, j = 1, …, K, with

π^{j}(k) = \{ \begin{matrix}\frac{1}{μ(j)} − 1, if k = j, \\ −1, otherwise. \end{matrix}

Substituting this into (17), we obtain (assuming, without loss of generality, that σ is an arbitrage portfolio)

(\frac{σ(j)}{μ(j)})^{2} − \frac{p(j)}{μ(j)} + ∑_{k} p(k) ≤ ∑_{k} \frac{σ^{2}(k)}{μ(k)}.

It remains to put

p(j) := \frac{σ^{2}(j)}{μ(j)} − μ(j) ∑_{k} \frac{σ^{2}(k)}{μ(k)}

(note that ∑_{k} p(k) = 0). ⊓ ⊔

3.3 Nature’s strategy

REFERENCES 11

The aim of this section is to prove the existence of the Nature’s winning strategies under the conditions of Theorems 1 and 2. It suffices only to prove that the Nature has a winning strategy in G^{=∞}. By Martin’s theorem about the determinacy of quasi-Borel games [4], either the Statistician helped by the Bookmaker or the Nature has a winning strategy in G^{=∞}. Therefore, it suffices to show that the Statistician helped by the Bookmaker cannot have a winning strategy. Assume that such a strategy exists; we will denote it by S. We will attain our goal if we prove that the Nature has a randomized strategy beating S with probability 1. We will construct such a strategy following Kolmogorov [3].

The Nature’s strategy is as follows: if D_{i} ≤ i^{2},

X_{i} := ( \begin{matrix}E_{i} + i \\ E_{i} − i \\ E_{i} \end{matrix} ) with probability ( \begin{matrix}D_{i}/(2i^{2}) \\ D_{i}/(2i^{2}) \\ 1 − D_{i}/i^{2} \end{matrix} ) ,  (19)

respectively; if D_{i} > i^{2},

X_{i} := ( \begin{matrix}E_{i} + \sqrt{D_{i}} \\ E_{i} − \sqrt{D_{i}} \end{matrix} ) with probability ( \begin{matrix}1/2 \\ 1/2 \end{matrix} ) .  (20)

Let this strategy play against S. Since always K_{i} ≥ 0, (3) implies that K_{i} is a nonnegative martingale (in the usual probabilistic sense). Therefore, K_{i} is bounded above almost surely (this follows from, e.g., Doob’s inequality or Doob’s convergence theorem). Besides, the Borel—Cantelli—Levy lemma (see, e.g., Shiryaev [6], Corollary VII.5.2) implies that, almost surely, |X_{i} − E_{i}| ≥ i for infinitely many i; therefore, almost surely, SLLN is not satisfied.

To make this argument rigorous, it remains to actually construct a probability space (Ω, P) with random variables X_{i}, i = 1, 2, …, satisfying (19) and (20). It is easy: we put Ω := {−1, 0, 1}^{∞},

X_{i}(ω) := \{ \begin{matrix}E_{i}, if ω_{i} = 0, \\ E_{i} ± i, if ω_{i} = ±1 and D_{i} ≤ i^{2}, \\ E_{i} ± \sqrt{D_{i}}, if ω_{i} = ±1 and D_{i} > i^{2}, \end{matrix}

where ω = ω_{1}ω_{2} … ∈ Ω, and

P(ω_{i} = 1 | F_{i−1}) := P(ω_{i} = −1 | F_{i−1}) := \{ \begin{matrix}D_{i}/(2i^{2}), if D_{i} ≤ i^{2}, \\ 1/2, otherwise, \end{matrix}

where F_{k} is the σ-algebra generated by ω_{1}, …, ω_{k}. (Recall that the Statistician/Bookmaker’s strategy is fixed, and so E_{i} and D_{i} are F_{i−1}-measurable.)

Acknowledgments

The research described in this publication was made possible in part by Grant No. MRS000 from the International Science Foundation.

References

[1] A. P. Dawid. Probability forecasting. In: Encyclopedia of Statistical Sciences (ed. by S. Kotz and N. L. Johnson). Vol. 7, p. 210–218. New York: Wiley [2] B. de Finetti. Theory of probability. Vol. 1. London: Wiley (1974)

[3] A. N. Kolmogorov. Sur la loi forte des grands nombres. C. r. Acad. sci. Paris 191, 910–912 (1930)

[4] D. A. Martin. An extension of Borel determinacy. Ann. Pure Appl. Logic 49, 279–293 (1990)

[5] G. Shafer. The art of causal conjecture, to appear

[6] A. N. Shiryayev. Veroyatnost’. 2nd ed. Moscow: Nauka (1989). English translation of the 1st edition: Probability. Berlin: Springer (1984).

[7] V. G. Vovk. A game of prediction with expert advice. COLT’95, to appear [8] V. G. Vovk. A purely martingale version of Kolmogorov’s strong law of large

numbers. Probab. Theory Appl., to appear