A purely martingale version of Lindeberg’s central limit theorem

V. G. Vovk

Technical Report CLRC-TR-99-03 June 1995

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

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

Abstract We prove Lindeberg’s central limit theorem in Glenn Shafer’s event-

tree framework for probability theory.

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

Our definitions follow Shafer’s [6] Chapters 11 (event trees) and 12 (martingale probability). For the first time the idea of martingale probability seems to occur in Dawid [2] (for details, see [8], Section 3).

An event tree is a partially ordered set Γ that satisfies

Axiom E1 Any two elements s and t of Γ are either ordered (i.e., s ≤ t or t ≤ s) or divergent (i.e., there is no u ∈ Γ such that s ≤ u and t ≤ u).

Axiom E2 Γ has an initial element □ (that is, □ ≤ s for all s ∈ Γ).

We call the elements of Γ situations, and we take s ≤ t to mean that t cannot happen unless s happens earlier.

A path is a maximal set of ordered situations. We will consider only event trees for which all paths are finite; let Γ be such an event tree. We identify the paths in Γ with the terminal situations of Γ in a natural way: a path is identified with its terminal situation.

The sample space is the set of all paths. A variable is a real-valued function on the sample space.

A process is a real-valued function on the event tree. A cut (of a situation s) is a maximal set of divergent situations (after s). A martingale is a process μ which satisfies

Axiom M If s ∈ Γ and Ξ is a cut of s, then there exist situations t_{1}, t_{2} ∈ Ξ such that μ(t_{1}) ≤ μ(s) ≤ μ(t_{2}).

A catalog is a linear space M of martingales^{1}. A catalog M is Doob if it satisfies the following axioms:

Axiom V0 M contains the constant martingales.

Axiom V1 If μ ∈ M and Ξ is a cut, then E_{Ξ}(μ) ∈ M.

By E_{Ξ}(μ) we mean the process μ′ defined by

μ′(s) := μ(Ξ(s)),

where

