Central limit theorem without probability

V. G. Vovk

Technical Report CLRC-TR-99-02 June 1995

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

Department of Computer Science Egham, Surrey TW20 0EX, England Probability does not exist

Bruno de Finetti

Abstract

Let X_{1}, …, X_{n} be a sequence of bounded unprobabilized random variables which are disclosed in this order. Before X_{i}, i = 1, …, n, is disclosed, the Bookmaker announces the price E_{i} for a ticket which will pay X_{i} and the price V_{i−1} for a ticket which will pay ∑_{j=i}^{n}(X_{j} − E_{j})^{2}. We prove that, under mild conditions,

\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})

can be approximated by the standard normal distribution N_{0,1}, in the sense that, for each bounded continuous function U and large n, ∫ U(w) N_{0,1}(dw) is close to being the fair price for the ticket which will pay

U (\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})) .

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

Theorem 1

1 Theorem

We consider the following perfect-information game involving the Statistician, the Bookmaker, and the Nature. The game proceeds in trials. At each trial i, i = 1, …, n, the Nature produces a real number X_{i}. Before that, at the beginning of trial i, the Bookmaker announces E_{i}, his prediction for X_{i}. The quality of the prediction E_{i} is measured by (X_{i} − E_{i})^{2} (sometimes this is called the Brier loss function). At the end of each trial i the Bookmaker announces V_{i}, his prediction for his cumulative loss ∑_{j=i+1}^{n}(X_{j} − E_{j})^{2} over the remaining trials; the initial prediction V_{0} is announced at the beginning of the game. We give the following operative interpretation to the Bookmaker’s predictions: before X_{i} is disclosed, the Bookmaker allows the Statistician to buy any amount, positive or negative, of variance tickets for $V_{i−1} each and X_{i}-tickets for $E_{i} each. A variance ticket is a contract which obliges the Bookmaker to pay the Statistician $(X_{i} − E_{i})^{2} every trial i and an X_{i}-ticket is a contract which obliges the Bookmaker to pay the Statistician $X_{i} after X_{i} is disclosed. After the Bookmaker has announced V_{i−1} and E_{i} but before X_{i} is disclosed, the Statistician buys as many variance tickets and X_{i}-tickets as he wishes; after that he will have, say, v_{i} variance tickets and e_{i} X_{i}-tickets. In this game the Statistician plays against the Bookmaker and the Nature who can coordinate their actions; we will use the word “Environment” to mean the Bookmaker and the Nature together.

Suppose the Statistician’s initial capital is K_{0}. We can describe unfolding of the game, including the evolution of the Statistician’s capital, as follows:

