This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
t)
t-e). Proof Clearly {X > t} c {X* > t) and {X > t) c {X* > t}, so we have "<" in (a) and the first inequality in (b).
Take a measurable cover A D {X > t), so P*(X > t) = P(A). Then X* < t a.s. outside A, so P(X* > t) < P(A), proving (a). Thus for 0 < 8 <
e, P(X* > t - 8) < P*(X > t - s). Letting 8 4, 0 proves (b). Let (0, A, P) be aprobability space. For a function f from Q into [-oo, oo]
let f* f dP := sup{ f gdP : g measurable, g < f}. Let f* be the essential supremum of all measurable functions g < f. Then just as for f*, f* is well-defined up to a.s equality and f* f dP = f f* dP whenever either side is defined, as in Theorem 3.2.1.
3.2 Measurable cover functions
99
It's easy to check that f* = -((- f)*) and that f* f dP = -(f * - f dP). So the convergence in law Y, = Yo as defined in Section 3.1 implies that f* g(Y-,) dQn - f g(Yo) dQoNext, here is a one-sided Tonelli-Fubini theorem for starred functions:
3.2.7 Theorem Let (X, A, P) x (Y, B, Q) be a product of two probability spaces. For a real-valued function f > 0 on X x Y, define f * with respect to P x Q. For each x E X let (E* f)(x) := f * f (x, y) dQ(y). Then
EiE2f(x,Y)
(3.2.8)
ff*(x,y)d(PxQ)(x,y),
where Ei = E* with respect to P. Also, if Q is purely atomic, so that >j Q({yj)) = 1 for some yj E Y, and (3.2.9)
f - dQ, then
Ei E2f(X, Y) < E*f(X, Y) = E2Ei f(X, Y).
Proof By the usual Tonelli-Fubini theorem, we have (3.2.10)
f
f*(x, y)d(P x Q)(Y) = ff f*(x, y)d Q(y) dP(x),
and f f *(x, y)d Q(y) is measurable in x. For each x E X let f (y) := f (x, y). Then f(x, y) < f *(x, y), which is measurable in y, so f,, (y) < f *(x, y) for Q-almost all y. Thus since E* fX = Efx by Theorem 3.2.1,
(E*f)(x) =
f
f,*(Y)dQ(Y) <
f
f*(x,Y)dQ(Y),
and (3.2.8) follows. Next, to prove (3.2.9), note that on Y, since Q is purely atomic, all real-valued functions are measurable (for the completion of Q), so E2 - E2, the left inequality follows from (3.2.8), and the equality from (3.2.10), so (3.2.9) is proved. We also have a one-sided monotone convergence theorem with stars:
3.2.11 Theorem Let (S2, A, P) be a probability space and let f be realvalued functions on Q such that f f f, that is, f (x) T f (x) for all x E Q. If
E* fl > -oo then E*fj T E*f as j -+ oo.
Proof By Theorem 3.2.1, E*fj = Ef * for each j, and as j -+ oo, f increases a.s. up to some function g where clearly g < f * almost surely. If
g < f * on some set A with P(A) > 0, then f < g on A implies f < g and so f * < g on A, a contradiction. The theorem follows.
100
Uniform Central Limit Theorems: Donsker Classes
Recall that for any measure space (X, A, µ) and any C C X, the outer measure is defined by s*(C) := inf(µ(A) : A E A, A D C). Note that there exist subsets Aj := A(j) of [0, 1] with outer measure k*(Aj) = I for all j and Aj J, 0 (RAP, Problem 3.4.2). Letting f := IA(.i), we have f 4, 0, and E* f = 1 for all j, so that the monotone convergence theorem fails for E* on decreasing sequences. Next is a Fatou lemma with stars.
3.2.12 Theorem Let (Q, A, P) be a probability space and f any nonnegative real-valued functions on 0. Then E* lim infs.,, f < lim infj,0 E* f j. Proof For 1 < k < m we have infra>k f, < fm and so E* fn < E* fm, thus E* infn>k fn < infra>k E*fm. Taking the supremum over k on both sides and using the previous monotone convergence theorem gives the result.
3.3 Almost uniform convergence and convergence in outer probability In Section 3.1 the definition of convergence of laws was adapted to define convergence in law for random elements which may not have laws defined. In this section the same will be done for convergence in probability and almost sure convergence. Let (0, A, P) be a probability space, (S, d) a metric space, and fn functions
from S2 into S. Then f, will be said to converge to fo in outer probability if
d(f, fo)* - 0 in probability as n - oo, or equivalently, by Lemma 3.2.6,
for every e > 0, P*(d(f , fo) > E) -k 0 as n -+ oo. Also, f, is said to converge to fo almost uniformly if as n - oo, d(fn, fo)* -k 0 almost surely. The following is immediate:
3.3.1 Proposition Almost uniform convergence always implies convergence in outer probability.
If fn are all measurable functions, then clearly convergence in outer probability is equivalent to the usual convergence in probability, and almost uniform convergence to almost sure convergence. Now some definitions will be given for Glivenko-Cantelli properties, which are laws of large numbers for empirical measures.
Definition. If (X, A, P) is a probability space and .P is a class of integrable real-valued functions, F C Gt (X, A, P), then F will be called a strong (resp.
3.3 Convergence without measurability
101
weak) Glivenko-Cantelli class for P if as n -+ oo, 11 P, - PII.r --+ 0 almost uniformly (resp. in outer probability). In the following proposition, part (C) is what is usually called "Egorov's theorem" for almost surely convergent sequences of measurable functions (RAP, Theorem 7.5.1).
3.3.2 Proposition Let (S2, A, P) be a probability space, (S, d) a metric . Then the following space, and f, any functions from 2 into S for n = 0, 1, are equivalent:
(A) fn - fo almost uniformly. (B) For any e > 0, P*{sup,,>m d(fn, fo) > e} 4, 0 as m -* oo. (C) For any 8 > 0 there is some B E A with P(B) > 1 - 8 such that fn -* fo uniformly on B. (D) There exist measurable hn > d(fn, fo) with hn -+ 0 a.s. Proof (A) implies that (SUpn>m d (fn, f0))* < Sup,,>m (d (fn,
f0)*)
4, 0 a.s. I
as m -+ oo,
which implies (B).
Assuming (B), for k = 1, 2, , let Ck := {supra>m(k) d(f, fo) > 1/k), where m (k) is large enough so that P* (Ck) < 2-k. Take measurable covers B k f o r Ck, so C k C Bk, Bk E A, and P(Bk) < 2-k. For r = 1 , 2, , let Ar := S2 \ Uk>r Bk. Then P(Ar) > 1 - 2-' and fn fo uniformly on Ar, so (C) holds. Now assume (C). Take Ck E A, k = 1, 2, , such that P(Ck) T 1 and f n -+ f o uniformly on Ck. W e can take Cl C C2 C . Take Mk such that
d(f, fo) < 1/k on Ck for all n >_ mk. Then d(fn, fo)* < 1/k on Ck, so d(fn, fo)* --> 0 a.s., proving (A). Clearly, (A) and (D) are equivalent.
Example. In [0, 1] with Lebesgue measure P let A 1 D A2 D . . . be sets with P*(A,) = 1 and fn°_1 An = 0 (e.g., RAP, Section 3.4, problem 2; Cohn, 1980, p. 35). Then 1An -* 0 everywhere and, in that sense, almost surely, but not almost uniformly. Note also that lAn doesn't converge to 0 in law as defined in Section 3.1. To avoid such pathology, almost uniform convergence is helpful.
3.3.3 Proposition Let (S, d) and (Y, e) be two metric spaces and (S2, A, P) a probability space. Let f, be functions f r o m 0 into S for n = 1 , 2,
, such
that f, - fo in outer probability as n -+ oo. Assume that fo has separable
Uniform Central Limit Theorems: Donsker Classes
102
range and is measurable (for the Borel or -algebra on S). Let g be a continuous function from S into Y. Then g(fn) g(o) in outer probability.
Note. If f G (fo) dP is defined for all bounded continuous real G (as it must be if fn fo, by definition) then the image measure P o f0 1 is defined on all Borel subsets of S (RAP, Theorem 7.1.1). Such a law does have a separable support except perhaps in some set-theoretically pathological cases (Appen-
dix Q. , let Bk :_ {x E S: d(x, y) < 1/k implies P r o o f Given e > 0, k = 1, 2, e(g(x), g(y)) < s, y E S}. Then each Bk is closed and Bk T S as k -+ oo. Fix k large enough so that P(f01(Bk)) > 1 - e. Then {e(g(fn), g(.f0)) > s) (1 f0 1(Bk) C {d (fn, .fo)
1/k}.
Thus
P*{e(g(fn),g(f0)) > e} < e+P*{d(fn, fo) > 1/k} < 2s for n large enough.
3.3.4 Lemma Let (S2, A, P) be a probability space and {gn }n o a uniformly bounded sequence of real-valued functions on Q such that go is measurable. If gn -* go in outer probability then lim supn,, f * gn dP < f go dP.
Proof Let I g, (x) I < M < oo for all n and all x E 22. We can assume M = 1. Given s > 0, for n large enough P*(I gn - goI > e) < e. Let An be a measurable set on which Ign - gol < e with P(S2 \ An) < e. Then
J
gndP < e+ J*gndP < 2s+ f A
A An
< 3s+ J $odP.
Letting s 1. 0 completes the proof. On any metric space, the a-algebra will be the Borel or -algebra unless something is said to the contrary.
3.3.5 Corollary If f, are functions from a probability space into a metric space, fn --* fo in outer probability, and fo is measurable with separable range, then fn = fo. Proof Apply Proposition 3.3.3 to g = G for any bounded continuous G and Lemma 3.3.4 to gn := G o fn and also to gn = -G o fn.
3.4 Perfect functions
103
3.4 Perfect functions For a function g defined on a set A let g[A] :_ {g(x) : x E A}. It will be useful that under some conditions on a measurable function g and general real-valued
f, (f o g)* = f * o g. Here are some equivalent conditions: 3.4.1 Theorem Let (X, A, P) be a probability space, (Y, l3) any measurable space, and g a measurable function from X to Y. Let Q be the restriction of P o g t to B. For any real-valued function f on Y, define f *for Q. Then the following are equivalent:
(a) For any A E A there is a B E B with B C g[A] and Q(B) > P(A); (b) for any A E A with P(A) > 0 there is a B E 8 with B C g[A] and Q(B) > 0; (c) for every real function f on Y, (f o g)* = f * o g a.s.; (d) f o r any D C Y, OD o 9)* = 1 *D o g a. s.
Proof Clearly (a) implies (b).
To show (b) implies (c), note that always (f o g)* < f* o g. Suppose (f o g)* < f * o g on a set of positive probability. Then for some rational
r, (fog)*
andIDog=(lDog)*=Oa.sonA.LetB:=Y\C.Then BCg[A],and
Q(B) = 1 - Q(C) = 1 -
f 1* d(P o g '),
which by the image measure theorem (RAP, Theorem 4.1.11) equals
1-J 1*DogdP = 1- J(1Dog)*dP > P(A). Note. In (a) or (b), if the direct image g[A] E B, we could just set B := g[A]. But, for any uncountable complete separable metric space Y, there exists a complete separable metric space S (for example, a countable product N°O of copies of N) and a continuous function f from S into Y such that f [B] is not a Borel set in Y (RAP, Theorem 13.2.1, Proposition 13.2.5). If f is only required to be Borel measurable, then S can also be any uncountable complete metric space (RAP, Theorem 13.1.1).
104
Uniform Central Limit Theorems: Donsker Classes
A function g satisfying any of the four conditions in Theorem 3.4.1 will be called perfect or P perfect. Coordinate projections on a product space are, as one would hope, perfect:
3.4.2 Proposition Suppose A = X x Y, P is a product probability v x m, and g is the natural projection of A onto Y. Then g is P-perfect.
Proof Here P o g-1 =m. For any B CA let By := {x : (x, y) E B}, y e Y. If B is measurable, then by the Tonelli-Fubini theorem, for C := {y: v(By) >
0}, C is measurable, C C g[B], and P(B) < m(C), so condition (a) of Theorem 3.4.1 holds.
3.4.3 Theorem Let (0, A, P) be a probability space and (S, d) a metric , (Yn,13,,) is a measurable space, gn a space. Suppose that for n = 0, 1, perfect measurable function from 0 into Y,,, and fn a function from Y into S, where fo has separable range and is measurable. Let Qn := P o gn 1 on 13n and suppose fn o gn - fo o go in outer probability as n --* oo. Then fn = fo as n oo for fn on (Yn, 13,,, Qn)
Before this is proved, an example will be given. Recall that for any measure space (X, S, µ) and C C X, the inner measure is defined by /,t. (C)
sup{µ(A) : A E S, ACC}. 3.4.4 Proposition
Theorem 3.4.3 can fail without the hypothesis that gn be
perfect.
Proof Let C C I := [0, 1] satisfy 0 = X*(C) < X*(C) = 1 for Lebesgue measure A (RAP, Theorem 3.4.4). Let P = A*, giving a probability measure on
the Borel sets of C (RAP, Theorem 3.3.6). Let 0 = C, fo = 0, Yn = I, fn :_ II\C, and let gn be the identity from C into Y,, for all n. Then fn o gn = 0 for all n, so f, o gn -+ fo o go in outer probability (and in any other sense). Let 13,, be the Borel or-algebra on Y,, = I for each n. Let G be the identity from I into IR. Then f * dQn = f * fn da, = 1 for n > 1, while f G(fo) dQo = 0, so fn does not converge to fo in law.
After Theorem 3.4.3 is proved, it will follow that the gn in the last proof are not perfect, as can also be seen directly from condition (c) or (d) in Theorem 3.4.1.
fo o go. Let H Proof of Theorem 3.4.3 By Corollary 3.3.5, fn o g, be any bounded, continuous, real-valued function on S. Then by RAP,
3.4 Perfect functions
105
Theorem 4.1.11,
JH(ffl(gfl))dP - f H(fo(go)) dP
f
H(fo) dQo
Also,
f *H(fn(gn))dP =
f H(fn(gn))*dP
by Theorem 3.2.1
f(Hofn)*(gn)dP
by Theorem 3.4.1
f(Hofn)*dQn
(RAP, Theorem 4. 1.11)
f * H(fn) dQn
by Theorem 3.2.1,
and the theorem follows.
In Proposition 3.4.2, X x Y could be an arbitrary product probability space, but projection is a rather special function. The following fact will show that all measurable functions on reasonable domain spaces are perfect.
Recall that a law P is called tight if sup{P(K) : K compact) = 1. A set P of laws is called uniformly tight if for every e > 0 there is a compact K such that P(K) > 1 - e for all P E P. Also, a metric space (S, d) is called universally measurable (u.m.) if for every law P on the completion of S, S is measurable for the completion of P (RAP, Section 11.5). So any complete metric space, or any Borel set in its completion, is u.m.
3.4.5 Theorem
Let (S, d) be a u.m. separable metric space. Let P be a
probability measure on the Borel or -algebra of S. Then any Borel measurable function g from S into a separable metric space Y is perfect for P.
Note. In view of Appendix C, the hypothesis that S be separable is not very restrictive.
Proof Let A be any Borel set in S with P(A) > 0. Let 0 < s < P(A). By the extended Lusin theorem (Theorem D.1, Appendix D) there is a closed set F with
P(F) > 1-s/2 such that g restricted to F is continuous. Since P is tight (RAP, Theorems 11.5.1 and 7.1.3), there is a compact set K C A with P(K) > s. Then C := F fl K is compact, C C A, P(C) > 0, and g is continuous on C,
so g[C] is compact, g[C] C g[A], and (P o g 1)(g[C]) > P(C) > 0, so the conclusion follows from Theorem 3.4.1.
106
Uniform Central Limit Theorems: Donsker Classes
Let (0, A, P) be a probability space and g a measurable function from S2 into Y where (Y, 8) is a measurable space. Let Q := P o g 1 on B. Call g quasiperfect for P or P-quasiperfect if for every C C Y with g -'(C) E A, C is measurable for the completion of Q. Then the probability space (0, A, P) is called perfect if every real-valued function G on 0, measurable for the usual Borel or -algebra on R, is quasiperfect.
Example. A measurable, quasiperfect function g on a finite set need not be perfect: let X:= {al, a2, a3, a4, a5, a6}, U := {al, a2}, V :_ {a3, a4}, W {a5, a6}, A := {0, U, V, W, U U V, U U W, V U W, X), P(U) = P(V) _
P(W) = 1/3, Y := {0, 1, 21, g(al) := g(a3)
0, g(a2) := g(a5) :=
1,
g(a4) := g(a6) := 2. Let B := {0, Y). For C C Y, g-1 (C) E A if and only if C E B, so g is quasiperfect. But P(U) > 0 and g[U] does not include any nonempty set in 13, so g is not perfect.
3.4.6 Proposition Any perfect function is quasiperfect.
Proof Let C C Y, A := 9_1(C) E A. By Theorem 3.4.1 take B C g[A]
with B E 8 and Q(B) > P(A). Then B C C, so Q(B) = P(g 1(B)) < P(g 1(C)) = P(A), and Q(B) = P(A). Thus the inner measure Q,,(C) = P o g 1(C). Likewise, Q. (Y \ C) = (P o g 1) (Y \ C), so Q*(C) = (P o g 1) (C) and C is Q-completion measurable.
U
3.5 Almost surely convergent realizations First let's recall a theorem of Skorokhod (RAP, Theorem 11.7.2): if (S, d) is a complete separable metric space, and Pn are laws on S converging to a law Po, then on some probability space there exist S-valued measurable functions X, such that P, for all n and X -+ Xo almost surely. This section will prove an extension of Skorokhod's theorem to our current setup. Having almost uniformly convergent realizations shows that the definition of convergence in law for random elements is reasonable. The realizations will be useful in some later proofs on convergence in law.
Suppose f, = fo where f, are random elements, in other words functions not necessarily measurable except for n = 0, defined on some probability spaces (52,,, into a possibly nonseparable metric space S. We want to find random elements Y "having the same laws" as f, for each n such that Yo almost surely or better, almost uniformly. At first look it isn't clear Yn what "having the same laws" should mean for random elements fn, n > 1, not
3.5 Almost surely convergent realizations
107
having laws defined on any nontrivial or-algebra. A way that turns out to work is to define Y, = fn o gn where gn are functions from some other probability space 0 with probability measure Q into Stn such that each gn is measurable and Q o gn1 = Q, for each n. Thus the argument of fn will have the same law Qn as before. It turns out, moreover, that the gn should be not only measurable but perfect. Before stating the theorem, here is an example to show that there may really be no way to define a or -algebra on S on which laws could be defined and yield an equivalence as in the next theorem, even if S is a finite set.
Example. Let (Xn, An, Qn) = ([0, 1], B, A) for all n (), = Lebesgue measure, 13 = Borel a-algebra ). Take sets C(n) C [0, 1] with O = A*(C(n)) < .X*(C(n)) = 1/n2 (RAP, Theorem 3.4.4). Let S be the two-point space {0, 11 with usual metric. Then f,, := lC(n) -* 0 in law and almost uniformly, but each "law" On := Qn o fn 1 is only defined on the trivial a-algebra {0, S). The only larger or -algebra on S is 2S, but no On for n > 1 is defined on 2S.
3.5.1 Theorem Let (S, d) be any metric space, (Xn, An, Qn) any probability . Suppose fo has spaces, and fn a function from Xn into S for each n = 0, 1, separable range So and is measurable (for the Borel a -algebra on So). Then fn = fo if and only if there exist a probability space (S2, S, Q) and perfect , such measurable functions gn from (S2, S) to (Xn, An) for each n = 0, 1, fo o go almost uniformly that Q o gn 1 = Qn on An for each n and fn o gn as n -+ oo. Notes. Proposition 3.4.4 and the "if and only if " in Theorem 3.5.1 show that the hypothesis that gn be perfect can't just be dropped from the theorem.
Proof "If" follows from Proposition 3.3.1 and Theorem 3.4.3. "Only if" will be proved very much as in RAP, Theorem 11.7.2. Let S2 be the Cartesian product fl 0Xn x In where each In is a copy of [0, 1]. Here gn will be the natural projection of 0 onto Xn for each n. Let P := Qo o fo 1 on the Borel or -algebra of S, concentrated in the separable subset So. A set B C S will be called a continuity set (RAP, Section 11.1) for P if P(dB) = 0 where 8B is the boundary of B. Then,
3.5.2 Lemma For any e > 0 there are disjoint open continuity sets Uj, j = 1, , J, for some J < oo, where for each j, diam Uj := sup{d(x, y) :
x,yEUj)<e,andwith 1:;J= 1P(Uj)>1-e.
108
Uniform Central Limit Theorems: Donsker Classes
Proof Let {xjf°° 1 be dense in So. Let B(x, r) :_ {y E S: d(x, y) < r} for 0 < r < oo and x E So. Then B(xj, r) is a continuity set of P for all but at most countably many values of r. Choose rj with e/3 < rj < e/2 such that B(xj, rj) is a continuity set of P for each j. The continuity sets form an algebra (RAP, Proposition 11.1.4). Let
U j := B(xj, rj) \ U{y: d(xi, y) < r,}. i<j
Then Uj are disjoint open continuity sets of diameters < e with
1, so there isaJ
1
P(Uj) _
1P(Uj)> 1-e.
Now to continue the proof of Theorem 3.5.1, for each k = 1, 2, - -, by the last lemma take disjoint open continuity sets Ukj := U(k, j) of P for j = 1, 2, .. -, Jk := J(k) < oo, with diam(Ukj) < 1/k, P(Ukj) > 0, and J(k)
E P(Ukj) > 1-2 -k.
(3.5.3)
j=1
For any open set U in S with complement F, let d(x, F) := inf{d(x, y) y E F). For r = 1, 2, - -, let Fr := {x : d (x, F) > 1/r}. Then Fr is closed and Fr T U as r -* oo. There is a continuous hr on S with 0 < hr < 1, hr = 1 on Fr, and hr = 0 outside F2r: let hr(X) := min(l, max(0, 2rd(x, F) - 1)). For each j and k, let F(k, j) := S \ Ukj. Take r := r(k, j) large enough so that P(F(k, f)r) > (1 - 2-k)P(Ukj). Let hkj be the hr as defined above for such an r and Hkj the her. For n large enough, say for n > nk, we have
jhki(fn)dQn > (1-2-k)P(Ukj) and
f* Hkj(fn)dQn < (1+2-k)P(Ukj) for all j = 1, - - -, Jk. We may assume n1 < n2 < ... . For every n = 0, 1, - , let fkjn := (hkj o fn)* for Qn, so that by Theorem - -
3.2.1,
fhki(fn)dQn =
ffkJndQn,
0 < ,fkjn < hkj(fn),
and fkjn is An-measurable. For n > 1 let Bkjn :_ (.fkjn > 0) E A. Let Bkjo
1(Ukj) E Ao. For each k and n, the Bkjn C f-1
for j= 1,---,Jk,andHkj(fn)=Ion Bkjn, soforn>nk, (3.5.4)
(1-2-k)P(Ukj) < Qn(Bkjn) < (1+2-k)P(Ukj),
are disjoint
3.5 Almost surely convergent realizations
109
and Qo(Bk jo) = P(Ukj). Let Tn := X, x In. Let it, be the product law Q, x .X on Tn where A is Lebesgue measure on the Borel or-algebra B in In. For each
k> 1, Ckjn
:= Bkjn x [0, F(k, j, n)] C T,,
Dkjn
:= Bkjo x [0, G(k, j, n)] C To,
where F and G are defined so that
An(Ckjn) = Ito(Dkjn) = min(Qn(Bkjn), Qo(Bkjo))
Then for each k, j, and n > nk,wehave by(3.5.4),since 1/(1+2-k) > 1-2-k,
(3.5.5) 1-2 -k < min(F, G)(k, j, n) < max(F, G)(k, j, n) = 1. Let J(k) Ckon
7'n \ U Ckjn,
J(k)
DkOn = To \ U Dkjn.
j=1
j=1
For k = 0let Jo := J(0) := 0, Coon Tn, Doon := To, and no := 0. For each n = 1, 2, , let k(n) be the unique k such that nk < n < nk+1 Then for n > 1, Tn is the disjoint union of sets Wnj Ck(n)jn, j = 0, 1, (3.5.6)
, Jk(n). We also have
If j > 1 and (v, s) E Wn j then V E Bk(n) jn so fn (v, S) E Uk(n) j
Next, To is the disjoint union of sets Enj := Dk(n) jn. Then µn (Wnj) = Ito(Enj)
for each n and j, and if j > 1 or k(n) = 0, then Ao(En j) > 0. For x in To and each n, (3.5.7)
let j (n, x) be the j such that x E En j .
Let L := (x E To : so(Enj(n,x)) > 0 for all n). Then To \ L C IJi En(i)o for some (possibly empty or finite) sequence n (i) such that po(En(1)o) = 0 for all i. Thus µo(L) = 1. For X E L and any measurable set B C Tn, in other words B is in the product
or-algebra An 0 B, let j := j(n, x), recall that Itn(Wnj) = t o(Enj), and let (3.5.8)
Pnj(B) := An(B fl Wnj)/Ito(Enj),
Pnx
Pnj(n,x).
Then Pnx is a probability measure on An 0 B. Let px be the product measure 1 -100 Pnx on T := IIn° 1 T, (RAP, Theorem 8.2.2).
Uniform Central Limit Theorems: Donsker Classes
110
3.5.9 Lemma For any measurable set H C T (for the infinite product a algebra with A® ® 13 on each factor), x i-+ px(H) is measurable on (To, Ao ®13).
Proof Let H be the collection of all H for which the assertion holds. Given n, Pnx is one of finitely many laws, each obtained for x in a measurable subset
En j. Thus if Y, is the natural projection of T onto Tn and H = Y,- 1(B) for some B E A®®13 then H E H. If H= ITEM Ym(i)(Bi), where Bi E An(i) 0 13 and M is finite, we may assume the m (i) are distinct. Then I
px(H) = niEMpx(Yn(i)(Bi)), so H E R. Then, any finite, disjoint union of such intersections is in 7-l. Such unions form an algebra. If Hn E 7-1 and Hn T H or Hn ,. H, then H E 7-1. Since the smallest monotone class containing an algebra is a a-algebra (RAP, Theorem 4.4.2), the lemma follows.
Now returning to the proof of Theorem 3.5.1, S2 = To x T. For any set C C S2, measurable for the product a-algebra, and x E To, let C, :_ l y E T : (x, y) E C}, and Q(C) := f px (Cx) dµo(x). Here x r-+ px (Cx) is measurable
if C is a finite union of products Ai x Fi where Ai E Ao ® 13 and Fi is product measurable in T. Such a union equals a disjoint union (RAP, Proposition 3.2.2). Thus by monotone classes again, x i-+ px(Cx) is measurable on To for
any product-measurable set C C Q. Thus Q is defined. It is then clearly a countably additive probability measure.
Let p be the natural projection of T onto Xn. Recall that Pnx = Pnj for all x E En j, by (3.5.7) and (3.5.8). The marginal of Q on X,,, in other words Q o gn 1, is by (3.5.8) again J(k(n))
E lso(Ej)Pnj o p-1 = An o
P-1
= Qn
j=0
Thus Q has marginal Qn on Xn for each n, as desired. By (3.5.3), 00
J(k)
E Q0 X 0 \ U f 1(Ukj) < 1: 2-k < 00. k=1
j=1
k
l
So Qo-almost every y E X o belongs to U f0 1(Uk j) for all large enough k. Also if t E 10 and t < 1, then by (3.5.5), t < G(k, j, n) for all j > 1 as soon
3.6 Conditions equivalent to convergence in law
111
as 1 - 2-k > t and n > nk. Thus for µo-almost all (y, t), there is an in such that (y, t) E U (k(n)) En j for all n > m. If x := (y, t) E En j for j > 1, then y E Bk(n) jo, so fo(y) E Uk(n) j. Also, by (3.5.8), Pnx = Pn j is concentrated in Wnj. For (v, s) E Wnj, fn (V) E Uk(n) j by (3.5.6). Since diam(Ukj) < 1/k for
each j > 1, Q*(d(fn(gn), .Po(go)) > 1/k(n) for some n > m)
< µo({(y, t) E Eno for some n > m}) -+ 0 as in -* oo, so fn (gn) -* fo (go) almost uniformly. Lastly, let's show that the gn are perfect. Suppose Q(A) > 0 for some A.
Now Q(A) = f px(Ax) dµo(x). Firstletn > 1. Thenforsomex, px(Ax) > 0. If µo(Eno) = 0, we take x Eno. Now T = Tn x T(n) where T(n) :_ ff1<(0nT,. Then on T, px = Pnx x Qnx for a law Qnx = fImonPmx on T(n). Let A (x) := A. By the Tonelli-Fubini theorem, px (Ax) = ff 1A(x) (u, v) dPnx (u) dQnx (v) Thus for some v, f 1 A(x) (u, v) dPnx (u) > 0. Choose and fix such a v as well as
x. Now Pnx = Pn j for j = j (n, x) with µo(En j) > 0. Let u = (s, t), s E Xn, and t E In. Then since Pn j = Qn x A restricted to a set of positive measure and normalized,
0 < ff1A(X)(stv)dQfl(s)dt. Choose and fix a t with 0 < f IA(x)(s, t, v)dQn(s). Let C IS E Xn (s, t, v) E Ax}. Then Qn(C) > 0. Clearly C C gn[A], so gn is perfect for n > 1 by Theorem 3.4.1. To show go is perfect, we have µo = Qo x ,., and px (Ax) > 0 for x = (y, t)
in a set X with Ao(X) > 0. There is a t E Io such that Qo(C) > 0 where C := {y: (y, t) E X). Then C C go[A], so go is perfect, finishing the proof of Theorem 3.5.1.
3.6 Conditions equivalent to convergence in law Conditions equivalent to convergence of laws on separable metric spaces are given in the portmanteau theorem (RAP, Theorem 11.1.1) and metrization theorem (RAP, Theorem 11.3.3). Here, the conditions will be extended to general random elements for the theory being developed in this chapter. For any probability space (S2, A, P) and real-valued function f on S2 let
E*f := f * f dP, E* f := f* f dP. If (S, d) is a metric space and f is a
112
Uniform Central Limit Theorems: Donsker Classes
real-valued function on S, recall (RAP, Section 11.2) that the Lipschitz seminorm of f is defined by
IIflIL
Sup{If(x) - f(y)Ild(x, y) : x 0 y)
and f is called a Lipschitz function if II f 11L < oo. The bounded Lipschitz := sup., If(x)j. norm is defined by II f II BL II f II L + II f II where Iif II Then f is called a bounded Lipschitz function if II f II BL < oo, and 11 II BL is a norm on the space of all such functions.
The extended portmanteau theorem about to be proved is an adaptation of RAP, Theorem 11.1.1, and some further facts based on the last section (Theorem
3.5.1). The proof to be given includes relatively easy implications, some of which consist of putting in stars at appropriate places in the proofs in RAP.
3.6.1 Theorem Let (S, d) be any metric space. F o r n = 0, 1 , 2, , let (Xn, An, Q,) be a probability space and fn a function from Xn into S. SupQo o f0 1 on S. pose fo has separable range So and is measurable. Let P Then the following are equivalent: (a) fn = fo;
(a') lim supn,, E*G(fn) < EG(fo) for each bounded continuous realvalued G on S; (b) E*G (fn) --* EG (fo) as n -+ oo for every bounded Lipschitzfunction
GonS; (b') (a') holds for all bounded Lipschitz G on S;
(c) sup{IE*G(fn) - EG(fo)I: IIG1IBL < 1) - Oasn - oo; (d) for any closed F C S, P(F) > lim supn,oo Qn (fn E F); (e) for any open U C S, P(U) < liminfn,oo(Qn)*(fn E U);
(f) for any continuity set A of P in S, Q* (fn E A) - P(A) and (Qn)*(fn E A) -* P(A) as n -* oo; (g) there exist a probability space (S2, S, Q) and measurable functions gn from S2 into Xn and hn from S2 into S such that the gn are perfect,
Qogn1 = Qn and Qohn1 = Pforalln, andd(fn ogn,hn) --). 0 almost uniformly.
Moreover, (g) remains equivalent if any of the following changes are made in it: "almost uniformly" can be replaced by "in outer probability"; we can take hn = fo o yn for some measurable functions yn from S2 into X0, which can be taken to be perfect; and we can take yn to be all the same, yn = yl for all n.
3.6 Conditions equivalent to convergence in law
113
Proof Clearly (a) implies (a'). Conversely, by interchanging G and -G, (a') implies
liminfn*cE*G(fn) > liminfn,,,,E*G(fn) > EG(fo), and (a) follows, so (a) and (a') are equivalent.
Clearly (a) implies (b), which is equivalent to (b') just as (a) is to (a'). To show (b) implies (c), let T be the completion of S. Then all the fn take values in T. Each bounded Lipschitz function G on S extends uniquely to such a function on T, and the functions G o fn on Xn are exactly the same. So we can assume in this step that S and So are complete. Let E > 0. By Ulam's theorem (RAP, Theorem 7.1.4), take a compact K C So with P(K) = Qo(fo E K) > 1 - E. Recall that d (x, K) := inf {d (x, y) :
y E K) and KE := Ix: d(x, K) < E}. Let g(x) := max(O, 1-d(x, K)/e) for 1 + 1/E < oo. Clearly 1K < g < 1KE. Since E*g(fn) -). Eg(fo) as n -+ oo, it follows that x E S. Then g is a bounded Lipschitz function with II9IIBL for n large enough (3.6.2)
(Q,,). (f, E K5) > E*g(fn) > Eg(fo) - E > I - 2E.
Let B be the set of all G on S with II G II BL < 1. Then the functions in B are uniformly equicontinuous, so their restrictions to K are totally bounded for the supremum distance over K by the Arzela-Ascoli theorem (RAP, Theorem 2.4.7). Let G I, , G j for some finite J be functions in B such that for each
G E B, supXEK I(G - Gj)(x)I < E for some j = 1, , J. Next, for any G E B, choose such a j. Then (3.6.3)
I E*G(fn) - EG(fo)I < IE*G(fn) - E*Gj(fn)I + I E*(Gj(fn)) - E(Gj(fo))I + I E(Gj(fo) - G(fo))I,
a sum of three terms. For the last term, splitting the integral into two parts according as fo c K or not, the first part is bounded by E and the second by 2E since I G j - G I < 2 everywhere and Qo (fo K) < E. The middle term on the right side of (3.6.3) is bounded above by
maxj<j IE*Gj(fn) - EGj(fo)I, which is less than E for n large enough by (b). The first term on the right in (3.6.3) is a sum of two parts, one over a measurable subset An of Xn where f, E KE with Q, (A,) > 1- 2E by (3.6.2), and the other over the complement of A. Since G and G j E B, and I G - G j I < E on
K, we haveIG - GjI <3s on K6. It follows that I (Go fn)*-(Gjo fn)*I <3E
Uniform Central Limit Theorems: Donsker Classes
114
on An, so the first part is bounded above by 3e. The second part is bounded by 2(1 - Qn(An)) < 46. So for n large enough the left side of (3.6.3) is less than 116 uniformly for G E B, and (c) follows. Clearly (c) implies (b), so (b) and (c) are equivalent. Next, (b) implies (d) by taking bounded Lipschitz functions gk decreasing down to 1 F as k - oo, specifically the functions g in the proof of (b) implies (c) with F in place of K
and 6 = 1/k. (d) and (e) are equivalent by taking complements. (d) and (e) together easily imply (f). For any bounded continuous function G, all but countably many of the sets
f G < t) are continuity sets of P. It follows that G can be approximated uniformly within e by a simple function F_ ti 1 Ai where Ai are continuity sets {ti-1 < G < ti}. So (f) implies (a), and (a) through (f) are all equivalent. Theorem 3.5.1 says that (a) implies (g), in the strongest form where hn
h 1 - fo o yl and yi is perfect. The weakest form of (g), with convergence in outer probability and hn depending on n and not necessarily a composition of fo with any (perfect) function,
will be shown to imply (b'). Given 6 > 0, take n large enough so that
Q*{d(.fn o gn, hn) > 6) < 6. n So on a measurable set An with Q(An) > 1 - e, we have d(fn o gn, hn) < e, and thus for any G E B (in other words II G II BL < 1) we have
IG(fn(gn)) -G(hn)I < 61A
+2. IA'-
It follows that
E*G(fn(gn)) < EG(hn)+36 = EG(fo)+3e (since hn has the same distribution as fo) and
E*G(fn (gn)) = E(((G o fn) o gn)*) = E((G o fn)* o gn) by Theorem 3.2.1 and since gn is perfect, and where all the expectations are with respect to Q. The latter integral, by the image measure theorem (RAP, Theorem 4.1.11), equals E*(G(fn)) (for Qn). Letting e 4. 0, (b') follows, so all of the forms of (g) are equivalent to any of (a) through (f). Theorem 1.1.1, in a special case, proved a form of convergence which in that case is now easily seen to imply the conditions in Theorem 3.6.1: the one in (c), for example. It will be shown that convergence in law is also equivalent to convergence in some analogues of the Prokhorov and dual-bounded-Lipschitz metrics, which
3.6 Conditions equivalent to convergence in law
115
metrize convergence of laws on separable metric spaces as shown in RAP, Theorem 11.3.3. We will have analogues of metrics, rather than actual metrics, because of the asymmetry between the nonmeasurable random elements f, and the limiting measurable random variable fo.
Definitions. Let (X., Am , Qm) be probability spaces, m = 0, 1, and let (S, d) be a metric space. Let fm be functions from Xm into S, m = 0, 1, such that fo is measurable and has separable range. Let P := Qo o f0 1. Then let
P(.fi, fo) := sup{IE*G(.fl) - EG(fo)I :
IIGIIBL <- 11,
and for F ranging over nonempty closed subsets of S,
p(.fi, .fo) := inf{e > 0: SUPF[P(F) - (Qi)*(fi E FE)] < e}. 3.6.4 Theorem For any metric space (S, d), probability spaces (Xm, Am, Qm) and functions fm from Xm into S, where fo has separable range and is measurable, the following are equivalent: (i) .fm
fo;
(ii) $(fm, Jo)
0 as m
(iii) p(fm, fo) - 0 as m
oo; oo.
Proof (i) and (ii) are equivalent just as (a) and (c) are in Theorem 3.6.1. To show that (ii) implies (iii), we have:
For any fl and fo as in the statement of Theorem 3.6.4, p(Ji, .fo) < min(l, (20(ft,
3.6.5 Lemma
.fo))1/2).
Proof Let F be any closed set in S and P = Qo o f01. Given 0 < s < 1, let g(x) := max(0, 1 - d(x, F)/e) as before. Then 11811 BL < 1 + 1/c, and
(Q1). (f, E FE) > jg(Ji)dQi >
fg(Jo)dQo_(JiJo)(l+) > P(F) - s cases,
if (fi, fo) < r2/2. Clearly p(fl, fo) < 1 in all (2p(.fi, .fo))1/2 when the latter is < 1, the lemma follows.
so letting s
Now to continue the proof of Theorem 3.6.4, applying the lemma to fm in place of fl for each in shows that (ii) implies (iii). To show that (iii) implies , let F k := {x : d (x, y) < 1/k (i), let U be an open set in S. For k = 1 , 2,
116
Uniform Central Limit Theorems: Donsker Classes
implies y E U). Then Fk are closed sets and Fk T U as k -f oo. For n large enough, p(fn, fo) < 1/k, and then P(Fk) < (Qn),k(fn E F1Ik) + k < (Qn)*(fn E U) + k, SO
P(Fk) < liminfn->oo(Qn)*(fn E U) + k Then letting k ->. oo gives P(U) < lim infn oo(Qn). (fn E U). This is (e) of Theorem 3.6.1, so the proof of Theorem 3.6.4 is complete. Next is a version of Theorem 3.6.4 where we have two indices.
3.6.6 Theorem
Let (S, d) be a metric space and (S2, S, Q) a probability
space. Suppose that f o r each m, n = 1 , 2, , fmn is a function from Q into S, and fo is a measurable function from Q into S with separable range. Then the following are equivalent:
(i) fm,n = fo, that is, for every bounded continuous real function G on S,
I*G(fm,n)dQ
f G (.f0) dQ asm,n -+ oo;
(ii) f(fmn, fo) - O as m, n -> oo; (iii) p(fmn, fo) -+ 0 as m, n -+ oo. Proof For a double sequence amn of real numbers, let lim SUpm
n,oo amn =
infk SUpm>k,n>k amn,
lim infm, n-#oo amn = SUpk lnfm>k, n>k amn
Then the steps in the proof of Theorem 3.6.1 showing that (a) through (f) are equivalent extend directly to convergence as m -+ oo and n -+ oo if lim supra,,, is replaced by lim Supm,n,oo (not by lim supm,o lim Supra,,, or the iterated lim sup in the reverse order, which may be different), and likewise for lim inf. Thus, the proof of Theorem 3.6.4 also extends.
We have the following:
3.6.7 Continuous mapping theorem Under the conditions of Theorem 3.6.4, if (T, e) is another metric space, G is a continuous function from S into T, and fo, then G(fm) G(fo) .fm Proof This follows directly from the definition of convergence in law =.
3.7 Asymptotic equicontinuity and Donsker classes
117
We also have
3.6.8 Theorem Suppose fm, m > 0, are measurable random variables taking values in a separable metric space S, so that laws G(fm) exist on the Borel or -algebra of S. Then convergence fm
fo is equivalent to convergence
of the laws G(fm) -+ G(o) in the usual sense. Proof For any bounded continuous real-valued function G on S, the functions G(fm) are measurable, so upper integrals reduce to integrals, and the result follows from the definitions.
3.7 Asymptotic equicontinuity and Donsker classes Recall from Section 3.1 the definitions of the empirical measures P, empirical process v,,, pseudometric pp, and the Gaussian process Gp. Recall that a set .F C 'C2 (p) is called pregaussian if a Gp process restricted to F exists whose
sample functions f i-+ Gp (f) ((o) are (almost) all bounded and uniformly continuous for pp on F. Such a Gp process is called coherent if, in addition, its sample functions are prelinear on .F as in Lemma 2.5.3.
3.7.1 Proposition For any probability measure P and pregaussian set F C G2(P), the symmetric convex hull sco(.F) of.F is also pregaussian, and there exists a Gp process defined on the linear span of .F and constant functions which is 0 on the constant functions and coherent on sco(.F). Proof A Gp process is isonormal on the space L2 (P) for the semi-inner product
(f, g)o,p := P(fg) - PfPg, and Gp is 0 on constant functions. So Theorem 2.5.5 on isonormal processes applies and gives the result. For a signed measure v and measurable function f such that f f d v is defined,
letv(f) := f fdv. A class ,F of functions will be said to satisfy the asymptotic equicontinuity
condition for P and a pseudometric r on F, or F E AEC(P, r) for short, if for every e > 0 there is a 3 > 0 and an no large enough such that for n > no,
f,gE.F, t(f,g)<S}>e} < E. Then.F E AEC(P) will mean.F E AEC(P, pp).
Uniform Central Limit Theorems: Donsker Classes
118
3.7.2 Theorem Let .T' C G2(X, A, P). Then the following are equivalent: (I) F is a Donsker class for P, in other words .F is P-pregaussian and vn
Gp in £'(F);
(II) (a) F is totally bounded for pp, and (b) F satisfies the asymptotic equicontinuity condition for P, F E AEC(P); (III) there is a pseudometric r on .F such that .F is totally bounded for r and
.T' E AEC(P, t).
Proof If F is a Donsker class and e > 0, then since F is pregaussian, it is totally bounded for pp by Theorem 2.3.5, so (a) holds. Take 0 < 3 < s/3 such that for any coherent Gp process,
Pr {sup{IGp(f) - Gp(g)I: pp(f, g) < 8} > s/31 < s/2. By almost surely convergent realizations (Theorem 3.5.1), for n > no large enough we can assume Pr*{Ilvn -GpII.p > s/3} < 8/2. If IIvn -GpII,p < s/3 and I Gp (f) - Gp (g) I < s/3 then I vn (f) - vn (g) l < s. So the asymptotic equicontinuity holds with the 3 and no chosen, and (b) holds, so (I) implies (II).
(II) implies (III) directly, with r = pp.
To show (III) implies (I), suppose F is r-totally bounded and F E AEC(P, r). Let UC := UC(F) denote the set of all real-valued functions on F uniformly continuous for T. Then UC is a separable subspace of t°O(F) for II Il.p since F is totally bounded and UC equals, in effect, the space of continuous functions on the compact completion (RAP, Corollary 11.2.5). For any finite subset g of F, by the finite-dimensional central limit theorem (RAP, Theorem 9.5.6) we can let n oo in the asymptotic equicontinuity
condition and so replace v (f - g) by Gp (f) - Gp (g) for f, g E 9. Given s > 0, take a 8 := 8(s) > 0 and no := no(s) < oo from the definition of asymptotic equicontinuity condition. Then 8 and no don't depend on 9 C F. So we can let CJ increase up to a countable dense set 7-l C F. Gp has sample functions almost surely uniformly continuous on H.
If fo E C and fk E 7-l are such that r(fk, fo) -+ 0 then by applying the finite-dimensional central limit theorem to the finite set 9 = { fo, fi, , fk} for each k, applying the asymptotic equicontinuity condition and letting k -+ oo we see that Gp is almost surely uniformly continuous for r on the set { f )j>o.
So Gp(fk) -- Gp(fo) almost surely. Thus for each f E F, the almost sure limit of Gp(hk) as hk - f through 7-l, which exists by uniform continuity, equals Gp (f) a.s., so the almost sure limit defines a Gp process. This Gp has uniformly continuous sample functions for r on F. So by Theorem 2.8.6, since
3.7 Asymptotic equicontinuity and Donsker classes
119
Gp is isonormal for ( , -)o, p, it follows that .F is pregaussian. So Gp has a law µ3 defined on the Borel sets of the separable Banach space UC. Given e > 0, take S > 0 from the asymptotic equicontinuity condition and a finite set 9 c Y such that for each f E F there is a g E 9 such that r (f, g) < S. Then 1189 is the set of all real-valued functions on 9. Let µ2 be the law of Gp on 1R and let tµ23 be the law on 1[89 x UC where Gp on g in R9 is just the restriction of Gp on UC. So µ23 has marginals µ2 and µ3. Let 1t1,n be the law of v on g, so µ1,n is also defined on R9. Then by the finite-dimensional central limit theorem again, the laws µ1,n converge to µ2 on 1[89. So for the Prokhorov metric p, since it metrizes convergence of laws (RAP,
Theorem 11.3.3), p(µt,,, µ2) < e for n large enough. Taken > no also, then fix n. By Strassen's theorem (RAP, Corollary 11.6.4), there is a law A12 on 1[89 x R9 with marginals 1t1,n and µ2 such that µ1,2{(x, Y): Ix - yA > E) < E. By the Vorob'ev-Berkes-Philipp theorem (1.1.10), there is a Borel measure /'t123 on 1[89 x 1[89 x UC having marginals A12 and µ23 on the appropriate spaces.
The next step is to link up v with its restriction to the finite set 9. The Vorob'ev-Berkes-Philipp theorem may not apply here since v on F may not be in a Polish space, at least not one that seems apparent. (About nonmeasurability on nonseparable spaces see the remarks at the end of Section 1.1.) Here we can use instead:
3.7.3 Lemma Let S and T be Polish spaces and (Q, A, P) a probability space. Let Q be a law on S x T with marginal q on S. Let V be a random variable on Q with values in S and law G(V) = q. Suppose there is a real random variable U on S2 independent of V with continuous distribution function FU. Then there is a random variable W : S2 i-). T such that the joint law G(V, W)
of(V,W)isQ. Proof Two metric spaces X, Y are called Borel-isomorphic if there is a one-toone Borel measurable map of X onto Y with Borel measurable inverse. Every Polish space is Borel-isomorphic to some compact subset of [0, 11, either the whole interval, a finite set, or a convergent sequence and its limit (RAP, Theorem 13.1.1). Since the lemma involves only measurability and not topological properties of the Polish spaces, we can assume S = T = [0, 11. Here we need the fact that for any real-valued random variable X with continuous distribution function F, F(X) has a uniform distribution in [0, 1 ], which can be seen as fol-
lows. For -oo < t < oo, the probability that X < t equals F(t). Now X < t implies F(X) < F(t). On the other hand, the probability that F(X) < F(t) is the supremum of probabilities that X < y for y such that F(y) < F(t), and this supremum is at most F(t). So the probability that X < t equals the probability
Uniform Central Limit Theorems: Donsker Classes
120
that F(X) < F(t). Since F is continuous, for any s with 0 < s < 1 there is a t E R with F(t) = s, so the probability that F(X) < s equals F(t) = s, and F(X) is uniformly distributed in [0, 1] as claimed. So, taking FU (U), we can assume U is uniformly distributed in [0, 1]. By way of regular conditional probabilities (RAP, Section 10.2; Bauer, 1981) we can write Q = f Qx dq(x) where for each x, Qx is a probability measure on T, so that for any measurable set A in (the square) S x T, Q(A) = f f 1 A (X, y) dQx (y) d q (x) (RAP, Theorems 10.2.1 and 10.2.2). Let Fx be the distribution function of Qx and
0 < t < 1.
Fx 1(t) := inf{u: Fx(u) > t1,
Then for any real z and 0 < t < 1, Fx 1(t) < z if and only if Fx(z) > t. Now x i-- Fx (z) is measurable for any fixed Z. It follows that x i-+ Fx 1(t) is measurable for each t, 0 < t < 1. For each x, Fx 1 is left-continuous and nondecreasing in t. It follows that (x, t) i-+ Fx 1(t) is jointly measurable. Thus f o r W (co) := F7 ) (U (w)), co H W (co) is measurable. For each x we have the image measure A o (Fx 1)-1 = Qx (RAP, Proposition 9.1.2). So for any bounded Borel function g,
J
gdQ =
f1 f1
JJ 0
g(x, y) dQx(y) dq(x)
by Theorem 10.2.1 of RAP
0
f
= J0
g(x, Fx 1(y)) dy dq (x) by the image measure theorem
0
I fo g (x, Fx 1(y)) d(q x A)(x, y) 1
1
0
by the Tonelli-Fubini
theorem
= E(g(V, FV 1(U))) = Eg(V, W), since U is independent of V and G(V) = q and by the image measure theorem again. So G(V, W) = Q, proving Lemma 3.7.3. Now let (Q, S, Q) be a probability space on which all the empirical processes v, and an independent U are defined, specifically a countable product of copies
of the probability space (X, A, P) times one copy of [0, 1] with Lebesgue measure A. Then Lemma 3.7.3 applies to Q with S = RO and T = V x
UC, where V is v, restricted to 9, and Q = µ123 on S x T. On Q we then have processes v,, and Gp defined on F, which by construction and the asymptotic equicontinuity condition are within 3e of each other uniformly on F except with a probability at most 38 (as in the proof of Donsker's theorem in Section 1.1).
3.8 Unions of Donsker classes
121
Lets j, 0 through the sequence s = 1 / k, k = 1, 2, . Let the approximation just shown hold for n > nk on a probability space (Qk, Sk, Qk). We can assume nk is nondecreasing ink. Let Akn be the vn process defined on S2k and let
Gkn be the corresponding Gp process on Stk. Let no := 1 and let (Qo, So, Qo) be a probability space on which vn processes Aon and Gp processes Go, Go
are defined, where Go is independent of the Aon processes. Let An Akn and Gn := Gk, if and only if nk < n < nk+1 for k = 0, 1 , . Then for all n, An is a vn process and Gn is a Gp process. Also, II A, - Gn CIF 0 in outer probability, so by Theorem 3.6.1, vn z' Gp on .T7, and (III) implies (I), proving Theorem 3.7.2.
3.8 Unions of Donsker classes It will be shown in this section that the union of any two Donsker classes F and
g is a Donsker class. This is not surprising: one might think it was enough, given the asymptotic equicontinuity conditions for the separate classes, for a given s > 0, to take the larger of the two no's and the smaller of the two 8's. But it is not so easy as that. For example, F and G could both be finite sets, with distinct elements of F at distance, say, more than 0.2 apart for pp, and likewise for CG, but there may be some element of F very close to an element of G. So the equicontinuity condition on the union won't just follow from the conditions on the separate families. Given a probability measure P, F C G2(P), s > 0, 8 > 0, and a positive integer no, say that AE(F, no, s, 8) holds if for all n > no,
Pr* {sup{Ivn(f - g)I: f, g E F, pp(f, g) < 8} > s} < E. Then the asymptotic equicontinuity condition, as in the previous section, holds for .P and P if and only if for every s > 0 there is a 8 > 0 and an no such that AE(F, no, s, 8) holds. The asymptotic equicontinuity condition, together with total boundedness of F for pp, is equivalent to the Donsker property of F for P (Theorem 3.7.2).
3.8.1 Theorem (K. Alexander) Let (S2, A, P) be a probability space and let .T'1 and F2 be two Donsker classes for P. Then F := .T'1 U .T72 is also a Donsker class for P.
Proof (M. Arcones) Given s > 0, take 8i > 0 and ni < oo so that AE(Fi, ni, s/3, 8i) holds, i = 1, 2. F1 and F2, being Donsker classes, are pregaussian, and Gp is an isonormal process for ( , )o,p, so F is pregaussian by Corollary
Uniform Central Limit Theorems: Donsker Classes
122
2.5.9. So there is an a > 0 such that for a suitable version of GP,
Pr{sup{JGP(f-g)j: pp(f,g)s/3} < 8/3. Let S := min(31, 82, a/3). Take finite sets hi c Ti, i = 1, 2, such that for
each i and f E Ti there is an h := Ti f E Hi with pp (f, h) < 3. Since 7-l := Ni U N2 is finite, by the finite-dimensional central limit theorem (RAP, Theorem 9.5.6), vn restricted to N converges in law to Gp restricted to H. Let
F(R, a, s/3) be the set of all y E R H such that I y(f) - y(g) I > 8/3 for some f, g E N with pp(f, g) < a. Then F(N, a, e/3) is closed and has probability less than s/3 for the law of Gp on IRx. Thus by the portmanteau theorem (RAP, Theorem 11.1.1), there is an m such that
AE(N, m, s/3, a) holds.
(3.8.2)
Let no := max(n 1, n2, m). It will be shown that AE(.TF, no, e, 3) holds. By the
asymptotic equicontinuity conditions in each Ti and since no > max(n1, n2) and S < min(81, 32), there is a set of probability less than s/3 for each i = 1, 2 such that outside these sets, I v,, (f) - vn (g) I < 8/3 for any f, g in the same
.T'i with pp(f, g) < S. For pairs f, g with pp(f, g) < 8, with f E .T'1 and g E F2, we have pP(ri f, r2$) < a since pp(f, rl f) < 8, pp(g, r2g) < S, and 33 < a. Thus by (3.8.2), I vn (rl f) - vn (r2g) I < s/3 for all such f, g, outside of another set of probability at most e/3. Thus
vn(f) - vn(g)I
Ivn(f) - vn(nif)I + Ivn(rlf) - vn(r2g)I + (vn (r2g) - vn (g) i
< e/3 + s/3 + e/3 = s
for all f E .T'1 and g E F2 except on a set of probability at most 8/3 + s/3 + s/3 = e.
3.9 Sequences of sets and functions This section will show how the asymptotic equicontinuity condition in Theorem 3.7.2 can be applied to prove that some sequences of sets and functions are Donsker classes. In Chapters 6 and 7, other sufficient conditions for the Donsker property will be given that will apply to uncountable families of sets and functions. 3.9.1 Theorem Let (X, A, P) be a probability space and {C,n },n> 1 a sequence of measurable sets. If 00
(3.9.2)
r(P(Cm)(1 - P(Cm)))' < oo forsome r < oo, m=1
3.9 Sequences of sets and functions
123
then the sequence {Cm),,,>1 is a Donsker class for P. Conversely, if the sets Cm are independent for P, then the sequence is a Donsker class only if (3.9.2) holds.
Proof Suppose (3.9.2) holds. Then the positive integers can be decomposed into two subsequences, over one of which P(Cm) 0 and over the other P(Cm) -+ 1. It's enough to prove the Donsker property separately for each subsequence by Theorem 3.8.1. For any measurable set A with complement
-vn(A) and Gp(A`) - -Gp(A). The transformation of these processes into their negatives preserves convergence in law if it holds. So we can assume P(Cm) ,(, 0 as m -- oo, and then E. P(Cm)' < oo. Also, {Cm}m>1 is totally bounded for pp. By Theorem 3.8.1 we can assume pm := P(Cm) < 1/2 for all m. For any i and m such that P(CiACm) = 0, we will have almost surely for any n that P. (Ci) = Pn (Cm ). So we can assume that P(C1 ACm) > 0 for all i 0 M. For any m such that P(Cm) = 0 we will have Pn (Cm) = 0 almost surely for any n, and then vn (Cm) = 0, so we can assume P (Cm) > 0 for all m. Let 0 < s < 1. Suppose we can find M and N such that for all n > N, Ac,
(3.9.3)
Pr {supra>MIVn(Cm)I >s} < s.
Then for J large enough, pm < pM12 form > J. Let y := min{P(Ci ACj :
1 < i < j < J), a := min(y, pM)12. Then sup{Ivn(Ci) - vn(Cj)I: P(CiACj) < a) <_ suP{Ivn(C,) - vn(CC)I: i, j > M}
< 2sup{Ivn(C1)I: j > M} < 2s with probability at least 1- e, proving the asymptotic equicontinuity condition. So it will be enough to prove (3.9.3). For that, recalling the binomial prob-
abilities defined in Section 1.3, it will suffice to find M and N such that for
n > N, 00
(3.9.4)
57, E
< 8/2
m=M and 00
B(npm - sn1 /2, n, pm) < s/2.
(3.9.5) M=M
Uniform Central Limit Theorems: Donsker Classes
124
Let qm := 1 - pm. For (3.9.5), by the Chernoff-Okamoto inequality (1.3.10), B(npm - En 1/2, n1
p.) < exp (- e2/(2pmgm)).
For some K, 1 < K < oo, pm < Km -1/'' for all m. Choose M large enough so that exp
m' e2/(2K)) < E/2,
M=M
and so (3.9.5) holds for all n. The other side, (3.9.4), is harder. Bernstein's inequality 1.3.2 gives, if 2pn1/2 > e and 0 < p < 1/2, with q := 1 - p, that
E(np + En1/2, n, p) < exp ( - e2/(2pq + en-1/2)} < exp (- E2/(6pq)). Then 00
E {E(npm +En1/2, n, pm) : 2pmn1/2 >
(3.9.6)
m=M 00
{exp-E2/(6pm)): 2pmn1/2 > e} M=M 00
exp (- e2m1/rl (6K)) < e/4
< M=M
for all n if M is large enough. It remains to treat the sum, which will be called S2, of (3.9.4) restricted to values of m with 2pmn1/2 < E.
(3.9.7)
For p:= pm, inequality (1.3.11) implies
E(np + en 1/2, n, p) < (npl (np +
En1/2))np+En1/2eenl/2
Lety:= y(n,m,e) :=n1/2pm/e,so y> 0. Let f(x) - (1+x)log(1+x Then
- (np + en1/2) log (1 + e/(pn1/2)) = En1/2 (1 - f(y)). Forx > 0, f(x) < 0. By (3.9.7), y < 1/2, so f(y) > f(1/2) > 3/2. Thus En1/2
1 < 2f(y)/3, En1/2 (1 - f(y)) < -En 1/2 f (y) /3, and 00
{exp(-(En1/2+npm) [log (1+E/(n1/2pm)}]/3): 2pmn112<E1
S2 m=1 00
JJ ((
M=1
{(pmnl/2/e)En1/2l3:
2pmn1/2 < E}
3.9 Sequences of sets and functions
since 1/y < (1 +
y)l+y, so (1 +
125
y)-(l+y) < y. Now since p,, < Km-1I' we
have S2 < S3 + S4 where 00
._
S3
i{
2Km-1/rfn- <
E}
m=1 E,vIn_13 1` m
K
e/nl(3r)
m>G
where G :_ (2K,1_n_/s)r > 2. Then for any n1 > (3r/s)2 and n > n
S3 <
(K,,,fn-/E) 8vfn-13
x-e,Jn_1(3r)dx
fG-1
< (K,//s) ,/3(s ,/
(3r)-1 - 1`-1(G
-
For K, E and r fixed, and n
oo, the logarithm of the latter expression is asymptotic to -En 1/2 (log 2)/3 -oo, so S3 -+ 0. Thus S3 < E/8 for n > n2 for some n2. Finally, define S4 by 00
E
{(Pm'In-/e)r,1rn_l3:
E<
2Km-1/rfn_}
m=1
<
(2K/i/sy2-E,`l3
-0
as n - o0, so S4 < E/8 forn > n3 for some n3. Thus forn > max(n 1, n2, n3), S2 < e/4. This and (3.9.6) give (3.9.4). So (3.9.2) implies that {Cm}m>1 is a Donsker class. For the converse, if the measurable sets {Cm }m>1 are independent for P and form a Donsker class for P, it will be shown that (3.9.2) holds. Note that for each n, P (Cm) are independent random variables for in = 1, 2, . First suppose
lim supm,,,,, pm =: p < 1 and for all n, EM' 1 pm = +oo. Then for each n, Pr{ P (Cm) = 1 for infinitely many in } = 1 by the Borel-Cantelli lemma. Now
Pn(Cm) = 1 implies vn(Cm) = n1/2(1 - pm) > n1/2(1 - p) /2 form large. From Theorem 3.7.2, { 1 C. : m > 1) must be totally bounded for pp and satisfy
the asymptotic equicontinuity condition. It follows that pm -* 0 as m - oo, and by the asymptotic equicontinuity condition, we must have En° 1 pm < 00 for some n. A symmetrical argument applies if lim infra + pm > 0. We can write {Cm )m> l as a union of two subsequences, one for which
P(C,) < 1/2 and another for which P(Cm) > 1/2, both Donsker classes. Thus by the argument just given, for some n < oo, the first subsequence sat-
isfies E. P(Cm)" < oo and the second, F_m(1 - P(Cm))" < oo. So for the original sequence, (3.9.2) holds.
126
Uniform Central Limit Theorems: Donsker Classes
Next, let's consider sequences of functions. For a probability space (A, A, P) and f E £2(A, A, P) let 0 ,2( f := f f 2 dP - (f f dP) 2 (the variance of f). Here is a sufficient condition for the Donsker property of a sequence { fm } which is easy to prove, yet turns out to be optimal of its kind:
3.9.8 Theorem If { fm}m>1 C G2(P) and Fn° 1 ci (fm) < oo, then {fm }m> 1 is a Donsker class for P.
Proof Since v, and Gp are the same on fm - Efm as on fm a.s. for all m, we can assume Efm = 0 for all m. Then fm - 0 in Go, so the sequence { fm} is totally bounded for pp. For any 0 < s < 1, n > 1 and m > 1, by Chebyshev's inequality,
Pr(Ivn(f )I > s/2) < 4 E o (f)/s2 < s j>m
j>m
form > mo for some mo < oo. We have a.s. for all n, vn (f) = 0 for all j such
that a (f) = 0 and vn (f) = v (fk) for all j and k with or p (f - fk) = 0. Let a be the infimum of o (f - f k ) over all j and k such that o (fj - fk) > 0, j < me, and o (f) > 0. Then a > 0 since in some pp neighborhood of fj there are only finitely many fk. Let 8 := min(a, 1). Then the probability that I vn (f) - vn (fk) I > s f o r some j, k with orp2 (f - fk) < 8 is less than s, implying the asymptotic equicontinuity condition and so finishing the proof by Theorem 3.7.2. The following shows that Theorem 3.9.8, although it does not imply the first half of Theorem 3.9.1, is sharp in one sense:
3.9.9 Proposition Let A := [0, 1] and P := U[0, 1] := Lebesgue measure on A. Let am > 0 satisfy Fm 1 am = +oo. Then there is a sequence { fm I C G2(A, A, P) with c,' (f.) < am for all m where { fm } is not a Donsker class. . 0. There exist cm J. 0 such that >m am cm = +oo (see problem 12). In A let Cm be independent sets with P(Cm) = am cm for
Proof We can assume am
1/2
each m (see problem 13). Let fm := cm I Cm. Then oP (fm) < f f,2 dP = am. For each n, almost surely Pn (Cm) > 1/n for infinitely many m. Then vn(Cm) > n-1/2/2 for infinitely many m and supm vn(fm) = +oo a.s., so the asymptotic equicontinuity condition fails and { fm } is not a Donsker class for P.
Problems
127
Problems 1. Let (0, A, P) be a probability space, let (S, d) be a (possibly nonseparable) metric space, and let xn, n = 0, 1, 2, , be points of S. Let fn ((o) = Xn
for all co. Show that fn = f0 if and only if xn - X. 2. In a general (possibly nonseparable) metric space show that if X0 - p E S is a constant random variable then random elements Xn = X0 if and only X0 in outer probability. if X,
3. Let (T, d) be any metric space and S C T a separable subspace. Let Xn, n > 0, be S-valued measurable random variables on some probability space such that Xn -) X0 in law as n --- oc, in S. Show that Xn = X0 as T-valued random elements. 4. Show that C := J(-oo, t] : t E R} is a Donsker class for any law P on R. Hint: Use Section 1.1.
5. Let Ak be independent sets in a probability space (S2, A, P) such that Y-k[P(Ak)(1 - P(Ak))]" = +oo for all n = 1, 2, - -. Show that {Ak}k>1 is not a Glivenko-Cantelli class, that is, SUpk I (Pn - P) (Ak) I doesn't con-
verge to 0 in probability as n - oo. Hint: See the last part of the proof of Theorem 3.9.1.
6. Let (A, A, P) be a probability space and let F C L2 (A, A, P) be a Donsker class for P. (a) Show that the convex hull of F, namely k
co(F) := j E ) , j : f E .P, j = 1, ... , k, Aj > 0, j=1 k
YAj=1, j=1
is a Donsker class. Hint: Use Theorem 2.5.5 to get that co(F) is pregaussian and Gp can be taken to be prelinear on co(F). Then use almost surely convergent realizations (3.5.1). (b) For any fixed k < oo, show that f : f E F for j = 1, , k} is also a Donsker class. Hints: Use induction and Theorem 3.8.1 on unions. (2f : f E F} is Donsker. Thus take k = 2. It is easy to show that 2F Then apply part (a). 7. Let c > 0. For Lebesgue measure A on [0, 1], the Poisson process with intensity measure cl is defined by first choosing n at random having a
Poisson distribution with parameter c, namely P(n = k) = e-`ck/k! for , then setting Yc := 8x, where Xj are i.i.d. with law). on k = 0, 1, [0, 1]. In the Banach space of bounded functions on [0, 1] with supremum
Uniform Central Limit Theorems: Donsker Classes
128
norm, prove that as c
oo (along any sequence) the random functions
t H (Yc - c? )c-1/2[0, t], 0 < t < 1, converge in law to the Brownian motion process xt, 0 < t < 1. (Recall that xt = L(llo,tl).) Hints: For c = ck -+ oo let n = nk be Poisson (ck). For F(t) - t, 0 < t < 1, write Yc(t) := Yc([0, t]) = n F, (t), so c-1/2(Yc(t)
- Ct)
_ (n/c)1/2[n1"2(Fn - F)(t)] + c-112(n - c)t.
By Donsker's theorem take Brownian bridges y(n) such that n 1/2(Fn - F)
is close to y(n) for n large. Also, c-1/2(n - c) is close in law by the central limit theorem and so in probability (Strassen's theorem) to some random N(0, 1) variable Zc. Show that one can take n((o) independent y(n('0)) of X1, X2, , then y( (w) is a Brownian bridge; apply the t w) := Vorob'ev-Berkes-Philipp theorem to take Zc independent of yt, and then yt + Zc t is Brownian. 8. Let P be a law on a separable, infinite-dimensional Hilbert space H such that f IIx X12 dP(x) < oo and with mean 0, so that f (x, h) dP(x) = 0 for all h E H. Let X1, X2, be i.i.d. in H with law P and Sn := X1 + + Xn.
(a) Show that the central limit theorem holds in H, that is, Sn/n1/2 converges in law to some normal measure on H. Hint: Prove, using variances, that the laws of Sn/n1/2 are uniformly tight. (b) Show that the class of functions x r* (x, h) for h E H with 1Ih 11 < 1 (the unit ball of the dual space of H) is a Donsker class of functions on H
for P. Hints: For part (a) let {en ] be an orthonormal basis so that for any x E H,
x = En xnen with lix 112 = En xn. Thus En Exn is finite. Show that for Exn/cn is still finite. For any K let some cn 0 slowly enough, CK be the set of x such that En (xn /cn )2 < K2 (an infinite-dimensional ellipsoid). Show that each CK is compact and that the laws of Sn/n1/2 are uniformly tight by way of the sets CK. Thus subsequences of these laws converge. Show that they all converge to the same Gaussian limit law, since by the Stone-Weierstrass theorem, functions depending on only finitely many xj are dense in the continuous functions on each CK. , X,n, Y1, 9. The two-sample empirical process. Let X1, , Yn be i.i.d. with the uniform distribution U[0, 1] on [0, 1] (Lebesgue measure restricted to [0, 1]). Let F be the empirical distribution function based , X,,,, and Gn likewise based on Y1, , Yn. Show that in the on X1, space of all bounded functions on [0, 1] with supremum norm, mn
(m+n)
1/2
(Fm
- Gn)
y
Problems
129
as m, n -* oo where t i-± yt, 0 < t < 1 is a Brownian bridge process. Hints: As in Donsker's theorem (1.1.1), form, n large, m1I2(F,, - F) is close to a Brownian bridge Y(m), and n 1/2 (Gn - F) is close to an independent Brownian bridge Z (n ). It follows that [(m n) / (m +n)] 1/2 (Fm - Gn) is
close to (n/(m +n))1/2Y(m) - (m/(m +n))1/2Z(n), which is a Brownian bridge.
10. Let fn (x) = cos(27rnx) for0 < x < I with law U[0, 1] on [0, 1]. For real c let Fc be the sequence of functions n-' fn for all n = 1, 2, . For what values of c is Fc pregaussian? A Donsker class? Hints: If c < 0 show easily that the class is not pregaussian and so not Donsker. If c > 0 then it is pregaussian, by metric entropy. If c > 1/2, it is Donsker by 3.9.8. Show that it is Donsker for 0 < c < 1 /2 by the Bernstein inequality and the asymptotic equicontinuity condition. 11. In R, for any law P on IR, show that for any fixed k < oo, k
U (aj, bj]: aj < bj for all j j=1
is a Donsker class, that is, .F := {lc : C E C} is a Donsker class. Hint: Apply Donsker's theorem (1.1.1) and take differences (and sums). For k = 2 reduce to the case of disjoint intervals and apply problem 6. Do induction to get general k.
12. Show that as stated in the proof of Proposition 3.9.9, for any am > 0 with E. an = +oo there are cm 1 0 with >m cmam = +oo. Hint: Take a sequence mk such that Flan : mk < m < mk+1} > k for each k = 1, 2, . Let cm have the same value for Mk < m < mk+1 13. Show that as also stated in the proof of Proposition 3.9.9, in [0, 1] for P = U[0, 1] there exist independent sets Cm with any given probabilities. Hint: Use binary expansions. By decomposing the set of positive integers into a countable union of countably infinite sets, show that ([0, 1], P) is isomorphic as a probability space to a countable Cartesian product of copies of itself. 14. Suppose that {Cm)m>1 are independent for P, 00
P(Cm)(1 - P(Cm)) _ +00, m=1
and cm
oo. Show that (cm I cm )m> 1 is not a Donsker class.
130
Uniform Central Limit Theorems: Donsker Classes
Notes
Notes to Section 3.1.
For any metric space (S, d), let Bb (S, d) be the o-
algebra generated by all balls B(x, r) := {y: d(x, y) < r}, x E S, r > 0. Then Bb (S, d) is always included in the Borel or -algebra 13(S, d) generated by all the open sets, with 13b(S, d)= 13(S, d) if (S, d) is separable. Suppose Y, are functions from a probability space (S2, P) into S, measurable
for Bb(S, d). Then each Y has a law it, = P o Yn 1 on Bb(S, d). Dudley (1966, 1967) defined convergence in law of Y to Yo to mean that f * Hdµ -k f Hd µo for every bounded continuous real-valued function Hon S. HoffmannJorgensen (1984) gave the newer definition adopted generally and here, where the upper integrals and integral are taken over n, not S, so that the laws µ are not necessarily defined on any particular or -algebra in S. Hoffmann-Jorgensen's monograph was published in 1991. Andersen (1985a,b), Andersen and Dobric (1987, 1988), and Dudley (1985) developed further the theory based on Hoffmann-Jorgensen's definition. Notes to Section 3.2. Blumberg (1935) defined the measurable cover function f *, see also Goffman and Zink (1960). (Thanks to Rae M. Shortt for pointing out Blumberg's paper.) Later, Eames and May (1967) also defined f *. Lemmas 3.2.2 through 3.2.6 are more or less as in Dudley and Philipp (1982, Section 2), except that Lemma 3.2.4(c) is new here. Theorem 3.2.1 and its proof are as in Vulikh (1967, pp. 78-79) for Lebesgue measure on an interval (the proof needs no change). Luxemburg and Zaanen (1983, Lemma 94.4 p. 222) also prove existence of essential suprema and infima of families of measurable (extended) real functions.
Note to Section 3.3. This section is based on parts of Dudley (1985). Notes to Section 3.4. Perfect probability spaces were apparently first defined by Gnedenko and Kolmogorov (1949, Section 3), and their theory was carried on among others by Ryll-Nardzewski (1955), Sazonov (1962), and Pachl (1979).
Perfect functions are defined and treated in Hoffmann-Jorgensen (1984, 1985) and Andersen (1985a,b); see also Dudley (1985).
Notes to Section 3.5. The existence of almost surely convergent random variables with a given converging sequence of laws was first proved by Skorokhod (1956) for complete separable metric spaces, then by Dudley (1968) for any separable metric space, with a re-exposition in RAP, Section 11.7, and by Wichura (1970) for laws on the a-algebra generated by balls in an arbitrary metric space
Notes
131
as mentioned in the notes to Section 3.1. The current version was given in Dudley (1985).
Notes to Section 3.6. Hoffmann-Jorgensen (1984), who defined convergence in law in the sense adopted in this chapter, also developed the theory of it as in this section, and partly in a more general form (with nets instead of sequences, and other classes of functions in place of the bounded Lipschitz functions). Andersen and Dobric (1987, Remark 2.13) pointed out that the portmanteau theorem (as in Topsoe, 1970, Theorem 8.1) "can be extended to the nonmeasurable case. The proof of this extension is the same as the ordinary proof." Much the same might be said of other equivalences in this section. Dudley (1990, Theorem A) gave a form of the portmanteau theorem and (Theorem B) of the metrization theorem (3.6.4).
But not all facts or proofs from the separable case extend so easily: for example, in the separable case, there is an inequality for the two metrics, 0 < 2p, in the opposite direction to Lemma 3.6.5, which follows from Strassen's theorem on nearby variables with nearby laws (RAP, Corollary 11.6.5), but Strassen's theorem seems not to extend well to the nonmeasurable case (Dudley, 1994).
Notes to Section 3.7. An early form of the asymptotic equicontinuity condition appeared in Dudley (1966, Proposition 2) and a later form in Dudley (1978).
The equivalence with a different pseudometric r in Theorem 3.7.2 is due to Gine and Zinn (1986, p. 58). Lemma 3.7.3 is essentially contained in the proof of Skorokhod (1976, Theorem 1), as Erich Berger kindly pointed out. See also Erlov (1975). Notes to Section 3.8. Alexander (1987, Corollary 2.7) stated Theorem 3.8.1 but didn't publish a proof of it, although he had written out an unpublished proof several years earlier. He says that the result is "an extension of a slightly weaker result of Dudley (1981)," where F2 is finite, but this author himself doesn't think his 1981 result was only "slightly weaker"! The proof presented was suggested by Miguel Arcones in Berkeley during the fall of 1991, but I take responsibility for any possible errors in it. Apparently van der Vaart (1996, Theorem A.3) first published a proof.
Notes to Section 3.9. Theorem 3.9.1 first appeared in Dudley (1978, Section 2), Theorem 3.9.8 and Proposition 3.9.10 in Dudley (1981), and Proposition 3.9.9 in Dudley (1984).
132
Uniform Central Limit Theorems: Donsker Classes
References Alexander, K. S. (1987). The central limit theorem for empirical processes on Vapnik-Cervonenkis classes. Ann. Probab. 15, 178-203. Andersen, N. T. (1985a). The central limit theorem for non-separable valued functions. Z. Wahrscheinlichkeitstheorie verve. Gebiete 70, 445-455. Andersen, N. T. (1985b). The calculus of non-measurable functions and sets. Various Publication Series no. 36, Matematisk Institut, Aarhus Universitet. Andersen, N. T., and Dobric, V. (1987). The central limit theorem for stochastic processes. Ann. Probab. 15, 164-177. Andersen, N. T., and Dobric, V. (1988). The central limit theorem for stochastic processes II. J. Theoret. Probab. 1, 287-303. Bauer, H. (1981). Probability Theory and Elements of Measure Theory, 2d ed. Academic Press, London. Blumberg, Henry (1935). The measurable boundaries of an arbitrary function. Acta Math. (Uppsala) 65, 263-282. Cohn, D. L. (1980). Measure Theory. Birkhauser, Boston.
Dudley, R. M. (1966). Weak convergence of probabilities on nonseparable metric spaces and empirical measures on Euclidean spaces. Illinois J. Math. 10, 109-126. Dudley, R. M. (1967). Measures on non-separable metric spaces. Illinois J. Math. 11, 449-453. Dudley, R. M. (1968). Distances of probability measures and random variables. Ann. Math. Statist. 39, 1563-1572.
Dudley, R. M. (1978). Central limit theorems for empirical measures. Ann. Probab. 6, 899-929; Correction 7 (1979) 909-911. Dudley, R. M. (1981). Donsker classes of functions. In Statistics and Related Topics (Proc. Symp. Ottawa, 1980), North-Holland, New York, 341-352. Dudley, R. M. (1984). A course on empirical processes. Ecole d'ete de probabilites de St.-Flour, 1982. Lecture Notes in Math. (Springer) 1097, 1-142. Dudley, R. M. (1985). An extended Wichura theorem, definitions of Donsker class, and weighted empirical distributions. In Probability in Banach Spaces V (Proc. Conf. Medford, 1984), Lecture Notes in Math. (Springer) 1153, 141-178. Dudley, R. M. (1990). Nonlinear functionals of empirical measures and the bootstrap. In Probability in Banach Spaces VII (Proc. Conf. Oberwolfach, 1988), Progress in Probability 21, Birkhauser, Boston, 63-82. Dudley, R. M. (1994). Metric marginal problems for set-valued or non-measurable variables. Probab. Theory Related Fields 100, 175-189.
References
133
Dudley, R. M., and Philipp, Walter (1983). Invariance principles for sums of Banach space valued random elements and empirical processes. Z. Wahrscheinlichkeitsth. verw. Gebiete 62, 509-552. Eames, W., and May, L. E. (1967). Measurable cover functions. Canad. Math. Bull. 10, 519-523. Erlov, M. P. (1975). The Choquet theorem and stochastic equations. Analysis Math. 1, 259-271. Gine, E., and Zinn, J. (1986). Lectures on the central limit theorem for empirical processes. In Probability and Banach Spaces (Proc. Conf. Zaragoza, 1985), Lecture Notes in Math. (Springer) 1221, 50-113. Gnedenko, B. V., and Kolmogorov, A. N. (1949). Limit Distributions for Sums of Independent Random Variables. Moscow. Transl. and ed. by K. L. Chung, Addison-Wesley, Reading, MA, 1954; rev. ed. 1968. Goffman, C., and Zink, R. E. (1960). Concerning the measurable boundaries of a real function. Fund. Math. 48, 105-111. Hoffmann-Jt rgensen, Jorgen (1984). Stochastic processes on Polish spaces. Published (1991): Various Publication Series no. 39, Matematisk Institut, Aarhus Universitet. Hoffmann-Jorgensen, Jorgen (1985). The law of large numbers for non-measurable and non-separable random elements. Asterisque 131, 299-356. Luxemburg, W. A. J., and Zaanen, A. C. (1983). Riesz Spaces, vol. 2. NorthHolland, Amsterdam. Pachl, Jan K. (1979). Two classes of measures. Colloq. Math. 42, 331-340. Ryll-Nardzewski, C. (1953). On quasi-compact measures. Fund. Math. 40, 125-130. Sazonov, V. V. (1962). On perfect measures (in Russian). Izv. Akad. Nauk SSSR 26, 391-414. Skorokhod, Anatolii Vladimirovich (1956). Limit theorems for stochastic processes. Theor. Probab. Appl. 1, 261-290. Skorokhod, A. V. (1976). On a representation of random variables. Theor. Probab. Appl. 21, 628-632 (English), 645-648 (Russian). Topsoe, Flemming (1970). Topology and Measure. Lecture Notes in Math. (Springer) 133. van der Vaart, Aad (1996). New Donsker classes. Ann. Probab. 24, 21282140.
Vulikh, B. Z. (1961). Introduction to the Theory of Partially Ordered Spaces (transl. by L. F. Boron, 1967). Wolters-Noordhoff, Groningen. Wichura, Michael J. (1970). On the construction of almost uniformly convergent random variables with given weakly convergent image laws. Ann. Math. Statist. 41, 284-291.
4
Vapnik-Cervonenkis Combinatorics
This chapter will treat some classes of sets satisfying a combinatorial condition. In Chapter 6, it will be shown that under a mild measurability condition to be treated in Chapter 5, these classes have the Donsker property, for all probability measures P on the sample space, and satisfy a law of large numbers (GlivenkoCantelli property) uniformly in P. Moreover, for either of these limit-theorem properties of a class of sets (without assuming any measurability), the VapnikCervonenkis property is necessary (Section 6.4). The present chapter will be self-contained, not depending on anything earlier in this book, except in some examples.
4.1 Vapnik-Cervonenkis classes Let X be any set and C a collection of subsets of X. For A C X let CA C n A := A nC := (Cf1A : C E C). Letcard(A) :_ I A I denotethecardinality (number of elements) of A and 2A :_ [B: B C A). Let AC(A) :_ ICAI. If A n C = 2A, then C is said to shatter A. If A is finite, then C shatters A if and only if AC (A) = 21 A1.
Let mc(n) := max[0C(F) : F C X , IF] = n} for n = 0, 1, IXI < n let mc(n) := mc(IXI). Then mc(n) < 2" for all n. Let V(C)
:
inf in: me (n) < 2")
if this is finite,
+00
if mc(n) = 2" for all n,
, or if
{I
sup {n: mo(n)=2"}, S(C)
:=
if C is empty.
1
Then S(C) - V (C) - 1, and S(C) is the largest cardinality of a set shattered by C, or +oo if arbitrarily large finite sets are shattered. So, V (C) is the smallest n 134
4.1 Vapnik-Cervonenkis classes
135
such that no set of cardinality n is shattered by C. If V (C) < oo, or equivalently if S(C) < oo, C will be called a Vapnik-Cervonenkis class or VC class. If X is finite, with n elements, then clearly 2X is a VC class, with S(2x) = n. Let NC
(N
\j/
N!/(j!(N - j)!),
j = 0, 1, ... N,
0,
j>N.
Then NC
4.1.1 Proposition NC
- -
, and
N = 1,2,.... Proof /For each j = 1, 2, - -, N, we have by the classical Pascal's triangle, I
Nl
(Ni 11+IN-1
I,
(N 0
I = INO 11 = 1.
Summing /over j, the conclusion follows. If N < k, we\ get 2N/ 2N-1
= 2N-1 +
For a non-VC class C we have mc(n) = 2' for all n. For a VC class, the next fact, which is fundamental in the Vapnik-Cervonenkis theory, will imply that mc(n) grows only as a polynomial rather than exponentially in n.
4.1.2 Theorem (Sauer's lemma) If mc(n) > nC
Proof The proof is by induction on k and n. For k = 1, nC
Fix k := K + 1. For n < k, as noted, it holds vacuously. For n = k, the hypothesis mc(n) > C
Vapnik-Cervonenkis Combinatorics
136
AC(HN) > NC
AC(HN) < NC
(4.1.3)
Let Cn := Hn n C :_ {A fl Hn : A E C}. Call a set E C HN full if both E and E U {xn } belong to Cn . Let f be the number of full sets. Then the map A i-+ A fl HN takes C n H onto C n HN and is two-to-one onto full sets and one-to-one onto non-full sets in C n HN. Thus
OC(H,,) = Ac(HN) + .f
(4.1.4)
Let F be the collection of all full sets. Suppose f = 0-F(HN) > NC
In the remaining case, f < NC
AC(H,,) < NC
Proof The inequality clearly holds for k = 0, so assume k > 1. By the binomial theorem, nk-1 (k + n) < (n + 1)k, so (4.1.6)
nk-1/(k
- 1)! +nk/k! < (n + 1)k/k!.
The proof will be done by induction on n and k. For k = 1 the inequality is n + 1 < 1.5n, which holds for all n > 2. For n = k + 2, the desired inequality is 2n - n - 1 < 1.5nii-2/(n - 2)! = 1.5(n -
1)nn-1/n!.
This can be checked directly for n = 3, 4, 5, and 6. Stirling's formula with an error bound (Theorem 1.3.13) gives n! < (n/e)n (2nn)1/2e1/(12n)
4.1 Vapnik-Cervonenkis classes
137
So it will be enough to prove
2n (n/e)n (2irn)1/2e11(12n) < 1.5(n -
1)nn-1
n>7,
which follows from (e/2)" > 2n1/2, n > 7; for f(x) := (e/2)x and g(x) :_ 2x1/2 it is straightforward to check that f (7) > g(7), f'(7) > g'(7), f" > 0, and g" < 0, so f (x) > g(x) for all x > 7. Now suppose the proposition has been proved for n = k + i, i = 2, , j, and for n = k + J, J := j + 1, for k = 1, , K, as we have done for j = 2 and for K = 1. We need to prove (4.1.5) for n = k + J and k = K + 1. We
have k+j = K + J and nC
< 1.5(k + j)k/k! + 1.5(K + J)K/K!
< 1.5nk/k!
by Proposition 4.1.1
by induction hypotheses by (4.1.6),
completing the proof.
Combining Theorem 4.1.2 and Proposition 4.1.5 gives mc(n) < 1.5nk/k! for n > k + 2 where k := S(C). To see that Theorem 4.1.2 is sharp, let X be an infinite set and C the collection of all subsets of X with cardinality k. Then S(C) = k and the inequality in the second sentence of the theorem becomes an equality for all n.
Let dens(C) be the infimum of all r > 0 such that for some K < oo, m c (n) < Kn' for all n > 1. Then we have
4.1.7 Corollary For any set X and C C 2X, dens(C) < S(C). Conversely if dens(C) < oc then S(C) < oo. Proof By Theorem 4.1.2 and Proposition 4.1.5, there is a K such that m c (n) <
Kns(c) for all n > S(C) + 2. The same holds for all n > 1, possibly with a larger K, so dens(C) < S(C). Conversely if dens(C) < oo then since mc(n) < Kn' < 2n for n large we have S(C) < oo. Note that S(C) can be determined by one large shattered set while dens(C) has to do with the behavior of C on arbitrarily large finite sets. For example if X is a set with card(X) = n and C = 2X then S(C) = n while dens(C) = 0.
For any set X, it is immediate that if C C D C 2X then S(C) < S(D) and dens(C) < dens(D). The following is straightforward since for any set X, the
138
Vapnik-Cervonenkis Combinatorics
map A r+ X \ A is one-to-one from 2X onto itself, and for any A, B, C C
X, Af1B#CflBifandonlyif(X\A)f1B#(X\C)f1B: 4.1.8 Proposition If X is any set, C C 2X and D := (X \ A : A E C) then for all B C X, AC(B) = AD(B), so m'(n) = mD(n) for all n, S(D) = S(C) and dens(D) = dens(C).
4.2 Generating Vapnik-Cervonenkis classes Let's begin with some examples of non-VC classes for which some limit theorems for empirical measures will fail. First, let X = [0, 1] and let C be the class of all finite subsets of X. Let P be the uniform (Lebesgue) law on [0, 1]. Clearly, S(C) = +oo, and C is not a VC
class. Also, for any possible value of Pn, we will have P,(A) = 1 for some A = {X1, , Xn} E C while P(A) = 0. Thus SUPAEC(Pn - P)(A) = 1 for all n, so C is not a Glivenko-Cantelli class for P; in other words, IIPn - PIIC
SUPAEC I(Pn - P)(A)I
doesn't approach 0 as n oo in outer probability or in any sense, since it is identically 1. It follows that C is also not a Donsker class for P. Note that all functions 1 A for A E C equal 0 almost surely for P. Thus, the whole class .F := {lA : A E C) reduces to the one point 0 in the space L2(P) of equivalence classes for equality almost everywhere of functions in G2(P), that is, measurable, square-integrable functions. Thus for purposes of empirical processes, functions equal a.s. P are not the same, and we need to deal with classes F C G2(P) of actual real-valued functions, not equivalence classes. Then the integral f fd(P, - P) will be well-defined for any f E L2(P). This
integral is linear in f and thus prelinear for f E T for any set J7 C G2(P). For the empirical process v, = n 1/2(P - P) we will not be taking versions or modifications as was done for Gaussian processes (Appendix J). Next, let C2 be the collection of all closed, convex subsets of R2. Let S1 be the unit circle {(x, y) : x2 + y2 = 11. For any finite subset F of S1, the convex polygon with vertices in F (a singleton if IFl = 1, or a line segment if
I F1 = 2) is in C2, and its intersection with S' is F. Thus S(C) = +oo and C is not a VC class. Let P be the uniform law dP(O) = dO/(2n) on S1. Then the Glivenko-Cantelli and Donsker properties fail for P just as in the previous example. Classes with S(C) finite, in other words Vapnik-Cervonenkis classes, can be
formed in various ways. Here is one. Let G be a collection of real-valued
4.2 Generating Vapnik-Cervonenkis classes
139
functions on a set X. Let
pos(g)
Ix: g(x) > 01, nn(g) := IX: g(x) > 0), gEG,
pos(G)
{pos(g): g E G}, nn(G) := {nn(g): g E G),
U(G)
pos(G) U nn(G).
4.2.1 Theorem Let H be an m-dimensional real vector space of functions on
a set X, let f be any real function on X, and let Hi := (f + h : h E H). Then S(pos(Hl)) = S(nn(H1)) = m. If H contains the constants then also S(U(H1)) = M.
Proof First it will be shown that S(pos(H1)) = m. Clearly card(X) > m. If card(X) = in, then H = Hl is the set ]RX of all real-valued functions on X, so the result holds.
Otherwise, let A C X with card(A) = m + 1. Let G be the vector space {a f + h : a E IR, h E H). Let rA : G ra IRA be the restriction of functions in G to A. If rA is not onto, take 0 v E IRA where v is orthogonal to rA(G) for the usual inner product -)A Let A+ := {x E A : v(x) > 0}. We can assume A+ is nonempty, replacing v by -v if necessary. If A+ = A fl pos(g) for some g E G, then (rA(g), V)A > 0, a contradiction. So pos(G) doesn't shatter A.
Suppose instead that rA(G) = RA. Then rA is 1-1 on G, f 0 H, and rA(H1) is a hyperplane in RA not containing 0, so that for some v E RA,
(j, v)A = -1 for all j E rA(H1). Again let A+ :_ {x E A : v(x) > 0). If A+ = A fl pos(f + h) for some h E H, then (rA(f + h), v)A > 0, a contradiction (here A+ may be empty). Thus pos(H1) never shatters A, so S(pos(Hi)) < m. For each x E X, a linear form 8x is defined on H by 3, (h) := h (x), h E H.
Let H' be the vector space of all real linear forms on H. Then H' is m-
dimensional. Let HH{aJxj: be the linear span in H' of the set of all 8,, x E X, (4.2.2)
HH
xj E X, aj E ]I8, r
1, 2,
}.
j-1 The map h H (r i-4 *(h)): h E H, r E HX, is 1-1 and linear from H JJJ
into (HX)', so HH is m-dimensional. Take B = {xl, , xm) C X such that the 8,1 are linearly independent in H. So rB (H) = RB, rB (H1) = JRB, and pos(rB(H1)) = 2B, so S(pos(Hi)) = m. Then S(nn(H1)) = m by taking complements (Proposition 4.1.8). If H contains the constant functions, then the sets nn(f ), f E H1, are the same as
140
Vapnik-Cervonenkis Combinatorics
the sets If > t), f E H1, t E R, and the sets pos(f), f E H1, are the same as the sets If > t), f E H1, t E R. Now for any finite subset A of X, f E Hl and t E R, since f takes only finitely many values on A, there exist s and u
such that AflIf >t}=AflIf >s}and AflIf >t}=AflIf >u}. So in this case S(U(H1)) = m. Examples. (I) Let H := Pd,k be the space of all polynomials of degree at most k on Rd. Then for each d and k, H is a finite-dimensional vector space of functions, so pos(H) is a Vapnik-Cervonenkis class. For k = 2, it follows specifically that the set of all ellipsoids in 1W' is included in a VapnikCervonenkis class and thus is one.
(II) Let X = R. Let H be the 1-dimensional space of linear functions f(x) = cx, x E 1k, c E R. Then S(pos(H)) = S(nn(H)) = 1 by Theorem 4.2.1, but U(H) shatters {0, 1). Since sets in U(H) are convex (half-lines), it follows that S(U(H)) = 2. So the condition that H contains the constants can't just be dropped from Theorem 4.2.1 for U(H). Let X be a real vector space of dimension m. Let H be the space of all real affine functions on X, in other words functions of the form h + c where h is real linear and c is any real constant. Then H has dimension m + 1 and pos(H) is the set of all open half-spaces of X. Letting f = 0 in Theorem 4.2.1 for this H gives a special case known as Radon's theorem. On the other hand, Theorem 4.2.1 for f = 0 with general X and H follows from Radon's theorem via the following stability fact.
4.2.3 Theorem If X and Y are sets, F is a function from X into Y, C C 2Y, S(F-t (C)) < S(C). If F is onto Y and F-1(C) := {F-1(A) : A E C}, then then S(F-1(C)) = S(C).
x j for i # j. Then , xm } where x; Proof Let F-1(C) shatter {xl, F(xi) 0 F(xj) for i ¢ j and C shatters {F(xl), , F(xm)}. So S(F-1(C)) < S(C). If F is onto Y and H C Y with card(H) = m, choose G C X such that F takes G 1-1 onto H. Then if C shatters H, F-1 (C) shatters G, so S(F-1(C)) = S(C). Now let X be any set and G a finite-dimensional real vector space of real functions on X. Then there is a natural map F : x H S from X into the space of linear functions on G. Then by Theorem 4.2.3 one could deduce Theorem 4.2.1 from its special case where X is an m- or (m + 1)-dimensional real vector space and f and all functions in H are affine, so that sets in pos(H1) are open half-spaces.
4.2 Generating Vapnik-Cervonenkis classes
141
Next it will be seen how a bounded number of Boolean operations preserves the Vapnik-Cervonenkis property.
, let C(k) be the 4.2.4 Theorem Let X be a set, C C 2X, and f o r k = 1 , 2, union of all (Boolean) algebras generated by k or fewer elements of C. Then dens(C(k)) < k dens(C), so if S(C) < oo then S(C(k)) < oo.
Proof Let dens(C) = r, so that for any s > 0 there is some M < oo such that mc(n) < Mnr+E for all n. For any A C X we have A n C(k) = (A n C)(k). An algebra A with k generators A1, , Ak has at most 2k atoms, which are those nonempty sets that are intersections of some of the A; and the complements of the rest. Sets in A are unions of atoms, so JAI < 22k. Thus IA n C(k) I < 22k IA n CIk < 22kMkIAlk(r+e). Letting E J, 0 gives dens(C(k)) < k dens(C). If S(C) < 00 then by Corollary 4.1.7, S(C(k)) < 00. The constant 22k is very large if k is at all large. Let C(lk) be the class of all intersections of at most k sets in C. Then C(nk) C C(k). For C(nk) the constant 22k is not needed. Theorems 4.2.1 and 4.2.4 can be combined to generate Vapnik-Cervonenkis classes. For example, half-spaces in Rd form a VC class. Intersections of at most k half-spaces give convex polytopes with at most k faces, so these form a VC class.
Remarks. Let X be an infinite set, r = 1 , 2,
, and let Cr be the collection of all subsets of X with at most r elements. Then clearly dens(Cr) = S(Cr) = r. It's easy to check that D := C(rk) consists of all sets B such that either B or X \ B
has at most kr elements. Thus mD(n) < 2(nC
d>5. Classes with V (C) = 0 or I are easily characterized:
4.2.5 Proposition A class C of subsets of a set X has V (C) = 0, or equivalently S(C) = -1, if and only if C is empty. Also, V (C) = 1, or equivalently
142
Vapnik-Cervonenkis Combinatorics
S(C) = 0, if and only if C contains exactly one set. Thus S(C) > 1 if and only if C contains at least two sets. Proof Clearly C shatters the empty set if and only if C contains at least one set. If C contains at least two sets, then for some A, B E C and X E X, X E A \ B.
Then C shatters {x), so S(C) > 1. Conversely if S(C) > 1, then clearly C contains at least two sets.
Here are two sufficient conditions for S(C) = 1:
4.2.6 Theorem If C is a collection of at least two subsets of a set X, then S(C) = 1 if either (a) C is linearly ordered by inclusion, or (b) any two sets in C are disjoint.
Proof In any case, S(C) > 1. If C is linearly ordered by inclusion, suppose it shatters {x, y). Let A, B E C, A fl {x, y} = {x}, B fl {x, y} = {y}. But A C B or B C A, giving a contradiction. If the sets in C are disjoint, then we can argue as in part (a), taking C E C with {x, y} C C, but C cannot be disjoint from A or B, a contradiction. Section 4.4 will go more into detail about classes of index 1.
*4.3 Maximal classes
Let C C A be classes of subsets of a set X. Then C will be called (A, n)maximal if S(C) = n while if C C D strictly and D C A, then S(D) > n. If A is the class 2X of all subsets of X, then C will be called n-maximal. If C is n-maximal, then clearly C is (A, n)-maximal for any A such that C C A C 2X. In view of Proposition 4.2.4, classes C with S(C) = i, i = -1 or 0, are empty or contain just one set, respectively, and so are always i -maximal. Thus n-maximality becomes interesting only for n > 1.
Examples. 1. For any set X, let C consist of 0 (the empty set) and all singletons (x} for x E X. Then C is clearly 1-maximal. 2. Let X = R. Let £ 7-1 consist of 0, R, and all left half-lines, closed (-oo, x] or open (-oo, x), for x E R. In other words, £7-l is the collection of all subsets A C JR such that whenever x < y e A then also x E A. Then clearly S(G7-l) = 1 since for x < y and A E £7-l, A fl {x, y} # (y}. On the
*4.3 Maximal classes
143
other hand if any subset of JR not in CH is adjoined, then some 2-element set is shattered, so £7-l is 1-maximal.
3. Let X = R and let Co consist of all subintervals of R, namely 0, R, any closed or open, left or right half-line, and any bounded interval, open or closed at either end. In other words, Co is the class of all convex subsets of R. Then S(Co) = 2, in fact Co shatters every 2-element subset of IR, while if x < y < z and A E Co, then A fl {x, y, z} {x, z}. On the other hand if any set not in Co is adjoined to it, its index becomes 3, so Co is 2-maximal. Here is an existence theorem for maximal classes:
4.3.1 Theorem Let X be a set and D C 2X. Suppose that C C D and S(C) = n. Then there exists a (D, n)-maximal class B with C C B.
Proof Zorn's lemma (RAP, Section 1.5) will be applied. Let (,t3a)aEI be such that C C Ba C D for all a in the index set I and such that the Ba are linearly ordered (i.e., form a chain) by inclusion, with S(Ba) = n for all a. Let A := Ua Ba. To show that S(A) = n, suppose A shatters a set F with I Fl = n + 1. Each of the 2"+1 subsets of F is induced by a set in some Ba. Since there are only finitely many of these sets and the Ba are linearly ordered by inclusion, there is some a such that Ba shatters F, a contradiction. So the chain {8a }aEI has an upper bound. So by Zorn's lemma the collection of all B with C C B C D and S(B) = n has a maximal element (for inclusion). The following fact is straightforward:
4.3.2 Proposition For any set X, Y C X, C C 2X, and Cy := C n Y, we have S(Cy) < S(C). Recall that Z2 := to, 1} with addition mod 2, in other words the usual addition except that I + 1 = 0. For any set X, the group Z2 of all functions from X into Z2, with the natural addition (f + g)(x) := f(x) + g(x) in Z2, provides a group structure for the collection 2X of all subsets of X. Addition of indicator functions mod 2 corresponds to the symmetric difference AAB :_ (A \ B) U (B \ A), so that I A + 1 B = I AAB mod 2. For any fixed set A C X, the translation 1 B H I A + 1 B takes Z 2 one-to-one and onto itself. If the functions are restricted to a subset Y C X, translation still takes Z2 one-to-one and onto itself. For any A C Xand C C 2X, let AAAC {AAC: C E C). Then for any finite F C X, C shatters F if and only if AAAC does. It follows that:
144
Vapnik-Cervonenkis Combinatorics
4.3.3 Proposition For any fixed set A C X and class C C 2X, S(C) S(AAAC). Also, C is n-maximal if and only if AAAC is. Next, we have:
4.3.4 Proposition If C is an n-maximal class of subsets of a set X, and n > 1, then UAc
Proof Suppose there is an x such that x A for all A E C. Take any B E C and let D := C U (B U {x}). Then by n-maximality, D must shatter some set F of cardinality n + 1 > 2, and evidently x E F. Thus D contains at least 2" > 2 sets which contain x, but it only contains one, a contradiction. This proves the first conclusion. The second follows on taking complements, setting A = X in Proposition 4.3.3.
On ZX = 2X there is a product topology coming from the discrete topology on Z2. The product topology is compact by Tychonoff's theorem (RAP, Theorem 2.2.8). 4.3.5 Proposition For any set X, any n-maximal class C C 2X is closed and therefore compact in 2X.
Proof Suppose Ca -* C is a convergent net in 2X with Ca E C for all a. Then for any finite set F C X, there is some a with Ca fl F = C fl F, so S(C U {C}) = S(C) and C E C. So C is closed (RAP, Theorem 2.1.3). A class C of subsets of a set X will be called complemented if X \ A E C for every A E C.
4.3.6 Theorem If S(C) = n, C C A strictly, and C is complemented, then C is not (A, n)-maximal.
Proof For any finite set F C X and G C F, G E C n F if and only if F \ G E C n F. Thus if IFl = n + 1, then IC n Fl < 21+1 - 2. So, for any
AEA\C,S(CU{A})=n. If F is a k-dimensional real vector space of real-valued functions on a set X containing the constants, and C is the collection U(F) of all sets {x : f (x) > 0}
or {x : f (x) > 0} for all f E .F, then S(C) = k by Theorem 4.2.1. Since C is complemented, if U(.F) 2X, then C is not k-maximal.
*4.4 Classes of index 1
145
Let X be any set and Ck the collection of all subsets of X with at most k elements. Then clearly S(C) = k. Also, C is k-maximal since if A 0 C, A C X, then I A I > k and if B is any subset of A with I B I = k + 1 then B is shattered by C U {A). For C = Ck we have me (n) C
*4.4 Classes of index 1 In this section the structure of classes C with S(C) = 1 will be treated. Recall that for classes of two or more sets, disjoint classes and classes linearly ordered by inclusion have S(C) = 1 (Proposition 4.2.6). A common extension of these two kinds of classes is given by treelike partial orderings, defined as follows. A binary relation < on a set X will be called a quasi-order if it is transitive:
x < y and y < z imply x < z; and reflexive: x < x for all x e X. The quasi-order is called a partial order if also x < y and y < x imply x = y. For any set S, inclusion ( C ) is a partial order on 2S or any subset of 2S. Let < be a quasi-order on a set X. Then two elements x and y of X are called comparable if at least one of x < y and y < x holds, or incomparable if neither holds. A quasi-order < on X will be called linear if any two elements of X are comparable. A quasi-order < will be called treelike if for any y E X and L Y := {x : x < y), the restriction of < to L Y is linear. 4.4.1 Theorem Let C C 2X contain at least two sets and satisfy, for any x in X, (4.4.2)
y
A fl {x, y) = 0 for some A E C.
Then the following are equivalent:
(a) S(C) = 1; (b) for every Y C X, the partial ordering of Cy := Y n C by inclusion is treelike; (c) for every Y C X with I Y I = 2, the partial ordering of Cy := Y n C by inclusion is treelike.
Note. Clearly, (4.4.2) holds if 0 E C.
146
Vapnik-Cervonenkis Combinatorics
Proof In proving (a) implies (b), since S(Cy) < S(C) and classes with S(C) < 1 contain at most one set and trivially have a treelike ordering by inclusion, we can assume Y = X. If C doesn't have a treelike ordering by inclusion, there is
a set D E C and B C D, C C D such that B and C are not comparable, so there exist some x E B \ C and Y E C \ B. Take A from assumption (4.4.2). But then the sets A, B, C, and D shatter (x, y) and S(C) > 2, a contradiction. So (b) holds. Now (b) implies (c) directly. If (c) holds and I Y I = 2, since 2Y doesn't have a treelike ordering by inclusion, C must not shatter Y, so (a) follows.
4.4.3 Proposition Let X be a set and A C 2X where 0 E A and for any B and C in A, B fl C E A. If C is (A, 1) -maximal and satisfies (4.4.2) for any
x# yin X, then 0ECandBflCECforanyBandCinC. Proof If x
y and (4.4.2) holds for A, then A fl {x, y} = 0 = 0 fl {x, y}, so adjoining 0 to C doesn't induce any additional subsets of sets with two elements, and S(C U 10)) = 1, so by maximality 0 E C. Suppose B, C E C and S(C U {B fl C}) > 1. Then for some x # yin X, B fl C fl (x, y) # D fl {x, y} for all D E C. Then by (4.4.2), we can assume x E B fl C. If {x, y} C B fl C C B then taking D = B would give a contradiction, so y 0 B fl C. Now B fl c fl {x, y} = {x} # D fl {x, y) for D = B or C implies y E B and y E C, again a contradiction. So B fl C E C.
4.4.4 Proposition Let X be a set and C a finite class of subsets of X with S(C) = 1 such that for any x y in X, (4.4.2) holds. Let D := D(C) consist of 0 and all intersections of nonempty subclasses of C. Then S(D) = 1. For each nonempty set D E D there is a C := C(D) E D such that C C D strictly (C 0 D) and if B is any set in D with B C D strictly, then B C C. Proof By Theorem 4.3.1, let C C E where £ is 1-maximal. Then by Proposition 4.4.3 for A = 2X and induction, C C D C E, so S(D) = 1. Clearly, D is finite. For each nonempty D E D, by Theorem 4.4.1, {B E D: B C D} is linearly ordered by inclusion and contains 0, so it has a largest element C(D) other than D itself.
4.4.5 Proposition
Under the hypotheses of Proposition 4.4.4, the sets
D \ C(D) for distinct nonempty D E D are all disjoint and are nonempty.
Proof Let A
B in D. If B C A, then B C C(A), so B and hence
B \ C(B) are disjoint from A \ C(A). Otherwise, A fl B C B strictly, and then
*4.4 Classes of index 1
Af1B C C(B), so again A \C(A) is disjoint from B\C(B). That A\C(A) 0 follows from the definitions.
147
0
for A
A graph is a nonempty set S together with a set E of unordered pairs {x, y} for some x y in S. Then S will be called the set of nodes and E the set of edges of the graph. The graph (S, E) is called a tree if (a) it is connected, in other words for any x and y in S there is a finite n and x; E S, i = 0, 1, , n, such that xo = x, x, = y, and {xk_1, xk} E E for
k= (b) the graph is acyclic, which means that there is no cycle, where a cycle
is a set of distinct xl,
, x E S such that n > 3, and letting xo := x,,,
{xk_1,xk} E Efork= 1, ,n. 4.4.6 Theorem (a) For in nodes, for any positive integer m, there exist connected graphs with in - 1 edges. (b) A connected graph with in nodes cannot have fewer than in - 1 edges. (c) A connected graph with m nodes has exactly m - 1 edges if and only if it is a tree.
Proof (a) is clear. (b) will be proved by induction. It is clearly true for in = 1, 2. Suppose (S, E) is a connected graph with BSI = in, I EI < in - 2, and m > 3. The edges in E contain at most 2m - 4 nodes, counted with multiplicity, so at least four nodes appear in only one edge each, or some node is in no edge, a contradiction. Select a node in only one edge and delete it and the edge that contains it. The remaining graph must be connected, but is not by induction assumption, a contradiction, so (b) holds.
For (c), let (S, E) be a connected graph with ISO = in and IEJ = m - 1. If the graph contains a cycle, we can delete any one edge in the cycle and the graph remains connected, contradicting (b). So (S, E) is a tree. Conversely, let (S, E) be a tree with I SI = m. It will be proved by induction that I E I < in - 1.
This is clearly true for m = 1, 2. Suppose I E I > in > 3. Take a maximal , xk} C S such that the xi are distinct and {xj_1, Xj) E E for set C := {xl, j = 2, , k. Then there is no y 0 X2 with {x1, y) E E: y cannot be any xj, j > 3, or there would be a cycle, and there is no such y C since C and k are maximal. So we can delete the node xl and the edge {xl, x21 from the graph, leaving a graph which is still a tree with in - 1 nodes and at least in - 1 edges, contradicting the induction hypothesis and so proving (c). Let the class D in Propositions 4.4.4 and 4.4.5 form the nodes of a graph G
whose edges are the pairs {C(D), D} for D E D, D # 0.
148
Vapnik-Cervonenkis Combinatorics
4.4.7 Proposition The graph G is a tree. Proof If D has m elements, then there are exactly m - I pairs {C(D), D}, for D E D, D # 0. Starting with any D E D, we have a decreasing sequence of sets D D C(D) D C(C(D)) D , which must end with the empty set, so all sets in D are connected in G via the empty set, and G is connected. Then by Theorem 4.4.6 it is a tree. 4.4.8 Proposition Let X be a finite set. Let C be 1-maximal in X and suppose (4.4.2) holds for all x y in X. Then C = D(C) as defined in Proposition 4.4.4. The sets D\C(D)for nonempty D E C are all the singletons {x}, x E X.
IfIXI=mthen ICI =m+1. Proof C = D(C) by Proposition 4.4.4. Suppose that for some D E C, D\C(D)
has two or more elements. Then for some B, C := C(D) C B C D where both inclusions are strict. It will be shown that S(C U {B}) = 1. If not, then for some x 0 y, C U {B} shatters {x, y}, so B fl {x, y} 54 F fl {x, y} for all F E C. Letting F = C shows that B fl {x, y} 0 0. Likewise, letting F = D shows that B fl {x, y} {x, y}. So we can assume B fl {x, y} = {x}. Taking F = D shows
that y e D. If G n {x, y} = (y) for some G E C, then y E G fl D E C, and G n D C D strictly, so G n D C C and y E C C B, giving a contradiction. So C U { BI does not shatter {x, y}, and S(C U { B)) = 1, contradicting 1-maximality of C.
So, each set D \ C(D) for 0 0 D E C is a singleton. Each singleton {x} equals D \ C(D) for at most one D E C by Proposition 4.4.5. By Proposition
4.3.4, X = UDEC D. For any x E X take D1 E C with x e D. Let . Forsomem, D,,, = 0, and {x} = Dj\C(Dj) D,+1 := C(D,) forn = 1, 2, for some j < m. So all singletons are of the form D \ C(D), D E C. This
gives a 1-1 correspondence between singletons and nonempty sets in D, so there are exactly m such sets and I D I = m + 1. Suppose throughout this paragraph that C is a class of two or more sets such that (4.4.2) holds with 0 replaced by {x, y}. Then the class of complements, N := {X \ C: C E C), satisfies the original hypotheses of Proposition 4.4.1. If C is 1-maximal, so is N by Proposition 4.3.3. So Theorem 4.4.1 and the facts numbered 4.4.3 through 4.4.7 apply to N, and so does Proposition 4.4.8 if X is finite. Then, C itself has a "cotreelike" ordering, where for each C E C, {D E C : C C D} is linearly ordered by inclusion. Propositions 4.4.3 and 4.4.4 apply to C if 0 is replaced by X and intersections by unions; in Proposition 4.4.4, we will have an immediate successor D(C) D C instead of a
*4.4 Classes of index 1
149
predecessor; and sets D(C) \ C instead of D \ C(D) in Propositions 4.4.5 and 4.4.8. The resulting tree (Proposition 4.4.7) then branches out as sets become smaller rather than larger. Next will be several facts in the general case, that is, without the hypothesis (4.4.2).
4.4.9 Theorem Let X be any set and C any collection of subsets with S(C) = 1. Then for any C E C, the collection Cx\c := (B \ C : B E C) satisfies (4.4.2) for any x y as a collection of subsets of X \ C. Likewise, Cc \ := (C \ B : B E C) satisfies (4.4.2) for any x y as a collection of subsets of C, S(Cc V) < 1 and S(CX\C) < 1.
Proof Letting B = C shows that both classes Cc \ and CX\c contain 0, so (4.4.2) holds for them. Both have index S < 1 by Propositions 4.3.2 and 4.3.3.
So, for an arbitrary class C with S(C) = 1, we have by Theorem 4.4.1 a treelike partial ordering by inclusion in one part X \ C of X and a cotreelike ordering in the complementary part C, for any C E C. If also X \ C happens to be in C, both orderings are linear. To see how the two orderings fit together in general, Proposition 4.3.3 gives:
4.4.10 Corollary Let C be any class of sets with S(C) = 1 and A E C. Let D := AAAC. Then S(D) = 1 and 0 E D. If C is 1-maximal, so is D. Then Theorem 4.4.1, Proposition 4.4.3, and if C is finite, Propositions 4.4.4, 4.4.5, 4.4.7, and if X is finite, Proposition 4.4.8, apply to D. The last sentence in Proposition 4.4.8 has a converse and extension:
4.4.11 Proposition Let X be finite with m elements and C C 2X with S(C) _ 1. Then C is 1-maximal if and only if ICI = m + I.
Proof For any fixed C E C, we can replace C by CAiC without loss of generality by Theorem 4.3.3. So we can assume 0 E C, and then (4.4.2) holds for all x, y. Then Proposition 4.4.8 implies "only if."
Conversely, let S(C) = 1 and ICI = m + 1. Let C C D strictly. Then IDS > m + 1, so by Sauer's lemma (Theorem 4.1.2), S(D) > 2. So C is 1-maximal.
Now, m + 1 = mC<1, which is the maximum value of mc(m) for S(C) = 1 by Sauer's lemma (Theorem 4.1.2). The example at the end of Section 4.3
150
Vapnik-Cervonenkis Combinatorics
shows that Proposition 4.4.11 in the form Cl I_ mC
a set X, a subset Y C X, and a class C c 2X, recall that Cy := C n Y {A n Y: A E C}.
4.4.12 Theorem If C is 1-maximal and 0
Y C X, then Cy is a 1-maximal
class of subsets of Y.
Proof Let A E C. Without changing 1-maximality, C can be replaced by AAAC (Proposition 4.3.3). So we can assume 0 E C. We can also assume that
IXI>2. Case 1. Suppose X is finite, I X I = m < oo. Then by Proposition 4.4.8 or
4.4.11, ICI = m + 1. Letx E Xand Y := X\{x}. Let B := {y E Y: {x, y} E C{x, y} and (y) E C{x, y} }. A set C C Y will be called full if C E C and
CU{x}E C. 4.4.13 Lemma If A C Y and A is full then A = B. Proof Suppose A is full. First suppose y (= A \ B. Then A U {x} E C implies {x, y} E C{x,y} and A E C implies {y} E C{x,y}, contradicting y
B.
Next, suppose y E B \ A. Then {x} = (A U {x}) n {x, y}, 0 = 0 n {x, y}, and y (= B imply that C shatters {x, y}, a contradiction. So A = B, proving the lemma.
El
Continuing the proof of Theorem 4.4.12, any two distinct sets in C have different intersections with Y, except possibly for B and B U {x}. Now Cl S=
m + 1 by Proposition 4.4.11, so ICyl > m and ICY = m since S(Cy) < 1 and I Y I = m - 1. So if m > 2, Cy is a 1-maximal class of subsets of Y by Proposition 4.4.11 again. Then by induction downward, Cy is 1-maximal in Y for any Y C X, Y 0, proving the theorem if X is finite.
Case 2. Let X be general and 0 Y finite. Suppose Cy is not 1-maximal in Y. Then by Case 1, for any finite Z D Y, Cz is not 1-maximal in Z. Let E be the class of all B C Y such that B Cy and S({B} U Cy) < 1. Suppose for each B E £ there is some finite Z(B) D Y such that there is no A C Z(B) with S({A} U CZ(B)) < 1 and A n Y = B. Let Z := UBEE Z(B). Then Z is a finite set including Y. So Cz is strictly included in some class D which is 1-maximal in Z, by Theorem 4.3.1 (with A = 2Z), and Dy is 1-maximal
*4.4 Classes of index 1
151
by Case 1. So B E Dy for some B E E, say D n Y = B for some D E D. Then A := D n Z(B) gives a contradiction.
So, for some B E E and any finite Z D Y, there is an A C Z such that A n Y = B and S(Cz U {A}) < 1. Let Dz be the class of all subsets D of X for which D n z is such a set A. Then Dz is compact in the product topology of 2X (which was treated in Proposition 4.3.5). For any finite U D Y
and V D Y, DU n Dv D DUuV 0 0. So the intersection of all DU is nonempty. Let D E DU for all finite U D Y. Then S(C U {D}) = 1, so
D E C, but D n Y = B
Cy, a contradiction. This finishes the proof in
Case 2.
Case 3. Let X be infinite and U any infinite subset. Let T (U) := {D C U : D n Y E Cy for all finite Y C U}. Then clearly CU C .F(U). Conversely, if D E .F(U), then for each finite Z C X, let Y := Z n U. Let g(Z) := {A E C : A n Y = D n Y}. Then 9(Z) is compact by Proposition 4.3.5, nonempty since D E .F(U), and decreases as Z increases. Thus there is some C E nz g(Z). Then for any finite Z, C n Z n U = D n z n U, so C n U = D n U = D. So D ECU and CU =.F(U). For each finite, nonempty Y C U, Cy is 1-maximal in Y by Case 2. Suppose
.F(U) is not 1-maximal in U. Let A C U, A .F(U), S(E) < 1 where E = (Al U.F(U). For each finite Y C U, Cy C Sy, so Cy = Ey. Let fly :=
{BEC: BnY=AnY}. Then Ry00andasshown above, I
lyfy#0.
Let B E ly Ry. Then A = B n U E Cu = .F(U), a contradiction. So CU is 1-maximal in U. I
For any set X and C C 2X, let x
4.4.14 Theorem If S(C) = 1, UBEC B = X, and C satisfies (4.4.2) for all x y, then
Proof Suppose S(C) = 1 and (4.4.2) holds for all x y. Let x
152
Vapnik-Cervonenkis Combinatorics
C, D E C with x E C \ D, y E D \ C. Then C shatters {x, y), a contradiction. So {x : x
y<x}EC,and0EC,soS(C)=1. Let A C X and suppose A is not linearly ordered by <. Take x, y E A which are not comparable for <. Since 0, Lx and L y are all in C, C U (A) shatters {x, y), and S(C U (A}) > 2.
Let B C X and suppose there exist x< y E B with x V B. Then Lx E C, Ly E C, and B fl {x, y} _ {y} imply that S(C U {B)) > 2. This has now been shown for any B V C, so C is 1-maximal. Example. Let X = 11, 2, 3, 4, 51 and
9=(0,(1),(5), 12,51,11,2,41,11,2,3,41,11,2,3,51,11,2,3,4,5)1. Let C be the complement of g in 2X. Then it can be checked that C is 3-maximal
but for Y = (1, 2, 3, 41, Cy is not 3-maximal in Y. So in Theorem 4.4.12, "1maximal" and "Y 0" cannot be replaced by "3-maximal" and "JYJ > 3" respectively.
*4.5 Combining VC classes Recalling the density as in Corollary 4.1.7, the following is clear:
4.5.1 Theorem For any set X, if A C 2X and C C 2X then dens(A U C) = max(dens(A), dens(C)). For the Vapnik-Cervonenkis index we have instead:
4.5.2 Proposition For any set X, A C 2X and C C 2X, S(A U C) < S(A) + S(C) + 1. This bound is optimal: for any nonnegative integers k and m there exist X and A, C C 2X with S(A) = k, S(C) = m, and S(A U C) _
k+m+1.
*4.5 Combining VC classes
153
Proof By Theorem 4.1.2, if k := S(A), m := S(C), and n > k + m + 2,
m,auc(n) < mA(n)+mC(n) < nC
(n) + j=0
j=n-m
(n)
<
2n,
so S(A U C) < n. It follows that S(A U C) < k + m + 1 as claimed. Conversely, given k and m let n = k + m + 1 and let X be a set with n members. Let A be the set of all subsets of X with at most k members and let C be the set of subsets
of X with at least n - m = k + 1 members. Then S(A) = k, S(C) = m, and A U C = 2X, so S(A U C) = n. Let X be a set and C, D any two collections of subsets of X. Let
CnD
{C n D: CEC, DED},
CuD
{CUD: CEC, DED}.
If A is a class of subsets of another set Y let
C®A := {CXA: CEC, AEA}. For such classes, we have:
4.5.3 Theorem For any C C 2X and D C 2X or 2Y let k := dens(C) and m := dens(D). Then we have dens(C El D) < k + m for El = n, u, or S. Proof For any of the three operations, we have m c E IV (n) < m c (n )m D (n ), and the conclusions follow.
For the Vapnik-Cervonenkis index the behavior of the El operations is not so simple. For k, m = 0, 1, 2, , and D = u, n, or ®, let D(k, m) :_ max{S(C El D) : S(C) = k, S(D) = m}. Here the maximum is taken where X and Y may be infinite sets. Then we have:
4.5.4 Theorem For any k = 0, 1, 2,
and m = 0, 1, 2,
, and El = u,
n, or ®, we have D(k, m) < oo.
Proof By Theorem 4.1.2 and Proposition 4.1.5, if S(C) = k and S(D) = m, then
mcoD(n) < mc(n)mD(n) < 9nk+m1(4k!m!) < 2n for n > no(k, m) large enough.
154
Vapnik-Cervonenkis Combinatorics
4.5.5 Theorem F o r any k, in = 0, 1 , 2,
,
n(k, m) = u(k, m) = ®(k, m).
Proof The first equation follows from taking complements (Proposition 4.1.8). For the second, for given k and in, by Theorem 4.5.4 it is enough to consider
large enough finite sets in place of X and Y, and then we can assume X =
Y. We have n(k, m) < ®(k, m) by restricting to the diagonal in X x X and applying Proposition 4.3.2. In the other direction, let fix and fly be the projections of X x Y onto X and Y respectively. Let C C 2X and A C 2Y.
Let.F:= (IIXI(C): C E C), B = {IIYI(A): A E A}. By Theorem 4.2.3, S(.T) = S(C) and S(B) = S(A). Since I} XI (C) n IIY I (A) = C x A it follows that S(.F n 8) > S(C ® A), and the theorem is proved. Let S(k, m) be the common value of the quantities in Theorem 4.5.5. Theorem 4.5.4 can be improved as follows. For any nonnegative integers j, k let
9(j, k) := sup{r E N: (rC 2r}. Then 9(j, k) < oo for each j, k by Proposition 4.1.5, and we have:
4.5.6 Proposition S(j, k) < B (j, k) for any j, k E N.
Proof Let S(C) = j and S(D) = k. Then for any n > 6(j, k), by Sauer's lemma (Theorem 4.1.2) and Proposition 4.1.5 again, mcuD(n)
< mc(n)m"(n) < (nC<j)(nC
Can the values S(k, m) be computed? It is shown in Dudley (1984, Proposition 9.2.8) that S(1, 1) = 3 (which is not a corollary of Proposition 4.5.2, apparently). Also, after Proposition 9.2.10 there, an example of L. Birge is given showing that S(l, 2) > 5. For classes satisfying stronger conditions, more can be proved:
4.5.7 Theorem Let X and Y be sets, C C 2X and D C 2Y. If C is linearly ordered by inclusion, then S(C ® D) < S(D) + 1. Proof Let m = S(D). We can assume that m < oo and X E C. Let F C X x Y
with IFI = in + 2. Suppose C ®D shatters F. The subsets of IIXF C X induced by C are linearly ordered by inclusion. Let G be the next largest subset
other than I1XF itself, and p E f}XF \ G. Take y such that (p, y) E F. Then all subsets of F containing (p, y) are induced by sets of the form I}XF x D, D E D. Thus H := F \ {(p, y)} is shattered by such sets. Now I H I = in + 1, and IIY must be one-to-one on H or it could not be shattered by sets of the given form. But then D shatters flyH, giving a contradiction.
*4.5 Combining VC classes
155
4.5.8 Theorem For any set X and C, D C 2X, if C is linearly ordered by inclusion, then S(C D D) < S(D) + 1 for D = n or u.
Proof First consider D = n. Again let m = S(D), and we can assume m < oo. Let F C X and I Fl = m + 2. Suppose C n D shatters F. Now CF is linearly ordered by inclusion. We can assume that X E C, so F E CF. Let G be the next largest element of CF and p E F \ G. Each set A C F containing p is of the form C f1 D fl F, C E C, D E D, so we must have C f1 F = F, and A = D fl F. So D shatters F \ (p), a contradiction. Since the complements of a class linearly ordered by inclusion are again linearly ordered by inclusion, the case of unions follows by taking complements (Proposition 4.1.8).
Then by Theorem 4.2.6 and induction we have:
4.5.9 Corollary Let Ci be classes of subsets of a set X and C := {n"=1 C; : Ci E Ci, i = 1, , n}, where each C1 is linearly ordered by inclusion. Then S(C) < n. Definition. For any set X and Vapnik-Cervonenkis class C C 2X, C will be
called bordered if for some F C X, with I Fl = S(C), and x (= X \ F, F is shattered by sets in C all containing x.
4.5.10 Theorem Let Ci C 2x0) be bordered Vapnik-Cervonenkis classes for i = 1, 2. Then S(C1®C2) > S(C1) + S(C2).
Proof Take F C X(i) and xi as in the definition of "bordered." Let H := ({x1} x F2) U (F1 x {x2}). Then IHI = S(C1) + S(C2). For any Vi C F, i = 1, 2, take Ci E Ci with Ci fl Fi = Vi and xi E Ci. Then (C1 x C2) fl H = ({x1 } x V2) U (V1 x {x21), so Ci ®C2 shatters H.
Theorem 4.5.10 extends by induction to any number of factors. One consequence is:
4.5.11 Corollary In JR let ,7 be the set of all intervals, which may be open or closed, bounded or unbounded on each side. In other words, ,7 is the set of all convex subsets of R. In JR let C be the collection of all rectangles parallel , m }. Then S(C) = 2m. to the axes, C :_ {III" 1 J : J i E ,7, i = 1, Let D be the set of all left half-lines (-oo, x] or (-oo, x) for x E R. Let
Vapnik-Cervonenkis Combinatorics
156
T :_ {IIm 1 Hi : Hi E D, i = 1, , m}, so T is the class of lower orthants parallel to the given axes. Then S(C) = m. Proof The class D is linearly ordered by inclusion and is bordered with S(D) =
1, and so is the class of half-lines [a, oo) or (a, oo), a E JR. The class ,7 of all intervals in R is bordered with S(J) = 2. The results now follow from Corollary 4.5.9 with n = 2m and n = m, and Theorem 4.5.10 and induction.
4.5.12 Proposition Let ,7 be the set of all intervals in JR. Let Y be any set and C C 2t' with Y E C. Then in JR x Y, S(,7 ®C) < 2 + S(C).
Proof If S(C) = +oo the result is clear, so suppose m := S(C) < oo. Let F C ] I R x Y with I FI = 3 + m and suppose ,7 ®C shatters F. Let (xi, yi ),
i=
, m + 3, be the points of F. Let u := mini xi and v := maxi xj. Let
1,
p := (u, yi) E F and q := (v, yj) E F. All subsets of F which include 1p, q) must be induced by sets of the form JR x C, C E C. So n y must be one-to-one on F \ { p, q }, and C shatters n y (F \ (p, q }) of cardinality m + 1, a contradiction.
4.6 Probability laws and independence Let (X, A, P) be a probability space. Recall the pseudometric dp (A, B) P(AAB) on A, where AAB := (A \ B) U (B \ A). Recall also that for any (pseudo) metric space (S, d) and s > 0, D(s, S, d) denotes the maximum number of points more than e apart (Section 1.2).
For a measurable space (X, A) and C C A let s(C) := inf{w : there is a K = K(w, C) < oo such that for every law P on A and 0 < s < 1, D(s, C, dp) < Ke-w). Definition.
This index s(C) turns out to equal the density:
4.6.1 Theorem For any measurable space (X, A) and C C A, dens(C) _ S (C).
Proof Let P be a probability measure on A. Suppose A,, , A, E C and be i.i.d. dp(Ai, Aj) > s > 0 for 1 < i < j < m, with m > 2. Let X1, X2, (P), specifically coordinates on a countable product of copies of (X, A, P).
4.6 Probability laws and independence Note that P may have atoms. For n = 1 , 2, Pr{for some i
157
,
j, Xk 0 Al DAB for all k < n)
< in (m - 1)(1 - s)'/2 < 1 forn large enough, n > -log(m(m-1)/2)/log(1-e). LetPn := n FY=18x,. (as usual) be empirical measures for P. For such n, there is positive probability that Pn (Ai AAA) > 0 for all i j, and so Ai and Aj induce different subsets of {X1, , Xn} and mc(n) > m. For any r > dens(C) there is an M =
M(r, C) < oo, where we can take M > 2, such that mc(n) < Mnr for all n.
Note that -log(1 - s) > E. Thus form > 2, m < M(2log(m2))rs-r, or m (log m) -r < M1 8-r for some M1 = Ml (r, C) = 4r M. For any 3 > 0 and ml-g < C large enough, (log m)' < Cm8 for all in > 1. Thus for all m > 0, M28-r for 0 < s < 1 for some M2 = M2(r, C, 8). Thus m < (M28-r)11(1-1)
Letting r ,I, dens(C) and 8 ,{ 0 gives dens(C) > s(C). In the converse direction, let IA I := card(A). Since it is not the case that
mc(n) < knt f o r all n > 1, for r < t < dens(C) and k = 1, 2, , let Ak C X with Ak 0 0 and I Ak n CI > k I Ak I t. Then I Ak I - oo as k oo. Let B0 := Al. Other sets Bj will be defined recursively. Let Bo, , B,_1 be disjoint subsets of X and let C(n) := Uo<j
Let Bn := Ak(n) \ C(n). So all the Bn are defined and disjoint. Each set in Bn n C is induced by at most 21 C(n)I different sets in Ak(n) n C. Thus
IBn n CI > IAk(n) n CI/21C(n)I > 224IAk(n)It > 224IBnIt. Since Bn is nonempty, it follows that I Bn n C I > 22', and hence I Bn I > 2n Let
an := IBnI-t/r,
S:_
IBnl1-t/r
< 00.
n=0
Let P be the probability measure on Un_1 Bn C X giving mass an/S to each point of Bn for each n. The distinct sets in Bn n C are at dp-distance at least an / S apart, and so are a set of elements of C which induce the subsets of Bn. So for all n,
D(an1(2S), C, dp) > I B. n CI > 224 I Bn I t
= 224an r = 224 (2S)-r(an/(2S))-r For s := an/(2S) -* 0 as n -+ oo, this implies D(s, C, dp) > 2 24
(2S)-rs-r
158
Vapnik-Cervonenkis Combinatorics
Since 2" - oo as a" 4. 0 this implies r < s(C). Then letting r f dens(C), the proof is complete. There is a notion of independence for sets without probability. To define it, for
any set X and subset A C X let A l := A and A-1 := X \ A. Sets A l , , A,,, from are called independent, or independent as sets, if for every function {1, , m} into {-1, +1}, n 1 As(j) 0 0. Such intersections, when they are , Am. nonempty, are called atoms of the Boolean algebra generated by A 1 , Thus for A 1, , Am to be independent as sets means that the Boolean algebra they generate has the maximum possible number, 2m, of atoms. If A 1, , Am are independent as sets, then one can define a probability law on the algebra they generate for which they are jointly independent in the usual probability sense and for which P(Ai) = 1/2, i = 1, , m. For example, choose a point in each atom and put mass 1/2m at each point chosen. Or, if desired, given any qi, 0 < qi < 1, one can define a probability measure Q for which the Ai are jointly independent and have Q(Ai) = qi, i = 1, , n. For a set X and C C 2X let I (C) be the supremum of m such that A t ,
are independent as sets for some Ai E C, i = 1,
, Am
, M.
4.6.2 Theorem F o r any set X , C C 2X, and n = 1, 2, , if S(C) > 2" then I (C) > n. Conversely, if I (C) > 2" then S(C) > n. So I (C) < 00 if and only if S(C) < oo. In both cases, 2" cannot be replaced by 2" - 1.
Proof Clearly, if a set Y has n or more independent subsets, then I Y I > 2'. Conversely, if I Y I = 2", we can assume that Y is the set of all strings of n digits
each equal to 0 or 1. Let Aj be the set of strings for which the jth digit is 1. Then the Aj are independent. It follows that if S(C) > 2", then I(C) > n, while if I Y I = 2" - 1 and C = 21', then S(C) = 2" - 1 while I (C) < n, as stated.
Conversely, if Bj are independent as sets for j = 1, , 2", Bj E C, let A(i) := Ai be independent subsets of {1, , 2"} for i = 1, , n. Choose
xi E nJEA(i) Bi n n0A(i)(X \ Bi). Then xi E Bj if and only if j E A(i).
For each setS C {1, ,n},
nAi nn({1,...,2"}\Ai) iES
for some j := is E 11, B; n
i0s , 2" }. Then j E Ai if and only if i E S, and (xi: i E S).
4.7 Vapnik-Cervonenkis properties of classes of functions
159
So C shatters {xl, , xn) and S(C) > n, as stated. If C consists of 2' - 1 (independent) sets, then clearly S(C) < n.
For any set X, C C 2X and Y C X, recall that Cy := Y n c := {Y fl C : Y) be the set of atoms of the algebra of subsets of Y
C E C}. Let At(C
I
generated by Cy, where in the cases to be considered, Cy will be finite because
C or Y is. Let Ac(Y) := IAt(C Y)J be the number of such atoms. Let mc(n) := sup{DA(Y) : A C C, IAA < n} < 2n. Let dens*(C) denote the infimum of all s > 0 such that for some C < oo, me (n) < Cn' for all n. For anyx E XletCX = {A E C: X E A}. LetC'' := {Cy: y E Y}. I
4.6.3 Theorem For any set X and A C C C 2X, with A finite,
(a) AA(X) = AcX (A); (b) for n = 1, 2, ... , me (n) = mcx'(n); (c) S(CX) = I (C); (d) dens*(C) = dens(CX) < I(C).
Proof For any B C A let
a(B) := n B fl n (X \ A). BES
AEA\l3
Then a (B) is an atom, in At(AI X), if and only if it is nonempty. Now y E a (B)
if and only if A fl Cy = B, so (a) follows. Then taking the maximum over A with IAA = n on both sides of (a) gives (b), which then implies (c) and (d). The last inequality follows from Corollary 4.1.7.
4.7 Vapnik-Cervonenkis properties of classes of functions The notion of VC class of sets has several extensions to classes of functions.
Definitions. Let X be a set and.F a class of real-valued functions on X. Let C C 2X. If f is any real-valued function, each set If > t } fort E R will be called a major set of f. The class .F will be called a major class for C if all the major sets of each f E ,F are in C. If C is a Vapnik-Cervonenkis class, then .F will be called a VC major class (for C). The subgraph of a real-valued function f will be the set {(x, t) E X x R:
0 < t < f(x) or f(x) < t < 01. If D is a class of subsets of X x R, and for each f E .F, the subgraph of f is in D, then .F will be called a subgraph class for D. If D is a VC class in X x JR then .F will be called a VC subgraph class.
Vapnik-Cervonenkis Combinatorics
160
The symmetric convex hull of F is the set of all functions E"'_1 c; f for f E F, c; E I[8, any finite m, and Ym1 Ic; I < 1. If 0 < M < oo, let H(F, M) denote M times the symmetric convex hull of F. Let HS (F, M) be the smallest class 9 of functions including H(.F, M) such that whenever gn E 9 for all n and gn (x) -> g(x) as n -+ oo for all x, we have g E tj. A class F of functions such that F C HS(G, M) for some M < oo and a given 9 will be called a VC subgraph hull class if G is a VC subgraph class, and a VC hull class if g = (IC: C E C} where C is a VC class of sets. So there are at least four possible ways to extend the notion of VC class to classes of functions. Some implications hold between these different conditions, but no two of them are equivalent. The next theorem deals with some of the easier cases of implication or non-implication.
4.7.1 Theorem Let F be a uniformly bounded class of nonnegative realvalued functions on a set X. Then
(a) if F is the set of indicators of members of a VC class of sets, then F is also a VC major class, a VC subgraph class, and a VC hull class; (b) if F is a VC major class then it is a VC hull class; (c) there exist VC hull classes F which are not VC major; (d) there exist VC subgraph classes F which are not VC major. Proof (a) The indicators of a VC class C of sets clearly form a VC major class (forCU{0, X}) and aVChull class. Also, the class of sets (Cx[0, 1])U(Xx{0}) for C E C form a VC class, for example by Theorem 4.5.4. So (a) holds. (b) Since .F is uniformly bounded and the definition of VC hull class allows
multiplication by a constant, we can assume 0 < f < 1 for all f E F. For such an f let n-1
A
n
n-1
l{f>j/n} j=1
jn l{ j/n< f<(j+1)/n}
j=0
Then fn (x) -> f(x) as n -+ cc for all x. (In fact, f(x)-1/n < fn (x) < f(x) for all x, so fn -> f uniformly.) So .F is a VC hull class. (c) Let X =1R2. Let C be the set of open lower left quadrants {(x, y) : x < a, y < b} for all a, b E R. Then S(C) = 2 by Corollary 4.5.11. Let F be the set of all sums Y-k 1 lc(k)/2k where C(k) E C. Then clearly .T' is a VC hull class. The sets where f > 0 for f in .F are exactly the countable unions of sets
4.8 Classes of functions and dual density
161
in C. But such unions are not a VC class; for example, they shatter any finite subset of the line x + y = 1. So .F is not a VC major class and (c) is proved. (d) Let f, := n-1 + n-21 B. for n = 1, 2, and for any measurable sets Bn. Then fn 4. 0, so the subgraphs of the functions fn are linearly ordered by inclusion and form a VC class of index 1 (Theorem 4.2.6(a)). Now If, > 1/n) = Bn for each n, and the sequence {Bn} need not form a VC class, for example let Bn be a sequence of independent sets (see Section 4.6). Then If,) is not a VC major class, proving (d).
4.8 Classes of functions and dual density For a metric space (S, d) and e > 0 recall D(s, S, d), the maximum number of points more than E apart. For a probability measure Q and 1 < p < oo we
have theLpmetric dp,Q(f,g):=(f If-gIPdQ)1/p.For aclass FC£"(Q) let D(p) (E, F, Q) := D(e, Jr, dp,Q). Let D(p) (E, F) be the supremum of D(E, F, dp,Q) over all laws Q concentrated in finite sets. If F is a class of measurable real-valued functions on a measurable space
(X, A), let FF(x) := supfEJ I f(x)I. Then a measurable function F will be called an envelope function for.F if and only if FF < F. If F2 is measurable it will be called the envelope function of F. For any law P on (X, A), F* is an envelope function for F, which in general depends on P.
Given .F, an envelope function F for it, E > 0, and 1 < p < oo, let DF i (e, F, Q) be the supremum of m such that ther