Ξ(s) := \{ \begin{matrix}s, if s is before Ξ, \\ t ∈ Ξ such that t ≤ s, otherwise. \end{matrix}

1Note that under this definition we do not need de Finetti’s assumption of coherence (which is about the same as the financial-theoretic requirement of nonexistence of arbitrage opportunities).

We will consider only catalogs which are Doob and satisfy the following condition: if {μ_{θ} | θ ∈ Θ} is a locally finite family of martingales (in the sense that for each situation s there exist only finitely many θ such that μ_{θ}(s) ≠ 0), then ∑_{θ∈Θ} μ_{θ} is a martingale.

Let M be a catalog on Γ; we say that (Γ, M) is a martingale tree. An Mmartingale difference is a process of the form s ↦ μ(s) − μ(s^{−}), where s^{−} is the mother of s (except □^{−} := □) and μ ∈ M. If U = U(ω) is a variable, we define the upper and lower expectation as follows:

E^{+}[U | M] := inf{μ(□) | μ ∈ M, μ(ω) ≥ U(ω), for all terminal ω ∈ Γ},
E^{−}[U | M] := sup{μ(□) | μ ∈ M, μ(ω) ≤ U(ω), for all terminal ω ∈ Γ}.

If s is a nonterminal situation and X is a partial process defined at least on the daughters of s, we define the one-step-ahead expectations

E_{s}^{+}[X | M] := inf{μ(s) | μ ∈ M, μ(t) ≥ X(t), for all daughters t of s},
E_{s}^{−}[X | M] := sup{μ(s) | μ ∈ M, μ(t) ≤ X(t), for all daughters t of s}.

If U is the indicator of an event (event is a subset of the sample space), the definition of E^{+} and E^{−} specializes to the definition of upper and lower probability:

P^{+}[E | M] := E^{+}[I(E) | M],
P^{−}[E | M] := E^{−}[I(E) | M],

where E is an event and I stands for the indicator. Note that always

E^{−}[U | M] = −E^{+}[−U | M],
P^{−}[E | M] = 1 − P^{+}[E^{c} | M].

Let (Γ_{n}, M_{n}) be a sequence of martingale trees and, for each n, U_{n} = U_{n}(ω) be a variable in (Γ_{n}, M_{n}). We say that U_{n} tends to 0 in probability, U_{n}(ω) ⟶^{M_{n}} 0, as n → ∞, if

∀δ > 0: lim_{n→∞} P^{+}[|U_{n}| > δ | M_{n}] = 0.

Notice that the definition of catalog implies that the lower expectation never exceeds the upper expectation.

The following theorem, which is the main result of this paper, is analogous to the martingale central limit theorem in Shiryaev [7], Theorem VII.8.4, and Liptser and Shiryaev [5], Theorem 5.5.9. We let N (du | m, σ^{2}) stand for the normal distribution in IR with mean m and variance σ^{2}. Each expression A(ω) containing ω is interpreted as the variable ω ↦ A(ω), ω ranging over the paths.

Theorem 1 Let (Γ_{n}, M_{n}) be a sequence of martingale trees and, for each n, X_{n} be an M_{n}-martingale difference in (Γ_{n}, M_{n}) and Ξ_{n} be a cut in Γ_{n}. Lindeberg’s condition

∀δ > 0: ∑_{s<Ξ_{n}(ω)} E_{s}^{+}[X_{n}^{2} I(|X_{n}| ≥ δ) | M_{n}] ⟶^{M_{n}} 0 (n → ∞)  (1)

Proof 3

and the condition

∑_{s<Ξ_{n}(ω)} E_{s}^{±}[X_{n}^{2} | M_{n}] ⟶^{M_{n}} σ^{2} (n → ∞),  (2)

where σ is a positive constant, imply that, for every bounded continuous function f: IR → IR,

E^{±} [f ( ∑_{s≤Ξ_{n}(ω)} X_{n}(s)) | M_{n}] ⟶ ∫_{−∞}^{∞} f(u) N (du | 0, σ^{2}) (n → ∞). (3)

2 Proof

In the proof of Theorem 1 we shall use Lindeberg’s method; the simplest variants of this proof appeared in [8] (the proof of Theorem 5) and [9] (the proof of Theorem 6).

First we notice that it suffices to prove that (1) and (2) imply that, for any bounded continuous f,

lim sup_{n→∞} E^{+} [f ( ∑_{s≤Ξ_{n}(ω)} X_{n}(s)) | M_{n}] ≤ ∫_{−∞}^{∞} f(u) N (du | 0, σ^{2}).  (4)

(This is because this inequality will continue to hold if we replace f by −f.) Fix bounded continuous f and assume (1) and (2); we are required to prove (4). Without loss of generality we assume that each Ξ_{n} is the terminal cut of Γ_{n}; therefore, we can replace Ξ_{n}(ω) by ω in (4).

First we assume that f is a smooth function that is constant outside a compact interval. We introduce the function

g(h) := sup_{x} |f(x + h) − f(x) − f′(x)h − \frac{1}{2}f′′(x)h^{2}|

and note that

|[f(x + h) − f(x)] − [f′(x)h + \frac{1}{2}f′′(x)h^{2}]| ≤ g(h)  (5)

and, for some constant K,

g(h) ≤ K|h|^{3}, g(h) ≤ Kh^{2}, ∀h.  (6)

We shall suppose that K > 2.

Fix arbitrarily small δ ∈ ]0, 1[. Let ϵ ∈ ]0, 1[ be so small that, for all v ∈ IR and all Δ ∈ ]0, 2ϵ],

|∫_{−∞}^{∞} f(u) N (du | v, Δ) − f(v)| ≤ δ  (7)

and

|∫_{−∞}^{∞} f(u) N (du | 0, σ^{2} + ϵ) − ∫_{−∞}^{∞} f(u) N (du | 0, σ^{2})| ≤ δ.  (8)

Let us check that such ϵ indeed exists. The existence of ϵ satisfying (7) follows from f being uniformly continuous and bounded—see, e.g., Feller [3], Lemma VII.1.1. To prove the existence of ϵ satisfying (8), it suffices to prove that the variation distance between the normal distributions N (du | 0, σ^{2}) and N (du | 0, σ^{2} + ϵ) tends to 0 as ϵ → 0. By Shiryaev [7], Theorem III.9.1, we can here replace the variation distance with 1 − H, where H is the corresponding Hellinger integral. An easy calculation shows that indeed H → 1 as ϵ → 0.

Fix n so large that the lower probability of the conjunction of the three inequalities

|∑_{s<ω} E_{s}^{±}[X_{n}^{2} | M_{n}] − σ^{2}| ≤ ϵ,  (9)
∑_{s<ω} E_{s}^{+}[X_{n}^{2} I(|X_{n}| ≥ δ^{2}) | M_{n}] ≤ δ^{4}  (10)

is at least 1 − δ. Inequality (10) implies

