Talagrand elmélete arról, hogyan becsüljük valószínűségi változok maximumának a várható értékét, és az elmélet alkalmazása az Ajtai–Komlós– Tusnády tétel bizonyítására.

A kiinduló probléma:

Legyenek ξ_{t}, t ∈ T, (együttesen) normális eloszlású valószínűségi változók, amelyekre Eξ_{t} = 0, és E(ξ_{s} − ξ_{t})^{2} = d(s, t)^{2}, s, t ∈ T.

Feladat:

E sup_{t∈T} ξ_{t} ≤ jó becslés a d(·, ·) mennyiség segítségével.

A feladat vizsgálatában a normális eloszlású valószínűségi változók következő tulajdonságát használtuk fel:

P (|ξ_{t} − ξ_{s}| > u) ≤ 2e^{−u^{2}/2d^{2}(s,t)} minden s, t ∈ T indexre és u > 0 számra. (1)

Általánosabb probléma: Legyenek ξ_{t}, t ∈ T, általános valószínűségi változók, amelyekre

P (|ξ_{t} − ξ_{s}| > u) ≤ h(u, d_{1}(s, t), d_{2}(s, t)), minden s, t ∈ T,

alkalmas d_{1}(·, ·), és d_{2}(·, ·) metrikákkal a T téren és valamely h(·, ·, ·) függvénnyel.

Feladat:

E sup_{t∈T} ξ_{t} ≤ jó becslés a d_{1}(·, ·) és d_{2}(·, ·) mennyiségek segítségével.

Fontos speciális eset: Legyenek ξ_{1}, …, ξ_{n} független egyforma eloszlású valószínűségi változók μ eloszlással, és legyen F a (korlátos) függvények alkalmas osztálya, amelynek

f ∈ F elemeire Ef(ξ_{1}) = 0. Vezessük be a S_{n}(f) = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f(ξ_{j}), f ∈ F, összegeket.

Feladat:

E sup_{f∈F} S_{n}(f) ≤ jó becslés.

E feladat vizsgálatában alkalmazható a Bernstein egyenlőtlenség, amely szerint:

P (|S_{n}(f) − S_{n}(g)| > u) = P (|\frac{1}{\sqrt{n}} ∑_{j=1}^{n}[f(ξ_{j}) − g(ξ_{j})]| > u) ≤ h_{n}(u, d_{1}(f, g), d_{2}(f, g)),

később megadott h_{n}(·) függvénnyel, ahol d_{1}^{2}(f, g) = E(f(ξ_{1}) − g(ξ_{1}))^{2} = ∫ [f(x) −

g(x)]^{2}μ( dx), és d_{2}(f, g) = sup_{x} |f(x) − g(x)|.

Ilyen tipusú becslések egy alkalmazása:

Ajtai–Komlós–Tusnády tételben vizsgált probléma.

Legyen adva N független, egyenletes eloszlású X_{1}, …, X_{N} valószínűségi változó a D = [0, 1] × [0, 1] egységnégyzeten, valamint N egyenletesen elhelyezett Y_{1}, …, Y_{N} pont ugyanezen a D egységnégyzeten. (Az Y_{l} pontok egyenletes elhelyezkedése a D egységnégyzeten azt jelenti, hogy a D egységnégyzet felbontható N darab 1/N területű közös belső pontot nem tartalmazó, nem elfajuló téglalap uniójára úgy, hogy mindegyikük pontosan egy Y_{l} pontot tartalmaz. Egy téglalap nem elfajuló, ha befogóinak aránya 1/10 és 10 között van.) Általánosabban egy Y_{1}, …, Y_{N} pontelhelyezést az egységnégyzeten egyenletesnek nevezünk, ha mindegyik pontnak \frac{1}{N} súlyt adva, létezik e tömegeloszlásnak olyan szállítása, amelyre az átszállított tömeg egyenletes eloszlású az egységnégyzeten, és a teljes tömegszállítás hosszának a várható értéke kisebb, mint C\sqrt{N} alkalmas fix C > 0 univerzális számmal. Valójában az egyenletes elhelyezésnek ezt a tulajdonságát használjuk fel.

A (véletlen) X_{l}, 1 ≤ l ≤ N, pontokat úgy akarjuk átindexelni az 1, …, N pontok

egy (π(1), …, π(N)) permutációja segítségével, hogy a ∑_{l=1}^{N} d(X_{π(l)}, Y_{l}) távolságösszeg,

ahol d(X_{π(l)}, Y_{l}) = |X_{π(l)} − Y_{l}| az X_{π(l)} és Y_{l} pontok euklideszi távolsága, minél kisebb

legyen. Milyen kicsivé tehető az E (∑_{l=1}^{N} d(X_{π(l)}, Y_{l})) várható érték alkalmas (véletlen)

permutáció segítségével?

Ajtai–Komlós–Tusnády tétel. Alkalmas (véletlen, pontosabban az X_{1}, …, X_{N} pontok helyétől függő π(·)) permutációval

E (∑_{l=1}^{N} d(X_{π(l)}, Y_{l})) ≤ L\sqrt{N log N}

egy univerzális L konstanssal.

Talagrand ezt az eredményt az általa kidolgozott elmélet segítségével bizonyítja. Először megmutatja egy kombinatorikai mini-max tételnek a segítségével, hogy a tétel állítása következik az

E sup_{f∈C} |∑_{l=1}^{N}(f(X_{l}) − ∫ f(u)λ( du))| ≤ L\sqrt{N log N}  (2)

egyenlőtlenségből, ahol C a D egységnégyzeten definiált Lipschitz 1 függvények halmaza. (Egy f(x) függvény Lipschitz 1 függvény egy (T, d) metrikus téren, ha |f(x) − f(y)| ≤ d(x, y) minden x, y ∈ T pontpárra.) Azután ezt az egyenlőtlenséget bizonyítja.

Az átfogalmazás bizonyításához szükséges kombinatorikai mini-max tétel.

Egy kombinatorikai mini-max tétel. Legyen C = (c_{i,j}), 1 ≤ i, j ≤ N, egy N ×N-es

mátrix, és vezessük be az M(C) = inf ∑_{i=1}^{N} c_{i,π(i)} összeget, ahol az infimumot az {1, …, N}

halmaz összes lehetséges (π(1), …, π(N)) permutációjára vesszük. Ekkor

M(C) = sup ∑_{1≤i≤N}(w_{i} + w′_{i}),

ahol a szuprémumot az összes olyan (w_{1}, …, w_{N}) és (w′_{1} …, w′_{N}) sorozatpárra vesszük, amelyre

w_{i} + w′_{j} ≤ c_{i,j} minden 1 ≤ i, j ≤ Nindexre.  (3)

A Talagrand-féle redukció indoklása:

Legyen f(x) = f(x|w_{i}, w′_{j}, 1 ≤ i, j ≤ N) = min_{1≤j≤N}[d(x, Y_{j}) − w′_{j}], minden olyan w_{i}, w′_{j},

1 ≤ i, j ≤ N, sorozatpárra, amely teljesíti a (3) relációt a c(i, j) = d(X_{i}, Y_{j}), 1 ≤ i, j ≤ N, (véletlen) mátrix-szal. Ekkor f(x) Lipschitz 1 függvény, és

inf_{π} ∑_{1≤l≤N} d(X_{l}, Y_{π(l)}) ≤ sup_{w_{i},w′_{i}teljesíti (3)-t a c(ij)=d(X_{i},Y_{j}) mátrix-szal} ∑_{1≤i≤N}(w_{i} + w′_{i})

≤ sup_{f∈C} ∑_{1≤i≤N}(f(X_{i}) − f(Y_{i}))

≤ sup_{f∈C} |∑_{j=1}^{N}(f(X_{j}) − ∫ f(u)λ( du))| + sup_{f∈C} |∑_{j=1}^{N}(f(Y_{j}) − ∫ f(u)λ( du))| .

(Valójában elég csak az f(x|w_{i}, w′_{j}, 1 ≤ i, j ≤ N) alakú függvények szuprémumát venni az f ∈ C függvényosztály helyett. A fenti egyenlőtlenség második sora a w_{i} ≤ f(X_{i}|w_{i}, w′_{j}) és w′_{j} ≤ −f(Y_{j}|w_{i}, w′_{j}) relációkból következik.) Várható értéket véve és az Y_{j} sorozat egyenletes elhelyezkedését kihasználva kapjuk a követező egyenlőtlenséget, amely biztosítja a kívánt redukciót.

E inf_{π} ∑_{1≤l≤N} d(X_{l}, Y_{π(l)}) ≤ E sup_{f∈C} |∑_{j=1}^{N}(f(X_{j}) − ∫ f(u)λ( du))| + O(\sqrt{N}).

Megjegyzés: A redukciót biztosító elv bizonyítása megjelenik már Kantorovics és Wasserstein munkáiban.

A Gauss változókról szóló maximum probléma vizsgálata.

Természetes skálázás:

N_{0} = 1, N_{n} = 2^{2^{n}}, n = 1, 2, …

Legyen d(s, t) = [E(ξ_{s} − ξ_{t})^{2}]^{1/2}, s, t ∈ T, a (természetes) metrika a T téren, d(t, A) = inf_{s∈A} d(s, t), t ∈ T, A ⊂ T, a t pont távolsága az A halmaztól,

Δ(A) = sup_{s,t∈A} d(s, t) az A halmaz átmérője.

Tétel Gauss mezők szuprémumának a várható értékéről. Legyen T véges vagy megszámlálható halmaz, T_{n}, n = 0, 1, …, a T halmaz olyan részhalmazainak sorozata, amelyekre |T_{0}| = 1, és |T_{n}| ≤ N_{n} = 2^{2^{n}}, n = 1, 2, …, ahol |A| jelöli egy A halmaz elemeinek számát. Ekkor

E sup_{t∈T} ξ_{t} ≤ L sup_{t∈T} ∑_{n=0}^{∞} 2^{n/2}d(t, T_{n})

alkalmas univerzális L konstanssal.