Environment chooses V_{0} ∈ ]0, ∞[ FOR i = 1, …, n:

Statistician chooses v_{i} ∈ IR

K_{i} := K_{i−1} − v_{i}V_{i−1} (1) Environment chooses E_{i} ∈ IR Statistician chooses e_{i} ∈ IR K_{i} := K_{i} − e_{i}E_{i} (2) Environment chooses X_{i} ∈ IR K_{i} := K_{i} + e_{i}X_{i} + v_{i}(X_{i} − E_{i})^{2} (3) Environment chooses V_{i} ∈ ]0, ∞[ K_{i} := K_{i} + v_{i}V_{i}. (4)

We call the pair (v_{i}, e_{i}) the portfolio held by the Statistician at trial i. Equations (1) and (2) show how the Statistician’s capital decreases when he buys the new portfolio; (3) describes the proceeds from holding the portfolio; (4) shows how the Statistician’s capital increases when he sells the old portfolio (the X_{i}-tickets become useless and he throws them away). We can summarize (1) through (4) as follows:

K_{i} := K_{i−1} + v_{i}(V_{i} − V_{i−1}) + v_{i}(X_{i} − E_{i})^{2} + e_{i}(X_{i} − E_{i}).  (5)

The addend v_{i}(V_{i} −V_{i−1}) represents the capital gain from holding the portfolio, v_{i}(X_{i}−E_{i})^{2} represents the dividends paid by the variance tickets, and e_{i}(X_{i}−E_{i}) represents the profit brought by the X_{i}-tickets.

We are going to prove a central limit theorem, and to do this we have to impose some restrictions on the Environment. We will require that V_{n} = 0 and, for some constant C > 1,

|X_{i}| ≤ C, i = 1, …, n,  (6)
|V_{i+1} − V_{i}| ≤ C, i = 0, …, n − 1,  (7)
V_{0} ≥ n/C.  (8)

Inequalities (6) simply mean that X_{i} are known to be uniformly bounded; (7) means that each observation carries not too much information about the predictability of the future observations (note that the sequence V_{i} is not necessarily monotonic); and (8) means that the Bookmaker believes that on the average his error |X_{i} − E_{i}| will not be excessively small. Therefore, the parameter C reflects the strength of the limitations imposed on the Environment.

To complete the description of the game between the Statistician and the Environment, we must specify a rule which says who won the game given its record

V_{0}v_{1}E_{1}e_{1}X_{1}V_{1} … v_{n−1}E_{n−1}e_{n−1}X_{n−1}V_{n−1}v_{n}E_{n}e_{n}X_{n}.

Let f: IR^{3n} → IR be a function of a partial record

V_{0}E_{1}X_{1}V_{1} … E_{n−1}X_{n−1}V_{n−1}E_{n}X_{n}.

By G(K_{0}, f | n, C) we denote the game which is played according to the above protocol (K_{0} is the Statistician’s initial capital, n is the duration of the game, and C is the constant from (6)–(8)) with the following winning condition: the Statistician wins if his final capital satisfies

K_{n} ≥ f(V_{0}E_{1}X_{1}V_{1} … E_{n−1}X_{n−1}V_{n−1}E_{n}X_{n});

otherwise, the Environment wins. It is well known that in a perfect-information game of finite duration such as G(K_{0}, f | n, C) one of the players has a winning strategy; we let G(K_{0}, f | n, C) ⌣ S stand for “the Statistician has a winning strategy in G(K_{0}, f | n, C)”.

Now we can define our basic notions, the upper and lower expectation:

E^{+}(f | n, C) := inf{K_{0} | G(K_{0}, f | n, C) ⌣ S};
E^{−}(f | n, C) := − E^{+}(−f | n, C).

Proof 3

We interpret E^{+}(f | n, C) as an upper bound on the maximal price that the Statistician can pay at the beginning of the game for the ticket which pays $f(V_{0} … X_{n}) at the end of the game. Indeed, having $ E^{+}(f |n, C)+ϵ, whatever small ϵ > 0 can be, is better for the Statistician than having the ticket: if the Statistician has $ E^{+}(f | n, C) + ϵ, he can consume $\frac{ϵ}{2} and still make more than $f(V_{0}, …, X_{n}) out of the remaining $ E^{+}(f | n, C) + \frac{ϵ}{2}. Analogously, E^{−}(f | n, C) is a lower bound on the minimal price that the Statistician can pay at the beginning of the game for that ticket. Indeed, having the ticket is better than having $ E^{−}(f | n, C) − ϵ: if the Statistician has the ticket, he can borrow $ E^{−}(f | n, C) − \frac{ϵ}{2} and set aside $ E^{−}(f | n, C) − ϵ consuming $\frac{ϵ}{2}; after that he can use his winning strategy in

G (− E^{−}(f | n, C) + \frac{ϵ}{2}, −f | n, C)

to make his debt of $ E^{−}(f | n, C) − \frac{ϵ}{2} into a debt of $f(V_{0} … X_{n}), which can be repaid with the ticket. (The Statistician can narrow the price span [E^{−}(f | n, C), E^{+}(f | n, C)] if he has additional information about the Environment.)

Now we can state the main result of this paper; we let N_{μ,σ^{2}} stand for the normal distribution in the real line IR with mean μ and variance σ^{2}.

Theorem 1 For arbitrarily large C and all bounded continuous U: IR → IR,

lim_{n→∞} E^{±} (U (\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})) | n, C) = ∫ U(w) N_{0,1}(dw).  (9)

2 Proof

First we prove two auxiliary results.

Lemma 2 E^{+}(f + g | n, C) ≤ E^{+}(f | n, C) + E^{+}(g | n, C).

Proof If the Statistician has winning strategies in G(a, f |n, C) and G(b, g|n, C), he can win G(a + b, f + g | n, C) acting as follows: if at trial i the winning strategies in G(a, f | n, C) and G(b, g | n, C) recommend portfolios (v′_{i}, e′_{i}) and (v′′_{i}, e′′_{i}), respectively, he chooses the portfolio (v′_{i} + v′′_{i}, e′_{i} + e′′_{i}). ⊓ ⊔

Lemma 3 (coherence) E^{−}(f | n, C) ≤ E^{+}(f | n, C).

Proof We are required to prove

E^{+}(f | n, C) + E^{+}(−f | n, C) ≥ 0.

By Lemma 2, it suffices to prove E^{+}(0 | n, C) ≥ 0. To disprove E^{+}(0 | n, C) < 0, note that if the Statistician’s initial capital is K_{0} < 0, the Environment can ensure 0 > K_{0} ≥ K_{1} ≥ … choosing E_{i} := 0, V_{i} := n − i, and