∑_{s<ω} E_{s}^{+}[X_{n}^{2} I(|X_{n}| ≥ δ) | M_{n}] ≤ δ  (11)

and, for all s < ω,

E_{s}^{+}[X_{n}^{2} | M_{n}] ≤ 2δ^{4}.  (12)

We shall show that for some martingale \overline{F} ∈ M_{n} we have

\overline{F} (□) = ∫_{−∞}^{∞} f(u) N (du | 0, σ^{2} + ϵ) + (2 sup |f′′| + 8Kσ^{2} + 13K)δ + δ (13)

and, for all ω satisfying (9) and (10),

\overline{F} (ω) ≥ f (∑_{t≤ω} X_{n}(t)) .  (14)

Since ω satisfies (9) and (10) with lower probability at least 1 − δ, our goal will be achieved (recall (8) and that δ can be taken arbitrarily small).

Put, for each situation s ∈ Γ_{n},

F (s) := ∫_{−∞}^{∞} f(S(s) + u) N (du | 0, σ^{2} + ϵ − ∑_{t<s} E_{t}^{mean}[X_{n}^{2} | M_{n}]) ,

where

S(s) := ∑_{t≤s} X_{n}(t), E_{s}^{mean} := \frac{1}{2}(E_{s}^{+} + E_{s}^{−}),

and N (du | m, v) is interpreted as N (du | m, 0) when v < 0. The idea behind the construction of \overline{F} is to “approximate”, in some sense, F.

For each s ∈ Γ_{n} and v ∈ IR put

F_{s}(v) := ∫_{−∞}^{∞} f(v + u) N (du | 0, σ^{2} + ϵ − ∑_{t≤s} E_{t}^{mean}[X_{n}^{2} | M_{n}]) .

When t is a daughter of s and t ≤ ω for an ω satisfying (9) and (10), we find (using Taylor’s formula and the fact^{2} that (5) continues to hold when f is replaced by F_{s}):

F (t) − F (s)
= F_{s}(S(s) + X_{n}(t)) − ∫_{−∞}^{∞} F_{s}(S(s) + u) N (du | 0, E_{s}^{mean}[X_{n}^{2} | M_{n}])
≤ [F_{s}(S(s)) + F′_{s}(S(s))X_{n}(t) + \frac{1}{2}F′′_{s}(S(s))X_{n}^{2}(t) + g(X_{n}(t))]
−[F_{s}(S(s)) + \frac{1}{2}F′′_{s}(S(s))E_{s}^{mean}[X_{n}^{2} | M_{n}]
+ ∫_{−∞}^{∞} g(u) N (du | 0, E_{s}^{mean}[X_{n}^{2} | M_{n}])]
= F′_{s}(S(s))X_{n}(t) + \frac{1}{2}F′′_{s}(S(s)) (X_{n}^{2}(t) − E_{s}^{mean}[X_{n}^{2} | M_{n}])
+ {g(X_{n}(t)) + ∫_{−∞}^{∞} g(u) N (du | 0, E_{s}^{mean}[X_{n}^{2} | M_{n}])} .

(15)

Let us estimate the “remainder” in the braces in (15): using the inequality

g(h) ≤ K|h|^{3} I(|h| ≤ δ) + Kh^{2} I(|h| > δ) ≤ Kδh^{2} + Kh^{2} I(|h| > δ), (16)

which follows from (6), we obtain

g(X_{n}(t)) ≤ KδX_{n}^{2}(t) + KX_{n}^{2}(t) I(|X_{n}(t)| > δ);

and using (16) and (12), we further obtain

∫_{−∞}^{∞} g(u) N (du | 0, E_{s}^{mean}[X_{n}^{2} | M_{n}])
≤ Kδ ∫_{−∞}^{∞} u^{2} N (du | 0, E_{s}^{mean}[X_{n}^{2} | M_{n}])
+K ∫_{−∞}^{∞} u^{2} I(|u| > δ) N (du | 0, E_{s}^{mean}[X_{n}^{2} | M_{n}])
≤ KδE_{s}^{mean}[X_{n}^{2} | M_{n}] + \frac{K}{δ} ∫_{−∞}^{∞} |u|^{3} N (du | 0, E_{s}^{mean}[X_{n}^{2} | M_{n}])
≤ KδE_{s}^{mean}[X_{n}^{2} | M_{n}] + \frac{K}{δ} (E_{s}^{mean}[X_{n}^{2} | M_{n}])^{3/2} ∫_{−∞}^{∞} |u|^{3} N (du | 0, 1)
≤ KδE_{s}^{mean}[X_{n}^{2} | M_{n}] + \frac{K}{δ} E_{s}^{mean}[X_{n}^{2} | M_{n}]2δ^{2}3
= 7KδE_{s}^{mean}[X_{n}^{2} | M_{n}].