Ez a becslés Dudley egy korábbi eredményének a javítása, és éles becslés. Megfogalmazom két következményét. Az első következmény valójában a tétel ekvivalens átfogalmazása, a második Dudley egy korábbi eredményével ekvivalens. Ezek megfogalmazása érdekében bevezetem a következő definiciót.

Megengedett particiósorozat definiciója. A_{0} ⊂ A_{1} ⊂ ⋯ a T halmaz megengedett particiósorozata, ha A_{n+1} az A_{n} partició finomítása minden n-re, és A_{n} elemszáma nem nagyobb, mint N_{n}.

Adva egy A_{n} (megengedett) particiósorozat és t ∈ T pont, jelölje A_{n}(t) az A_{n} partició t pontot tartalmazó elemét. A következő mennyiségek bevezetése hasznosnak bizonyult.

γ_{2}(T, d) = inf sup_{t∈T} ∑_{n=0}^{∞} 2^{n/2}Δ(A_{n}(t)),

és általánosabban minden α > 0 számra

γ_{α}(T, d) = inf sup_{t∈T} ∑_{n=0}^{∞} 2^{n/α}Δ(A_{n}(t)),

ahol az infimum az összes A_{n}, n = 0, 1, 2, …, megengedett particiósorozatra vétetik.

Gauss mezők szuprémumának a várható értékéről szóló tétel egy változata. Legyen T véges vagy megszámlálható halmaz. Ekkor

E sup_{t∈T} ξ_{t} ≤ Lγ_{2}(T, d)

alkalmas univerzális L konstanssal.

Igaz e tétel alábbi megfordítása.

Alsó becslés Gauss mezők szuprémumának a várható értékéről. Legyen T véges vagy megszámlálható halmaz. Ekkor

E sup_{t∈T} ξ_{t} ≥ \frac{1}{L}γ_{2}(T, d)

alkalmas univerzális L > 0 konstanssal.

A Dudley eredmény megfogalmazása érdekében vezessük be a következő mennyiséget.

e_{n}(T) = e_{n}(T, d) = inf sup_{t∈T} d(t, T_{n})  (4)

ahol az infimum T összes legfeljebb N_{n} elemű (N_{n} = 2^{2^{n}}, ha n ≥ 1, N_{0} = 1) T_{n} részhalmazára vétetik. (Azaz azt a lehető legkisebb ε > 0 számot keressük, amelyre a T halmaz lefedhető legfeljebb N_{n} darab ε sugarú gömbbel. A T_{n} halmaz a fedést biztosító gömbök középpontjainak a halmaza.)

Dudley becslése Gauss mezők szuprémumának a várható értékéről.

E sup_{t∈T} ξ_{t} ≤ L ∑_{n=0}^{∞} 2^{n/2}e_{n}(T).

A felső becslések bizonyítása valójában csak azt használja fel, hogy normális eloszlású valószínűségi változók teljesítik az (1) egyenlőtlenséget. Hasonlóan bizonyítható ennek egy változata, amely a Bernstein egyenlőtlenséggel együtt becslést ad független, egyforma eloszlású valószínűségi változók összegeiből álló véletlen mennyiségek szuprémumának a várható értékére.

Tétel alkalmas valószínűségi változók szuprémumának a várható érték becsléséről. Legyen adva egy T, megszámlálható sok elemből álló téren két d̄_{2}(·, ·) és d̄_{1}(·, ·) távolság, valamint X_{t}, t ∈ T, valószínűségi változók családja, amelyre EX_{t} = 0 minden t ∈ T pontra, létezik olyan t_{0} ∈ T pont, amelyre X_{t_{0}} ≡ 0, és

P (|X_{t} − X_{s}| > u) ≤ 2 exp \{− min (\frac{u^{2}}{d̄_{2}(s, t)^{2}} , \frac{u}{d̄_{1}(s, t)})\}  (5)

minden s, t ∈ T elempárra és u > 0 számra. Ekkor

E sup_{t∈T} E|X_{t}| ≤ L (γ_{1}(T, d̄_{1}) + γ_{2}(T, d̄_{2})) .

Bernstein egyenlőtlenség. Legyenek Y_{1}, Y_{2}, … független valószínűségi változók, amelyekre EY_{j} = 0, |Y_{j}| ≤ U valamilyen U számmal minden j indexre. Ekkor minden v > 0 számra

P (|∑_{j≥1} Y_{j}| > v) ≤ 2 exp \{− min (\frac{v^{2}}{4 ∑_{j≥1} EY_{j}^{2}} , \frac{v}{2U} )\} .

A Bernstein egyenlőtlenség speciálisan lehetővé teszi az előtte kimondott tétel alkalmazását a következő esetben. Legyen adva N független, egyforma eloszlású Y_{1}, …, Y_{N} valószínűségi változó μ eloszlással, és korlátos függvények egy (megszámlálható) F osztálya, 0 ∈ F, amelynek elemeire ∫ f dμ = 0 minden f ∈ F -re. Vezessük be az

S_{N}(f) = \frac{1}{\sqrt{N}} ∑_{j=1}^{N} f(Y_{j}), f ∈ F, mennyiségeket. Ha F játssza a T halmaz szerepét,

akkor az (5) formula teljesül d̄_{2} = 2d_{2} és d̄_{1} = \frac{2d_{∞}}{\sqrt{N}} választással, ahol d_{2} és d_{∞} az L_{2} illetve az L_{∞} norma által definiált távolság az (X, A, μ) mértéktérben. Ezért érvényes a fenti két eredménynek az alábbi következménye.

Következmény. Tekintsük az előbb definiált Y_{1}, …, Y_{N} valószínűségi változókat, F függvényosztályt, valamint d_{2} és d_{∞} metrikákat. Legyen S_{N}(F) = sup_{f∈F} S_{N}(f). Ekkor

ES_{N}(F) ≤ L (γ_{2}(F, d_{2}) + \frac{1}{\sqrt{N}} γ_{1}(F, d_{∞}))  (6)

alkalmas univerzális L > 0 konstanssal.

A Gauss mezők szuprémumának várható értékéről szóló tétel bizonyítása. Feltehetjük, hogy a T halmaz véges, a tekintett T_{0}, T_{1}, …, T_{n} sorozatra T_{n} = T alkalmas n index-szel, és T_{0} = {t_{0}} olyan, hogy ξ_{t_{0}} ≡ 0. (Ez utóbbi feltevést azért tehetjük, mert E sup_{t∈T} ξ_{t} =

E sup_{t∈T} ξ_{t} − Eξ_{t_{0}} = E sup_{t∈T}(ξ_{t} − ξ_{t_{0}}), és d^{2}(s, t) = E(ξ_{s} − ξ_{t})^{2} = E[(ξ_{s} − ξ_{t_{0}}) − (ξ_{t} − ξ_{t_{0}})]^{2}.)

Legyen X = sup_{t∈T} ξ_{t}. Ekkor P (X ≥ 0) = 1, és EX = − ∫_{0}^{∞} vdP (X ≥ v) = ∫_{0}^{∞} P (X ≥

v) dv. Ezért a P (X ≥ v) valószínűségek jó becslésére van szükségünk.

Minden t ∈ T pontra és 0 ≤ k ≤ n számra definiáljuk azt a t_{π(k)} ∈ T_{k} pontot,

amelyre d(t, t_{π(k)}) = min_{s∈T_{k}} d(t, s). Ekkor ξ_{t} = ∑_{k=1}^{n}(ξ_{t_{π(k)}} − ξ_{t_{π(k−1)}}). Egy rögzített u > 0

számra legyen

Ω_{k}(u) = {ω: |ξ_{t_{π(k)}}(ω) − ξ_{t_{π(k−1)}}(ω)| < u2^{k/2}d(t_{π(k)}, t_{π(k−1)}) minden t ∈ T pontra.},

1 ≤ k ≤ n, és Ω(u) = ⋂_{k=1}^{n} Ω_{k}(u). Ekkor P (Ω \ Ω_{k}(u)) ≤ N_{k}N_{k−1} · 2e^{−2^{k}u^{2}/2}, és minden

u ≥ 2 számra P (Ω \ Ω(u)) ≤ ∑_{k=1}^{n} 2^{3/2·2^{k}} · 2e^{−u^{2}/2}e^{−2(2^{k}−1)} ≤ 4e^{−u^{2}/2}. Másrészt minden

ω ∈ Ω(u) elemi eseményre sup_{t∈T} ξ_{t}(ω) ≤ uS, ahol

S = sup_{t∈T} ∑_{k≥1} 2^{k/2}d(t_{π(k)}, t_{π(k−1)}).

Innen P (\frac{X}{S} ≥ u) ≤ 4e^{−u^{2}/2}, ha u ≥ 2. Másrészt P (\frac{X}{S} ≥ u) ≤ 1, ha u ≤ 2, ezért E \frac{X}{S} ≤ L alkalmas L > 0 konstanssal. Viszont d(t_{π(k)}, t_{π(k−1)}) ≤ d(t_{π(k)}), t) + d(t_{π(k−1)}, t) = d(t, T_{k}) + d(t, T_{k−1}), és ezt az azonosságot 2^{k/2}-val megszorozva, és k-ra összegezve, majd t-ben maximumot véve kapjuk, hogy S ≤ (1 + \sqrt{2}) sup_{t∈T} ∑_{k≥0} 2^{k/2}d(t, T_{k}), és

E sup_{t∈T} ξ_{t} ≤ LS ≤ (1 + \sqrt{2})L sup_{t∈T} ∑_{n≥0} 2^{n/2}d(t, T_{n}).