X_{i} := \{ \begin{matrix}1, if e_{i} < 0, \\ −1, otherwise. \end{matrix}

⊓ ⊔

We begin the proof of Theorem 1 by noting that it actually suffices to prove

\overline{lim}_{n→∞} E^{+} (U (\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})) | n, C) ≤ ∫ U(w) N_{0,1}(dw). (10)

Indeed, substituting in (10) −U in place of U, we will obtain

\underline{lim}_{n→∞} E^{−} (U (\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})) | n, C) ≥ ∫ U(w) N_{0,1}(dw),

which together with (10) and Lemma 3 implies (9).

So we will prove (10). First we will assume that U is a smooth function whose 3rd and 4th derivatives are bounded: for some constant c and all w ∈ IR, |U^{(3)}(w)| ≤ c and |U^{(4)}(w)| ≤ c. Without loss of generality we also assume that the Environment always chooses E_{i} ∈ [−C, C].

Put

u(D, S) := ∫ U(w) N_{S,D}(dw),

where D ≥ 0 and S ∈ IR; we will construct a strategy for the Statistician which will enable him to have about u(D_{i}, S_{i}), where

D_{i} := \frac{V_{i}}{V_{0}} , S_{i} := \frac{1}{\sqrt{V_{0}}} ∑_{j=1}^{i}(X_{j} − E_{j}),

at the end of each trial i provided he started off with u(D_{0}, S_{0}). It is well known (and easy to check) that u satisfies Kolmogorov’s backward equation:

D > 0 ⟹ \frac{∂u}{∂D} = \frac{1}{2} \frac{∂^{2}u}{∂S^{2}} .  (11)

Putting ΔA_{i} := A_{i+1} − A_{i}, i = 0, …, n − 1, we find:

\begin{matrix}Δu(D_{i}, S_{i}) = \frac{∂u}{∂D} (D_{i}, S_{i})ΔD_{i} + \frac{∂u}{∂S} (D_{i}, S_{i})ΔS_{i} \\ +\frac{1}{2} \frac{∂^{2}u}{∂D^{2}} (D′_{i}, S′_{i})(ΔD_{i})^{2} + \frac{1}{2} \frac{∂^{2}u}{∂D∂S} (D′_{i}, S′_{i})ΔD_{i}ΔS_{i} + \frac{1}{2} \frac{∂^{2}u}{∂S^{2}} (D′_{i}, S′_{i})(ΔS_{i})^{2}, \end{matrix}

(12)

where (D′_{i}, S′_{i}) is a point strictly between (D_{i}, S_{i}) and (D_{i+1}, S_{i+1}). Applying Taylor’s formula to \frac{∂^{2}u}{∂S^{2}} , we find

\frac{∂^{2}u}{∂S^{2}} (D′_{i}, S′_{i}) = \frac{∂^{2}u}{∂S^{2}} (D_{i}, S_{i}) + \frac{∂^{3}u}{∂D∂S^{2}} (D′′_{i}, S′′_{i})ΔD′_{i} + \frac{∂^{3}u}{∂S^{3}} (D′′_{i}, S′′_{i})ΔS′_{i}, (13)

where (D′′_{i}, S′′_{i}) is a point strictly between (D_{i}, S_{i}) and (D′_{i}, S′_{i}), and ΔD′_{i} and ΔS′_{i} satisfy |ΔD′_{i}| ≤ |ΔD_{i}|, |ΔS′_{i}| ≤ |ΔS_{i}|. Plugging (13) and (11) into (12), we find:

Δu(D_{i}, S_{i}) = \frac{∂u}{∂D} (D_{i}, S_{i}) (ΔD_{i} + (ΔS_{i})^{2}) + \frac{∂u}{∂S} (D_{i}, S_{i})ΔS_{i}
+\frac{1}{2} \frac{∂^{2}u}{∂D^{2}} (D′_{i}, S′_{i})(ΔD_{i})^{2} + \frac{1}{2} \frac{∂^{2}u}{∂D∂S} (D′_{i}, S′_{i})ΔD_{i}ΔS_{i}
+\frac{1}{2} \frac{∂^{3}u}{∂D∂S^{2}} (D′′_{i}, S′′_{i})ΔD′_{i}(ΔS_{i})^{2} + \frac{1}{2} \frac{∂^{3}u}{∂S^{3}} (D′′_{i}, S′′_{i})ΔS′_{i}(ΔS_{i})^{2}.

(14)

We can see that it is natural for the Statistician to choose the portfolio