Therefore, we obtain from (15):

F (t) − F (s)
≤ F′_{s}(S(s))X_{n}(t) + \frac{1}{2}F′′_{s}(S(s)) (X_{n}^{2}(t) − E_{s}^{mean}[X_{n}^{2} | M_{n}])
+KδX_{n}^{2}(t) + KX_{n}^{2}(t) I(|X_{n}(t)| > δ) + 7KδE_{s}^{mean}[X_{n}^{2} | M_{n}].

(17)

N (du | v, σ^{2} + ϵ − ∑_{t≤s} E_{t}^{mean}[X_{n}^{2} | M_{n}]) .

2This fact follows from Kolmogorov’s [4] Theorem IV.5.1: we can average (5) with respect to x distributed as

For each s ∈ Γ_{n} define the level of s to be

lev(s) := #{t | t < s}.

If s ∈ Γ_{n} and μ is a process, the s-local component Loc_{s}(μ) of μ is the only s-local process (a process is s-local if μ(□) = 0 and μ(t_{1}) = μ(t_{2}) whenever t_{1} ≠ s and t_{2} is a daughter of t_{1}) which satisfies

Loc_{s}(μ)(t) − Loc_{s}(μ)(s) = μ(t) − μ(s), t ∈ D(s),

D(s) being the daughter set of s. Note that μ can be recovered from Loc_{s}(μ), s ∈ Γ_{n}:

μ = μ(□) + ∑{Loc_{s}(μ) | s is a nonterminal situation}.

For each s ∈ Γ_{n} fix three s-local martingales μ_{s}, μ_{s}^{+}, μ_{s}^{−} ∈ M_{n} such that, on D(s),

μ_{s} ≥ X_{n}^{2} I(|X_{n}| > δ) − E_{s}^{+}[X_{n}^{2} I(|X_{n}| > δ) | M_{n}] − δ2^{− lev(s)},
μ_{s}^{+} ≥ X_{n}^{2} − E_{s}^{+}[X_{n}^{2} | M_{n}] − δ2^{− lev(s)},
μ_{s}^{−} ≤ X_{n}^{2} − E_{s}^{−}[X_{n}^{2} | M_{n}] + δ2^{− lev(s)}.

Now we can define the martingale \overline{F}. The initial value \overline{F} (□) is given by (13), and for each nonterminal s ∈ Γ_{n} the s-local component of \overline{F} is defined as the following weighted sum of μ_{s}, μ_{s}^{+}, μ_{s}^{−}, and the s-local component of X_{n}:

Loc_{s}(\overline{F}) = F′_{s}(S(s)) Loc_{s}(X_{n}) + Kδμ_{s}^{+} + Kμ_{s} + \frac{1}{2}F′′_{s}(S(s))μ_{s}^{±},

where