Gauss mezők szuprémumának a várható értékéről szóló tétel egy változatának a bizonyítása. Tekintsünk egy megengedett A_{0} ⊂ A_{1} ⊂ ⋯ particiósorozatot. Válasszunk ki az A_{n} partició minden A ∈ A_{n} eleméből egy s ∈ A pontot, és ezek egyesítése legyen a T_{n} halmaz. Ekkor d(t, T_{n}) ≤ Δ(A_{n}(t)), mert az s ∈ T_{n} ∩ A_{n}(t) pontra d(s, t) ≤ Δ((A_{n}(t)). Ezért

E sup_{t∈T} ξ_{t} ≤ L sup_{t∈T} ∑_{n=0}^{∞} 2^{n/2}d(t, T_{n}) ≤ L sup_{t∈T} ∑_{n=0}^{∞} 2^{n/2}Δ(A_{n}(t)),

és infimumot véve az összes lehetséges megengedett particióra megkapjuk a kívánt állítást.

Dudley becslésének bizonyítása.

E sup_{t∈T} ξ_{t} ≤ L sup_{t∈T} ∑_{n=0}^{∞} 2^{n/2}d(t, T_{n}) ≤ L ∑_{n=0}^{∞} 2^{n/2} sup_{t∈T} d(t, T_{n})

minden olyan T_{n} ⊂ T, n = 1, 2, …, sorozatra, amelyre |T_{n}| ≤ N_{n}. Válasszuk a T_{n} halmazt úgy, hogy |T_{n}| ≤ N_{n}, és sup_{t∈T_{n}} d(t_{n}, T) ≤ 2e_{n}(T). Ezzel a választással megkapjuk

a kívánt becslést.

Példa, amikor Dudley eredménye gyengébb becslést ad, mint Talagrand-é. Legyen b_{1}, b_{2}, … független standard normális eloszlású valószínűségi változók sorozata, ξ_{n} = \frac{b_{n}}{\sqrt{log n}}, 2 ≤ n ≤ N_{p} + 1. Becsüljuk meg az E max_{2≤n≤N_{p}+1} ξ_{n} kifejezést Dudley és

Talagrand eredményének a segítségével. Ekkor e_{m}(T) ≥ \frac{1}{2}2^{−m}, ha 1 ≤ m ≤ p, mert minden T_{m}, |T_{m}| ≤ N_{m}, 1 ≤ m ≤ p, halmazhoz létezik olyan t ∉ T_{m} pont, amelyre t ≤ 2^{2^{m}} + 2, és erre a t pontra d(t, T_{m}) ≥ \frac{1}{2}2^{−m/2}. Ezért ∑ 2^{m/2}e_{m}(T) ≥ \frac{1}{2}p, és Dudley eredménye nem ad jobb becslést, mint Lp. Talagrand eredményének a segítségével az E max_{2≤n≤N_{p}+1} ξ_{n} ≤ L becslést kapjuk. Azaz

olyan becslést kapunk, amely nem függ a p paramétertől. Valóban, legyen T_{m} = {2, …, N_{m}} ∪ {N_{p} + 1}, 1 ≤ m ≤ p. Ezzel a választással, |T_{m}| = N_{m}, 1 ≤ m ≤ p, és ha egy t pontra N_{m−1} < t ≤ N_{m}, akkor d(t, T_{l}) = 0 az l ≥ m esetben, és

d(t, T_{l}) ≤ d(t, N_{p} + 1) ≤ 2 · 2^{−m/2}, ha l < m. Ezért ∑_{l=0}^{∞} 2^{l/2}d(t, T_{l}) ≤ 2 ∑_{l=0}^{m} 2^{(l−m)/2} ≤ L_{1}.

Az alkalmas valószínűségi változók szuprémumának a várható érték becsléséről szóló tétel bizonyítása hasonló a Gauss mezők szuprémumának várható értékéről szóló tétel bizonyításához. Ezért ennek az eredménynek a bizonyítását nem tárgyalom.

Gauss valószínűségi változó maximumának várható értékére adott alsó becslés bizonyítása.

A Gauss változók maximumának várható értékére adott alsó becslés az alábbi két tételen múlik. Ezek megfogalmazásában a következő jelölést használjuk.

Jelölés: Adva egy (T, d) metrikus tér, egy a ∈ T pont és egy r > 0 szám B_{d}(a, r) jelöli az a középpontú r sugarú kört a T téren a d metrika szerint.

Tétel A. Legyen adva normális eloszlású valószínűségi változók egy ξ_{t}, t ∈ T, rendszere egy (T, d) metrikus téren, (T véges vagy megszámlálható halmaz), amelyre Eξ_{t} = 0, t ∈ T, és E(ξ_{t} − ξ_{s})^{2} = d^{2}(s, t), s, t ∈ T. Ha ebben a rendszerben megadunk m darab ξ_{t_{1}}, …, ξ_{t_{m}} valószínűségi változót úgy, hogy d(t_{j}, t_{l}) ≥ a minden 1 ≤ j < l ≤ m indexre valamely a > 0 számmal, valamint H_{l} ⊂ B_{d}(t_{l}, σ), 1 ≤ l ≤ m, halmazokat

valamely σ > 0 számmal, és H = ⋃_{j=1}^{m} H_{j}, akkor teljesül az

E sup_{t∈H} ξ_{t} ≥ \frac{a}{L_{1}} \sqrt{log m} − L_{2}σ\sqrt{log m} + min_{1≤l≤m} E sup_{t∈H_{l}} ξ_{t}

egyenlőtlenség valamely univerzális L_{1} > 0 és L_{2} > 0 számokkal.

Speciálisan, ha σ < \frac{a}{2L_{1}L_{2}} , akkor

E sup_{t∈H} ξ_{t} ≥ \frac{a}{2L_{1}} \sqrt{log m} + min_{1≤l≤m} E sup_{t∈H_{l}} ξ_{t}.

A második eredmény megfogalmazása érdekében bevezetjük a következő definiciót.

Növekedési tulajdonság definiciója egy metrikus téren adott funkcionálokra. Legyen adva egy F (A), A ⊂ T, (nem feltétlenül lineáris) funkcionál egy metrikus tér részhalmazain, amelyre F (A) ≤ F (B), ha A ⊂ B. Ez a funkcionál teljesíti a növekedési tulajdonságot τ ≥ 1, c > 0 és r ≥ 4, paraméterekkel, ha minden n ≥ 0, m = N_{n+τ} = 2^{2^{n+τ}} (a τ paraméter csak az m szám definiciójában jelenik meg), egész és a > 0 valós számokra, valamint olyan t_{1}, …, t_{m} pontokra a T térben, amelyekre d(t_{j}, t_{l}) > a minden 1 ≤ j, l ≤ m, j ≠ l, indexpárra, és t_{l} ∈ B_{d}(s, ar), 1 ≤ l ≤ m, valamely s ∈ T pontra, és tetszőleges H_{l} ⊂ B_{d} (t_{l}, \frac{a}{r}), 1 ≤ l ≤ m, halmazokra

F ( ⋃_{1≤l≤m} H_{l}) ≥ ca2^{(n+1)/2} + min_{1≤l≤m} F (H_{l}).  (7)

(A fenti definicióban megköveteltük, hogy a tekintett t_{l} pontok mindegyike egy rögzített ar sugarú gömbben legyen, de viszonylag távol legyenek egymástól. Sőt, a t_{l} pontok H_{l} ⊂ B_{d}(t_{l}, \frac{a}{r}) “környezetei” is viszonylag távol vannak egymástól. Valójában a legfontosabb olyan bizonyításokban, ahol a növekedési tulajdonság teljesülését ellenőrizni kell, olyan t_{l}, 1 ≤ l ≤ m, pontrendszereket tekintünk, amelyek nem feltétlenül teljesítik a t_{l} ∈ B_{d}(s, ar) feltételt alkalmas s ∈ T ponttal minden 1 ≤ l ≤ m indexre, de a másik két feltétel, amely a H_{l}, 1 ≤ l ≤ m, halmazok viszonylagos nagy távolságát biztosítja, érvényes rájuk. Ez azt jelenti, hogy a növekedési tulajdonság definiciójában szereplő (7) relációt H_{l} halmazok egy gazdagabb osztályában ellenőrizzük, mint szükséges volna. Ez azonban általában nem okoz problémát.)

Tétel B. Legyen F (A), A ⊂ T, növekedési tulajdonságot teljesítő funkcionál egy (T, d) (megszámlálható számosságú) metrikus téren valamely τ ≥ 1, c > 0 és r ≥ 4 paraméterekkel, amelyre F (A) ≤ F (B), ha A ⊂ B. Ekkor létezik a T térnek olyan A_{0} ⊂ A_{1} ⊂ A_{2} ⊂ ⋯ (finomodó) particiósorozata, amelyre a A_{n} partició elemszáma kisebb, mint 2^{2^{n+τ}}, és

sup_{t∈T} ∑_{n=0}^{∞} c2^{n/2}Δ(A_{n}(t)) ≤ Lr(F (T) + cΔ(T))  (8)

alkalmas univerzális L > 0 konstanssal.

A Tétel B-ben szereplő particiósorozat lehet nem megengedett, mert abban A_{n} elemszáma N_{n+τ} -val van becsülve N_{n} helyett. De ez nem okoz problémát, mert e tétel segítségével könnyen lehet találni a (8) formulát teljesítő megengedett particiósorozatot is. Ugyancsak érdemes megjegyezni, hogy érdekes alkalmazásokban Δ(T) ≤ const. F (T), és ekkor a Δ(T) szám elhagyható a (8) becslés jobboldalán az L konstans megnővelése árán.

A Tétel A-ban tekintett F (A) = E sup_{t∈A} ξ_{t} funkcionál teljesíti a növekedési tulaj-

donságot τ = 1, elég kicsi c > 0 és elég nagy r ≥ 4 számokkal. Ezért alkalmazható rá a Tétel B. Sőt, mivel Δ(T) = sup_{s,t∈T} [E(ξ_{s} − ξ_{t})^{2}]^{1/2} ≤ const. sup_{s,t∈T} E|ξ_{s} − ξ_{t}| ≤

const. E sup_{s,t∈T}(ξ_{s} − ξ_{t}) ≤ const. F (T), a (8) formulából megkapjuk az alsó becslés Gauss

mezők szuprémumának a várható értékéről nevű tétel bizonyítását.

A Tétel A bizonyítása Ledoux koncentrációs egyenlőtlenségén alapul normális valószínűségi változók maximumáról valamint a Szudakov egyenlőtlenségen. Ez két egyébként is nagyon fontos eredmény normális valószínűségi változókról.

Ledoux koncentrációs egyenlőtlensége normális eloszlású valószínűségi változók maximumáról. Legyen adva ξ_{t}, t ∈ T, Eξ_{t} = 0, (együttesen) Gauss valószínűségi változók egy rendszere, ahol T vagy véges halmaz vagy T megszámlálható, és E sup_{t∈T} ξ_{t} <

∞. Legyen σ^{2} ≥ sup_{t∈T} Eξ_{t}^{2}. Ekkor

P (|sup_{t∈T} ξ_{t} − E sup_{t∈T} ξ_{t}| > u) ≤ 2e^{−u^{2}/2σ^{2}} minden u > 0 számra.

Szudakov egyenlőtlensége. Legyen adva m darab ξ_{1}, …, ξ_{m} normális valószínűségi változó, amelyekre Eξ_{j} = 0, és E(ξ_{j} − ξ_{k})^{2} ≥ a^{2} minden 1 ≤ j < k ≤ m indexpárra valamely a > 0 számmal. Ekkor

E sup_{1≤j≤m} ξ_{j} ≥ \frac{a}{L}\sqrt{log m}

valamely univerzális L > 0 számmal.

A Tétel A bizonyítása. Legyen η_{t} = ξ_{t} − ξ_{t_{l}}, ha t ∈ H_{l}, és Y_{l} = sup_{t∈H_{l}} η_{t}. Ekkor

sup_{t∈H_{l}} ξ_{t} = ξ_{t_{l}} + Y_{l} = ξ_{t_{l}} + EY_{l} + (Y_{l} − EY_{l}) ≥ ξ_{t_{l}} + EY_{l} − |Y_{l} − EY_{l}| ≥ ξ_{t_{l}} + EY_{l} − V,

ahol V = max_{1≤l≤m} |Y_{l} − EY_{l}|. Innen

sup_{t∈H} ξ_{t} = max_{1≤l≤m} sup_{t∈H_{l}} ξ_{t} ≥ max_{1≤l≤m} ξ_{t_{l}} + min_{1≤l≤m} EY_{l} − V,

és várható értéket véve

E sup_{t∈H} ξ_{t} ≥ E max_{1≤l≤m} ξ_{t_{l}} + min_{1≤l≤m} EY_{l} − EV.

Továbbá E max_{1≤l≤m} ξ_{t_{l}} ≥ \frac{a}{L_{1}} \sqrt{log m} a Szudakov egyenlőtlenség alapján, min_{1≤l≤m} EY_{l} =

min_{1≤l≤m} E sup_{t∈T_{l}} ξ_{t}, mert E sup_{t∈T_{l}}(ξ_{t}−ξ_{t_{l}}) = E sup_{t∈T_{l}} ξ_{t}, és Ledoux koncentrációs egyenlőtlensége

alapján EV ≤ Lσ\sqrt{log m}, mert P (V > u) ≤ min (1, 2me^{−u^{2}/2σ^{2}}), és EV = ∫_{0}^{∞} P (V > u) du.

A Tétel B bizonyítását, amely egy meglehetősen bonyolult teljes indukciós eljáráson alapul elhagyom, csak néhány kommentárt fűzök hozzá. A tételben szereplő particiósorozatot bizonyos optimalitási tulajdonságokat figyelembe vevő mohó algoritmussal kapjuk meg, és ez egy meglehetősen implicit eljárást ad. Ezért a bizonyítás nem ad effektív, konstruktív módszert egy jó particiósorozat megtalálására. A bizonyítás fő nehézségét annak az indukciós állításnak a megfogalmazása és igazolása jelenti, amelyből következik a tétel állítása.

A Talagrand könyvben szereplő Tétel B valójában az itt megfogalmazott állításnál általánosabb eredményt tartalmaz. Ott az van bebizonyítva, hogy ha az F (A), A ⊂ T, funkcionál (sőt az általános esetben nem feltétlenül egy F funkcionált, hanem esetleg egy F_{n}, n = 1, 2 …, funkcionálsorozatot tekintünk) egy a (7) formulához hasonló, de általánosabb tipusú egyenlőtlenséget teljesít, akkor abból egy a (8) formulához hasonló explicit módon megfogalmazott egyenlőtlenség következik. Számunkra ennek az általánosabb eredménynek a következő speciális esete lesz különösen fontos. Ha

F ( ⋃_{1≤l≤m} H_{l}) ≥ c2^{(n+1)p/α}a^{p} + min_{1≤l≤m} F (H_{l}).  (9)

valamilyen 2 ≥ p ≥ 1 és 2 ≥ α ≥ 1 számokkal, (és a H_{l} halmazok teljesítik az egy metrikus téren adott funkcionálokra bevezetett növekedési tulajdonság definiciójában szereplő feltételeket), akkor

sup_{t∈T} ∑_{n=0}^{∞} c2^{np/α}Δ^{p}(A_{n}(t)) ≤ Lr^{p}(F (T) + cΔ^{p}(T))  (10)

alkalmas univerzális L > 0 konstanssal és egy olyan A_{0} ⊂ A_{1} ⊂ A_{2} ⊂ ⋯ particiósorozattal, amelyre a A_{n} partició elemszáma kisebb, mint 2^{2^{n+τ}}.

A (9) és (10) formulában megfogalmazott eredményt fogjuk alkalmazni a számunkra fontos, később tárgyalandó ellipszoid tétel bizonyításában, amely a (11) képletben bevezetett γ_{α,p}(T, d) mennyiségre ad felső becslést bizonyos speciális (T, d) terekben. Ez az eredmény teszi lehetővé, hogy bizonyos feladatokban jó becslést adjunk a minket érdeklő γ_{2}(T, d) mennyiségre is. Az ellipszoid tétel bizonyításában a Tételt B-t fordított szereposztásban alkalmazzuk, mint a Gauss mezők szuprémumának várható értékére adott alsó becslés bizonyításában. Itt a γ_{α,p}(T, d) kifejezésre akarunk felső becslést adni, és ennek érdekében egy jó, a (9) formulát teljesítő F funkcionált keresünk. Ezután a (10) formula segítségével kapunk jó felső becslést a γ_{α,p}(T, d) kifejezésre.

A tárgyalt eredmények alkalmazása, az Ajtai–Komlós–Tusnády tétel bizonyítása.

Jelölje ℓ^{2} a t = (t_{1}, t_{2}, …), ∑_{j=1}^{∞} t_{j}^{2} < ∞, sorozatokból álló Hilbert teret, legyen adva

független standard normális valószínűségi változók egy g_{1}, g_{2} … sorozata, és definiáljuk

minden t = (t_{1}, t_{2}, …) ∈ ℓ^{2} pontra az X_{t} = ∑_{k=1}^{∞} t_{k}g_{k} valószínűségi változót. Adva egy

T ⊂ ℓ^{2} halmaz meg akarjuk becsülni az E sup_{t∈T} X_{t} várható értéket. Az általános fel-

adat arról, hogy becsüljük meg Gauss valószínűségi változók szuprémumának a várható értékét visszavezethető erre a problémára. A most megfogalmazott kérdés valójában ekvivalens a γ_{2}(T, d) mennyiség becslésével, ahol d az L_{2} norma által definiált metrika az ℓ^{2} térben.

A γ_{2}(T, d) becslése nehéz feladat az általános esetben. Viszont e mennyiség nagyságrendje explicite megadható, ha T a következő E = E(a_{1}, a_{2}, …) alakú ellipszoid.

E = E(a_{1}, a_{2}, …) = \{t = (t_{1}, t_{2}, …): ∑_{k=1}^{∞} \frac{t_{k}^{2}}{a_{k}^{2}} ≤ 1\}  (11)

valamely a_{1}, a_{2}, … pozitív számokkal. Feltesszük, hogy a (11) formulában szereplő a_{k} ≥ 0 együtthatók között minden A > 0 számra csak véges sok olyan a_{k} szám van, amelyre a_{k} > A.

Sok fontos probléma megoldásában nem elegendő a γ_{2}(T, d) becslése ilyen T = E ellipszoidokra, hanem a γ_{2}(T, d) mennyiséget olyan T ⊂ E alakú halmazokra kell megbecsülni, amelyek lényegesen kisebbek, mint az E halmaz. Például véges sok elemből álló T halmazokat kell tekintenünk. Az ilyen kérdések vizsgálata érdekében hasznosnak bizonyult a következő mennyiség bevezetése és vizsgálata:

γ_{α,p}(T, d) = (inf sup_{t∈T} ∑_{n≥0} (2^{n/α}Δ(A_{n}(t))^{p})^{1/p} α > 0, p > 0  (12)

ahol az infimum az összes megengedett particiósorozatra vétetik fel. A legfontosabb eset (a p = 1 paraméter mellett) a p = 2 eset. Ilyen választással jó becslést tudunk adni a γ_{α,2}(E, d) mennyiségekre, ahol E egy a (11) formulában definiált ellipszoid. De sok érdekes esetben γ_{2}(E, d) = γ_{2,1}(E, d) = ∞, és annak érdekében, hogy jó becslést kapjunk a γ_{2}(T, d) mennyiségre egy véges sok elemből álló T ⊂ E alakú halmazra, olyan minél kisebb α ≥ 1 számot keresünk, amelyre γ_{α,2}(E, d) < ∞.

Az előbb említett probléma jelenik meg akkor is, ha egyforma eloszlású, független valószínűségi változók összegeiként megjelenő valószínűségi változók szuprémának a várható értékét becsüljük meg az (6) formula segítségével. Itt a γ_{2}(F, d_{2}) mennyiségen kívül a γ_{1}(F, d_{∞}) mennyiséget is meg kell becsülni. De az igazi nehézséget az első mennyiség becslése okozza. A következő lemmában, illetve annak következményében megmutatjuk, hogyan vezet az Ajtai–Komlós–Tusnády tétel Talagrand féle átfogalmazásának a vizsgálata egy γ_{2}(T, d), T ⊂ E, alakú kifejezés becslésének a vizsgálatához.

Lemma korlátos deriváltakkal rendelkező függvények tulajdonságairól. Legyen f(x, y) olyan kétváltozós függvény, amelyre |\frac{∂f}{∂x} | ≤ 1, |\frac{∂f}{∂y} | ≤ 1, és f(x, 0) = f(x, 1),

0 ≤ x ≤ 1, f(0, y) = f(1, y), 0 ≤ y ≤ 1. Ekkor az f(x, y) = ∑ c(j, k)e^{2πi(jx+ky)}, Fourier sor c(j, k) együtthatói teljesítik a ∑_{−∞<j,k<∞}(j^{2} + k^{2})|c(j, k)|^{2} ≤ \frac{1}{2π^{2}} egyenlőtlenséget.

Ez a becslés akkor is érvényben marad, ha az f(x, y) függvény differenciálhatósági feltételeit a következő némileg gyengébb feltétellel helyettesítjük. Az f(x, y) függvény, mint az y változó függvénye abszolut folytonos majdnem minden x-re, és mint az x változó függvénye abszolut folytonos majdnem minden y-ra. Továbbá e függvény majdnem mindenütt létező parciális deriváltjai majdnem minden x és y pontra teljesítik a |\frac{∂f}{∂x} | ≤ 1 és |\frac{∂f}{∂y} | ≤ 1 egyenlőtlenségeket. Ezek a feltételek teljesülnek, ha f(x, y) Lipschitz 1 függvény.

Bizonyítás: Számítsuk ki \frac{∂f}{∂x} Fourier együtthatóit, és alkalmazzuk e függvény Fourier sorára a Parseval formulát. Parciális integrálással

c(−j, −k) = ∫ e^{2πi(jx+ky)}f(x, y) dx dy = −\frac{1}{2πij} ∫ e^{2πi(jx+ky)} \frac{∂f(x, y)}{∂x} dx dy,

ha j ≠ 0, ahonnan ∑_{−∞<j,k<∞} 4π^{2}j^{2}|c(j, k)|^{2} ≤ ∫ (\frac{∂f(x,y)}{∂x})^{2} dx dy ≤ 1. (Az utolsó becs-

lés első egyenlőtlenségében azért nem írhatunk azonosságot, mert a \frac{∂f(x,y)}{∂x} függvény C(0, k) alakú Fourier együtthatói helyett nullát írtunk.) Hasonlóan

∑_{−∞<j,k<∞} k^{2}|c(j, k)|^{2} ≤ \frac{1}{4π^{2}} ∫ (\frac{∂f(x, y)}{∂y})^{2} dx dy ≤ \frac{1}{4π^{2}} ,

és ebből a két egyenlőtlenségből következik a lemma első bekezdésének az állítása.

Ugyanez az érvelés érvényben marad a második bekezdésben megfogalmazott tulajdonságok teljesülése esetén is. Azt kell meggondolni, hogy az alkalmazott parciális deriválással kapott azonosság ekkor is érvényben marad, mert

∫_{0}^{1} \frac{∂ (e^{2πi(jx+ky)}f(x, y))}{∂x} dx = [e^{2π(jx+ky)}f(x, y)]_{0}^{1} = 0 majdnem minden y-ra

az abszolut folytonossági feltétel miatt, és hasonló módon megkapjuk a másik számunkra szükséges azonosságot az x és y változó szerepének felcserélésével. Ha f(x, y) Lipschitz 1 függvény, akkor teljesíti az abszolut folytonosságról előírt tulajdonságokat, és a parciális deriváltjai kisebbek, mint 1.

Megfogalmazom a lemma alábbi (nyilvánvaló) 1. következményét. Ez az eredmény azért hasznos a számunkra, mert ez lehetővé teszi, hogy olyan Lipschitz 1 függvényekkel is dolgozhassunk, amelyek periodikusan kiterjeszthetők Lipschitz 1 függvénnyé az egész síkon.

1. következmény. Adva egy f(x, y) Lipschitz 1 függvény az egységnégyzeten definiáljuk ennek f_{e}(x, y) periodikusan folytatható kiterjesztését a [0, 2]×[0, 2] négyzetre a következő módon: Legyen f_{1}(x, y) = f(x, y), ha 0 ≤ x, y ≤ 1, és f_{1}(x, y) = f(x, 2 − y), ha 0 ≤ x ≤ 1, és 1 ≤ y ≤ 2. Legyen ezután f_{e}(x, y) = f_{1}(x, y), ha 0 ≤ x ≤ 1 és 0 ≤ y ≤ 2, f_{e}(x, y) =

f_{1}(2 − x, y), ha 1 ≤ x ≤ 2 és 0 ≤ y ≤ 2. Ekkor f_{e}(x, y) = ∑_{−∞<j,k≤∞} c(j, k)e^{iπ(jx+ky)}

olyan c(j, k) Fourier együtthatókkal, amelyekre ∑(k^{2} + j^{2})|c(j, k)|^{2} ≤ \frac{2}{π^{2}} .

Az Ajtai–Komlós–Tusnády tétel Talagrand-féle átfogalmazásának bizonyításában hasznos lesz az 1. következmény. Vegyük ugyanis a (2) formulában tekintett az egységnégyzeten definiált Lipschitz 1 függvények C osztályának véges T ⊂ C véges részhalmazait. Szükségünk lesz egy olyan jó becslésre a T halmaztól függő γ_{2}(T, d_{2}) mennyiségre, amely csak a T halmaz számosságától függ. Ilyen becslést az alább megfogalmazott 2. következmény segítségével tudunk adni, amely könnyen látható az 1. következmény segítségével. Ennek érdekében vezessük be az

E = \{(a(j, k), b(j, k)), 0 ≤ j, k < ∞, (j, k) ≠ (0, 0), ∑_{(j,k)} \frac{a^{2}(j, k) + b^{2}(j, k)}{\frac{1}{2π^{2}(j^{2}+k^{2})}} ≤ 1\}

(13)

ellipszoidot. Ezen ellipszoid segítségével megfogalmazzuk a következő állítást.

2. következmény. Legyen T az egységnégyzeten definiált az ∫_{[0,1]×[0,1]} f(x, y) dx dy = 0 feltételt teljesítő Lipschitz 1 függvényekből álló, C függvényosztály egy véges részhalmaza. Ekkor γ_{2}(T, d_{2}) ≤ sup_{U∈E, |U|=|T |} γ_{2}(U, d), ahol E a (13) formulában definiált ellipszoid,

az egyenlőtlenség jobboldalán szereplő d a E téren definiált L_{2} norma által indukált metrikát jelöli, és |U| = |T | azt jelenti, hogy U és T elemszáma megegyezik.

Bizonyítás. Tekintsük minden f ∈ C függvénynek a 2. következményben definiált f_{e} kiterjesztését a [0, 2] × [0, 2] négyzetre, és legyen T_{e} az {f_{e}: f ∈ T } halmaz. Ekkor γ_{2}(T, d_{2}) = \frac{1}{2}γ_{2}(T_{e}, d_{2}), mert d_{2}(f, g) = \frac{1}{2}d_{2}(f_{e}, g_{e}) minden f, g ∈ C függvényre. Írjuk fel minden f_{e} ∈ T_{e} függvény

f_{e}(x, y) = ∑_{\begin{matrix}(j,k): 0≤j,k<∞, \\ (j,k)≠(0,0) \end{matrix}} [\sqrt{2}a(j, k)\frac{cos(π(jx + ky))}{\sqrt{2}} + \sqrt{2}b(j, k)\frac{sin(π(jx + ky))}{\sqrt{2}}]

Fourier sorát. Az 1. következmény alapján e Fourier sor együtthatói teljesítik az ∑(j^{2}+ k^{2})(2a^{2}(j, k) + 2b^{2}(j, k)) ≤ \frac{4}{π^{2}} egyenlőtlenséget. (Azért tértünk át a \frac{1}{\sqrt{2}} sin és \frac{1}{\sqrt{2}} cos függvényekre az e^{i(sx+ty)} alakú függvények helyett, hogy valós értékű (ortonormált) függvényekkel és együtthatókkal dolgozhassunk.) Feleltessük meg minden f függvénynek az 2a(j, k) és 2b(j, k), 0 ≤ j, k < ∞, (j, k) ≠ (0, 0) együtthatókat. Ezen együtthatók sorozata benne van a a \frac{2\sqrt{2}}{π}E ellipszoidban, ahol E-t a (13) formulában definiáltuk. Továbbá ez a leképezés izomorfia az L_{2}([0, 1] × [0, 1]) tér és a a {j, k), 0 ≤ j, k < ∞, (j, k) ≠ 0} párokkal indexezett az L_{2} normával ellátott tér között. Innen következik, hogy ha U jelöli a T_{e} halmaz képét ezen transzformáció szerint, akkor γ_{2}(T_{e}, d_{2}) ≤ γ_{2}(U, d), ezért igaz a 3. következmény.

Meg akarjuk becsülni a γ_{2}(U, d) mennyiséget véges U ⊂ E halmazokra. Nyílvánvaló, hogy γ_{2}(U, d) ≤ γ_{2}(E, d). Viszont, mint később ismertetett eredményekből látszik, γ_{2}(E, d) = ∞, ezért ilyen módon nem kapunk hasznos eredményt. Viszont hasznos a következő becslés, amely a Talagrand könyv egyik legfontosabb eredménye.

Ellipszoid tétel. Tekintsük a (11) formulában definiált E ellipszoidot. Erre az ellipszoidra a (12) formulában definiált γ_{α,p}(T, d) mennyiség p = 2 és α ≥ 1 választással valamint a szokásos Euklideszi d metrikával teljesíti a

γ_{α,2}(E, d) ≤ K(α) sup_{ε>0} ε · card {i: a_{i} ≥ ε}^{1/α}

egyenlőtlenséget egy csak az α paramétertől függő K(α) konstanssal.

Az Ajtai–Komlós–Tusnády tétel Talagrand-féle bizonyításában a (13) formulában definiált ellipszoidot kell tekintenünk. Erre card {i: a_{i} ≥ ε} ≤ const. ε^{−2}. (Azon (j, k) nem negatív egészekből álló párokat kell tekinteni, amelyekre j^{2} + k^{2} ≤ ε^{−2}.) Ezért γ_{2,2}(E, d) ≤ const. Ez a becslés segít a kívánt egyenlőtlenség bizonyításában.

Ezenkívül szükségünk van egy olyan becslésre, amely a γ_{1}(C, d_{∞}) kifejezés becslését teszi lehetővé a (6) formulában, ahol d_{∞} a szuprémum metrika az C tér elemei között. Erről szól a következő eredmény.

Tétel Lipschitz függvények L_{∞} normában sűrű hálóinak nagyságáról. Tekintsük az egységnégyzeten definiált Lipschitz 1 függvények C terét a d_{∞} szuprémum normával, és vezesük be a következő N(B, d_{∞}, ε) mennyiséget minden B ⊂ C halmazra és ε > 0 számra. N(B, d_{∞}, ε) a legkisebb elemszámú a B halmazt lefedő (a d_{∞} szuprémum norma szerint) ε sugarú gömbökből álló rendszer számossága. Ekkor minden ε > 0 számra N(C, d_{∞}, ε) ≤ e^{L/ε^{2}} valamilyen univerzális L > 0 számmal. Ebből a relációból következik, hogy (4) formulában bevezetett e_{n}(T, d) függvény T = C és d = d_{∞} választással teljesíti az e_{n}(C, d_{∞}) ≤ L2^{−n/2} egyenlőtlenséget alkalmas L > 0 konstanssal.

Bizonyításvázlat. Tekintsük egy h ∈ C függvény A(h, 2^{−k}) = {f: sup |f(x, y)−h(x, y)| ≤ 2^{−k}, f ∈ C} 2^{−k} sugarú környezetét, k = 0, 1, 2, . . .. Be lehet látni, hogy

N(A(h, 2^{−k}), d_{∞}, 2^{−(k+1)}) ≤ e^{L2^{2(k+1)}}.

Azt kell ennek érdekében felhasználni, hogy ha két f_{1} és f_{2} Lipschitz 1 tulajdonságú függvénynek a [0, 1] × [0, 1] egységnégyzetnek egy 2^{−(k+2)} szélességű rácsára vett megszorítására a szuprémum norma szerinti távolság kisebb, mint 2^{−(k+2)}, akkor

sup_{(x,y)∈[0,1]×[0,1]} |f_{1}(x, y) − f_{2}(x, y)| ≤ 2^{−(k+1)}.

Ennek az egyenlőtlenségnek a felhasználásával be lehet látni k szerinti teljes indukcióval, hogy N(C, d_{∞}, 2^{−k}) ≤ e^{2L2^{2k}} minden k = 0, 1, … számra. Innen viszont következik, hogy N(C, d_{∞}, ε) ≤ e^{L̄/ε^{2}} valamilyen univerzális L > 0 számmal számmal minden ε > 0 számra, ahonnan e_{n}(C, d_{∞}) ≤ L2^{−n/2}.

Az Ajtai–Komlós–Tusnády tétel Talagrand–féle bizonyítása. Elég belátni a (2) egyenlőtlenség érvényességét akkor, ha C a [0, 1]×[0, 1] egységnégyzeten definiált, és az egész síkra kiterjeszthető Lipschitz 1 függvények családja, és X_{1}, …, X_{N} független, a [0, 1] × [0, 1] egységyzeten egyenletes eloszlású valószínűségi változók sorozata. Sőt, azt is feltehetjük, hogy Ef(X_{1}) = 0 minden f ∈ C függvényre.

Válasszuk azt a legnagyobb m egész számot, amelyre 2^{−m} ≥ \frac{1}{N}. Ekkor az előző tétel alapján e_{m}(C, d_{∞}) ≤ L2^{−m/2} ≤ \frac{L}{\sqrt{N}}, azaz meg lehet adni a C halmazosztálynak olyan N_{m} = 2^{2^{m}} vagy annál kevesebb elemből álló olyan T = T_{N} részhalmazát, amelyre minden f ∈ C függvényre létezik olyan f̄ ∈ T függvény, hogy sup |f(x, y) − f̄(x, y)| ≤

\frac{L}{\sqrt{N}}. Ebből speciálisan az is következik, hogy | ∑_{j=1}^{N} f(X_{j}) − ∑_{j=1}^{N} f̄(X_{j})| ≤ L\sqrt{N}. Ezért

E sup_{f∈C} |∑_{j=1}^{N} f(X_{j})| ≤ E sup_{f∈T} |∑_{j=1}^{N} f(X_{j})| + L\sqrt{N},

ahonnan következik, hogy elég belátni azt, hogy

E sup_{f∈T} |\frac{1}{\sqrt{N}} ∑_{j=1}^{N} f(X_{j})| = E sup_{f∈T} S_{N}(f) ≤ L\sqrt{log N}.

Ezen egyenlőtlenség bizonyításához elég megmutatni a (6) formula alapján, hogy

γ_{2}(T, d_{2}) ≤ L\sqrt{log N}, és γ_{1}(T, d_{∞}) ≤ L\sqrt{N log N},

ahol d_{2} az L_{2} és d_{∞} az L_{∞} szuprémum norma által definiált metrika a [0, 1] × [0, 1] egységnégyzeten definiált függvények terén.

A γ_{2}(T, d_{2}) ≤ L\sqrt{log N} egyenlőtlenség bizonyításában felhasználjuk a 2. következményt. Ennek alapján elég megmutatni, hogy γ_{2}(U, d) ≤ \sqrt{log N} minden olyan U ∈ E halmazra, amelyre |U| ≤ N_{m} = 2^{2^{m}}. Itt E a (13) formulában definiált ellipszoidot jelöli. Viszont γ_{2,2}(U, d) ≤ γ_{2,2}(E, d) ≤ L egy univerzális L > 0 számmal. Ez azt jelenti, hogy létezik az U halmaznak egy olyan megengedett A_{0} ⊂ A_{1} ⊂ ⋯ ⊂ A_{m} particiósorozata, amelyre

∑_{n=0}^{m−1} (2^{n/2}Δ(A_{n}(t)))^{2} ≤ L minden t ∈ U pontra.

(Mivel |U| ≤ N_{m}, feltehetjük, hogy a megengedett particiósorozat legfeljebb m különbőző particióból áll, mert A_{n} = A_{m}, ha n ≥ m, és az m-ik partició csupa 1 elemű, tehát nulla átmérőjű halmazból áll. Ezért Δ(A_{n}(t)) = 0, ha n ≥ m.) Innen a Cauchy–Schwarz egyenlőtlenség alapján

∑_{n=0}^{m−1} 2^{n/2}Δ(A_{n}(t)) ≤ \sqrt{m} (∑_{n=1}^{m} (2^{n/2}Δ(A_{n}(t)))^{2})^{1/2}
≤ L\sqrt{m} ≤ L\sqrt{log N} minden t ∈ U pontra,

ahonnan γ_{2}(U, d) ≤ L\sqrt{log N}, tehát a 2. következmény alapján γ_{2}(T, d_{2}) ≤ L\sqrt{log N}.

Másrészt, adva egy (T, d) metrikus tér, definiáljuk a következő γ_{α}(T, d)-hez hasonló mennyiséget. Tekintsünk olyan T_{0}, T_{1}, … halmazokat, amelyekre |T_{n}| ≤ N_{n}, és T_{n} ⊂ T. A γ_{α}(T, d) mennyiséghez hasonlóan definálhatjuk a γ̄_{α}(T, d|T_{0}, T_{1}, …) = sup_{t∈T} ∑_{0≤n<∞} 2^{n/α}d(t, T_{n}) kifejezéseket, (illetve vehetjük ezek γ̄_{α}(T, d) infimumát az összes

a feltételeknek eleget tevő T_{0}, T_{1}, … sorozatra). Bár itt nem tárgyaltam, a Talagrand könyvben be van bizonyítva, hogy γ_{α}(T, d) ≤ K(α)γ̄_{α}(T, d|T_{0}, T_{1}, …) egy csak az α paramétertől függő K(α) > 0 konstanssal. Ezt az eredményt fogom használni az alábbiakban. Ennek alapján elég a γ_{1}(T, d_{∞}) mennyiség helyett a γ̄_{1}(T, d_{∞}|T_{0}, T_{1}, …) mennyiségre adni jó becslést alkalmas T_{0}, T_{1}, ⋯ ⊂ T halmazokkal.

Válasszuk a T halmaz olyan T_{n} részhalmazait, amelyekre sup_{t∈T} d_{∞}(t, T_{n}) ≤ L2^{−n/2},

és |T_{n}| ≤ N_{n}, ha 0 ≤ n ≤ m. Ez az előző tétel szerint lehetséges. Legyen T_{n} = T, ha n ≥ m. Ilyen választással

γ_{1}(T, d_{∞}) ≤ Kγ̄_{1}(T, d_{∞}|T_{0}, T_{1}, …) ≤ K ∑_{n=0}^{m} 2^{n} sup_{t∈T} d_{∞}(t, T_{n})

≤ KL ∑_{n=0}^{m} 2^{n/2} ≤ KL(\sqrt{2} + 1)2^{m/2} ≤ L̄\sqrt{N}.

Ez azt jelenti, hogy γ_{1}(T, d_{∞}) ≤ L̄\sqrt{N}, ami a kívántnál kissé élesebb becslés.

Nyílt probléma.

Legyen g(x, y) sűrűségfüggvény a [0, 1] × [0, 1] egységnégyzeten, X_{1}, …, X_{N} független valószínűségi változók sorozata g(x, y) sűrűségfüggvénnyel, és Y_{1}, …, Y_{N} a g(x, y) sűrűségfüggvény által meghatározott mérték szerint egyenletesen elhelyezett pontok. (Ez azt jelenti, hogy az Y_{l}, 1 ≤ l ≤ N, pontokba \frac{1}{N} tömeget elhelyezve, ezek átszállíthatóak a g(x, y) sűrűségfüggvény által meghatározott mérték szerinti eloszlásba úgy, hogy a szállítási útvonal hosszának várható értéke kisebb, mint const. \sqrt{N}.) Létezik-e mindig az {1, 2, …, N} halmaznak az

E (∑_{j=1}^{N} d(X_{π(j)}, Y_{j})) ≤ L\sqrt{N log N}

egyenlőtlenséget valamely univerzális L > 0 konstanssal teljesítő π permutációja, vagy ehhez szükséges bizonyos megkötéseket tenni a g(x, y) sűrűségfüggvény tulajdonságairól?

Az ellipszoid tétel bizonyításának hátteréről.

Az ellipszoid tétel bizonyításában fontos szerepet játszik az alábbi egyszerű lemma, amely annak a valós számokból álló végtelen sorozatok terén definiált normának a geometriai tulajdonságairól szól, amely szerint a (11) formulában definiált ellipszoid az egységgömb. Tekintsük a (11) formulában bevezetett E ellipszoidot, és vezessük be a

következő ∥ · ∥_{E} normát a t = (t_{1}, t_{2}, …) sorozatok terén. Legyen ∥t∥_{E}^{2} = ∑_{k=1}^{∞} \frac{t_{k}^{2}}{a_{k}^{2}} , ha

t = (t_{1}, t_{2}, …), és az a_{k} constansok megegyeznek a E ellipszoid definiciójában szereplő a_{k} konstansokkal.

Lemma végtelen sorozatok terén definiált L_{2} normák tulajdonságairól. Legyen x = (x_{1}, x_{2}, …) és y = (y_{1}, y_{2}, …) két olyan sorozat, amelyekre ∥x∥_{E} ≤ 1 és ∥y∥_{E} ≤ 1. Ekkor

∥\frac{x + y}{2} ∥_{E} ≤ 1 − \frac{∥x − y∥_{E}^{2}}{8} .

Bizonyítás.

∥x + y∥_{E}^{2} + ∥x − y∥_{E}^{2} = 2∥x∥_{E}^{2} + 2∥y∥_{E}^{2} ≤ 4,

ahonnan

∥\frac{x + y}{2} ∥_{E} ≤ (1 − \frac{1}{4}∥x − y∥_{E}^{2})^{1/2} ≤ 1 − \frac{1}{8}∥x − y∥_{E}^{2}.

Az ellipszoid tétel egy olyan általánosabb tétel következményeként adódik, amely olyan norma által indukált távolságggal rendelkező terekkel foglalkozik, amely norma egy az előző lemmához hasonló tulajdonsággal rendelkezik. Ezért bevezetjük a következő definiciót.

p-konvex Banach terek definiciója. Egy Banach teret valamely ∥ · ∥ normával pkonvexnek nevezünk p ≥ 1 kitevővel és η paraméterrel, ha e Banach tér minden olyan x, y vektorára, amelyekre ∥x∥ ≤ 1 és ∥y∥ ≤ 1

∥\frac{x + y}{2} ∥ ≤ 1 − η∥x − y∥^{p}, p ≥ 1.

A következő tétel érvényes p-konvex Banach terekre.

Tétel p-konvex terekben való becslésekről. Legyen T egy η paraméterrel rendelkező p-konvex tér, 1 ≤ p ≤ 2, egységgömbje. Tekintsünk egy másik ∥ · ∥_{1} normát ezen a Banach téren. Ekkor minden 1 ≤ α ≤ 2 számra

γ_{α,p}(T, d) ≤ K(α, p, η) sup_{0≤n<∞} 2^{n/α}e_{n}(T, d)

valamely K(α, p, η) > 0 csak az α, p és η paraméterektől függő számmal, ahol γ_{α,p}(T, d) a (12) formulában és e_{n}(T, d) a (4) formulában definiált kifejezés a T (a p-konvex Banach tér normája szerinti) egységgömbbel és a ∥ · ∥_{1} norma által indukált d távolsággal.

Az ellipszoid tétel a fenti p-konvex terekben való becslésekről szóló tétel következményeként kapható meg, ha azt a t = (t_{1}, t_{2}, …) végtelen sorozatokból álló Hilbert térre alkalmazzuk a ∥ · ∥_{E} normával (ez az előző lemma szerint p-konvex Banach tér p = 2

választással és η = \frac{1}{8} paraméterrel) és a hagyományos ∥t∥^{2} = ∑_{k=1}^{∞} t_{k}^{2} normát választjuk

a ∥ · ∥_{1} normának. Az ellipszoid tétel bizonyításához még egy eredmény szükséges a ∥ · ∥_{E} norma és az annak definiciójában szereplő a_{k} konstansok kapcsolatáról.

Tétel a ∥ · ∥_{E} norma és az annak definiciójában szereplő a_{k} konstansok kapcsolatáról. Az E ellipszoidot a (11) formulában definiáló a_{k} sorozat legyen monoton csökkenő. Ekkor

e_{n}(E, d) ≥ \frac{1}{2}a_{2^{n}} és e_{n+3}(E, d) ≤ 3 max_{1≤k≤n} a_{2^{k}}2^{k−n},

ahol e_{n}(E, d) a (4) formulában van definiálva, és d a szokásos ∥t∥^{2} = ∑_{k=1}^{∞} t_{k}^{2}, ha t =

(t_{1}, t_{2}, …) Hilbert-térbeli norma által definiált metrika.

Az ellipszoid tétel bizonyítása az előző eredmények alapján. Alkalmazzuk a p-konvex terekben való becslésekről szóló tételt a ∥ · ∥_{E} normával, melynek a (11) formulában

definiált E ellipszoid az egységgömbje, és a ∥ · ∥_{1} norma legyen ∥t∥_{1}^{2} = ∑_{k=1}^{∞} t_{k}^{2}, ha t =

(t_{1}, t_{2}, …). Azt kapjuk, hogy

γ_{α,2}(E, d) ≤ K(α) sup_{0≤n<∞} 2^{n/α}e_{n}(E, d).

Az E ellipszoid definiciójában szereplő t_{k} változók indexeinek esetleges átrendezésével feltehetjük, hogy az a_{k} konstansok monoton csökkennek. Ez lehetővé teszi a 2^{n/α}e_{n}(E, d) mennyiség becslését a ∥ · ∥_{E} norma és az annak definiciójában szereplő a_{k} konstansok kapcsolatáról szóló tétel segítségével. Azt kapjuk, hogy

2^{n/α}e_{n}(E, d) ≤ 3 max_{1≤k≤n−3} 2^{k/α}2^{(k−n)(1−1/α)}a_{2^{k}} ≤ C max_{1≤k≤n} 2^{k/α}a_{2^{k}},

mert (k − n)(1 − 1/α) ≤ 0, ha k ≤ n és α ≥ 1. Innen

γ_{α,2}(E, d) ≤ K̄(α) sup_{0≤n<∞} 2^{n/α}a_{2^{n}}.

Az a_{i} sorozat monotonitását kihasználva ε = a_{2^{n}} választással azt kapjuk, hogy card {i: a_{i} ≥ ε} ≥ 2^{n}, ezért ε (card {i: a_{i} ≥ ε})^{1/α} ≥ 2^{n/α}a_{2^{n}}. Innen,

γ_{α,2}(E, d) ≤ K̄(α) sup_{0≤n<∞} 2^{n/α}a_{2^{n}} ≤ K̄(α) sup_{ε>0} ε (card {i: a_{i} ≥ ε})^{1/α} .

A p-konvex terekben való becslésekről szóló tétel bizonyításának alapgondolata. A bizonyítás a Tétel B egy itt ki nem mondott általánosabb változatát használja. Ebben az általánosításban egy metrikus téren adott funkcionálok növekedési tulajdonságát kissé általánosabban definiáljuk. Ugyanolyan tulajdonságú t_{l} pontokat és H_{l} halmazokat tekintünk, de a (7) reláció helyett azt követeljük meg, hogy az F funkcionál az

F ( ⋃_{1≤l≤m} H_{l}) − min_{1≤l≤m} F (H_{l}) ≥ h(n, a)  (14)

egyenlőtlenséget teljesítse valamilyen alkalmas h(n, a) függvénnyel. A speciális h(n, a) = ca2^{(n+1)/2} választás a (7) formulát adja. Az általános esetben a növekedési tulajdonság teljesülése valamely h(n, a) függvénnyel a (8) formula egy változatát implikálja, amely-

ben a sup_{t∈T} ∑_{n=1}^{∞} c2^{n/2}Δ(A_{n}(t)) összeg helyett egy hasonló, de a h(n, a) függvénytől függő

kifejezés szerepel. Célunk a (14) formula bizonyítása olyan F funkcionállal és h(n, a) függvénnyel, amelyre a Tétel B általános alakja a p-konvex terekben való becslésekről szóló tétel eredményét adja.

A következő a T egységgömb részhalmazain definiált F funkcionál segítségével próbáljuk belátni a tételt.

F (A) = 1 − inf{∥v∥: v ∈ conv A}, A ⊂ T.

Itt és a továbbiakban conv A az A halmaz konvex burkát jelöli.

Ezzel az F funkcionállal és alkalmas h(n, a) függvénnyel próbáljuk belátni a (14) relációt. Az ellenőrizendő reláció megfogalmazása érdekében rögzítünk egy n pozitív egész és egy valós a > 0 számot, majd tekintünk m = N_{n+2} olyan t_{1}, …, t_{m} ∈ T pontot, amelyekre d(t_{l}, t_{l′}) ≥ a, ha 1 ≤ l, l′ ≤ m, és l ≠ l′, (τ = 1 választással dolgozunk) valamint H_{l} ∈ T ∩ B_{d}(t_{l}, \frac{a}{r}), 1 ≤ l ≤ m, halmazokat valamilyen elég nagy r ≥ 4 számmal. (A funkcionálok növekedési tulajdonságának ellenőrzésekor kell ilyen objektumokat tekinteni. Itt nem írjuk elő, hogy a t_{l}, 1 ≤ l ≤ m, pontok mindegyike egy rögzített B_{d}(s, ar) gömbben feküdjön.) A d metrika a fenti definiciókban a ∥ · ∥_{1} norma által definiált távolság.

Legyen

u = inf {∥v∥: v ∈ conv (⋃_{l=1}^{m} H_{l})} = 1 − F (⋃_{l=1}^{m} H_{l}) ,

és válasszunk egy olyan u′ számot, amelyre

u′ > max_{1≤l≤m} inf{∥v∥: v ∈ conv H_{l}} = 1 − min_{1≤l≤m} F (H_{l}).

A (14) formula bizonyításában jó becslést adunk az u′ − u különbségre egy alkalmas h(n, a) függvénnyel. Ennek érdekében először az e_{n}(T, d) mennyiségre adunk alsó becslést (a ∥ · ∥_{1} norma által meghatározott d távolsággal) az u′ − u és a paraméterek segítségével.

Válasszunk olyan v_{l} ∈ conv H_{l}, 1 ≤ l ≤ m, pontokat, amelyekre ∥v_{l}∥ ≤ u′′ = min(u′, 1). Ilyen v_{l} pontok léteznek. Olyan v_{l} ∈ conv H_{l} pontokat kell választani, amelyekre ∥v_{l}∥ elég közel van az inf{∥v∥: v ∈ conv H_{l}} mennyiséghez. Ekkor a p-konvex tulajdonság miatt

∥\frac{v_{l} + v_{l′}}{2u′′} ∥ ≤ 1 − η ∥\frac{v_{l} − v_{l′}}{u′′} ∥^{p} ,

és mivel \frac{v_{l}+v_{l′}}{2} ∈ conv ( ⋃_{j=1}^{m} H_{j}), \frac{u}{u′′} ≤ ∥\frac{v_{l}+v_{l′}}{2u′′} ∥ minden 1 ≤ l, l′ ≤ m indexre. Ezért

\frac{u}{u′′} ≤ 1 − η ∥\frac{v_{l} − v_{l′}}{u′′} ∥^{p} ,

Innen azt kapjuk (l′ = 1 választással), hogy mivel p ≥ 1

∥v_{l} − v_{1}∥ ≤ u′′ (\frac{u′′ − u}{ηu′′})^{1/p} ≤ (\frac{u′′ − u}{η})^{1/p} ≤ (\frac{u′ − u}{η})^{1/p} .

Legyen R = (\frac{u′−u}{η})^{1/p}. Ekkor a w_{l} = \frac{v_{l}−v_{1}}{R}, 1 ≤ l ≤ m, pontok mindegyikére ∥w_{l}∥ ≤ 1, azaz w_{l} ∈ T. Továbbá, mivel a v_{l} pontok konstrukciójából és a H_{l} halmazok tulajdonságaiból adódik, hogy d(v_{l}, v_{l′}) ≥ \frac{a}{2}, ha l ≠ l′, és a d távolság egy normából származik, ezért d(w_{l}, w_{l′}) ≥ \frac{a}{2R} minden 1 ≤ l, l′ ≤ m, és l ≠ l′ számra. Ez viszont azt jelenti, hogy e_{n+1}(T, d) ≥ \frac{a}{4R}. Valóban, ha vesszük a T halmaz tetszőleges b < \frac{a}{4R} sugarú gömbökkel való fedését, akkor a w_{l} pontok mindegyike különbőző gömbben van, ezért a fedő gömbök száma legalább m = N_{n+2}, ezért e_{n+1}(T, d) ≥ b.

Az e_{n+1}(T, d) ≥ \frac{a}{4R} egyenlőtlenségből azt kapjuk, hogy u′ − u ≥ η (\frac{a}{4e_{n+1}(T,d)})^{p}. Felhasználva az u és u′ mennyiségek definicióját, illetve szabadságunkat az u′ megválasztásában azt kapjuk, hogy

F ( ⋃_{1≤l≤m} H_{l}) − min_{1≤l≤m} F (H_{l}) ≥ η (\frac{a}{4e_{n+1}(T, d)})^{p} .

Ez egy (14) tipusú egyenlőtlenség speciális h(n, a) = η (\frac{a}{4e_{n+1}(T,d)})^{p} függvénnyel.

Vezessük be az S = sup_{n≥1} 2^{n/α}e_{n}(T, d), és c = \frac{η}{(4S)^{p}} mennyiségeket. Ezen kifejezések

segítségével felírhatjuk az utolsó egyenlőtlenség alábbi következményét.

F ( ⋃_{1≤l≤m} H_{l}) − min_{1≤l≤m} F (H_{l}) ≥ c2^{(n+1)p/α}a^{p}.

A Tétel B általánosabb alakjából, pontosabban annak a (8) és (9) formulában megfogalmazott következményéből és a tekintett F funkcionál néhány könnyen ellenőrizhető tulajdonságából kapjuk, hogy

sup_{t∈T} ∑_{n=0}^{∞} c2^{np/α}Δ^{p}(A_{n}(t)) ≤ C(α, p, η).

Mivel

∑_{n=0}^{∞} c2^{np/α}Δ^{p}(A_{n}(t)) = \frac{η}{(4S)^{p}} ∑_{n=0}^{∞} (2^{n/α}Δ(A_{n}(t)))^{p} ,

ebből az egyenlőtlenségből, illetve az S mennyiség definiciójából (némi extra munkával) következik a tétel állítása.

A γ_{2}(E, d) becslése egy hiperboloidra.

A γ_{2}(E, d) mennyiség értékét egy a (11) formában definiált E hiperboloidra egy univerzális konstans szorzó erejéig pontosan meg lehet adni. Nevezetesen a (11) formulában definiált E ellipszoidra

\frac{1}{L} (∑_{k=1}^{∞} a_{k}^{2})^{1/2} ≤ γ_{2}(E, d) ≤ L (∑_{k=1}^{∞} a_{k}^{2})^{1/2}  (15)

egy univerzális L > 0 számmal. Ennek az egyenlőtlenségnek a bizonyítása egyszerű,

ha a γ_{2}(E, d) helyett a vele azonos nagyságrendű E ( sup_{t=(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} t_{k}g_{k}) kifejezést

becsüljük meg, ahol g_{1}, g_{2}, … független, standard normális eloszlású valószínűségi változók sorozata.

Felírhatjuk, hogy

E ( sup_{t=(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} t_{k}g_{k})^{2} = E (  sup_{t=(t_{1},t_{2},...): ∑_{k=1}^{∞}(\frac{t_{k}}{a_{k}} )^{2}≤1} ∑_{k=1}^{∞} \frac{t_{k}}{a_{k}} (a_{k}g_{k}))^{2}

= E ∑_{k=1}^{∞} a_{k}^{2}g_{k}^{2} = ∑_{k=1}^{∞} a_{k}^{2},

mivel a baloldalon a várható értéken belül szereplő összeg rögzített g_{1}(ω), g_{2}(ω), … értékekre a \frac{t_{k}}{a_{k}} = _{\frac{a_{k}g_{k}}{(∑_{k=1}^{∞} a_{k}^{2}g_{k}^{2})^{1/2}}} , k = 1, 2, …, helyen veszi fel a maximumát. Innen

és a Schwarz egyenlőtlenségből adódik, hogy E ( sup_{t=(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} t_{k}g_{k}) ≤ ( ∑_{k=1}^{∞} a_{k}^{2})^{1/2}.

Ledoux normális valószínűségi változók maximumáról szóló koncentrációs egyenlőtlensé-

ge segítségével meg lehet mutatni, hogy az E ( sup_{t=(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} t_{k}g_{k}) ≥ C ( ∑_{k=1}^{∞} a_{k}^{2})^{1/2}

alsó becslés is érvényes alkalmas C > 0 konstanssal. Azt kell észrevenni, hogy ezen eredményből következik, hogy a tekintett szuprémum várható értéke nem lehet sokkal kisebb, mint a második momentumának négyzetgyöke. Ugyanis ezen eredmény alapján

E ( sup_{(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} t_{k}g_{k} − E ( sup_{(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} t_{k}g_{k}))^{2} ≤ 2 sup_{(t_{1},t_{2},...)∈E} E (∑_{k=1}^{∞} t_{k}g_{k})^{2}

= 2 sup_{(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} t_{k}^{2} = 2 sup_{(t_{1},t_{2},...)∈E} ∑_{k=1}^{∞} (\frac{t_{k}}{a_{k}} )^{2} a_{k}^{2} ≤ 2 sup_{1≤k<∞} a_{k}^{2} ≤ 2 ∑_{k=1}^{∞} a_{k}^{2}.

A (15) formula azt adja az Ajtai–Komlós–Tusnády tétel bizonyításában szereplő (13) formulában definiált E ellipszoidra, hogy γ_{2}(E, d) = ∞. Ez magyarázatot ad arra, hogy miért kellett a bizonyításban a γ_{1,2}(E, d) mennyiséget becsülni a γ_{2}(E, d) kifejezés helyett.

Ki lehet számolni a Dudley becslésében fellépő ∑_{n=0}^{∞} 2^{n/2}e_{n}(E, d) menyiség pontos

nagyságrendjét is (konstans szorzó erejéig) egy a (11) formulában definiált ellipszoidra. A számolás legfontosabb lépése a ∥ · ∥_{E} norma és az annak definiciójában szereplő a_{k} konstansok kapcsolatáról szóló korábban megfogalmazott tétel bizonyítása. Ennek az eredménynek az összehasonlítása a γ_{2}(E, d) kifejezére adott becsléssel szintén megmutatja, hogy bizonyos esetekben Talagrand becslése normális eloszlású valószínűségi változók maximumának a várható értékéről lényegesen jobb, mint Dudley becslése. De mivel erre az eredményre itt nincs szükségünk, ezért ennek tárgyalását elhagyom.