(\underbrace{\frac{1}{V_{0}} \frac{∂u}{∂D} (D_{i}, S_{i})}_{variance tickets}, \underbrace{\frac{1}{\sqrt{V_{0}}} \frac{∂u}{∂S} (D_{i}, S_{i})}_{X_{i+1}-tickets})

at trial i + 1. In this case, the first two addends of (14) give the increment of the Statistician’s capital (cf. (5)), and we can rewrite (14) as

Δu(D_{i}, S_{i}) = ΔK_{i}
+\frac{1}{2} \frac{∂^{2}u}{∂D^{2}} (D′_{i}, S′_{i})(ΔD_{i})^{2} + \frac{1}{2} \frac{∂^{2}u}{∂D∂S} (D′_{i}, S′_{i})ΔD_{i}ΔS_{i}
+\frac{1}{2} \frac{∂^{3}u}{∂D∂S^{2}} (D′′_{i}, S′′_{i})ΔD′_{i}(ΔS_{i})^{2} + \frac{1}{2} \frac{∂^{3}u}{∂S^{3}} (D′′_{i}, S′′_{i})ΔS′_{i}(ΔS_{i})^{2}.

(15)

¿From (11) we deduce

\frac{∂^{2}u}{∂D^{2}} = \frac{1}{2} \frac{∂^{3}u}{∂D∂S^{2}} ;
\frac{∂^{2}u}{∂D∂S} = \frac{∂^{2}u}{∂S∂D} = \frac{1}{2} \frac{∂^{3}u}{∂S^{3}} ;
\frac{∂^{3}u}{∂D∂S^{2}} = \frac{∂^{3}u}{∂S^{2}∂D} = \frac{1}{2} \frac{∂^{4}u}{∂S^{4}} .

Since \frac{∂^{3}u}{∂S^{3}} and \frac{∂^{4}u}{∂S^{4}} , being averages of U^{(3)} and U^{(4)}, cannot exceed c, we obtain from (15) and (6)–(8):

|Δu(D_{i}, S_{i}) − ΔK_{i}|
≤ c (|ΔD_{i}|^{2} + |ΔD_{i}||ΔS_{i}| + |ΔD_{i}||ΔS_{i}|^{2} + |ΔS_{i}|^{3})
≤ c (\frac{C^{2}}{V_{0}^{2}} + \frac{C}{V_{0}} \frac{2C}{\sqrt{V_{0}}} + \frac{C}{V_{0}} \frac{4C^{2}}{V_{0}} + \frac{(2C)^{3}}{V_{0}^{3/2}} )
≤ \frac{C_{1}}{(n/C)^{3/2}} ≤ C_{2}n^{−3/2}

(C_{1} and C_{2} are some constants). Summing over i = 0, …, n − 1, we obtain

|(u(D_{n}, S_{n}) − u(D_{0}, S_{0})) − (K_{n} − K_{0})| ≤ C_{2}n^{−1/2},

i.e.,

|U (\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})) − ∫ U(w) N_{0,1}(dw) − (K_{n} − K_{0})| ≤ C_{2}n^{−1/2}.

Therefore, for an arbitrarily small δ > 0,

G (∫ U(w) N_{0,1}(dw) + δ, U (\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})) | n, C) ⌣ S, (16)

provided n is sufficiently large.

Now we drop the assumption that U is a smooth function with bounded U^{(3)} and U^{(4)}. Let δ > 0. We are required to prove that, from some n on, (16) holds. Since U is bounded and continuous, we can find, for arbitrarily large c and arbitrarily small ϵ, a smooth \overline{U} such that:

⋄ outside [−c − 1, c + 1], \overline{U} is constant and equals sup_{w} |U(w)|; ⋄ inside [−c, c], U ≤ \overline{U} ≤ U + ϵ; ⋄ inside [−c − 1, −c] and inside [c, c + 1], \overline{U} is monotonic and \overline{U} ≥ U.

Taking c sufficiently large and ϵ sufficiently small, we will have

U ≤ \overline{U}, ∫ (\overline{U}(w) − U(w)) N_{0,1}(dw) < \frac{δ}{2}.  (17)

Since U^{(3)} and U^{(4)} are smooth and finite (i.e., zero outside a finite interval), they are bounded. Therefore, we already proved that, from some n on,

G (∫ \overline{U}(w) N_{0,1}(dw) + \frac{δ}{2}, \overline{U} (\frac{1}{\sqrt{V_{0}}} ∑_{i=1}^{n}(X_{i} − E_{i})) | n, C) ⌣ S. (18)

It remains to note that (16) follows from (17) and (18).

Acknowledgments

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