μ_{s}^{±} := \{ \begin{matrix}μ_{s}^{+}, if F′′_{s}(S(s)) > 0, \\ μ_{s}^{−}, if F′′_{s}(S(s)) < 0. \end{matrix}

We deduce from (17):

F (t) − F (s) ≤ \overline{F} (t) − \overline{F} (s)
+\frac{1}{2} sup |f′′| (\frac{E_{s}^{+}[X_{n}^{2}|M_{n}]−E_{s}^{−}[X_{n}^{2}|M_{n}]}{2} + δ2^{− lev(s)})
+Kδ (E_{s}^{+}[X_{n}^{2} | M_{n}] + δ2^{− lev(s)})
+K (E_{s}^{+}[X_{n}^{2} I(|X_{n}| > δ) | M_{n}] + δ2^{− lev(s)}) + 7KδE_{s}^{mean}[X_{n}^{2} | M_{n}].

Therefore, for each ω satisfying (9) and (10) we obtain (without loss of generality we assume ϵ ≤ δ):

F (ω) − F (□) ≤ \overline{F} (ω) − \overline{F} (□)
+\frac{1}{2} sup |f′′|(ϵ + 2δ) + Kδ(σ^{2} + ϵ + 2δ) + K(δ + 2δ) + 7Kδ(σ^{2} + ϵ)
≤ \overline{F} (ω) − \overline{F} (□) + (2 sup |f′′| + 8Kσ^{2} + 13K) δ

(see (9) to (11)). So we obtain:

\begin{matrix}\overline{F} (ω) ≥ \overline{F} (□) + F (ω) − F (□) − (2 sup |f′′| + 8Kσ^{2} + 13K) δ \\ = F (ω) + δ = ∫_{−∞}^{∞} f(u) N (du | S(ω), Δ) + δ ≥ f(S(ω)) \end{matrix}

(see (7)), where Δ ∈ [0, 2ϵ]. Hence we established (14), which completes the proof under the assumption that f is smooth and constant outside a finite interval.

Lemma 2 For any σ > 0, ϵ > 0, and bounded continuous f: IR → IR, there exists a smooth and constant outside a finite interval function f̃ such that f ≤ f̃ and

∫_{−∞}^{∞} f̃(u) N (du | 0, σ^{2}) ≤ ∫_{−∞}^{∞} f(u) N (du | 0, σ^{2}) + ϵ.  (18)

Proof There are an increasing finite sequence t_{1}, …, t_{k} of real numbers and a function g: IR → IR which is constant on each of the intervals

]−∞, t_{1}] ,]t_{1}, t_{2}] , …,]t_{k−1}, t_{k}] ,]t_{k}, ∞[

and satisfies g(−∞) = g(∞) and

f ≤ g, ∫_{−∞}^{∞} g(u) N (du | 0, σ^{2}) ≤ ∫_{−∞}^{∞} f(u) N (du | 0, σ^{2}) + \frac{ϵ}{2}.

It is well known that there exists a smooth function ϕ: IR → [0, 1] such that ϕ(t) = 1 for t ≤ 0 and ϕ(t) = 0 for t ≥ 1 (see, e.g., (7.1) of Billingsley [1]). Choose δ > 0 which does not exceed any of the values \frac{t_{2}−t_{1}}{2} ,…, \frac{t_{k}−t_{k−1}}{2} . Using the function ϕ, one can easily construct a smooth function f̃ such that:

⋄ g ≤ f̃,

⋄ f̃(t) = g(t) for each t ∉ ⋃_{i=1}^{k}]t_{i} − δ, t_{i} + δ[ ;

⋄ f̃(t) ∈ [g(t_{i}−), g(t_{i}+)] when t ∈ ]t_{i} − δ, t_{i} + δ[ .

Choosing sufficiently small δ, we ensure

∫_{−∞}^{∞} f̃(u) N (du | 0, σ^{2}) ≤ ∫_{−∞}^{∞} g(u) N (du | 0, σ^{2}) + \frac{ϵ}{2}.

⊓ ⊔

Now we can easily finish the proof. We are required to establish (4) for any bounded continuous f. By Lemma 2, there exists a smooth and constant outside a finite interval function f̃ such that f ≤ f̃ and (18) holds. Since (4) holds for f̃, we have:

lim sup_{n→∞} E^{+}[f(S) | M_{n}] ≤ lim sup_{n→∞} E^{+}[f̃(S) | M_{n}]
≤ ∫_{−∞}^{∞} f̃(u) N (du | 0, σ^{2}) ≤ ∫_{−∞}^{∞} f(u) N (du | 0, σ^{2}) + ϵ.

Since ϵ can be arbitrarily small, this proves (4).

REFERENCES 8

Acknowledgments

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

References

[1] P. Billingsley. Convergence of probability measures. New York: Wiley (1968)

[2] A. P. Dawid. Calibration-based empirical probability (with discussion). Ann. Statist. 13, 1251–1285 (1985)

[3] W. Feller. An introduction to probability theory and its applications. Vol. 2. 2nd ed. New York: Wiley (1971)

[4] A. N. Kolmogorov. Foundations of the theory of probability. New York: Chelsea (1950)

[5] R. S. Liptser, A. N. Shiryaev. Theory of martingales. Dordrecht: Kluwer (1989)

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

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

[8] V. G. Vovk. A logic of probability, with application to the foundations of statistics (with discussion). J. R. Statist. Soc. B 55, 317–351 (1993)

[9] V. G. Vovk. Forecasting point and continuous processes: prequential analysis. Test 2, 189–217 (1993)

[10] V. G. Vovk. A purely martingale version of Kolmogorov’s strong law of large numbers. Probab. Theory Appl., to appear