Koncentracja Miary

Rafał Latała

22 maja 2009

Poniższe notatki powstają na podstawie (wybranych) wykładów z Koncentracji Miary, prowadzonych w semestrze wiosennym 2008/09.

Przepraszam za wszystkie nieścisłości i omyłki mogące pojawić się w tekście i jednocześnie zwracam się z prośbą do czytelników, którzy zauważyli błędy lub mają jakieś inne uwagi na temat notatek o kontakt mailowy na adres rlatala@mimuw.edu.pl z podaniem wersji notatek (daty) do której chcą się ustosunkować.

Dziękuje panom Kamilowi Kosińskiemu i Piotrowi Nayarowi za nadesłane komentarze.

Rafał Latała

1 Wprowadzenie

Zacznijmy od następującej definicji otoczki zbioru.

Definicja 1.1. Niech (X, d) będzie przestrzenią metryczną, zaś A dowolnym podzbiorem X. Dla t > 0 określamy t-otoczenie zbioru A wzorem

A_{t} := {x ∈ X: d(x, A) < t} = ⋃_{y∈A} B(y, t),

gdzie B(y, t) oznacza kulę otwartą w X o środku w y i promieniu t.

Okazuje się, że dla wielu ważnych przykładów miar probabilistycznych μ na (X, d) miara μ(A_{t}) szybko zbiega do 1 jeśli tylko μ(A) 1/2. Badanie tego zjawiska, zwanego fenomenem koncentracji miary i jego konsekwencji będzie celem tego wykładu.

Na początek wykładu podamy kilka przykładów, których dowody przedstawimy później.

Przykład 1. Niech d oznacza odległość geodezyjną na n wymiarowej sferze S^{n} = {x ∈ ℝ^{n+1} : |x| = 1}, zaś σ_{n} oznacza unormowaną miarę powierzcniową na S^{n}. Wówczas okazuje się, że jeśli chcemy zminimalizować σ_{n}(A_{t}) po wszystkich zbiorach ustalonej miary ekstremalne są kule (zwane też czapeczkami), to znaczy

σ_{n}(A) = σ_{n}(B(x_{0}, r)) ⇒ σ_{n}(A_{t}) σ_{n}(B(x_{0}, r)_{t}) = σ_{n}(B(x_{0}, r + t)).

W szczególności jeśli σ_{n}(A) 1/2, to

σ_{n}(A_{t}) σ_{n}(B(x_{0}, \frac{π}{2} + t) ) 1 − exp( − \frac{(n − 1)t^{2}}{2} ).

Wprowadźmy kluczową definicję:

Definicja 1.2. Niech μ będzie miarą probabilistyczną na (X, d). Funkcją koncentracji miary μ definiujemy jako

α_{μ}(t) = α_{(X,d,μ)} (t) := sup\{1 − μ(A_{t}): μ(A) \frac{1}{2}\}.

Zatem α_{σ_{n}} (t) exp(−\frac{n−1}{2} t^{2}).

Uwaga. Zauważmy, że funkcja koncentracji σ_{n} szybko zbiega do 0 przy n → ∞. Jedną z przyczyn tego zjawiska jest to, że miara ta nie jest dobrze unormowana. Jeśli przez σ_{n,R} określimy rozkład jednostajny na sferze RS^{n}, to ponieważ jest on obrazem σ_{n} przy jednokładności o skali R, to

α_{σ_{n,R}} (t) = α_{σ_{n}} ( \frac{t}{R}) exp( − \frac{n − 1}{2R^{2}} t^{2}).

Zauważmy też, że

∫_{RS^{n}} x_{i}x_{j}dσ_{n,R}(x) = \frac{R^{2}}{n} δ_{i,j} .

Zatem miara jednostajna na \sqrt{n}S^{n} ma dobrą normalizację, to znaczy taką, że macierz kowariancji jest identycznością. Dla tej miary dla n 2,

α_{σ_{n,\sqrt{n}}} (t) exp( − \frac{n − 1}{2n} t^{2}) exp( − \frac{1}{4}t^{2}).

Przykład 2. Niech γ_{k} oznacza kanoniczny rozkład gaussowski na ℝ^{k} tzn. rozkład z gęstością (2π)^{−k/2} exp(−|x|^{2}/2). Wówczas ekstremalnymi zbiorami w problemie izoperymetrycznym okazują się półprzestrzenie, tzn. jeśli

γ_{k}(A) = γ_{k}((−∞, r] × ℝ^{k−1} ) = Φ(r),

to

γ_{k}(A_{t}) γ_{k}( ((−∞, r] × ℝ^{k−1} )_{t}) = γ_{k}((−∞, r + t] × ℝ^{k−1} ) = Φ(r + t).

W szczególności

α_{γ_{k}} (t) 1 − Φ(t) \frac{1}{2}e^{−t^{2}/2} .

Zauważmy, że powyższe oszacowania nie zależą od wymiaru przestrzeni.

Przykład 3. Niech ν będzie symetrycznym rozkładem wykładniczym, tzn. rozkładem na ℝ z gęstością \frac{1}{2} exp(−|x|). Przez ν^{k} będziemy oznaczać rozkład produktowy ν ⊗ … ⊗ ν na ℝ^{k}. Wyznaczenie ekstremalnych zbiorów dla problemu izoperymetrycznego związanego z tą miarą jest trudne i nieznane dla k ≠ 1. Choć wiadomo, że ekstremalne nie są półprzestrzenie postaci (−∞, r] × ℝ^{k−1} , to są one optymalne z dokładnością do stałej, tzn.

ν^{k}(A) = ν((−∞, r]) ⇒ ν^{k}(A_{t}) ν( ( − ∞, r + \frac{1}{2\sqrt{6}}t]).

W szczególności

α_{ν^{k}}(t) 1 − ν( ( − ∞, \frac{1}{2\sqrt{6}}t]) = \frac{1}{2} exp( − \frac{1}{2\sqrt{6}}t) .

Zauważmy, że znowu uzyskane oszacowanie nie zależy od wymiaru przestrzeni.

Przykład 4. Niech μ będzie unormowaną miarą liczącą na kostce dyskretnej \{0, 1\}^{n} z metryką d(x, y) = \frac{1}{n}#\{i: x_{i} ≠ y_{i}\}. Tu problem izoperymetryczny daje się rozwiązać (optymalne są kule, ewentualnie z dodanymi punktami na brzegu). W tym przypadku można pokazać, że

α_{μ}(t) e^{−2nt^{2}} .

Krótki przegląd wyników pokazuje, że w wielu ważnych zastosowaniach można wykazać, że α_{μ}(t) C_{1} exp(−t^{2}/C_{2}) – mówimy wtedy, że funkcja koncentracji jest typu gaussowskiego. Widzielismy też przykład, w którym α_{μ}(t) C_{1} exp(−t/C_{2}) – mówimy wtedy o koncentracji wykładniczej.

1.1 Koncentracja funkcji lipschitzowskich

W wielu zastosowaniach nie interesuje nas jak zmienia się miara otoczenia zbioru, a raczej jak szybko maleją ogony funkcji określonych na przestrzeni. W tej części powiążemy ze sobą te zjawiska. Zacznijmy od definicji mediany i modułu ciągłości.

Definicja 1.3. Niech μ będzie miarą probabilistyczną na (X, d) oraz f: X → ℝ. Medianą f względem μ nazywamy taką liczbę M = Med_{μ}(f) dla której μ({x: f(x) M}), μ({x: f(x) M}) 1/2. Modułem ciągłości f nazywamy funkcję

w_{f} (t) := sup{|f(x) − f(y)|: d(x, y) t}.

Fakt 1.1. Dla dowolnej funkcji F: X → ℝ,

μ({x: F (x) > Med_{μ}(F) + w_{F}(t)}) α_{μ}(t)

oraz

μ({x: |F (x) − Med_{μ}(F)| > w_{F}(t)}) 2α_{μ}(t).

Dowód. Niech A := {x: F (x) Med_{μ}(F)} wówczas μ(A) 1/2 zatem μ(A_{t}) 1−α_{μ}(t). Ponadto, jeśli x ∈ A_{t}, to istnieje y ∈ A takie, że d(x, y) < t i wówczas F (x) F (y) + w_{F}(t) Med_{μ}(F) + w_{F}(t), stąd pierwsza nierówność w fakcie. Stosując ją do −F i zauważając, że Med_{μ}(−F) = −Med_{μ}(F) oraz w_{−F} = w_{F} dostajemy

μ({x: F (x) < Med_{μ}(F) − w_{F}(t)}) α_{μ}(t).

Dodając powyższą nierówność do poprzedniej otrzymamy ostatnią część faktu.

Przypomnijmy definicję funkcji lipschitzowskiej

Definicja 1.4. Funkcję F: (X, d) → ℝ nazywamy lipschitzowską, jeśli

∥F ∥_{Lip} := sup_{x≠y} \frac{|F (x) − F (y)|}{d(x, y)} < ∞.

Mówimy, że funkcja jest L-lipschitzowska jeśli ∥F ∥_{Lip} L, tzn. |F (x) − F (y)| Ld(x, y) dla wszystkich x, y ∈ X.

Analogicznie można zdefiniować funkcje lipschitzowskie między przestrzeniami metrycznymi.

Fakt 1.2. i) Jeśli F jest lipschitzowska ze stałą L, to dla t > 0,

μ({x: F (x) > Med_{μ}(F) + t}) α_{μ}(t/L)

oraz

μ({x: |F (x) − Med_{μ}(F)| > t}) 2α_{μ}(t/L).

ii) Na odwrót, jeśli dla każdej funkcji 1-lipschitzowskiej F i ustalonego t > 0,

μ({x: F (x) Med_{μ}(F) + t}) α,

to α_{μ}(t) α.

Dowód. i) Wynika z Faktu 1.1 i oczywistego szacowania w_{f} (t) tL.

ii) Ustalmy zbiór A taki, że μ(A) 1/2 i określmy F (x) := d(x, A). Wówczas F jest 1-lipschitzowska oraz Med_{μ}(F) = 0, zatem

α μ({F t}) = μ({x: d(x, A) t}) = 1 − μ(A_{t}).

Często łatwiej i naturalniej jest wykazywać koncentrację funkcji lipschitzowskich wokół średniej a nie mediany. Kolejny fakt pokazuje jak odzyskać funkcję koncentracji w takim przypadku.

Fakt 1.3. Załóżmy, że μ jest miarą probabilistyczną na przestrzeni metrycznej (X, d) oraz dla ograniczonych funkcji 1-lipschitzowskich F i t > 0 zachodzi

μ( {x: F (x) > ∫ F dμ + t}) α(t).  (1)

Wówczas dla dowolnego zbioru borelowskiego A takiego, że μ(A) > 0 zachodzi

1 − μ(A_{t}) α(μ(A)t).

W szczególności

α_{μ}(t) α( \frac{t}{2}).

Ponadto, jeśli lim_{t→∞} α(t) = 0, to dowolna funkcja 1-lipschitzowska jest całkowalna i jeśli dodatkowo α jest ciągła, to (1) zachodzi dla wszystkich funkcji 1-lipschitzowskich.

Dowód. Ustalmy zbiór borelowski A taki, że μ(A) > 0 oraz t > 0. Niech F (x) := min{d(x, A), t}, wówczas F jest ograniczona, 1-lipschitzowska i ∫ F dμ t(1 − μ(A)). Stąd na mocy (1),

1 − μ(A_{t}) = μ({F t}) μ( {F ∫ F dμ + μ(A)t}) α(μ(A)t).

W szczególności, jeśli μ(A) 1/2, to 1 − μ(A_{t}) α(t/2).

By udowodnić drugą część faktu, ustalmy funkcję 1-lipschitzowską F i niech F_{n} := min{|F |, n}. Z (1) zastosowanej do −F_{n} dostajemy

μ( {x: F_{n}(x) ∫ F_{n}dμ − t}) α(t).

Wybierzmy t_{0} takie, że α(t_{0}) < 1/2 oraz m := Med_{μ}|F |. Wówczas μ({F_{n} m}) 1/2, czyli zbiory {F_{n} m} oraz {F_{n} > ∫ F_{n}dμ − t_{0}} mają niepuste przecięcie. Zatem ∫ F_{n}dμ m + t_{0} i z twierdzenia Lebesgue’a o zbieżności monotonicznej dostajemy ∫ |F |dμ m + t_{0} < ∞. Ostatnią część tezy dostajemy stosując (1) do min{max{F, −n}, n} i przechodząc z n → ∞.

1.2 Obserwowalna średnica zbioru

Średnicą zbioru A w przestrzeni metrycznej (X, d) nazywamy

Diam(A) := sup{d(x, y): x, y ∈ A}.

Jeśli próbujemy obserwować jakiś obiekt, to możemy przyjąć, że zbiory miary mniejszej niż pewne κ > 0 są dla nas niezauważalne (założenie to np. dla κ = 10^{−10} wydaje się całkiem uzasadnione, jeśli miara μ jest związana ze stopniem oświetlenia obiektu). Motywuje to definicje częściowej średnicy

PartDiam_{μ}(X, d) = inf{Diam(A): μ(A) 1 − κ}.

W praktyce również nie jesteśmy w stanie obserwować obiektów wielowymiarowych, a jedynie ich przekroje. Stosując pewne uproszczenie możemy założyć, że przestrzeń obserwujemy za pomocą funkcji 1-lipschitzowskich F, tzn. badamy rozkład μ ∘ F^{−1} na F (X) (np. natężenie światła). Stąd wprowadzamy

Definicja 1.5. Obserwowalną średnicą przestrzeni (X, d) względem miary μ nazywamy wielkość

ObsDiam_{μ}(X, d) := sup{PartDiam_{μ∘F^{−1}} (F (X)): F: X → ℝ, ∥F ∥_{Lip} 1}.

Fakt 1.4.

ObsDiam_{μ}(X, d) 2α_{μ}^{−1} (κ/2),

gdzie α_{μ}^{−1} (ε) = inf{r > 0: α_{μ}(r) ε}.

Dowód. Ustalmy funkcję 1-lipschitzowską F na X i niech M = Med_{μ}(F), wówczas na podstawie Faktu 1.2,

μ ∘ F^{−1} ([M + r, M − r]) = μ(|F − M| r) 1 − 2α_{μ}(r).

Zatem

ObsDiam_{μ}(X, d) 2 inf{r: 2α_{μ}(r) κ} = 2α_{μ}^{−1} (κ/2).

Przykład. Dla gaussowskiej koncentracji α_{(X,d,μ)} (t) C_{1} exp(−t^{2}/C_{2}) mamy ObsDiam_{μ}(X, d) 2\sqrt{C_{2} ln(2C_{1}/κ)}.

W szczególności ObsDiam_{σ_{n}} (S^{n}) jest rzędu 1/\sqrt{n}, podczas gdy nietrudno sprawdzić, że Diam(S^{n}) = π i PartDiam_{μ}(S^{n}) π/2.

1.3 Transport miary

W wielu zagadnieniach będziemy używali pojęcia transportu miary.

Definicja 1.6. Niech μ i ν będą miarami na przestrzeniach metrycznych X i Y. Powiemy, że funkcja borelowska φ: X → Y transportuje miarę μ na miarę ν (ew. miara ν jest obrazem miary μ przy przekształceniu φ) jeśli ν(A) = μ ∘ φ^{−1} (A) dla wszystkich A ∈ B(Y).

Szczególnie wygodny jest transport lipschitzowski.

Fakt 1.5. Jeśli φ: X → Y jest L-lipschitzowska oraz φ transportuje miarę μ na ν, to α_{ν}(t) α_{μ}(t/L).

Dowód. Wystarczy zauważyć, że (φ^{−1} (A))_{t/L} ⊂ φ^{−1} (A_{t}).

2 Nierówności izoperymetryczne

W tej części omówimy kilka nierówności izoperymetrycznych, pokazując różne sposoby ich dowodzenia - poprzez powiązane nierówności funkcyjne, symetryzacje czy transport miary.

2.1 Klasyczna izoperymetria

Chociaż w tym wykładzie będziemy się zajmować miarami probabilistycznymi, to przegląd nierówności izoperymetrycznych zaczniemy od klasycznego przypadku n-wymiarowej miary Lebesgue’a λ_{n}.

Twierdzenie 2.1. Jeśli A jest podzbiorem borelowskim ℝ^{n} takim, że λ_{n}(A) = λ_{n}(B(x_{0}, r)), to dla dowolnego t > 0,

λ_{n}(A_{t}) λ_{n}(B(x_{0}, r)_{t}) = λ_{n}(B(x_{0}, r + t)).

Twierdzenie 2.2 (Nierówność Prekopy-Leindlera). Jeśli s ∈ [0, 1] oraz f, g, h: ℝ^{n} → [0, ∞) spełniają warunek

h(sx + (1 − s)y) f(x)^{s}g(y)^{1−s} dla x, y ∈ ℝ^{n},  (2)

to

∫_{ℝ^{n}} h(x)dx ( ∫_{ℝ^{n}} f(x)dx)^{s}( ∫_{ℝ^{n}} g(x)dx)^{1−s}

Dowód. Najpierw wykażemy, że dla niepustych zbiorów A, B ∈ B(ℝ^{n}) zachodzi

λ_{1}(A + B) λ_{1}(A) + λ_{1}(B).

Ponieważ λ_{1}(A) = sup{λ_{1}(K): K ⊂ A, K zwarty}, to możemy przyjąc, że zbiory A i B są zwarte. Ponadto odpowiednio je przesuwając możemy też zakładać, że supA = inf B = 0. Wówczas A ∩ B = ∅ oraz

λ_{1}(A + B) λ_{1}(A ∪ B) = λ_{1}(A) + λ_{1}(B).

Nierówność Prekopy-Leindlera udowodnimy przez indukcje po n. Najpierw rozważmy n = 1. Możemy zakładać, że f, g i h są ograniczone, a z uwagi na jednorodność, że supf(x) = supg(x) = suph(x) = 1. Zauważmy, że dla 0 r < 1, {h r} ⊃ s{f r} + (1 − s){g r}, więc całkując przez części dostajemy

∫ h(x)dx = ∫_{0}^{1} λ_{1}({h r})dr ∫_{0}^{1} λ_{1}(s{f r} + (1 − s){g r})dr
∫_{0}^{1} λ_{1}(s{f r}) + λ_{1}((1 − s){g r})dr
= s ∫ fdx + (1 − s) ∫ gdx ( ∫ fdx)^{s}( ∫ gdx)^{1−s} .

Załóżmy teraz, że n 2 oraz teza twierdzenia zachodzi dla n − 1. Niech f, g, h spełniają (2) i określmy dla x ∈ ℝ

F (x) = ∫_{ℝ^{n−1}} f(x, z)dz, G(x) = ∫_{ℝ^{n−1}} g(x, z)dz oraz H(x) = ∫_{ℝ^{n−1}} g(x, z)dz.

Zauważmy, że dla ustalonego x, y ∈ ℝ

h(sx + (1 − s)y, sz_{1} + (1 − s)z_{2}) f(x, z_{1})^{s}g(y, z_{2})^{1−s} dla z_{1}, z_{2} ∈ ℝ^{n−1} .

Zatem na mocy założenia indukcyjnego

H(sx + (1 − s)y) F (x)^{s}G(y)^{1−s} .

Stosując nierówność Prekopy-Leindlera w udowodnionym wcześniej przypadku n = 1 dostajemy

∫_{ℝ^{n}} h(x)dx = ∫_{ℝ} H(x)dx ( ∫_{ℝ} F (x)dx)^{s}( ∫_{ℝ} G(x)dx)^{1−s}
= ( ∫_{ℝ^{n}} f(x)dx)^{s}( ∫_{ℝ^{n}} g(x)dx)^{1−s}

Wniosek 2.3 (Nierówność Brunna-Minkowskiego). Dla dowolnych niepustych zbiorów borelowskich A, B ⊂ ℝ^{n},

λ_{n}(sA + (1 − s)B) λ_{n}(A)^{s}λ_{n}(B)^{1−s} dla s ∈ [0, 1]

oraz

λ_{n}(A + B)^{1/n} λ_{n}(A)^{1/n} + λ_{n}(B)^{1/n}.

Dowód. Pierwsza nierówność natychmiast wynika z nierówności Prekopy-Leindlera zastosowanej do funkcji f = 𝟙_{A}, g = 𝟙_{B} oraz h = 𝟙_{sA+(1−s)B} .

By udowodnić drugą wystarczy rozważyć przypadek, gdy A i B są zbiorami skończonej i niezerowej miary. Przyjmijmy wtedy

Ã = \frac{A}{s}, B̃ = \frac{B}{1 − s} oraz s = \frac{λ_{n}(A)^{1/n}}{λ_{n}(A)^{1/n} + λ_{n}(B)^{1/n}} .

Wówczas λ_{n}(Ã) = λ_{n}(B̃) = (λ_{n}(A)^{1/n} + λ_{n}(B)^{1/n})^{n}, więc na podstawie wykazanej poprzednio nierówności

λ_{n}(A+B) = λ_{n}(sÃ+(1−s)B̃) λ_{n}(Ã)^{s}λ_{n}(B̃)^{1−s} = (λ_{n}(A)^{1/n}+λ_{n}(B)^{1/n})^{n}.

Uwaga. Suma dwu zbiorów borelowskich nie musi być zbiorem borelowskim, ale można wykazać, że jest zbiorem mierzalnym w sensie Lebesgue’a.

Dowód Twierdzenia 2.1. Niech c_{n} = λ_{n}(B(0, 1)), wówczas λ_{n}(A) = c_{n}r^{n} i na podstawie Wniosku 2.3,

λ_{n}(A_{t}) = λ_{n}(A + B(0, t)) (λ_{n}(A)^{1/n} + λ_{n}(B(0, t))^{1/n})^{n}
= c_{n}(r + t)^{n} = λ_{n}(B(x_{0}, r + t)).

Definicja 2.1. Dla miary μ na przestrzeni probabilistycznej (X, d) określamy zewnętzną miarę brzegową μ^{+} wzorem

μ^{+} (A) := lim inf_{t→0+} \frac{μ(A_{t}) − μ(A)}{t} .

Uwaga. Jeśli miara μ na ℝ^{n} ma ciągłą gęstość g(x) oraz zbiór A ma gładki brzeg, to

μ^{+} (A) = ∫_{∂A} g(x)dH_{n−1} (x),

gdzie H_{n−1} oznacza n − 1 wymiarową miarę Haussdorffa.

Równoważna różniczkowa forma klasycznej nierówności izoperymetrycznej mówi, że spośród zbiorów ustalonej objętości najmniejszą powierzchnię brzegu ma kula. Dokładniej:

Twierdzenie 2.4. Jeśli A jest podzbiorem borelowskim ℝ^{n} takim, że λ_{n}(A) = λ_{n}(B(x_{0}, r)), to

λ_{n}^{+} (A) λ_{n}^{+} (B(x_{0}, r)) = nc_{n}^{1/n}(λ_{n}(A))^{(n−1)/n} ,

gdzie

c_{n} = λ_{n}(B(0, 1)) = \frac{π^{n/2}}{Γ(n/2 + 1)} .

2.2 Izoperymetria sferyczna

Twierdzenie 2.5. Jeśli A jest podzbiorem borelowskim S^{n} takim, że σ_{n}(A) = σ_{n}(B(x_{0}, r)) to dla dowolnego t > 0,

σ_{n}(A_{t}) σ_{n}(B(x_{0}, r)_{t}) = σ_{n}(B(x_{0}, r + t)).

Wniosek 2.6.

α_{σ_{n}} (t) \sqrt{\frac{π}{8}} exp( − \frac{(n − 1)}{2} t^{2}).

Dowód. Dla n = 1 nie ma co dowodzić (bo zawsze α_{μ}(t) 1/2). Będziemy więc zakładać, że n 2. Zauważmy, że

σ_{n}(B(x_{0}, r)) = s_{n}^{−1} ∫_{0}^{r} sin^{n−1} tdt,

gdzie s_{n} = ∫_{0}^{π} sin^{n−1} tdt. Zatem

α_{σ_{n}} (t) = 1−σ_{n}(B(x_{0}, t+π/2)) = s_{n}^{−1} ∫_{t+π/2}^{π} sin^{n−1} udu = s_{n}^{−1} ∫_{t}^{π/2} cos^{n−1} udu.

Stosując oszacowanie cosu exp(−u^{2}/2) dla t ∈ [0, π/2] dostajemy

∫_{t}^{π/2} cos^{n−1} udu ∫_{t}^{π/2} e^{−(n−1)u^{2}/2} du \frac{1}{\sqrt{n − 1}} ∫_{t\sqrt{n−1}}^{∞} e^{−s^{2}/2} ds

= \begin{matrix}√ & \overline{2π} \\ √ & \overline{n − 1} \end{matrix} (1 − Φ(t\sqrt{n − 1} )) \begin{matrix}√ & \overline{π} \\ √ & \overline{2(n − 1)} \end{matrix} e^{−(n−1)t^{2}/2} .

Ponadto łatwe całkowanie przez części daje, że dla n 3, s_{n} = \frac{n−2}{n−1} s_{n−2} , stąd

\sqrt{n − 1} s_{n} = \frac{n − 2}{\sqrt{n − 1}} s_{n−2} \sqrt{n − 3} s_{n−2} ,

zatem

inf_{n 2} \sqrt{n − 1} s_{n} = min\{s_{2}, \sqrt{2}s_{3}\} = min\{2, π/\sqrt{2}\} = 2.

2.3 Izoperymetria gaussowska

Przypomnijmy, że przez γ_{k} oznaczamy kanoniczny rozkład gaussowski na ℝ^{k}, tzn. rozkład z gęstością (2π)^{−k/2} exp(−|x|^{2}/2).

Głównym wynikiem, który wykażemy jest to, że dla rozkładów gaussowskich optymalne dla problemu izoperymetrycznego są półprzestrzenie afiniczne, to znaczy zbiory postaci

H = {x ∈ ℝ^{k}: ⟨x, u⟩ < r} dla pewnych u ∈ S^{k−1} i r ∈ [−∞, ∞] .  (3)

Twierdzenie 2.7. Niech H będzie półprzestrzenią afiniczną, a A zbiorem borelowskim w ℝ^{k} takim, że γ_{k}(H) = γ_{k}(A). Wówczas dla dowolnego t > 0, γ_{k}(H_{t}) γ_{k}(A_{t})

Zanim przystąpimy do dowodu twierdzenia pokażemy, że γ_{k} jest granicą rzutowań rozkładów jednostajnych na \sqrt{n}S^{n−1} .

Niech P = P_{k,n} oznacza kanoniczny rzut ℝ^{n} na ℝ^{k} dla k < n, zaś σ̃_{n−1} oznacza unormowaną miarę powierzchniową na \sqrt{n}S^{n−1} . Oznaczmy przez μ_{k,n} obraz σ̃_{n−1} przy tym rzutowaniu tzn.

μ_{k,n}(A) = σ̃_{n−1} (P_{k,n}^{−1}(A)) dla A ∈ B(ℝ^{k}).

Fakt 2.8 (Lemat Poincaré). Miara μ_{k,n} zbiega słabo przy n → ∞ do miary γ_{k}, co więcej

lim_{n→∞} μ_{k,n}(A) = γ_{k}(A) dla dowolnego zbioru borelowskiegoA.

Dowód. Proste rozumowanie pokazuje, że miara μ_{k,n} ma gęstość g_{k,n}(x) = c_{k,n}^{−1} g̃_{n,k}(x), gdzie g̃_{n,k} = (\frac{n−|x|^{2}}{n} )^{(n−k)/2} 𝟙_{\{|x| \sqrt{n}\}} oraz c_{k,n} = ∫_{ℝ^{k}} g̃_{n,k}(x)dx. Oczywiście lim_{n→∞} g̃_{k,n}(x) = exp(−|x|^{2}/2), ponadto |g̃_{k,n}(x)| exp(−(n − k)|x|^{2}/(2n)) exp(−|x|^{2}/(2n)) dla n > k, więc z twierdzenia Lebesgue’a o zbieżności zmajoryzowanej lim_{n→∞} c_{n,k} = ∫_{ℝ^{k}} exp(−|x|^{2}/2)dx, czyli gęstość miary μ_{k,n} zbiega punktowo do gęstości miary γ_{k}. Teza faktu wynika z twierdzenia Scheffe’go (zob. zad.8.1.7 w [1]).

Dowód Twierdzenia 2.7. Ze względu na rotacyjną niezmienniczość miary γ_{k} możemy dla uproszczenia notacji założyć, że H = {x: x_{1} < r}. Ustalmy dowolne r_{0} < r i niech H_{0} = {x: x_{1} < r_{0}}. Zauważmy, że γ_{k}(H_{0}) < γ_{k}(A) zatem na podstawie Lematu Poincaré μ_{k,n}(H_{0}) μ_{k,n}(A) dla dużych n. Ponieważ P_{k,n}^{−1}(H_{0})∩\sqrt{n}S^{n−1} jest kulą w \sqrt{n}S^{n−1} , więc na mocy izoperymetrii sferycznej

σ̃_{n−1} ((P_{k,n}^{−1}(A))_{t}) σ̃_{n−1} ((P_{k,n}^{−1}(H_{0}))_{t}).

Zauważmy, że przekształcenie P_{k,n} jest oczywiście 1-lipschitzowskie, więc

μ_{k,n}(A_{t}) μ_{k,n}(P_{k,n}((P_{k,n}^{−1}(A))_{t})) μ_{k,n}(P_{k,n}((P_{k,n}^{−1}(H_{0}))_{t})).

Nietrudno zauważyć, że

P_{k,n}((P_{k,n}^{−1}(H_{0}))_{t}) = {x: x_{1} < r_{n}}

oraz r_{n} → r_{0} + t przy n → ∞. Stąd

γ_{k}(A_{t}) = lim_{n→∞} μ_{k,n}(A_{t}) lim_{n→∞} μ_{k,n}({x: x_{1} < r_{n}}) = γ_{k}({x: x_{1} < r_{0} + t}),

z dowolności r_{0} < r wynika teza. Twierdzenie 2.9. Jeśli γ_{k}(A) = Φ(x) to γ_{k}(A_{t}) Φ(x + t) oraz γ_{k}^{+} (A) I_{γ}(γ_{k}(A)), gdzie I_{γ}(x) := φ(Φ^{−1} (x)) oraz φ(x) = Φ′(x) = \frac{1}{\sqrt{2π}} exp(−x^{2}/2). Dowód. Wystarczy zauważyć, że jeśli γ_{k}(H) = Φ(x) i H jest postaci (3), to H_{t} = {x ∈ ℝ^{k}: ⟨x, u⟩ < r + t} i γ_{k}(H_{t}) = Φ(x + t).

Zauważając, że Φ(0) = 1/2 otrzymujemy: Wniosek 2.10. α_{γ_{k}} (t) 1 − Φ(t) \frac{1}{2} exp(−t^{2}/2).

Na podstawie Faktu 1.2 dostajemy: Wniosek 2.11. Jeśli F: ℝ^{k} → ℝ jest funkcją L-lipschitzowską oraz t 0 to

γ_{k}(\{x: F (x) Med_{γ_{k}} (F) + t\}) 1 − Φ(t/L) \frac{1}{2}e^{− \frac{t^{2}}{2L^{2}}}

oraz

γ_{k}(\{x: |F (x) − Med_{γ_{k}} (F)| t\}) 2(1 − Φ(t/L)) e^{− \frac{t^{2}}{2L^{2}}}

Transportując w sposób lipschitzowski miarę gaussowską można uzyskać oszacowania funkcji koncentracji dla innych miar. Pokażemy dwa przykłady. Wniosek 2.12. Niech μ_{[0,1]^{n}} oznacza rozkład jednostajny na kostce [0, 1]^{n}. Wówczas μ_{[0,1]^{n}} jest (2π)^{−1/2} -lipschitzowskim obrazem γ_{n}. W szczególności α_{μ_{[0,1]^{n}}} \frac{1}{2} exp(−πt^{2}). Dowód. Określmy f: ℝ → (0, 1) wzorem

f(x) = μ_{[0,1]}([0, f(x)]) = γ_{1}((−∞, x]) = Φ(x).

Wówczas f transportuje γ_{1} na μ_{[0,1]}, to znaczy μ_{[0,1]} = γ_{1} ∘ f^{−1} . Ponadto f′(x) = (2π)^{−1/2} exp(−x^{2}/2) (2π)^{−1/2} , czyli f jest (2π)^{−1/2} -lipschitzowska. Jeśli teraz określimy F: ℝ^{n} → (0, 1)^{n} wzorem F (x) = (f(x_{1}), …, f(x_{n})), to F transportuje γ_{n} na μ oraz F jest (2π)^{−1/2} -lipschitzowska. Ostatnie oszacowanie w tezie wniosku jest konsekwencją Faktu 1.5 i Wniosku 2.10.

Wniosek 2.13. Niech B_{n} = {x ∈ ℝ^{n}: |x| 1} oznacza kulę jednostkową w ℝ^{n}, zaś μ_{B_{n}} będzie rozkładem jednostajnym na B_{n}. Wówczas istnieje stała C taka, że μ_{B_{n}} jest Cn^{−1/2} -lipschitzowskim obrazem γ_{n}. W szczególności α_{μ_{Bn}} \frac{1}{2} exp(−nt^{2}/(2C)).

Dowód. Ponieważ obie miary γ_{n} i μ_{B_{n}} są rotacyjnie niezmiennicze, będziemy szukać funkcji T: ℝ^{n} → B_{n} transportującej γ_{n} na μ_{B_{n}} postaci T x = \frac{x}{|x|}φ(|x|). Wystarczy sprawdzić, że γ_{n}(B(0, t)) = μ_{n}(B(0, φ(t))), czyli całkując we współrzęsnych sferycznych, że dla t 0,

φ(t)^{n} = \frac{1}{c_{n}} ∫_{0}^{t} r^{n−1} e^{−r^{2}/2} dr,  (4)

gdzie

c_{n} = ∫_{0}^{∞} r^{n−1} e^{−r^{2}/2} dr = 2^{(n−2)/2} Γ(\frac{n}{2}).

Z (4) wynika, że

φ(t)^{n} \frac{1}{c_{n}} e^{−t^{2}/2} ∫_{0}^{t} r^{n−1} dr = \frac{1}{nc_{n}} t^{n}e^{−t^{2}/2} .

Różniczkując stronami (4) dostajemy nφ′(t)φ(t)^{n−1} = t^{n−1} e^{−t^{2}/2} /c_{n}, zatem

φ′(t) = \frac{1}{nc_{n}} ( \frac{t}{φ(t)} )^{n−1} e^{−t^{2}/2} \frac{1}{nc_{n}} (nc_{n}e^{t^{2}/2})^{(n−1)/n} e^{−t^{2}/2} (nc_{n})^{−1/n} .

Ze wzoru Stirlinga dostajemy

nc_{n} = 2^{n/2}Γ(\frac{n}{2} + 1) (\frac{n}{e})^{n/2},

więc

∥φ∥_{Lip} = sup_{t 0}|φ′(t)| \begin{matrix}√ & \overline{e} \\ √ & \overline{n} \end{matrix}.

Otwarty problem. Rozwiązać zagadnienie izoperymetryczne dla zbiorów symetrycznych, to znaczy znaleźć dla ustalonego t > 0, c ∈ [0, 1],

inf {γ_{k}(A_{t}): γ_{k}(A) = c, A = −A}

oraz

inf {γ_{k}^{+} (A): γ_{k}(A) = c, A = −A}.

Dość naturalna hipoteza mówi, że dla c 1/2 rozwiązaniem obu problemów są zbiory postaci [−a, a] × ℝ^{k−1} zaś dla c < 1/2 drugi problem się optymalizuje dla (ℝ \ [−a, a]) × ℝ^{k−1} . Podobny problem można postawić dla miary σ_{n}, ale tam analogiczna hipoteza okazuje się być niestety fałszywa.

3 Koncentracja w przestrzeniach produktowych

3.1 Transformata Laplace’a

Wiele dalszych szacowań będzie oparte na transformacie Laplace’a zmiennej losowej.

Definicja 3.1. Transformatą Laplace’a zmiennej losowej Z nazywamy funkcję

L_{Z}(λ) := Ee^{λZ} λ ∈ ℝ.

Podobnie jeśli μ jest miarą probabilistyczną na pewnej przestrzeni X oraz F: X → ℝ, to transformatę Laplace’a F względem μ określamy

L_{F,μ}(λ) := ∫_{X} e^{λF (x)} dμ(x).

Fakt 3.1. Dla dowolnej zmiennej losowej Z,

P(Z t) inf_{λ 0} e^{−λt} L_{Z}(λ) dla t 0.

W szczególności, jeśli dla pewnego a > 0,

L_{Z}(λ) exp(aλ^{2}) λ ∈ ℝ,

to dla t 0

P(Z t) exp( − \frac{t^{2}}{4a}) oraz P(|Z| t) 2 exp( − \frac{t^{2}}{4a}).

Dowód. Pierwsza część wynika z nierówności Czebyszewa, a druga z pierwszej i prostego rachunku.

Zatem by udowodnić, że funkcja koncentracji miary μ jest gaussowska wystarczy wykazać, że L_{F,μ}(λ) exp(aλ^{2}) dla pewnego a > 0 i wszystkich funkcji 1-lipschitzowskich F takich, że ∫ F dμ = 0.

3.2 Metody Martyngałowe

Twierdzenie 3.2 (Nierówność Azumy). Niech (M_{k}, F_{k})_{k=0}^{n} będzie martyngałem o ograniczonych przyrostach takim, że ∥M_{k}−M_{k−1} ∥_{∞} a_{k}. Wówczas

P(M_{n} − M_{0} t) exp( − \frac{t^{2}}{2 ∑ _{i=1}^{n} a_{i}^{2}} ) .

Dowód. Określmy dla 1 k n, d_{k} := M_{k} − M_{k−1} , wówczas E(d_{k}|F_{k−1} ) = 0. Mamy \frac{1−u}{2} (−x) + \frac{1+u}{2} x = ux, więc z wypukłości exp(x),

e^{ux} \frac{1 − u}{2} e^{−x} + \frac{1 + u}{2} e^{x} = u sinh(x) + cosh(x) dla |u| 1.

Stosując tę nierówność dla u = d_{k}/a_{k} i x = λa_{k} dostajemy

E(e^{λd_{k}} |F_{k−1} ) E( \frac{d_{k}}{a_{k}} |F_{k−1} ) sinh(λa_{k}) + cosh(λa_{k}) = cosh(λa_{k}).

Liczymy

Ee^{λ(M_{n} −M_{0})} = Ee^{λ(M_{n−1} −M_{0}+d_{n})} = E(e^{λ(M_{n−1} −M_{0})} E(e^{λd_{n}} |F_{n−1} ))
cosh(λa_{n})Ee^{λ(M_{n−1} −M_{0})} .

Zatem iterując powyższą nierówność i stosując oszacowanie (wynikające np. z rozwinięcia w szereg Taylora) cosh(x) exp(x^{2}/2) dostajemy

L_{M_{n} −M_{0}} (λ) = Ee^{λ(M_{n} −M_{0})} ∏_{k=1}^{n} cosh(λa_{k}) exp(\frac{1}{2} ∑_{k=1}^{n} a_{k}^{2}λ^{2}).

Teza twierdzenia wynika z Faktu 3.1.

Uwaga. Najczęściej będziemy mieli F_{0} = {∅, Ω}, wówczas M_{0} jest stałe, a ponieważ martyngał ma stałą wartość oczekiwaną, to M_{0} = EM_{n}.

W poniższych zastosowaniach będziemy przyjmować M_{k} = E_{μ}(F |F_{k}) dla całkowalnej funkcji F: X → ℝ i odpowiednio dobranego (F_{k}) ciągu σ-ciał podzbiorów X.

Wniosek 3.3. Niech (X_{i}, d_{i}) będą przetrzeniami metrycznymi, X = X_{1} × ⋯× X_{n} z odległością l_{1}, to znaczy d(x, y) = ∑ _{i=1}^{n} d_{i}(x_{i}, y_{i}) dla x, y ∈ X oraz niech μ = μ_{1} ⊗ …⊗ μ_{n} będzie produktem miar probabilistycznych μ_{i} na X_{i}. Wówczas dla dowolnej funkcji 1-lipschitzowskiej F na X

μ( \{x: F (x) ∫ F dμ + t\}) exp(−\frac{t^{2}}{2D^{2}} ),

gdzie D = (∑ _{i=1}^{n} Diam(X_{i})^{2})^{1/2}. W szczególności

α_{μ}(t) exp( − \frac{t^{2}}{8D^{2}} ).

Dowód. Na mocy Faktu 1.3 wystarczy wykazać pierwszą nierówność tezy. Niech F_{k} będzie σ ciałem generowanym przez pierwsze k-współrzędnych oraz M_{k} := E_{μ}(F |F_{k}). Wówczas oczywiście

M_{k}(x) = M̃_{k}(x_{1}, …, x_{k}) = ∫_{X_{k+1} ×...×X_{n}} F (x)dμ_{i+1} (x_{i+1} ) ⋯dμ_{n}(x_{n}),

stąd

|M_{k}(x) − M_{k−1} (x)| = |M̃_{k}(x_{1}, …, x_{k}) − ∫_{X_{k}} M̃_{k}(x_{1}, …, x_{k})dμ_{k}(x_{k})|

sup_{y_{k},z_{k}∈X_{k}} |M̃_{k}(x_{1}, …, x_{k−1} , y_{k}) − M̃_{k}(x_{1}, …, x_{k−1} , z_{k})|

sup_{y∈X,z_{k}∈X_{k}} |F (x_{1}, …, x_{k−1} , y_{k}, y_{k+1} , …, y_{n}) − F (x_{1}, …, x_{k−1} , z_{k}, y_{k+1} , …, y_{n})|

sup_{y_{k},z_{k}∈X_{k}} d_{k}(y_{k}, z_{k}) Diam(X_{k})

i teza wynika z Twierdzenia 3.2.

Definicja 3.2. Mówimy, że skończona przestrzeń metryczna (X, d) ma długość conajwyżej l, jeśli istnieje rosnący ciąg podziałów X, {X} = A_{0}, A_{1}, …, A_{n} = {{x}: x ∈ X} (A_{i} jest podpodziałem A_{i−1} ) oraz liczby a_{1}, …, a_{n} spełniające (∑ _{i=1}^{n} a_{i}^{2})^{1/2} l takie, że dla dowolnego A ∈ A_{i−1} oraz B, C ∈ A_{i}, B, C ⊂ A istnieje bijekcja Φ: B → C dla której d(x, Φ(x)) a_{i} dla x ∈ B.

Uwaga. Biorąc A_{0} = {X} i A_{1} = {{x}: x ∈ X} widzimy, że każda skończona przestrzeń metryczna ma długość nie większą niż Diam(X).

Twierdzenie 3.4. Jeśli (X, d) jest skończoną przestrzenią metryczną o długości co najwyżej l, zaś μ unormowaną miarą liczącą na X, to dla funkcji 1-lipschitzowskich F na X,

μ( \{x: F (x) ∫ F dμ + t\}) exp(−\frac{t^{2}}{2l^{2}}),

w szczególności

α_{μ}(t) exp( − \frac{t^{2}}{8l^{2}} ).

Dowód. Ustalmy funkcję 1-lipschitzowską F. Niech F_{i} będzie σ-ciałem generowanym przez A_{i} oraz M_{i} := E_{μ}(F |F_{i}) dla i = 0, …, n. Wówczas

M_{i}(x) = \frac{1}{#A} ∑_{y∈A} F (y) dla x ∈ A ∈ A_{i}.

Zatem, jeśli A ∈ A_{i−1} , B, C ∈ A_{i}, B, C ⊂ A oraz Φ: B → C jest bijekcją jak w Definicji 3.2, to dla x ∈ B, y ∈ C,

|M_{i}(x) − M_{i}(y)| = | \frac{1}{#B} ∑_{z∈B} (F (z) − F (Φ(z))| sup_{z∈B}|F (z) − F (Φ(z))|

sup_{z∈B}d(z, Φ(z)) a_{i}.

Ponieważ M_{i−1} na A ∈ A_{i−1} jest uśrednieniem M_{i} po B ⊂ A, B ∈ A_{i}, to mamy |M_{i}(x) − M_{i−1} (x)| a_{i}, czyli ∥M_{i} − M_{i−1} ∥_{∞} a_{i−1} . Teza wynika z Twierdzenia 3.2 oraz Faktu 1.3.

Przykład 1. Niech X = \{0, 1\}^{n} z odległością d(x, y) = \frac{1}{n}#\{i: x_{i} ≠ y_{i}\}. Możemy wtedy położyć

A_{i} = {{(x_{1}, …, x_{i})} × {0, 1}^{n−i} : x_{1}, …, x_{i} ∈ {0, 1}}

i łatwo sprawdzić, że założenia definicji są spełnione z a_{i} = \frac{1}{n}. Zatem l = 1/\sqrt{n} i

α_{(\{0,1\}^{n} ,d,μ)} exp(−\frac{nt^{2}}{8}).

Przykład 2. Ogólniej niech X_{i} będą skończonymi zbiorami, X = X_{1} × ⋯× X_{n}, d(x, y) = #{i: x_{i} ≠ y_{i}} oraz μ będzie unormowaną miarą liczącą na X. Analogicznie jak poprzednio

A_{i} = {{(x_{1}, …, x_{i})} × X_{i+1} × ⋯× X_{n}: x_{j} ∈ X_{j}, 1 j i}

oraz a_{i} = 1. Zatem l = \sqrt{n} i

α_{(X,d,μ)} exp(−\frac{t^{2}}{8n}).

Przykład 3. Niech Π^{n} będzie grupą permutacji zbioru {1, …, n} z metryką d(σ, π) = #{i: σ_{i} ≠ π_{i}}, a μ unormowaną miarą liczącą na Π^{n}. Niech A_{i} składa się ze zbiorów postaci

A_{j_{1},...,j_{i}} = {σ ∈ Π^{n}: σ(1) = j_{1}, …, σ(i) = j_{i}}.

Wówczas jeśli B, C ∈ A_{i} są podzbiorami pewnego A ∈ A_{i−1} to B = A_{j_{1},...,j_{i−1} ,p}, C = A_{j_{1},...,j_{i−1} ,q} i możemy zdefiniować bijekcję Φ między B i C jako Φ = τ_{p,q} ∘ σ, gdzie τ_{p,q} jest transpozycją zamieniającą p z q. Łatwo sprawdzić, że d(σ, Φ(σ)) 2/n, zatem l = 2/\sqrt{n} i

α_{(Π^{n} ,d,μ)} exp(−\frac{nt^{2}}{32}).

Ostatnie twierdzenie z tej części wiąże się z miarą Haara na zwartej grupie metrycznej (G, d), to znaczy taką miarą probabilistyczną μ, że μ(gA) = μ(A) = μ(Ag) dla dowolnego A ∈ B(G) i g ∈ G. Zakładamy, że d jest niezmiennicza na translacje, tzn d(hg_{1}, hg_{2}) = d(g_{1}, g_{2}) = d(g_{1}h, g_{2}h) dla g_{1}, g_{2}, h ∈ G. Dla podgrupy domkniętej H ⊂ G można wprowadzić odległość na G/H wzorem

ρ(g_{1}H, g_{2}H) = d(g_{1}, g_{2}H) = d(g_{2}^{−1} g_{1}, H).

Twierdzenie 3.5. Niech μ będzie miarą Haara na zwartej grupie metrycznej (G, d) oraz G = G_{0} ⊃ G_{1} ⊃ ⋯⊃ G_{n} = {e} będzie ciągiem domkniętych podgrup. Wówczas

α_{(G,d,μ)} exp( − \frac{t^{2}}{8l^{2}} ),

gdzie l = (∑ _{i=1}^{n} Diam(G_{i−1} /G_{i})^{2})^{1/2}.

Dowód. Niech F będzie funkcją 1-lipschitzowską, M_{i} = E_{μ}(F |F_{i}) gdzie F_{i} jest σ-ciałem generowanym przez zbiory gG_{i}. Załóżmy, że g_{1}G_{i}, g_{2}G_{i} ⊂ g_{0}G_{i−1} wówczas g_{0}^{−1} g_{1}, g_{0}^{−1} g_{2} ∈ G_{i−1} , więc ze zwartości G_{i}

Diam(G_{i−1} /G_{i}) d(g_{0}^{−1} g_{1}, g_{0}^{−1} g_{2}G_{i}) = d(g_{0}^{−1} g_{1}, g_{0}^{−1} g_{2}h) = d(g_{1}, g_{2}h)

dla pewnego h ∈ G_{i}. Określmy przekształcenie Φ wzorem Φ(g) = g_{2}hg_{1}^{−1} g, wówczas Φ zachowuje miarę μ oraz jest homeomorfizmem między g_{1}G i g_{2}G. Ponadto

|F (g)−F (Φ(g))| d(g, Φ(g)) = d(g, g_{2}hg_{1}^{−1} g) = d(g_{1}, g_{2}h) Diam(G_{i−1} /G_{i}).

Stąd oscylacja M_{i} na g_{0}G_{i−1} jest nie większa niż a_{i} = Diam(G_{i−1} /G_{i}) czyli po uśrednieniu ∥M_{i} − M_{i−1} ∥_{∞} a_{i} i możemy stosować Twierdzenie 3.2

3.3 Nierówność Poincaré

Definicja 3.3. Mówimy, że miara probabilistyczna μ na (X, d) spełnia nierówność Poincaré ze stałą C, jeśli dla wszystkich ograniczonych lipschitzowskich funkcji f na X zachodzi

Var_{μ}(f) C ∫ |∇f|^{2}dμ,  (5)

gdzie

|∇f|(x) := lim sup_{y→x} \frac{|f(x) − f(y)|}{d(x, y)} ,

jeśli x jest punktem skupienia X i |∇f|(x) = 0, jeśli x jest punktem izolowanym X.

Uwaga 1. W przypadku, gdy X = ℝ^{n} ze standardową metryką euklidesową możemy użyć twierdzenia Rademachera, które mówi, że każda funkcja Lipchitzowska jest różniczkowalna prawie wszędzie i wtedy |∇f|(x) jest dla prawie wszystkich x równy długości zwykłego gradientu f. Ponadto standardowy argument aproksymacyjny pokazuje, że by wykazać nierówność Poincaré dla miar probabilistycznych na ℝ^{n} wystarczy sprawdzić (5) dla ograniczonych funkcji klasy C^{1}(ℝ^{n}) o ograniczonych pochodnych rzędu jeden.

Uwaga 2. Będziemy wykorzystywali tylko dwie własności |∇f|. Mianowicie, że dla funkcji 1-lipschitzowskich |∇f| 1 oraz, że dla dowolnej funkcji klasy C^{1}(ℝ), |∇g(F)| |g′(F)||∇F | (w szczególności |∇(f + c)| = |∇f|).

Uwaga 3. Załóżmy, że miara μ ma gęstość postaci e^{−V} na ℝ^{n}. Wówczas proste całkowanie przez części pokazuje, że

∫ |∇f|^{2}dμ = ∫ (−△f + ⟨∇V, ∇f⟩)fdμ.

Definiując operator Lf := −△f + ⟨∇V, ∇f⟩ widzimy, że L1 = 0. Nierówność Poincaré mówi, że dla funkcji f o średniej 0, czyli prostopadłych do 1, ∫ fLfdμ C^{−1} ∫ f^{2}dμ. Biorąc pod uwagę samosprzężoność L nierówność (5) jest równoważna temu, że kolejna wartość własna L to conajmniej 1/C. Dlatego nierówność Poincaré się nazywa nierównością �luki spektralnej” (spectral gap inequality).

Czasem wygodniej w nierówności Poincaré zastąpić wariancję funkcji przez całkę kwadratu odchylenia od mediany, okazuje się, że prowadzi to do równoważnej nierówności.

Fakt 3.6. Nierówność Poincaré jest równoważna nierówności

∀_{f∈Lip(X)} E_{μ}|f − Med_{μ}f|^{2} C̃ ∫ |∇f|^{2}dμ.

Co więcej optymalne stałe w obu nierównościach spełniają C_{opt} C̃_{opt} (1 + \sqrt{2})^{2}C_{opt}.

Dowód. Ponieważ

Var_{μ}(f) = inf_{c∈ℝ} E_{μ}(f − c)^{2} E_{μ}|f − Med_{μ}f|^{2},

więc oczywiście C_{opt} C̃_{opt}.

By udowodnić przeciwne oszacowanie zauważmy, że

Var_{μ}(f) |Med_{μ}f − E_{μ}f|^{2}μ({|f − E_{μ}f| Med_{μ}f − E_{μ}f})

\frac{1}{2}|Med_{μ}f − E_{μ}f|^{2}.

Stąd

(E_{μ}|f − Med_{μ}f|^{2})^{1/2} Var_{μ}(f)^{1/2} + |Med_{μ}f − E_{μ}f| (1 + \sqrt{2})Var_{μ}(f)^{1/2}

i otrzymujemy C̃_{opt} (1 + \sqrt{2})^{2}C_{opt}.

Twierdzenie 3.7. Załóżmy, że miara μ spełnia nierówność Poincaré ze stałą C. Wówczas dla każdej funkcji 1-lipschitzowskiej F i t > 0

μ( \{F ∫ F dμ + t\}) 2 exp( − \frac{t}{\sqrt{C}}).

W szczególności α_{X}(t) 2 exp(−t/2\sqrt{C}).

Dowód. Rozpatrując F − ∫ F dμ możemy założyć, że F ma średnią zero. Zauważmy, że dla dowolnej funkcji różniczkowalnej g mamy |∇g(F)| |g′(F)||∇F | |g′(F)|. Niech

M(λ) := M_{μ,F} (λ) = ∫ e^{λF} dμ.

Stosując nierówność Poincaré do e^{λF/2} dostajemy

Var_{μ}(e^{λF/2}) = M(λ) − M( \frac{λ}{2})^{2} C ∫ |∇e^{λF/2}|^{2}dμ \frac{Cλ^{2}}{4} M(λ).

Zatem dla λ < 2/\sqrt{C} dostajemy

M(λ) \frac{1}{1 − Cλ^{2}/4} M( \frac{λ}{2})^{2}.

Iterując tę nierówność n razy dostajemy

M(λ) ∏_{k=0}^{n−1} ( \frac{1}{1 − Cλ^{2}/4^{k+1}} )^{2^{k}}M( \frac{λ}{2^{n}} )^{2^{n}} .

Ponieważ M(0) = 1 i M′(0) = ∫ F dμ = 0, to M(λ/2^{n})^{2^{n}} → 1 przy n → ∞ i

M(λ) ∏_{k=0}^{∞} ( \frac{1}{1 − Cλ^{2}/4^{k+1}} )^{2^{k}}.

Zauważmy, że

∏_{k=0}^{∞} (1 − Cλ^{2}4^{−k−1} )^{2^{k}} 1 − Cλ^{2} ∑_{k=0}^{∞} 2^{k}4^{−k−1} = 1 − \frac{C}{2}λ^{2}.

W szczególności M(1/\sqrt{C}) 2 i teza wynika z nierówności Czebyszewa.

Fakt 3.8. Symetryczny rozkład wykładniczy ν na ℝ z gęstością \frac{1}{2}e^{−|x|} spełnia nierówność Poincaré ze stałą 4.

Dowód. Proste całkowanie przez części pokazuje, że dla funkcji h ∈ C_{ogr}^{1}(ℝ),

∫ h(x)dν(x) = h(0) + ∫ sgn(x)h′(x)dν(x).

Niech f ∈ C_{ogr}^{1}(ℝ) i g(x) = f(x) − f(0) wówczas

∫ g^{2}dν = 2 ∫ sgn(x)g′(x)g(x)dν(x) 2( ∫ g^{′2}dν)^{1/2}( ∫ g^{2}dν)^{1/2},

stąd

Var_{ν}(f) ∫ g^{2}dν 4 ∫ g^{′2}dν = 4 ∫ f^{′2}dν.

Fakt 3.9. Załóżmy, że μ_{i} są miarami probabilistycznymi na X_{i}, X = X_{1} × … × X_{n} oraz μ = μ_{1} ⊗ μ_{2} ⊗ ⋯⊗ μ_{n}. Wówczas dla dowolnej funkcji f ∈ L^{2}(X, μ)

Var_{μ}(f) ∑_{i=1}^{n} E_{μ}Var_{μ_{i}} (f).

Dowód. Prosta indukcja pokazuje, że wystarczy rozpatrzeć przypadek n = 2. Wówczas

Var_{μ}(f) = E_{μ_{2}} E_{μ_{1}} (f − E_{μ}f)^{2} = E_{μ_{2}} [Var_{μ_{1}} (f) + (E_{μ_{1}} f − E_{μ}f)^{2}]
= E_{μ}Var_{μ_{1}} (f) + E_{μ_{2}} [E_{μ_{1}} (f − E_{μ_{2}} f)]^{2}
E_{μ}Var_{μ_{1}} (f) + E_{μ_{2}} E_{μ_{1}} [(f − E_{μ_{2}} f)^{2}] = E_{μ}Var_{μ_{1}} (f) + E_{μ}Var_{μ_{2}} (f),

gdzie ostatnia nierówność wynika np. z nierówności Jensena.

Wniosek 3.10. Załóżmy, że miary probabilistyczne μ_{i} na (X_{i}, d_{i}) spełniają nierówność Poincaré ze stałą C_{i} względem gradientu |∇_{i}|. Wówczas miara μ = μ_{1}⊗⋯ ⊗μ_{n} spełnia nierówność Poincaré ze stałą C = max_{i} C_{i} względem gradientu ∇f danego wzorem

|∇f|^{2} = ∑_{i=1}^{n} |∇_{i}f|^{2}.

Dowód. Z Faktu 3.9 dostajemy

Var_{μ}(f) ∑_{i=1}^{n} E_{μ}Var_{μ_{i}} (f) ∑_{i=1}^{n} E_{μ}C_{i}E_{μ_{i}} |∇_{i}f|^{2} CE_{μ} ∑_{i=1}^{n} |∇_{i}f|^{2}.

Wniosek 3.11. Produktowy rozkład wykładniczy ν^{n} spełnia nierówność Poincaré na ℝ^{n} ze stałą 4. W szczególności α_{ν^{n}} (t) 2 exp(−t/4).

Kolejną przyjemną własnością nierówności Poincaré jest jej stabilność ze względu na zaburzenia miary μ.

Fakt 3.12. Załóżmy, że μ jest miarą probabilistyczną na X, V jest ograniczoną funkcją borelowską oraz dν = Z^{−1} e^{V}dμ, gdzie Z = ∫ e^{V}dμ. Wówczas jeśli miara μ spełnia nierówność Poincaré ze stałą C to ν spełnia nierówność Poincaré ze stałą Ce^{2∥V ∥_{∞}} .

Dowód. Weźmy funkcję lipschitzowską f, odejmując stałą możemy założyć, że E_{μ}f = 0. Wówczas

Var_{ν}(f) E_{ν}f^{2} = \frac{1}{Z} ∫ f^{2}e^{V}dμ \frac{1}{Z} e^{∥V ∥_{∞}} ∫ f^{2}dμ

\frac{1}{Z} e^{∥V ∥_{∞}} C ∫ |∇f|^{2}dμ = Ce^{∥V ∥_{∞}} ∫ |∇f|^{2}e^{−V} dν

Ce^{2∥V ∥_{∞}} ∫ |∇f|^{2}dν.

Fakt 3.13. Jeśli miara ν na (Y, ρ) jest L-lipschitzowskim obrazem miary μ na (X, d) oraz μ spełnia nierówność Poincaré ze stałą C, to ν spełnia nierówność Poincaré ze stałą CL^{2}.

Dowód. Niech ν = μ ∘ φ^{−1} , gdzie φ: X → Y i ∥φ∥_{Lip} L. Dla funkcji lipschitzowskich f na Y otrzymujemy

Var_{ν}(f) = Var_{μ}(f ∘ φ) C ∫ |∇f ∘ φ|^{2}dμ
CL^{2} ∫ |∇f|^{2}(φ(x))dμ(x) = CL^{2} ∫ |∇f|^{2}dν,

gdzie przedostatnia nierówność wynika z punktowego oszacowania |∇f ∘ φ|(x) L|∇f|(φ(x)).

Wniosek 3.14. Istnieje stała uniwersalna L_{0} 12.5 taka, że dowolna miara symetryczna log-wklęsła μ o wariancji 1 na prostej jest L_{0}-lipschitzowskim obrazem symetrycznej miary wykładniczej ν. Stąd μ spełnia nierówność Poincare ze stałą 4L_{0}^{2} 620.

Dowód. Niech g będzie gęstością miary μ, wówczas g = e^{−h} , gdzie h: ℝ → (−∞, ∞] jest funkcją parzystą wypukłą, w szczególności g(0) = ∥g∥_{∞} . Określmy

x_{0} := inf{x > 0: g(x) g(0)/e}.

Zauważmy, że z log-wklęsłości wynika, że g(x) e^{−x/x_{0}} g(0) dla x > x_{0} oraz g(0) g(x) g(0)/e dla 0 x < x_{0}. Stąd

2x_{0} \frac{g(0)}{e} ∫_{−x_{0}}^{x_{0}} g(x)dx 1 = 2(∫_{0}^{x_{0}} + ∫_{x_{0}}^{∞} )g(x)dx

2(x_{0}g(0) + ∫_{x_{0}}^{∞} e^{−x/x_{0}} g(0)dx) = 2x_{0}g_{0}(1 + \frac{1}{e}).

Analogicznie

\frac{2}{3}x_{0}^{3} \frac{g(0)}{e} ∫_{−x_{0}}^{x_{0}} x^{2}g(x)dx 1 = 2(∫_{0}^{x_{0}} + ∫_{x_{0}}^{∞} )x^{2}g(x)dx

2g(0)(∫_{0}^{x_{0}} x^{2}dx + ∫_{x_{0}}^{∞} x^{2}e^{−x/x_{0}} dx) = 2x_{0}^{3}g_{0}(\frac{1}{3} + \frac{5}{e}).

Zatem

\frac{e}{2(e + 1)} x_{0}g(0) \frac{e}{2}, \frac{3e}{2(e + 15)} x_{0}^{3}g(0) \frac{3e}{2},

skąd wnioskujemy, że

\sqrt{\frac{3}{e + 15}} x_{0} \sqrt{3(e + 1)} oraz \frac{e}{2\sqrt{3}(e + 1)^{3/2}} g(0) \frac{e\sqrt{e + 15}}{2\sqrt{3}} .

Określmy φ: ℝ → ℝ wzorem

ν(−∞, x] = μ(−∞, φ(x)].

Wówczas φ transportuje ν na μ, jest nieparzysta i niemalejąca, zatem

∥φ∥_{Lip} = sup_{x 0}φ′(x) = sup_{x 0} \frac{1}{2} \frac{e^{−x}}{g(φ(x))} .

Rozpatrzmy dwie możliwości:

i) φ(x) x_{0}. Wówczas g(φ(x)) g(0)/e i

\frac{1}{2} \frac{e^{−x}}{g(φ(x))} \frac{e}{2g(0)} \sqrt{3}(e + 1)^{3/2}.

ii) φ(x) > x_{0}. Zauważmy, że z logarytmicznej wklęsłości g wynika, że g(φ(x)+ t) g(φ(x))e^{−t/x_{0}} dla t > 0, stąd

\frac{1}{2}e^{−x} = ν([x, ∞)) = μ([φ(x), ∞)) = ∫_{0}^{∞} g(φ(x) + t)dt
∫_{0}^{∞} g(φ(x))e^{−t/x_{0}} dt = x_{0}g(φ(x)).

Zatem

\frac{1}{2} \frac{e^{−x}}{g(φ(x))} x_{0} \sqrt{3(e + 1)} .

Podsumowując oba przypadki otrzymujemy ∥φ∥_{Lip} \sqrt{3}(e + 1)^{3/2} 12.5.

Uwaga. Wniosek 3.14 (z nieco gorszą stałą) jest prawdziwy bez założenia symetrii miary μ. Dowód jest bardzo podobny, choć nieco bardziej żmudny.

3.3.1 Charakteryzacja na prostej

Okazuje się, że daje się podać prostą charakteryzację miar na ℝ, które spełniają nierówność Poincaré. Zanim ją sformułujemy podamy ściśle związany fakt dotyczący tak zwanych ważonych nierówności Hardy’ego.

Twierdzenie 3.15 (Muckenhoupt). Załóżmy, że μ i ν są miarami na [0, ∞). Wówczas istnieje stała C < ∞ taka, że dla każdej funkcji ograniczonej f,

∫_{0}^{∞} | ∫_{0}^{x} f(t)dt|^{2}dμ C ∫_{0}^{∞} |f(x)|^{2}dν(x)  (6)

wtedy i tylko wtedy gdy

B := sup_{r 0}μ[r, ∞) ∫_{0}^{r} \frac{1}{p(x)}dx < ∞,

gdzie p oznacza gęstość części absolutnej ν. Co więcej, jeśli C_{opt} jest najmniejszą stałą C taką, że zachodzi (6), to B C_{opt} 4B.

Dowód. Zamieniając f na |f| i zauważając, że wyzerowanie f na nośniku części singularnej ν nie zmienia lewej strony (6) wnioskujemy, że wystarczy badać nierówność

∫_{0}^{∞} | ∫_{0}^{x} f(t)dt|^{2}dμ C ∫_{0}^{∞} |f(x)|^{2}p(x)dx  (7)

dla nieujemnych f.

Zauważmy, że dla f 0 (7) implikuje

μ[r, ∞)( ∫_{0}^{r} f(t)dt)^{2} C ∫_{0}^{r} |f(x)|^{2}p(x)dx

Przyjmując f(x) = \frac{1}{p(x)}𝟙_{\{p(x) 1/n\}} i biorąc najlepszą możliwą stałą dostajemy

μ[r, ∞) ∫_{0}^{r} \frac{1}{p(x)}𝟙_{\{p(x) 1/n\}} dx C_{opt},

skąd po przejściu z n → ∞ i wzięciu supremum po r dostajemy B C_{opt}.

By udowodnić, że C_{opt} 4B wystarczy wykazać, że (7) zachodzi z C = 4B. Załóżmy wpierw, że miara μ ma gęstość g i przyjmijmy

h(x) := ( ∫_{0}^{x} \frac{1}{p(t)}dt)^{1/2}

wówczas na mocy nierówności Schwarza i twierdzenia Fubiniego

∫_{0}^{∞} | ∫_{0}^{x} f(t)dt|^{2}dμ = ∫_{0}^{∞} | ∫_{0}^{x} f(t)dt|^{2}g(x)dx

∫_{0}^{∞} g(x)[ ∫_{0}^{x} f^{2}(t)p(t)h(t)dt ∫_{0}^{x} \frac{1}{p(u)h(u)}du]dx

= ∫_{0}^{∞} f^{2}(t)p(t)h(t)[ ∫_{t}^{∞} g(x) ∫_{0}^{x} \frac{1}{p(u)h(u)}dudx]dt

Zauważmy, że

∫_{0}^{x} \frac{1}{p(u)h(u)}du = ∫_{0}^{x} 2h′(u)du = 2h(x),

więc na mocy definicji B (użytej dwa razy)

∫_{t}^{∞} g(x) ∫_{0}^{x} \frac{1}{g(u)h(u)}dudx = 2 ∫_{t}^{∞} g(x)( ∫_{0}^{x} \frac{1}{p(u)}du)^{1/2}dx
2\sqrt{B} ∫_{t}^{∞} g(x)( ∫_{x}^{∞} g(u)du)^{−1/2} dx = 4\sqrt{B} ∫_{t}^{∞} \frac{d}{dx}( − ∫_{x}^{∞} g(u)du)^{1/2}dx
= 4\sqrt{B}( ∫_{t}^{∞} g(x)dx)^{1/2} 4B( ∫_{t}^{∞} \frac{1}{p(x)}dx)^{−1/2} = 4Bh^{−1} (t).

Zatem

∫_{0}^{∞} | ∫_{0}^{x} f(t)dt|^{2}dμ ∫_{0}^{∞} f^{2}(t)p(t)h(t)4Bh^{−1} (t) = 4B ∫_{0}^{∞} f^{2}(t)p(t)dt.

Jeśli miara μ nie ma gęstości, to znajdujemy miary μ_{n} z gęstościami zbieżne słabo do μ takie, że μ_{n}[x, ∞) μ[x, ∞) Można np przyjąć

μ_{n}(A) = n ∫_{0}^{1/n} μ(A + t)dt

Wówczas

sup_{r 0}μ_{n}[r, ∞) ∫_{0}^{r} \frac{1}{p(x)}dx sup_{r 0}μ[r, ∞) ∫_{0}^{r} \frac{1}{p(x)}dx = B,

więc

∫_{0}^{∞} | ∫_{0}^{x} f(t)dt|^{2}dμ = lim_{n→∞} ∫_{0}^{∞} | ∫_{0}^{x} f(t)dt|^{2}dμ_{n} 4B ∫_{0}^{∞} |f(x)|^{2}p(x)dx.

Twierdzenie 3.16. Załóżmy, że μ jest miarą probabilistyczną na ℝ o medianie m, zaś p oznacza gęstość jej części absolutnie ciągłej. Wówczas miara μ spełnia nierówność Poincaré ze skończoną stałą C wtedy i tylko wtedy gdy max{B_{+} , B_{−} } < ∞, gdzie

B_{+} = sup_{x>m} μ[x, ∞) ∫_{m}^{x} \frac{1}{p(y)}dy

B_{−} = sup_{x<m} μ(−∞, x] ∫_{x}^{m} \frac{1}{p(y)}dy.

Co więcej optymalna stała C_{opt} w nierówności Poincaré spełnia

\frac{1}{(1 + \sqrt{2})^{2}} max\{B_{+} , B_{−} \} C_{opt} 4 max\{B_{+} , B_{−} \}.

Dowód. Z Twierdzenia 3.15 (zastosowanego do miary μ obciętej do [m, ∞) i f′ zamiast f) wynika, że dla dowolnej funkcji Lipschitzowskiej f,

∫_{m}^{∞} (f(x)−f(m))^{2}dμ(x) = ∫_{m}^{∞} ( ∫_{m}^{x} f′(t)dt)^{2}dμ(x) 4B_{+} ∫_{m}^{∞} f^{′2}(x)dμ(x).

Analogicznie rozpatrując miarę μ na odcinku (−∞, m),

∫_{−∞}^{m} (f(x) − f(m))^{2}dμ(x) 4B_{−} ∫_{m}^{∞} f^{′2}(x)dμ(x).

Dodając stronami dostajemy

Var_{μ}(f) ∫ (f(x) − f(m))^{2}dμ(x) 4 max{B_{+} , B_{−} } ∫ f^{′2}(x)dμ(x),

czyli C_{opt} 4 max{B_{+} , B_{−} }.

By udowodnić nierówność w drugą stronę zauważmy, że jeśli f jest ograniczoną funkcją oraz g(x) = 0 dla x m i g(x) = ∫_{m}^{x} f(t)dt dla x > m, to g jest lipschitzowska, g′(x) = f(x)𝟙_{{x m}} p.w. oraz Med_{μ}(g) = 0. Stąd na podstawie Faktu 3.6,

∫_{m}^{∞} | ∫_{m}^{x} f(t)dt|^{2}dμ = ∫ |g(x) − Med_{μ}g|^{2}dμ(x)
(1 + \sqrt{2})^{2}C_{opt} ∫_{0}^{∞} g^{′2}(x)dμ(x)
= (1 + \sqrt{2})^{2}C_{opt} ∫_{m}^{∞} |f(x)|^{2}dμ(x).

Stąd Twierdzenie 3.15 implikuje B_{+} (1 + \sqrt{2})^{2}C_{opt}, analogicznie pokazujemy B_{−} (1 + \sqrt{2})^{2}C_{opt}.

3.4 Logarytmiczna Nierówność Sobolewa

Definicja 3.4. Załóżmy, że μ jest miarą probabilistyczną na X, zaś f nieujemną funkcją mierzalną na X. Entropię f względem μ definiujemy wzorem

Ent_{μ}(f) := \{ \begin{matrix}∫ f logfdμ − ∫ fdμ log∫ fdμ & jeśli ∫ f log(1 + f)dμ < ∞ \\ ∞ & jeśli ∫ f log(1 + f)dμ = ∞. \end{matrix}

Z wypukłości funkcji x logx na [0, ∞) wynika, że Ent_{μ}(f) 0, łatwo też zauważyć, że Ent_{μ}(λf) = λEnt_{μ}(f) dla λ 0.

Definicja 3.5. Mówimy, że miara probabilistyczna na (X, d) spełnia logarytmiczną nierówność Sobolewa ze stałą C, jeśli dla wszystkich ograniczonych lipschitzowskich funkcji f na X zachodzi

Ent_{μ}(f^{2}) 2C ∫ |∇f|^{2}dμ.  (8)

Twierdzenie 3.17. Załóżmy, że miara μ spełnia logarytmiczną nierówność Sobolewa ze stałą C. Wówczas dla każdej funkcji 1-lipschitzowskiej F i t > 0

μ( \{F ∫ F dμ + t\}) exp( − \frac{t^{2}}{2C}).

W szczególności α_{X}(t) exp(−t^{2}/8C).

Dowód. Ustalmy ograniczoną funkcję 1-Lipschitzowską F taką, że ∫ F dμ = 0. Wystarczy, że pokażemy iż dla λ 0

M(λ) := M_{F,λ} = ∫ e^{λF} dμ e^{Cλ^{2}/2} .

Zastosujmy logarytmiczną nierówność Sobolewa do f^{2} := e^{λF} . Wówczas

Ent_{μ}(f^{2}) = λE_{μ}F e^{λF} − E_{μ}e^{λF} logE_{μ}e^{λF} = λM′(λ) − M(λ) logM(λ)

oraz

∫ |∇f|^{2}dμ = \frac{λ^{2}}{4} ∫ |∇F |^{2}e^{λF} \frac{λ^{2}}{4} M(λ).

Zatem (8) daje

λM′(λ) − M(λ) logM(λ) C \frac{λ^{2}}{2} M(λ).  (9)

Określmy H(λ) := \frac{1}{λ} logM(λ) dla λ > 0. Wówczas

lim_{λ→0} H(λ) = \frac{M′(0)}{M(0)} = ∫ F dμ = 0

oraz na podstawie (9)

H′(λ) = −\frac{1}{λ^{2}} logM(λ) + \frac{1}{λ} \frac{M′(λ)}{M(λ)} \frac{C}{2}.

Zatem H(λ) Cλ/2 czyli M(λ) exp(Cλ^{2}/2).

Lemat 3.18. Dla dowolnej funkcji nieujemnej na X,

Ent_{μ}(f) = sup{ ∫ fgdμ: ∫ e^{g}dμ 1}.  (10)

Dowód. Z jednorodności obu stron (10) możemy zakładać, że ∫ fdμ = 1, wówczas Ent_{μ}(f) = ∫ f logfdμ.

Nietrudno sprawdzić, że dla u > 0, sup_{v∈ℝ}(uv − e^{v}) = u logu − u, zatem

uv u logu − u + e^{v} dla u 0, v ∈ ℝ.  (11)

Zatem biorąc g takie, że ∫ e^{g}dμ 1 dostajemy

∫ fgdμ ∫ (f logf − f + e^{g})dμ = Ent_{μ}(f) − 1 + ∫ e^{g}dμ Ent_{μ}(f).

By udowodnić nierówność w przeciwną stronę wystarczy przyjąć g = logf.

Z powyższego lematu łatwo wykazać tensoryzowalność entropii:

Fakt 3.19. Załóżmy, że μ_{i} są miarami probabilistycznymi na X_{i}, X = X_{1}× … × X_{n} oraz μ = μ_{1} ⊗ μ_{2} ⊗ ⋯⊗ μ_{n}. Wówczas dla dowolnej nieujemnej funkcji f na X

Ent_{μ}(f) ∑_{i=1}^{n} E_{μ}Ent_{μ_{i}} (f).

Dowód. Weźmy funkcję g na X taką, że ∫ e^{g}dμ 1 oraz przyjmijmy dla i = 1, …, n,

g^{i}(x_{1}, …, x_{n}) := log( \frac{∫ e^{g(x_{1},...,x_{n})} dμ_{1}(x_{1}) ⋯dμ_{i−1} (x_{i−1} )}{∫ e^{g(x_{1},...,x_{n})} dμ_{1}(x_{1}) ⋯dμ_{i}(x_{i})} ).

Wówczas g ∑ _{i=1}^{n} g^{i} oraz ∫ e^{g^{i}}dμ_{i} 1, stąd

∫ fgdμ ∑_{i=1}^{n} ∫ fg^{i}dμ = ∑_{i=1}^{n} ∫ ( ∫ fg^{i}dμ_{i})dμ ∑_{i=1}^{n} ∫ Ent_{μ_{i}} (f)dμ.

Wniosek 3.20. Załóżmy, że miary probabilistyczne μ_{i} na (X_{i}, d_{i}) spełniają logarytmiczną nierówność Sobolewa ze stałą C_{i} względem gradientu |∇_{i}|. Wówczas miara μ = μ_{1}⊗⋯ ⊗μ_{n} spełnia logarytmiczną nierówność Sobolewa ze stałą C = max_{i} C_{i} względem gradientu ∇f danego wzorem

|∇f|^{2} = ∑_{i=1}^{n} |∇_{i}f|^{2}.

Dowód. Z Faktu 3.19 dostajemy

Ent_{μ}(f^{2}) ∑_{i=1}^{n} E_{μ}Ent_{μ_{i}} (f^{2}) ∑_{i=1}^{n} E_{μ}2C_{i}E_{μ_{i}} |∇_{i}f|^{2} 2CE_{μ} ∑_{i=1}^{n} |∇_{i}f|^{2}.

Fakt 3.21. i) Niech μ_{1} = \frac{1}{2}δ_{1} + \frac{1}{2}δ_{−1} , wówczas dla dowolnego f: \{−1, 1\} → ℝ,

Ent_{μ_{1}} (f^{2}) 2Ent_{μ_{1}} |Df|^{2},

gdzie Df(x) = \frac{1}{2}(f(x) − f(−x)).

ii) Niech μ_{n} = μ_{1} ⊗ ⋯ ⊗ μ_{1} będzie rozkładem jednostajnym na {−1, 1}^{n}, wówczas dla dowolnego f: {−1, 1}^{n} → ℝ,

Ent_{μ_{n}} (f^{2}) 2Ent_{μ_{n}} |Df|^{2},

gdzie |Df|^{2}(x) = \frac{1}{4} ∑ _{i=1}^{n} (f(x)−f(s_{i}(x)))^{2} oraz s_{i}((x_{1}, …, x_{n})) = (x_{1}, …, x_{i−1} , −x_{i}, x_{i+1} , …, x_{n}).

Dowód. i) Z uwagi na jednorodność możemy zakładać, że E_{μ_{1}} f^{2} = 1, wówczas istnieje t ∈ [−1, 1] takie, że f(1) = 1+t oraz f(−1) = 1−t i nierówność z punktu i) ma postać α(t) 0, gdzie

α(t) := 1 − \sqrt{1 − t^{2}} − \frac{1 + t}{2} log(1 + t) − \frac{1 − t}{2} log(1 − t).

Nietrudno sprawdzić, że α(0) = α′(0) = 0 oraz

α′′(t) = \frac{1}{1 − t^{2}} ( \frac{t^{2}}{\sqrt{1 − t^{2}}} − \frac{t^{2}}{1 + \sqrt{1 − t^{2}}} ) 0,

więc istotnie α(t) 0.

ii) Wynika z punktu i) i Faktu 3.19.

Twierdzenie 3.22. Miara γ_{n} spełnia logarytmiczną nierówność Sobolewa z C = 1.

Dowód. Z uwagi na Fakt 3.19 wystarczy rozważyć przypadek n = 1. Niech f ∈ C_{ogr}^{1}(ℝ). Określmy g_{n}: {−1, 1}^{n} → ℝ wzorem

g_{n}(x) := f(\frac{x_{1} + … + x_{n}}{\sqrt{n}} ).

Niech μ_{n} i |Df| będą jak w Fakcie 3.21. Wówczas na mocy centralnego twierdzenia granicznego

Ent_{μ_{n}} (g_{n}^{2}) = ∫ g_{n}^{2} logg_{n}^{2}dμ_{n} − ∫ g_{n}^{2}dμ_{n} log∫ g_{n}^{2}dμ_{n} → Ent_{γ_{1}}(f^{2}).

Ponadto kładąc T_{n}(x) = n^{−1/2} (x_{1} + … + x_{n})

|Dg_{n}|(x)^{2} = \frac{1}{4} ∑_{i=1}^{n} (f(T_{n}(x)) − f(T_{n}(x) − 2\frac{x_{i}}{\sqrt{n}}))^{2} = f′(T_{n}(x))^{2} + r_{n}

gdzie r_{n} zbiega do zera jednostajnie względem |T_{n}(x)|. Zatem

lim_{n→∞} E_{μ_{n}} |Dg_{n}|(x)^{2} = lim_{n→∞} E_{μ_{n}} f′(T_{n}(x))^{2} = E_{γ_{1}}f′(x)^{2}.

Fakt 3.23. Załóżmy, że μ jest miarą probabilistyczną na X, V jest ograniczoną funkcją borelowską oraz dν = Z^{−1} e^{V}dμ, gdzie Z = ∫ e^{V}dμ. Wówczas jeśli miara μ spełnia logaryticzną nierówność Sobolewa ze stałą C to ν spełnia logarytmiczną nierówność Sobolewa ze stałą Ce^{4∥V ∥_{∞}} .

Dowód. Funkcja φ(u) = u logu jest wypukła na [0, ∞) stąd dla dowolnych s, t, φ(s + t) φ(t) + φ′(t)s, więc

φ( ∫ f^{2}dν) = φ(t + ∫ (f^{2} − t)dν) φ(t) + φ′(t) ∫ (f^{2} − t)dν.

Zatem

Ent_{ν}(f^{2}) = inf_{t∈ℝ}[φ(f) − φ(t) − φ′(t)(f^{2} − t)]dν

\frac{1}{Z} e^{∥V ∥_{∞}} inf_{t∈ℝ} ∫ [φ(f) − φ(t) − φ′(t)(f^{2} − t)]Ze^{−V} dν

= \frac{1}{Z} e^{∥V ∥_{∞}} Ent_{μ}(f^{2}) \frac{2C}{Z}e^{∥V ∥_{∞}} ∫ |∇f|^{2}dμ

2Ce^{2∥V ∥_{∞}} ∫ |∇f|^{2}dν.

Kolejny fakt dowodzimy tak samo jak dla nierówności Poincaré.

Fakt 3.24. Jeśli miara ν na (Y, ρ) jest L-lipschitzowskim obrazem miary μ na (X, d) oraz μ spełnia logarytmiczną nierówność Sobolewa ze stałą C, to ν spełnia logarytmiczną nierówność Sobolewa ze stałą CL^{2}.

Stosując nierówność logarytmiczną Sobolewa do funkcji f = 1 + εg dowodzimy

Fakt 3.25. Jeśli miara probabilistyczna μ spełnia logarytmiczną nierówność Sobolewa ze stałą C, to spełnia również nierówność Poincaré ze stałą C.

Opierając się na twierdzeniu Muckenhoupta da się wyprowadzić kryterium równoważne nierówności logarytmicznej Sobolewa dla miar na prostej.

Twierdzenie 3.26. Załóżmy, że μ jest miarą probabilistyczną na ℝ o medianie m, zaś p oznacza gęstość jej części absolutnie ciągłej. Wówczas miara μ spełnia logarytmiczną nierówność Sobolewa ze skończoną stałą C wtedy i tylko wtedy gdy max{B_{+} , B_{−} } < ∞, gdzie

B_{+} = sup_{x>m} μ[x, ∞) ln( \frac{1}{μ[x, ∞)} ) ∫_{m}^{x} \frac{1}{p(y)}dy

B_{−} = sup_{x<m} μ(−∞, x] ln( \frac{1}{μ(−∞, x]} ) ∫_{x}^{m} \frac{1}{p(y)}dy.

Co więcej optymalna stała C_{opt} w nierówności Poincaré spełnia

\frac{1}{150}(B_{+} + B_{−} ) C_{opt} 468(B_{+} + B_{−} ).

3.5 Nierówność Bobkowa

Nierówność logarytmiczna Sobolewa implikuje koncentrację gaussowską, ale nie implikuje gaussowskiej izoperymetrii. Okazuje się, że jest silniejsza nierówność, która implikuje gaussowską izoperymetrię, a jednocześnie ma szereg równie dobrych własności jak nierówność Poincaré czy logarytmiczna nierówność Sobolewa.

Przedstawione poniżej rozumowania można podobnie jak w poprzednich sekcjach prowadzić w większej ogólności, jednak by uniknąć szczegółów technicznych ograniczymy się do miar na ℝ^{n} i funkcji gładkich.

W tej części przez I będziemy oznaczać gaussowską funckję izoperymetryczną, tzn I(x) = φ(Φ^{−1} (x)), gdzie φ = (2π)^{−1/2} exp(−|x|^{2}/2). Dodatkowo określamy I(0) = I(1) = 0.

Definicja 3.6. Mówimy, że miara probabilistyczna μ na ℝ^{n} spełnia nierówność Bobkowa ze stałą C, jeśli dla wszystkich f ∈ C_{ogr}^{1}(ℝ^{n}) o wartościach w przedziale [0, 1] zachodzi

I( ∫ fdμ) ∫ \sqrt{I(f)^{2} + C|∇f|^{2}} dμ.  (12)

Fakt 3.27. Jeśli miary μ_{i} spełniają nierówność Bobkowa ze stałymi C_{i}, to miara μ_{1} ⊗ ⋯⊗ μ_{n} spełnia nierówność Bobkowa ze stałą max_{i} C_{i}.

Twierdzenie 3.28. Jeśli miara probabilistyczna μ na ℝ^{n} spełnia nierówność Bobkowa na ze stałą C, to

μ^{+} (A) I(μ(A)) dla A ∈ B(ℝ^{n})

oraz

μ(A_{t}) Φ(Φ^{−1} (μ(A)) + t) dla A ∈ B(ℝ^{n}), t > 0.

Twierdzenie 3.29. Kanoniczna miara gaussowska γ_{n} spełnia nierówność Bobkowa z C = 1.

3.6 Nierówności Splotu Infimum

Zacznijmy od zaproponowanej przez Maureya definicji.

Definicja 3.7. Splotem infimum dwu funkcji f i g określonych na ℝ^{n} nazywamy funkcję f□g daną wzorem

f□g(x) := inf{f(y) + g(x − y): y ∈ ℝ^{n}}.

Niech μ będzie miarą probabilistyczną na ℝ^{n} oraz φ: ℝ^{n} → [0, ∞]. Mówimy, że para (μ, φ) ma własność (τ) bądź, że miara μ spełnia nierówność splotu infimum z funkcją kosztu φ jeśli

∫ e^{f□φ} dμ ∫ e^{−f} dμ 1

dla dowolnej ograniczonej mierzalnej funkcji f na ℝ^{n}.

Pierwszą użyteczną cechą własności (τ) jest jej tensoryzowalność.

Fakt 3.30. Jeśli pary (μ_{i}, φ_{i}) mają własność (τ), μ = μ_{1} ⊗ ⋯⊗ μ_{n} oraz

φ(x_{1}, …, x_{n}) = φ_{1}(x_{1}) + … + φ_{n}(x_{n}),

to również para (μ, φ) ma własność (τ).

Dowód. Prosty argument indukcyjny pokazuje, że wystarczy udowodnić tezę dla n = 2. Niech f = f(x, y) będzie ograniczoną funkcją na ℝ^{n_{1}} × ℝ^{n_{2}} , określmy g na ℝ^{n_{2}} jako

g(y) := − ln( ∫ e^{−f(x,y)} dμ_{1}(x)).

Dodatkowo wprowadźmy oznaczenie f^{y}(x) = f(x, y). Wówczas dla dowolnych y, ỹ

∫ e^{f□φ(x,y)} dμ_{1}(x) ∫ e^{fỹ□φ_{1}(x)+φ_{2}(y−ỹ)} dμ_{1}(x) e^{g(ỹ)+φ_{2}(y−ỹ)}

na mocy własności (τ) dla (μ_{1}, φ_{1}). Stąd

∫ e^{f□φ(x,y)} dμ_{1}(x) e^{g□φ_{2}(y)}

i korzystając z Twierdzenia Fubiniego i (τ) dla (μ_{1}, φ_{2}).

∫ e^{f□φ} dμ_{1} ⊗ μ_{2} ∫ e^{g□φ_{2}(y)} dμ_{2}(y) ( ∫ e^{−g(y)} dμ_{2}(y))^{−1}
= (∫ e^{−f} dμ_{1} ⊗ μ_{2})^{−1} .

Następny fakt pokazuje w jaki sposób można transportować (τ).

Fakt 3.31. Załóżmy, że μ jest miarą probabilistyczną na ℝ^{n}, zaś φ funkcją kosztu na ℝ^{n} taką, że (μ, φ) spełnia własność (τ). Jeśli T: ℝ^{n} → ℝ^{m} oraz funkcja ψ na ℝ^{m} spełnia ψ(T x − T y) φ(x − y) dla wszystkich x, y, to para (μ ∘ T^{−1} , ψ) ma własność (τ).

Dowód. Niech f będzie ograniczoną funkcją na ℝ^{m}. Zauważmy, że

f ∘T □φ(x) = inf_{y}(f(T y)+φ(x−y)) inf_{y}(f(T y)+ψ(T x−T y)) f□ψ(T x).

Zatem

∫ e^{f□ψ} dμ ∘ T^{−1} = ∫ e^{f□ψ(T x)} dμ(x) ∫ e^{f∘T □φ(x)} dμ(x) ( ∫ e^{−f∘T} dμ)^{−1}
= ( ∫ e^{−f} dμ ∘ T^{−1} )^{−1} .

By sformułować związki nierówności splotu infimum z koncentracją określmy zbiór

B_{φ}(t) = {x: φ(x) t}.

Zacznijmy od prostego faktu Fakt 3.32. Jeśli (μ, φ) ma własność (τ) to dla dowolnego zbioru borelowskiego A takiego, że μ(A) > 0 mamy

1 − μ(A + B_{φ}(t)) \frac{1}{μ(A)} e^{−t} .

Dowód. Zastosujmy własność (τ) do funkcji f = 0 na zbiorze A i f = ∞ poza zbiorem A. Zauważmy, że f□φ t poza zbiorem A + B_{φ}(t), zatem

1 ∫ e^{f□φ} dμ ∫ e^{−f} dμ e^{t}(1 − μ(A + B_{φ}(t))μ(A).

Uwaga. Funkcja f w poprzednim dowodzie nie była oczywiście ograniczona, ale łatwo ominąć ten problem stosując nierówność (τ) do f_{n} = n𝟙_{ℝ^{n} \A} dla n t.

Poprzedni Fakt daje dobre oszacowanie tylko dla dużych wartości t. Nieco modyfikując jego dowód da się uzyskać też nierówności koncentracyjne dla małych t.

Fakt 3.33. Załóżmy, że para (μ, φ) ma własność (τ). Wówczas dla dowolnego zbioru borelowskiego A i t > 0,

μ(A + B_{φ}(t)) \frac{e^{t}μ(A)}{(e^{t} − 1)μ(A) + 1} .  (13)

W szczególności

μ(A + B_{φ}(t)) > min{e^{t/2}μ(A), 1/2}  (14)

oraz

μ(A) \frac{1}{2} ⇒ 1 − μ(A + B_{φ}(t)) < e^{−t/2} (1 − μ(A)).  (15)

Ponadto

μ(A) = ν(−∞, x] ⇒ μ(A + B_{φ}(t)) ν(−∞, x + t/2].  (16)

Dowód. Niech f(x) = t𝟙_{ℝ^{n} \A}. Wówczas f jest nieujemna, więc f□φ też jest nieujemna (rozpatrujemy tylko nieujemne funkcje kosztu). Dla x ∉ A+B_{φ}(t) mamy f□φ(x) t.

Zatem własność (τ) daje

1 ∫ e^{f□φ(x)} dμ(x) ∫ e^{−f(x)} dμ(x)

[μ(A + B_{φ}(t)) + e^{t}(1 − μ(A + B_{φ}(t)))][μ(A) + e^{−t} (1 − μ(A))], skąd bezpośredni rachunek prowadzi do (13).

Niech f_{t}(p) := e^{t}p/((e^{t} − 1)p + 1), zauważmy, że f_{t} is rosnąca względem p oraz dla p e^{−t/2} /2,

(e^{t} − 1)p + 1 e^{t/2} + 1 − \frac{1}{2}(e^{t/2} + e^{−t/2} ) < e^{t/2},

skąd otrzymujemy (14). Ponadto dla p 1/2,

1 − f_{t}(p) = \frac{1 − p}{(e^{t} − 1)p + 1} \frac{1 − p}{(e^{t} + 1)/2} < e^{−t/2} (1 − p)

i dostajemy (15).

Niech F (x) = ν(−∞, x] i g_{t}(p) = F (F^{−1} (p) + t). Poprzednie rachunki pokazują, że dla t, p > 0, f_{t}(p) g_{t/2}(p), jeśli F^{−1} (p)+t/2 0 lub F^{−1} (p)

0. Ponieważ g_{t+s} = g_{t} ∘ g_{s} i f_{t+s} = f_{t} ∘ f_{s}, otrzymujemy f_{t}(p) g_{t/2}(p) dla wszystkich t, p > 0, zatem (13) implikuje (16).

Niech jak do tej pory ν oznacza miarę na ℝ z gęstością \frac{1}{2}e^{−|x|} , zaś ν_{+} , ν_{−} miary z gęstościami odpowiednio e^{−x} 𝟙_{[0,∞)} i e^{x}𝟙_{(−∞,0]} .

Fakt 3.34. Para (ν_{+} , φ_{0}) ma własność (τ), gdzie

φ_{0}(x) = \{ \begin{matrix}\frac{1}{18}x^{2} & dla |x| 2 \\ \frac{2}{9}(|x| − 1) & dla |x| > 2. \end{matrix}

Lemat 3.35. Dla wszystkich x ∈ ℝ mamy 2|φ′_{0}(x)| 1 oraz

(1 − 4φ′_{0}(x)^{2})e^{φ_{0}(x)} 1.

Dowód. Pierwszą nierówność otrzymujemy przez łatwe sprawdzenie. By udowodnić drugą, z uwagi na symetrię φ_{0}, wystarczy rozpatrywać przypadek x 0. Ponadto φ′_{0}(x) jest stałe dla x 2 a φ_{0} rosnące na tym przedziale, więc możemy zakładać, że 0 x 2. Wówczas nierówność po podstawieniu y = x^{2}/18 ma postać

e^{−y} 1 − \frac{8}{9}y, 0 y \frac{2}{9}.

Funkcja e^{−y} jest wypukła, więc wystarczy sprawdzić tylko y = 0 i y = 2/9.

Dowód Faktu 3.34. Ustalmy funkcję ograniczoną f, przyjmijmy g := f□φ_{0} i niech

I_{0} := ∫_{0}^{∞} e^{−f(x)−x} dx, I_{1} := ∫_{0}^{∞} e^{g(x)−x} dx.

Musimy pokazać, że I_{0}I_{1} 1. Dla t ∈ (0, 1) zdefiniujmy x(t) i y(t) wzorami

∫_{0}^{x(t)} e^{−f(x)−x} dx = tI_{0} oraz ∫_{0}^{y(t)} e^{g(x)−x} dx = tI_{1}.

Wówczas

x′(t) = I_{0}e^{f(x(t))+x(t)} , y′(t) = I_{1}e^{−g(y(t))+y(t)} .

Na mocy definicji g, g(y(t)) f(x(t)) + φ_{0}(y(t) − x(t)), więc

y′(t) I_{1}e^{−f(x(t))−φ_{0}(y(t)−x(t))+y(t)} .

Niech z(t) = \frac{1}{2}(x(t) + y(t)) − φ_{0}(x(t) − y(t)), wówczas

z′(t) = ( \frac{1}{2} − φ′_{0}(x(t) − y(t)))x′(t) + ( \frac{1}{2} + φ′_{0}(x(t) − y(t)))y′(t).

Pisząc dla uproszczenia x i y zamiast x(t) i y(t) stosując poprzednie oszacowanie y′(t) oraz nierówność między średnia arytmetyczną i geometryczną dostajemy (wykorzystując parzystość φ_{0})

z′(t) \frac{1}{2}(1 − 2φ′_{0}(x − y))I_{0}e^{x+f(x)} + \frac{1}{2}(1 + 2φ′_{0}(x − y))I_{1}e^{−φ_{0}(x−y)+y−f(x)}
\sqrt{1 − 4φ′_{0}(x − y)^{2}} \sqrt{I_{0}I_{1}} e^{\frac{1}{2} (x+y)− \frac{1}{2} φ_{0}(x−y)}
= \sqrt{I_{0}I_{1}} e^{z(t)} \sqrt{1 − 4φ′_{0}(x − y)^{2}} e^{\frac{1}{2} φ_{0}(x−y)} .

Zatem na mocy Lematu 3.35, (−e^{−z(t)} )′= e^{−z(t)} z′(t) \sqrt{I_{0}I_{1}} , co po odcałkowaniu daje \sqrt{I_{0}I_{1}} 1.

Uwaga. Funkcja g jest ciągła, więc y jest różniczkowalna. Funkcja f nie musi być ciągła więc x nie musi być różniczkowalna. Jednak z ograniczoności f łatwo wywnioskować lokalną Lipschitzowskość x (stąd też z), a zatem różniczkowalność x prawie wszędzie. Funkcja e^{−z(t)} jest zatem lokalnie lipschitzowska, czyli jest całką swojej pochodnej, która istnieje p.w..

Wniosek 3.36. Miara ν spełnia nierówność infimum z funkcją kosztu φ_{1} postaci

φ_{1}(t) = 2φ_{0}(\frac{t}{2}) = \{ \begin{matrix}\frac{1}{36}t^{2} & dla |t| 4 \\ \frac{2}{9}(|t| − 2) & dla |t| > 4. \end{matrix}

Dowód. Z wypukłości funkcji φ_{0} łatwo wynika, że φ_{1} = φ_{0}□φ_{0}. Ponieważ miara ν_{−} jest symetrycznym odbiciem ν_{+} a funkcja φ_{0} jest symetryczna, to (ν_{−} , φ_{0}) ma własność (τ), więc (ν_{+} ⊗ ν_{−} , φ_{0}(x) + φ_{0}(y)) też ma (τ). Miara ν jest splotem miar ν_{+} i ν_{−} , czyli obrazem ν_{+} ⊗ ν_{−} przy przekształceniu T (x, y) = x + y. Teza wynika z Faktu 3.31

Wiemy, że miara ν a zatem i miara produktowa ν^{n} spełniają nierówność Poincaré, więc jeśli ν^{n}(A) \frac{1}{2}, to ν^{n}(A+tB_{2}^{n}) 1−e^{−t/C} dla pewnej stałej absolutnej C. Okazuje się, że można tę nierówność wzmocnić.

Zanim sformułujemy twierdzenie (które pierwszy z gorszymi stałymi udowodnił Talagrand) wprowadźmy następujące oznaczenie kuli jednostkowej w l_{p}^{n} dla 1 p < ∞

B_{p}^{n} := {x ∈ ℝ^{n}: ∑_{i=1}^{n} |x_{i}|^{p} 1}.

Twierdzenie 3.37. Dla dowolnego zbioru borelowskiego A w ℝ^{n} takiego, że ν^{n}(A) > 0 mamy dla t 0,

1 − ν^{n}(A + 6\sqrt{t}B_{2}^{n} + 9tB_{1}^{n}) \frac{1}{ν^{n}(A)}e^{−t} .

Ponadto

ν^{n}(A) = ν(−∞, x] ⇒ ν^{n}(A + 6\sqrt{2t}B_{2}^{n} + 18tB_{1}^{n}) ν(−∞, x + t].

Dowód. Para (ν^{n}, φ_{n}) ma własność (τ), gdzie φ_{n}(x_{1}, …, x_{n}) = φ_{1}(x_{1}) + … + φ_{1}(x_{n}). Łatwo sprawdzić, że

B_{φ_{n}} (t) ⊂ 6\sqrt{t}B_{2}^{n} + 9tB_{1}^{n}.

Teza wynika zatem z Faktów 3.32 i 3.33.

3.7 Nierówności Splotu Infimum dla Funkcji Wypukłych

3.8 Nierówność Logarytmiczna Sobolewa dla Funkcji Wypukłych

Fakt 3.38. Załóżmy, że F: ℝ^{n} → ℝ jest lipschitzowska oraz wypukła po każdej współrzędnej. Wówczas dla dowolnej produktowej miary probabilistycznej μ na ℝ^{n},

Ent_{μ}(e^{f} ) ∫ ∫ ∑_{i=1}^{n} (x_{i} − y_{i})^{2}(∂_{i}f)^{2}(x)e^{f(x)} dμ(x)dμ(y).

Twierdzenie 3.39. Załóżmy, że F: [0, 1]^{n} → ℝ jest L-lipschitzowska oraz wypukła po każdej współrzędnej. Wówczas dla dowolnej produktowej miary probabilistycznej μ na [0, 1]^{n},

μ( \{F ∫ F dμ + t\}) exp( − \frac{t^{2}}{4L^{2}} ) dla t 0.

Dowód. Bez straty ogólności (zastępując F przez aF +b) możemy zakładać, że L = 1 oraz ∫ F = 0. Wówczas |∇F | 1 p.w., więc Fakt 3.38 implikuje, że dla λ > 0,

Ent_{μ}(e^{λF} ) λ^{2} ∫ ∫ ∑_{i=1}^{n} (x_{i} − y_{i})^{2}(∂_{i}F)^{2}(x)e^{λF (x)} dμ(x)dμ(y)
λ^{2} ∫ ∫ |∇F |^{2}(x)e^{λF (x)} dμ(x)dμ(y) λ^{2} ∫ e^{λF} dμ.

Kładąc M(λ) = ∫ e^{λF} dostajemy dla λ > 0,

λM′(λ) − M(λ) logM(λ) = Ent_{μ}(e^{λF} ) λ^{2}M(λ).

Czyli funkcja H(λ) = \frac{1}{λ} logM(λ) spełnia H′(λ) 1, a ponieważ H(0+) = ∫ F dμ = 0, więc H(λ) λ, czyli M(λ) exp(λ^{2}). Stąd Fakt 3.1 implikuje tezę.

Uwaga. Jeśli F jest wypukła, to −F jest wklęsła, a dla funkcji wklęsłych nie da się łatwo zmodyfikować dowodu Faktu 3.38. Dlatego podane metody dają tylko oszacowanie górnego odchylenia od średniej funkcji wypukłych.

3.9 Aproksymacja przez otoczkę wypukłą

W tej części będziemy zakładać, że przestrzeń X ma strukturę produktową, tzn. X = X_{1} × X_{2} × ⋯× X_{n}. Określmy

d_{a}(x, y) = ∑_{i=1}^{n} a_{i}𝟙_{{x_{i} ≠y_{i}}} .

Z Wniosku 3.3 wynika, że dla |a| = 1, α_{μ,X,d_{a}} (t) exp(−|t|^{2}/8), jednak poszerzenie zbioru w każdej z metryk d_{a} wygląda nieco inaczej. Celem tego rozdziału jest uzyskanie jednostajnej wersji tego wyniku.

Dla A ⊂ X i x ∈ X określmy

D_{A}^{c}(x) := sup_{|a|=1} d_{a}(x, A).

Okazuje się, że D_{A}^{c}(x) można zdefiniować w równoważny, nieco bardziej abstrakcyjny sposób.

Dla A ⊂ X i x ∈ X określmy

U_{A}(x) := {(𝟙_{{x_{i} ≠y_{i}}} )_{1 i n} : y ∈ A} ⊂ {0, 1}^{n}

oraz

V_{A}(x) := conv{U_{A}(x)} ⊂ [0, 1]^{n}.

Łatwo zauważyć, że V_{A}(x) jest domkniętym wielościanem wypukłym. Ponadto 0 ∈ V_{A}(x) wtedy i tylko wtedy gdy 0 ∈ A.

Kolejny fakt łączy V_{A}(x) i D_{A}^{c}(x).

Fakt 3.40. Dla dowolnego A ⊂ X i x ∈ X,

d(0, V_{A}(x)) = inf_{y∈V_{A}(x)} |y| = D_{A}^{c}(x).

Dowód. i) D_{A}^{c}(x) d(0, V_{A}(x)). Niech z ∈ V_{A}(x) takie, że |z| = d(0, V_{A}(x)). Ustalmy a ∈ S^{n−1} , wtedy

inf_{s∈U_{A}(x)} ⟨a, s⟩ = inf_{y∈V_{A}(x)}⟨a, y⟩ ⟨a, z⟩ |z|.

Zatem istnieje y ∈ A takie, że s = (𝟙_{{x_{i} ≠y_{i}}} )_{i} ∈ U_{A}(x) spełnia ⟨a, s⟩ |z|. Stąd

d_{a}(x, A) d_{a}(x, y) = ∑_{i=1}^{n} a_{i}𝟙_{{x_{i} ≠y_{i}}} = ⟨a, s⟩ |z|,

czyli D_{A}^{c}(x) |z| = d(0, V_{A}(x)).

ii) D_{A}^{c}(x) d(0, V_{A}(x)). Ustalmy z ∈ V_{A}(x) taki, że |z| = d(0, V_{A}(x)). Jeśli z = 0, to nierówność jest oczywista, w przeciwnym przypadku niech a := z/|z|. Zauważmy, że dla dowolnego s ∈ V_{A}(x) i θ ∈ [0, 1], θs+(1−θ)z ∈ V_{A}(x), zatem

|z|^{2} |θs + (1 − θ)z|^{2} = |z + θ(s − z)|^{2} = |z|^{2} + 2θ⟨z, s − z⟩ + θ^{2}|s|^{2}.

Biorąc θ → 0+ dostajemy ⟨z, s − z⟩ 0, czyli

⟨a, s⟩ = \frac{1}{|z|}⟨z, s⟩ \frac{1}{|z|}⟨z, z⟩ = |z|.

Stąd

D_{A}^{c}(x) d_{a}(x, A) = inf_{s∈U_{A}(x)} ⟨a, s⟩ |z| = d(0, V_{A}(x)).

Twierdzenie 3.41. Załóżmy, że μ = μ_{1} ⊗ ⋯⊗ μ_{n} jest probabilistyczną miarą produktową na X = X_{1}×⋯ ×X_{n}. Wówczas dla dowolnego niepustego, mierzalnego zbioru A w X,

∫ exp( \frac{(D_{A}^{c})^{2}}{4} )dμ \frac{1}{μ(A)} .

W szczególności dla t > 0,

μ(\{D_{A}^{c} t\}) \frac{1}{μ(A)} e^{−t^{2}/4} .

Dowód. Przeprowadzimy indukcję po n. Dla n = 1, mamy D_{A}^{c}(x) = 𝟙_{X\A}(x), więc

∫ exp( \frac{(D_{A}^{c})^{2}}{4} )dμ = e^{1/4}(1 − μ(A)) + μ(A) 2(1 − μ(A)) + μ(A) \frac{1}{μ(A)} .

Załóżmy, że n 2 i teza zachodzi dla n − 1. Dla uproszczenia notacji przyjmiemy

X̃ = X_{1} × ⋯× X_{n−1} , μ̃ = μ_{1} ⊗ ⋯⊗ μ_{n−1}

oraz dla x ∈ X będziemy pisać x = (x̃, x_{n}), gdzie x̃ ∈ X̃. Ustalmy A ⊂ X = X̃ × X_{n} i przyjmijmy

B = {x̃: x = (x̃, x_{n}) ∈ A} oraz A(x_{n}) = {x̃: x = (x̃, x_{n}) ∈ A} dla x_{n} ∈ X_{n}.

Zauważmy, że jeśli s ∈ U_{A(x_{n})}, to (s, 0) ∈ U_{A}(x), a jeśli t ∈ U_{B}(x), to (t, 1) lub (t, 0) należą do U_{A}(x). Zatem jeśli wybierzemy s ∈ V_{A(x_{n})}(x) oraz t ∈ V_{B}(x), to (s, 0) ∈ U_{A}(x) oraz (t, b) ∈ V_{A}(x) dla pewnego b ∈ [0, 1], czyli z wypukłości zbioru V_{A}(x), (θs+(1−θ)t, (1−θ)b) ∈ V_{A}(x). Stąd z wypukłości funkcji |x|^{2},

D_{A}^{c}(x)^{2} |θs + (1 − θ)t|^{2} + |(1 − θ)b|^{2} θ|s|^{2} + (1 − θ)|t|^{2} + (1 − θ)^{2},

czyli z dowolności wyboru t i s,

D_{A}^{c}(x)^{2} θD_{A(x_{n})}^{c}(x̃)^{2} + (1 − θ)D_{B}^{c}(x̃)^{2} + (1 − θ)^{2}.

Odcałkowywując i korzystając z nierówności Höldera dostajemy

∫X̃ exp( \frac{D_{A}^{c}(x̃, x_{n})^{2}}{4} )dμ̃(x̃)
e^{(1−θ)^{2}/4} ( ∫X̃ exp( \frac{D_{A(x_{n})}^{c}(x̃)^{2}}{4} )dμ̃(x̃))^{θ}( ∫X̃ exp( \frac{D_{B}^{c}(x̃)^{2}}{4} )dμ̃(x̃))^{1−θ} .

Zatem na mocy założenia indukcyjnego (zastosowanego do zbiorów A(x_{n}) i B w X̃) dostajemy dla dowolnego θ ∈ [0, 1],

∫X̃ exp( \frac{D_{A}^{c}(x̃, x_{n})^{2}}{4} )dμ̃(x̃) e^{(1−θ)^{2}/4} ( \frac{1}{μ̃(A(x_{n}))})^{θ}( \frac{1}{μ̃(B)})^{1−θ} .  (17)

Zauważmy teraz, że

inf_{θ∈[0,1]} e^{(1−θ)^{2}/4} u^{−θ} 2 − u dla u ∈ [0, 1].  (18)

Istotnie dla u e^{−1/2} możemy przyjąć θ = 1 + 2 logu i po zlogarytmowaniu pozostaje sprawdzić, że f(u) := log(2 − u) + log(u) + log^{2}(u) 0. Prosty rachunek pokazuje, że dla u ∈ [0, 1], (uf′)′= −2(u−2)^{−2} +2u^{−1} 0, czyli uf′(u) f′(1) = 0, więc f(u) f(1) = 0.

Dla u e^{−1/2} kładziemy θ = 0 i sprawdzamy (numerycznie lub korzystając z poprzedniego rozumowania dla u = e^{−1/2} ), że e^{1/4} 2 − e^{−1/2} 2 − u.

Nierówności (17) oraz (18) z u = μ̃(A(x_{n}))/μ̃(B) implikują

∫X̃ exp( \frac{D_{A}^{c}(x̃, x_{n})^{2}}{4} )dμ̃(x̃) \frac{1}{μ̃(B)}(2 − \frac{μ̃(A(x_{n}))}{μ̃(B)}).

Zatem

∫_{X} exp( \frac{D_{A}^{c}(x̃, x_{n})^{2}}{4} )dμ(x) ∫_{X_{n}} \frac{1}{μ̃(B)}(2 − \frac{μ̃(A(x_{n}))}{μ̃(B)})dμ_{n}(x_{n})

= \frac{1}{μ̃(B)}(2 − \frac{μ̃(A)}{μ̃(B)}) \frac{1}{μ(A)} ,

gdyż v(2 − v) 1 dla v ∈ [0, 1].

Przykład. Niech X = {0, 1}^{n} oraz μ = μ_{p}^{n}, gdzie μ_{p} = pδ_{1} + (1 − p)δ_{0}. Załóżmy, że zbiór A ⊂ {0, 1}^{n} jest monotonicznie dziedziczny, w sensie

x ∈ A, y ∈ {0, 1}^{n}, y x ⇒ y ∈ A.

Niech dla x ∈ X

N(x) := #{1 i n: x_{i} = 1},

wówczas

d_{H}(x, A) D_{A}^{c}(x)\sqrt{N(x)},

gdzie d_{H} oznacza metrykę Hamminga. Istotnie, przyjmijmy a = N(x)^{−1/2} (𝟙_{{x_{i}=1}} )_{i} i weźmy y ∈ A takie, że

d_{a}(x, y) = \frac{1}{\sqrt{N(x)}} ∑_{x_{i}=1} 𝟙_{\{y_{i} ≠x_{i}\}} D_{A}^{c}(x).

Z uwagi na monotoniczną dziedziczność A możemy przyjąć, że y_{i} = 0 dla x_{i} = 0, zatem

d_{H}(x, y) = ∑_{i=1}^{n} 𝟙_{\{x_{i} ≠y_{i}\}} = ∑_{x_{i}=1} 𝟙_{\{y_{i} ≠x_{i}\}} \sqrt{N(x)}D_{A}^{c}(x).

Stąd dla s > 0,

μ_{p}^{n}({d_{H}(x, A) r}) μ_{p}^{n}({D_{A}^{c}(x) rs^{−1/2} }) + μ_{p}^{n}({N(x) > s})

\frac{1}{μ_{p}^{n}(A)} e^{− \frac{r^{2}}{4s}} + μ_{p}^{n}(\{N(x) > s\}).

Można sprawdzić, że drugi czynnik jest mały dla s = nα z α > p.

Twierdzenie 3.41 prowadzi do koncentracji pewnej klasy funkcji lipschitzowskich w odpowiednim sensie . Mianowicie zachodzi

Wniosek 3.42. Załóżmy, że funkcja F: X → ℝ spełnia warunek

∀_{x∈X} ∃_{a=a(x)∈S^{n−1}} ∀_{y∈X} F (x) F (y) + d_{a}(x, y).  (19)

Wówczas dla dowolnej probabilistycznej miary produktowej μ na X,

μ({|F − Med_{μ}(F)| t}) 4e^{−t^{2}/4} dla t > 0.

Dowód. Dla m ∈ ℝ połóżmy A = {F m}, zauważmy, że warunek (19) implikuje, że dla dowolnego x ∈ X,

F (x) m + d_{a(x)}(x, A) m + D_{A}^{c}(x),

stąd

μ(\{F m + t\}) μ(\{D_{A}^{c}(x) t\}) \frac{1}{μ(A)} e^{−t^{2}/4} .

Zatem dla dowolnego m,

μ({F m})μ({F m + t}) e^{−t^{2}/4} .

Biorąc m = Med_{μ}(F) i m = Med_{μ}(F) − t dostajemy tezę.

4 Wybrane Zastosowania

4.1 Twierdzenie Dvoretzky’ego

W tej części wykorzystamy izoperymetrię gaussowską do dowodu twierdzenia Dvoretzky’ego, które mówi, że jeśli wymiar przestrzeni unormowanej jest odpowiednio wysoki, to da się w nią włożyć prawie izometrycznie kwymiarową przestrzeń euklidesową.

Musimy najpierw wyjaśnić co to znaczy prawie izometryczne włożenie. Ponieważ wszystkie przestrzenie euklidesowe są izometryczne, będziemy mówić o włożeniach l_{2}^{k}.

Definicja 4.1. Powiemy, że przestrzeń l_{2}^{k} się wkłada ze stałą C w przestrzeń unormowaną E, jeśli istnieją wektory v_{1}, …, v_{k} ∈ E takie, że

|t| ∥ ∑_{i=1}^{k} t_{i}v_{i} ∥ C|t| dla wszystkicht ∈ ℝ^{k}.

Uwaga 4.1 Ostatnią definicję można sformułować równoważnie (biorąc u_{i} = v_{i}/\sqrt{C}) jako istnienie u_{1}, …, u_{k} ∈ E takich, że

\frac{1}{\sqrt{C}}|t| ∥ ∑_{i=1}^{k} t_{i}u_{i} ∥ \sqrt{C}|t| dla wszystkich t ∈ S^{k−1} .

Definicja 4.2. Dla wektora gaussowskiego w przestrzeni unormowanej E postaci X = ∑ _{i=1}^{m} v_{i}g_{i}, gdzie g_{1}, …, g_{n} są niezależnymi zmiennymi N (0, 1) określmy

σ(X) := sup\{(Eφ(X)^{2})^{1/2} : φ ∈ E^{∗}, ∥φ∥ 1\} oraz d(X) := ( \frac{E∥X∥}{σ(X)} )^{2}.

Dla przestrzeni unormowanej E określamy

d(E) = sup{d(X): X = ∑_{i=1}^{m} v_{i}g_{i}, v_{i} ∈ E}.

Fakt 4.1. Jeśli X = ∑ _{i=1}^{m} v_{i}g_{i} jest wektorem gaussowskim w E, to

σ(X) = sup_{|t|=1} ∥ ∑_{i=1}^{m} t_{i}v_{i} ∥.

Dowód. Mamy

sup_{|t|=1} ∥ ∑_{i=1}^{m} t_{i}v_{i} ∥ = sup_{|t|=1} sup_{∥φ∥ 1} φ( ∑_{i=1}^{m} t_{i}v_{i}) = sup_{∥φ∥ 1} sup_{|t|=1} ∑_{i=1}^{m} t_{i}φ(v_{i})

= sup_{∥φ∥ 1} ( ∑_{i=1}^{m} φ^{2}(v_{i}))^{1/2} = sup_{∥φ∥ 1} (Eφ(X)^{2})^{1/2} = σ(X).

Jesteśmy teraz gotowi, by sformułować twierdzenie Dvoretzky’ego w wersji pochodzącej od Milmanna.

Twierdzenie 4.2. Dla dowolnego ε > 0 istnieje stała c(ε) > 0 taka, że dla dowolnej przestrzeni unormowanej E oraz k c(ε)d(E), l_{2}^{k} się wkłada ze stałą 1 + ε w E.

Zanim przejdziemy do dowodu tego twierdzenia wprowadzimy jedną ważną definicję i udowodnimy kilka lematów.

Definicja 4.3. Zbiór A ⊂ X nazywamy ε-siecią przestrzeni metrycznej (X, d), jeśli dla dowolnego x ∈ X istnieje y ∈ A takie, że d(x, y) ε.

Dalej na przestrzeni S^{n−1} będziemy rozważać metrykę dziedziczoną z przestrzeni euklidesowej ℝ^{n}.

Lemat 4.3. Dla 0 < ε 1 istnieje ε-sieć N w S^{n−1} taka, że #N (\frac{3}{ε})^{n}.

Dowód. Niech N będzie maksymalnym podzbiorem S^{n−1} którego dowolne dwa elementy są odległe o więcej niż ε. Wówczas N jest ε-siecią oraz kule (w ℝ^{n}) (B(x, ε/2))_{x∈N} są rozłączne i zawierają się w kuli B(0, 1 + ε/2). Stąd przyjmując c_{n} = λ_{n}(B(0, 1)) dostajemy

c_{n}(1 + \frac{ε}{2})^{n} = λ_{n}(B(0, 1 + \frac{ε}{2}) ) λ_{n}( ⋃_{x∈N} B(x, \frac{ε}{2}) )

= ∑_{x∈N} λ_{n}(B(x, \frac{ε}{2}) ) = #Nc_{n}( \frac{ε}{2})^{n},

zatem #N (\frac{2}{ε} + 1)^{n} (\frac{3}{ε})^{n}.

Lemat 4.4. Niech N będzie ε-siecią w S^{n−1} dla pewnego ε ∈ [0, 1]. Wówczas dla dowolnych wektorów v_{1}, …, v_{n} w E,

sup_{|t|=1} ∥ ∑_{i=1}^{n} v_{i}t_{i} ∥ \frac{1}{1 − ε} sup_{s∈N} ∥ ∑_{i=1}^{n} v_{i}s_{i} ∥

oraz

inf_{|t|=1} ∥ ∑_{i=1}^{n} v_{i}t_{i} ∥ inf_{s∈N} ∥ ∑_{i=1}^{n} v_{i}s_{i} ∥ − \frac{ε}{1 − ε} sup_{s∈N} ∥ ∑_{i=1}^{n} v_{i}s_{i} ∥.

Dowód. Z definicji ε-sieci łatwo wynika, że dowolny wektor t ∈ S^{n−1} można zapisać w postaci t = s + au, s ∈ N, u ∈ S^{n−1} , a ε, stąd

|∥ ∑_{i=1}^{n} v_{i}t_{i} ∥ − ∥ ∑_{i=1}^{n} v_{i}s_{i} ∥| a∥ ∑_{i=1}^{n} v_{i}u_{i} ∥ ε sup_{u∈S^{n−1}} ∥ ∑_{i=1}^{n} v_{i}u_{i} ∥.

Dowód Twierdzenia 4.2. Bez straty ogólności możemy przyjąć, że ε < 1, dobierzmy δ > 0 takie, że (1+δ)/(1−δ) \sqrt{1 + ε} oraz 1−δ−δ(1+δ)/(1−δ) 1/\sqrt{1 + ε} (np. można przyjąć δ = ε/20). Niech N będzie δ-siecią w S^{k−1} mocy nie większej niż (\frac{3}{δ})^{k}. Na podstawie Lematu 4.4 i Uwagi 4.1 wystarczy wykazać, że istnieją wektory u_{1}, …, u_{k} w E takie, że

1 − δ ∥ ∑_{i=1}^{k} t_{i}u_{i} ∥ 1 + δ dla t ∈ N.

Niech X = ∑ _{i=1}^{m} v_{i}g_{i} spełnia d(X) d(E)/2, dla uproszczenia notacji przyjmijmy d = d(E), σ = σ(X) oraz M = E∥X∥. Niech F: ℝ^{m} → ℝ będzie dane wzorem F (x) = ∥ ∑ _{i=1}^{m} v_{i}x_{i}∥. Wówczas na mocy Faktu 4.1 funkcja F jest σ-Lipschitzowska, ponadto X ∼ F (G), gdzie G ∼ γ_{m}. Stąd

P( | \frac{∥X∥}{M} − 1| δ) = γ_{m}( |F (G) − ∫ F dγ_{m} | δM) 2 exp( − \frac{δ^{2}M^{2}}{2σ^{2}}),

gdzie ostatnia nierówność jest konsekwencją Twierdzeń 3.17 i 3.22. Niech X_{1}, …, X_{k} będą niezależnymi kopiami zmiennej X. Wówczas, dla dowolnego t ∈ S^{n−1} , zmienne ∑ _{i=1}^{m} t_{i}X_{i} ma ten sam rozkład co X. Zatem

P( |∥ ∑_{i=1}^{k} t_{i} \frac{X_{i}}{M} ∥ − 1| δ) = P( | \frac{∥X∥}{M} − 1| δ) 2e^{−δ^{2}d(X)/2} 2e^{−δ^{2}d/4} ,

czyli

P(∃_{t∈N} |∥ ∑_{i=1}^{k} t_{i} \frac{X_{i}}{M} ∥ − 1| δ) 2#Ne^{−δ^{2}d/4} 2( \frac{3}{δ})^{k}e^{−δ^{2}d/4} < 1,

jeśli tylko k c(δ)d, czyli można za u_{i} przyjąć X_{i}(ω)/M dla pewnego ω.

By móc stosować Twierdzenie 4.2 potrzebujemy oszacowań z dołu d(E). Zacznijmy od geometrycznego lematu.

Lemat 4.5 (Dvoretzky-Rogers). Niech E będzie n-wymiarową przestrzenią unormowaną. Wówczas istnieją wektory v_{1}, …, v_{n} ∈ E takie, że ∥ ∑ _{i=1}^{n} t_{i}v_{i}∥ |t| dla t ∈ ℝ^{n} oraz ∥v_{i}∥ \frac{n−i+1}{n} .

Dowód. Przypomnijmy, że dla T: l_{2}^{n} → E określamy

∥T ∥ = sup{∥T x∥: |x| 1}.

Zbiór operatorów o normie nie większej niż jeden można traktować jako zwarty podzbiór ℝ^{n^{2}} , w szczególności istnieje operator T taki, że ∥T ∥ 1 oraz

det(T) = max{det(S): S: l_{2}^{n} → E, ∥S∥ 1}.

Wówczas dla dowolnego ε > 0,

det(T + εS) det(T)∥T + εS∥^{n}.

Mamy jednak

det(T + εS) = det(T) det(I + εT^{−1} S) = det(T)(1 + εtr(T^{−1} S) + o(ε)),

więc

1 + εtr(T^{−1} S) ∥T + εS∥^{n} + o(ε) (1 + ε∥S∥)^{n} + o(ε) 1 + εn∥S∥ + o(ε).

Wykazaliśmy w ten sposób, że tr(T^{−1} S) n∥S∥ dla dowolnego S: l_{2}^{n} → E. Niech S = T P, gdzie P oznacza rzut ortogonalny na podrzestrzeń V. Wówczas

∥T P ∥ tr(T^{−1} T P) = tr(P) = dimV.

Niech y_{1} ∈ ℝ^{n} będzie takie, że |y_{1}| = 1 i ∥T y_{1}∥ = ∥T ∥. Jeśli wybraliśmy już y_{1}, …, y_{k}, to kładziemy V_{k} = {y_{1}, …, y_{k}}^{⊥} i wybieramy y_{k+1} ∈ V_{k} takie, że |y_{k+1} | = 1 oraz ∥T y_{k+1} ∥ = ∥T P_{k}∥ (n − k)/n, gdzie P_{k} oznacza rzut ortogonalny na V_{k}. Wystarczy, że położymy v_{k} = T y_{k}.

Lemat 4.6. Niech ε_{i} będą niezależnymi symetrycznymi zmiennymi losowymi przyjmującymi wartości ±1. Wówczas dla dowolnych wektorów u_{i} ∈ E, E∥ ∑ _{i=1}^{n} u_{i}ε_{i}∥ max_{1 i n} ∥u_{i}∥.

Dowód. Mamy dla dowolnego 1 i n,

E∥ ∑_{k=1}^{n} u_{k}ε_{k}∥ = E\frac{1}{2}( ∥u_{i}ε_{i} + ∑_{k≠i}^{n} u_{k}ε_{k}∥ + ∥u_{i}ε_{i} − ∑_{k≠i}^{n} u_{k}ε_{k}∥)
E∥u_{i}ε_{i}∥ = ∥u_{i}∥.

Wniosek 4.7. Dla dowolnej przestrzeni unormowanej E wymiaru n, d(E) \frac{1}{C} logn.

Dowód. Niech v_{i} będą takie jak w Lemacie 4.5 oraz X = ∑ _{i=1}^{n} v_{i}g_{i}. Wówczas σ(X) = 1. Niech (ε_{i}) będzie ciągiem niezależnych symetrycznymi zmiennych losowych przyjmujących wartości ±1, niezależnym od (g_{i}). Wówczas na mocy symetrii g_{i},

E∥X∥ = E∥ ∑_{i=1}^{n} ε_{i}g_{i} ∥ E max_{i n}∥v_{i}g_{i}∥ \frac{1}{2}E max_{i ⌈n/2⌉} |g_{i}| c\sqrt{logn}.

Wkładanie l_{2}^{k} w przestrzeń E można wysłowić w bardziej geometryczny sposób. Mianowicie obrazem kuli w l_{2}^{k} przy liniowym, nieosobliwym przekształceniu jest k-wymiarowa elipsoida. To, że przekształcenie liniowe jest prawie izometrią znaczy, że odpowiednie k-wymiarowe przekroje kuli jednostkowej w E są bliskie tej elipsoidzie. Istnieje też wzajemna odpowiedniość między kulami jednostkowymi w n-wymiarowych przestrzeniach unormowanych a n-wymiarowymi symetrycznymi ciałami wypukłymi (tzn. zwartymi symetrycznymi zbiorami w ℝ^{n} o niepustym wnetrzu). Stąd otrzymujemy równoważne sformułowanie twierdzenia Dvoretzky’ego.

Twierdzenie 4.8. Istnieje stała c(ε) taka, że dla dowolnego n-wymiarowego symetrycznego ciała wypukłego i k c(ε) logn istnieje k wymiarowa podprzestrzeń V i elipsoida E w V taka, że

E ⊂ K ∩ V ⊂ (1 + ε)E.

4.2 Wektory i Procesy Gaussowskie

Procesy i zmienne gaussowskie odgrywają kluczową rolę w rachunku prawdopodobieństwa i statystyce matematycznej. W poprzednim paragrafie widzieliśmy też, że wektory gaussowskie pełnią ważną rolę w zastosowaniach geometrycznych. Udowodniliśmy tam też pierwszą wersję koncentracji, która jest kluczowa w rozmaitych zastosowaniach, w tej części podamy jej dokładne sformułowanie.

Zacznijmy od przypomnienia definicji.

Definicja 4.4. Proces (G_{t})_{t∈T} nazywamy procesem gaussowskim, jeśli dla dowolnych t_{1}, …, t_{n} ∈ T wektor losowy (G_{t_{1}}, …, G_{t_{n}}) ma rozkład gaussowski. Proces nazywamy scentrowanym, jeśli EG_{t} = 0 dla t ∈ T.

By uniknąć problemów związanych z mierzalnością będziemy zakładać, że zbiór T jest przeliczalny. Alternatywnie można zakładać ośrodkowość procesu.

Twierdzenie 4.9. Załóżmy, że (G_{t})_{t∈T} jest procesem gaussowskim, indeksowanym przez przeliczalny zbiór indeksów T, takim, że sup_{t∈T} G_{t} < ∞ prawie na pewno. Wówczas E sup_{t∈T} G_{t} < ∞ oraz dla u > 0,

P( sup_{t∈T}G_{t} − E sup_{t∈T}G_{t} u) exp( − \frac{u^{2}}{2σ^{2}} )  (20)

i

P( sup_{t∈T}G_{t} − E sup_{t∈T}G_{t} −u) exp( − \frac{u^{2}}{2σ^{2}} ),  (21)

gdzie

σ := sup_{t∈T}(Var(G_{t}))^{1/2}.

Dowód. Krok I. T = {t_{1}, …, t_{n}} jest zbiorem skończonym. Wówczas istnieje macierz A = (a_{ij})_{1 i n,1 j k} oraz wektor m ∈ ℝ^{n} takie, że

(G_{t_{1}}, …, G_{t_{n}}) ∼ m + AX, X ∼ γ_{k}.

Określmy F: ℝ^{k} → ℝ wzorem

F (x) = max_{1 i n} {m_{i} + ∑_{j=1}^{k} a_{ij} x_{j}},

wówczas

∥F ∥_{Lip} = max_{i}( ∑_{j=1}^{k} a_{ij}^{2} )^{1/2} = max_{i}Var(G_{t_{i}})^{1/2} = σ.

Stąd

P( sup_{t∈T}G_{t} − E sup_{t∈T}G_{t} u) = γ_{k}( {F − ∫ F dγ_{k} u}) e^{−u^{2}/2σ^{2}} ,

gdzie ostatnia nierówność wynika z Twierdzeń 3.17 i 3.22. Korzystając z tego, że funkcja −F też jest σ-lipschitzowska wyprowadzamy (21) w przypadku skończonego T.

Krok II. T = {t_{1}, t_{2}, …} jest nieskończone. Połóżmy T_{n} := {t_{1}, …, t_{n}},

M_{n} := E max_{1 i n} G_{t_{i}} oraz σ_{n} := max_{1 i n} Var(G_{t_{i}})^{1/2}.

Niech A spełnia P(sup_{t∈T} G_{t} A) 1/4. Z Kroku I dostajemy

P( max_{1 i n} G_{t_{i}} − M_{n} −σ_{n}) e^{−1/2} ,

zatem

P( max_{1 i n} G_{t_{i}} > M_{n} − σ_{n}) 1 − e^{−1/2} > \frac{1}{4} P( sup_{t∈T}G_{t} A),

stąd A M_{n} − σ_{n}. Mamy więc

E sup_{t∈T}G_{t} = sup_{n}M_{n} sup_{n}{A + σ_{n}} A + σ < ∞.

Ponadto z Kroku I wynika

P( max_{1 i n} G_{t_{i}} M_{n} + u) e^{−u^{2}/2σ_{n}^{2}} e^{−u^{2}/2σ^{2}}

i przechodząc z n → ∞ otrzymujemy (20). Podobnie wyprowadzamy (21).

Uwaga 4.2 Łącząc (20) i (21) dostajemy

P( | sup_{t∈T}G_{t} − E sup_{t∈T}G_{t}| u) 2 exp( − \frac{u^{2}}{2σ^{2}} ) dla u > 0.

Zauważmy też, że |G_{t}| = max{G_{t}, −G_{t}}, więc w (20), (21) i powyższej nierówności można zastąpić G_{t} przez |G_{t}|.

Uwaga 4.3 Korzystając z izoperymetrii gaussowskiej (Wniosek 2.11) zamiast nierówności logarytmicznej Sobolewa możemy udowodnić, że przy oznaczeniach Twierdzenia 4.9 dla u > 0,

P( sup_{t∈T}G_{t} − Med( sup_{t∈T}G_{t}) u) Φ( \frac{u}{σ}) \frac{1}{2} exp( − \frac{u^{2}}{2σ^{2}} )

oraz

P( | sup_{t∈T}G_{t} − Med( sup_{t∈T}G_{t}) | u) 2Φ( \frac{u}{σ}) exp( − \frac{u^{2}}{2σ^{2}} ).

Wniosek 4.10. Przy założeniach i oznaczeniach Twierdzenia 4.9,

lim_{t→∞} \frac{1}{u^{2}} logP( sup_{t∈T}G_{t} u) = −\frac{1}{2σ^{2}} .

Ponadto,

E exp(α sup_{t∈T}G_{t}^{2}) < ∞

wtedy i tylko wtedy gdy α < \frac{1}{2σ^{2}} .

Dowód. Z Twierdzenia 4.9

\frac{1}{u^{2}} logP( sup_{t∈T}G_{t} u) −\frac{1}{2σ^{2}} .

Z drugiej strony,

lim inf_{t→∞} \frac{1}{u^{2}} logP( sup_{t∈T}G_{t} u) sup_{t∈T} lim inf_{t→∞} \frac{1}{u^{2}} logP(G_{t} u)

= sup_{t∈T}−\frac{1}{2Var(G_{t})} = −\frac{1}{2σ^{2}} .

Druga część tezy dla α < \frac{1}{2σ^{2}} wynika natychmiast z (20) (dla |G_{t}|). Ponadto, jeśli G_{t} ∼ N (a_{t}, σ_{t}^{2}) ∼ a_{t} + σ_{t}g, to dla 0 α < 1/2σ_{t}^{2}

Ee^{αG_{t}^{2}} Ee^{ασ_{t}^{2}g^{2}} 𝟙_{g 0} = \frac{1}{2}Ee^{ασ_{t}^{2}g^{2}} = \frac{1}{2}\sqrt{\frac{1}{1 − 2ασ_{t}^{2}}} ,

więc E exp(α sup_{t∈T} G_{t}^{2}) sup_{t∈T} E exp(αG_{t}^{2}) = ∞ dla α \frac{1}{2σ^{2}} .

Definicja 4.5. Wektor losowy X w ośrodkowej przestrzeni Banacha F nazywamy gaussowskim, jeśli dla dowolnego φ ∈ F^{∗}, φ(X) ma rozkład gaussowski.

Założenie o ośrodkowości F ma charakter techniczny, służy uniknięciu problemów z mierzalnością (w nieośrodkowej przestrzeni Banacha suma dwóch wektorów losowych nie musi być mierzalna). Alternatywnie można zakładać, że norma w F jest wybijana przez przeliczalny ciąg funkcjonałów o normie jeden.

Twierdzenie 4.11. Załóżmy, że X jest wektorem gaussowskim w ośrodkowej przestrzeni Banacha. Wówczas E∥X∥ < ∞ oraz dla u > 0,

P(∥X∥ − E∥X∥ u) e^{− \frac{u^{2}}{2σ^{2}}} oraz P(∥X∥ − E∥X∥ −u) e^{− \frac{u^{2}}{2σ^{2}}} ,

gdzie

σ := {Var(φ(X))^{1/2} : φ ∈ F^{∗}, ∥φ∥ 1}.

Dowód. Wystarczy zauważyć, że istnieje przeliczalny podzbiór D kuli jednostkowej w F^{∗} taki, że ∥x∥ = sup_{φ∈D} φ(X) i skorzystać z Twierdzenia 4.9 dla procesu gaussowskiego (φ(X))_{φ∈D} .

Wniosek 4.12. Przy oznaczeniach Twierdzenia 4.11 dla p 1,

(E∥X∥^{p})^{1/p} E∥X∥ + C\sqrt{p}σ,

gdzie C jest pewną stałą uniwersalną.

Uwaga 4.4 Jak nietrudno zauważyć

(E∥X∥^{p})^{1/p} sup_{∥φ∥ 1} (E|φ(X)|^{p})^{1/p} \frac{1}{C} \sqrt{p}σ.

Wynika też stąd, że

(E∥X∥^{p})^{1/p} E∥X∥ + C̃ sup_{∥φ∥ 1} (E|φ(X)|^{p})^{1/p}.

4.3 Procesy Empiryczne

4.3.1 Sumy niezależnych zmiennych losowych

Zacznijmy od przypomnienia trzech nierówności dla sum niezależnych, rzeczywistych, ograniczonych zmiennych losowych.

Zakładamy, że zmienne X_{1}, X_{2}, …, X_{n} są niezależne oraz S = ∑ _{i=1}^{n} X_{i}.

Twierdzenie 4.13 (Nierówność Hoeffdinga). Dla dowolnego t > 0

P(S − ES t) exp( − \frac{t^{2}}{2D^{2}} ),

gdzie D = (∑ _{i=1}^{n} ∥X_{i} − EX_{i}∥_{∞}^{2} )^{1/2}.

Nierówność Hoeffdinga daje dobre oszacowanie tylko, gdy D^{2} jest zbliżona do Var(S). W przeciwnym przypadku dobrze jest stosować precyzyjniejsze nierówności.

Twierdzenie 4.14 (Nierówność Bernsteina). Załóżmy, że |X_{i} − EX_{i}| C dla 1 i n. Wówczas dla t 0,

P(S − ES t) exp( − \frac{t^{2}}{2Var(S) + \frac{2}{3}Ct} ).

Nierówność Bernsteina dla t małych daje ogon gaussowski S, a dla t dużych ogon wykładniczy. Okazuje się, że można ją polepszyć by dla dużych t otrzymać ogon poissonowski.

Twierdzenie 4.15 (Nierówność Bennetta). Załóżmy, że |X_{i} − EX_{i}| C dla 1 i n. Wówczas dla t 0,

P(S−ES t) exp( − \frac{Var(S)}{C^{2}}h( \frac{Ct}{Var(S)}) ) exp( − \frac{t}{2C} ln(1+ \frac{tC}{Var(S)}) ),

gdzie h(x) := (1 + x) ln(1 + x) − x dla x 0.

4.3.2 Oszacowania supremów procesów empirycznych

W tej części będziemy zakładać, że X_{i} są niezależnymi zmiennymi losowymi o wartościach w pewnej przestrzeni mierzalnej (V, V), zaś F pewną przeliczalną rodziną funkcji mierzalnych na V. Proces postaci

( ∑_{i=1}^{n} f(X_{i}))_{f∈F}

nazywamy procesem empirycznym. Będzie nas interesowało poszukiwanie oszacowań supremum takiego procesu, to znaczy zmiennej

Z = sup_{f∈F} ∑_{i=1}^{n} f(X_{i}).

Na pierwszy rzut oka powyższa definicja nie wydaje się naturalna. Poniższe dwa przykłady powinny pomóc w zrozumieniu motywacji za nią stojących.

Przykład 1. Sumy niezależnych wektorów losowych. Załóżmy, że X_{i} są niezależnymi wektorami losowymi o wartościach w pewnej ośrodkowej przestrzeni Banacha F i niech S = ∑ _{i=1}^{n} X_{i}. Wybierzmy taki przeliczalny zbiór funcjonałów D w kuli jednostkowej F^{∗}, by ∥x∥ = sup_{φ∈D} φ(x) dla wszystkich x ∈ F. Wówczas

∥S∥ = ∥ ∑_{i=1}^{n} X_{i} ∥ = sup_{φ∈D} ∑_{i=1}^{n} φ(X_{i}).

Przykład 2. Rozkłady empiryczne. Niech μ bedzie pewnym (ustalonym, ale nieznanym) rozkładem probabilistycznym na (V, V), zaś X_{1}, X_{2}, … niezależnymi zmiennymi losowymi o rozkładzie μ. Wówczas μ możemy estymować przez rozkład empiryczny

μ_{n} := \frac{1}{n} ∑_{i=1}^{n} δ_{X_{i}} .

Naturalne pytanie brzmi: czy μ_{n} zbiega do μ i jak szybko? Przykładowo, twierdzenie Gliwienki-Cantelli mówi, że jeśli V = ℝ, to dystrybuanta μ_{n} zbiega do dystrybuanty μ jednostajnie prawie na pewno. By badać szybkość zbieżności ustala się pewną klasę funkcji F na V i bada się

sup_{f∈F} | ∫ fdμ_{n} − ∫ fdμ| = sup_{f∈F} | ∑_{i=1}^{n} \frac{1}{n}(f(X_{i}) − ∫ fdμ)|.

Dowody twierdzeń, które omówimy w tym paragrafie będą opartę o metodę entropijną, którą już wcześniej stosowaliśmy przy badaniu nierówności logarytmicznej Sobolewa.

Twierdzenie 4.16. Załóżmy, że 0 f 1 dla f ∈ F. Wówczas dla dowolnego λ 0,

Ee^{λZ} e^{(e^{λ} −1)EZ} .

W szczególności dla t 0,

P(Z − EZ t) exp( − EZh( \frac{t}{EZ} ) ) exp( − \frac{t}{2} log(1 + \frac{t}{EZ} ) ),

gdzie h(x) = (1 + x) log(1 + x) − x dla x 0.

Lemat 4.17. Niech Φ(u) = e^{−u} + u − 1, wówczas dla λ 0,

Ent_{P}(e^{λZ} ) Φ(λ)EZe^{λZ} .

Dowód. Stosując nierówność logx x − 1 dla t/x = ∫ e^{f} dμ, a następnie podstawienie t = e^{u} dostajemy dla dowolnej miary probabilistycznej μ,

Ent_{μ}(e^{f} ) = ∫ e^{f} (f − log∫ e^{f} )dμ = inf_{t>0} ∫ [fe^{f} − (logt + 1)e^{f} + t]dμ
= inf_{u∈ℝ} ∫ Φ(f − u)e^{f} dμ.  (22)

Bez straty ogólności możemy przyjąć, że #F = N < ∞, niech μ_{i} oznacza rozkład (f(X_{i}))_{f∈F} na E = [0, 1]^{N} oraz μ = μ_{1} ⊗ ⋯⊗ μ_{n}. Określmy też

Z(x) = max_{1 k N} ∑_{i=1}^{n} x_{i}^{k} dla x = (x_{1}, …, x_{n}) ∈ E^{n}.

Wówczas rozkład Z względem P jest taki sam jak Z(x) względem μ, czyli

Ent_{P}(e^{λZ} ) = Ent_{μ}(e^{λZ(x)} ) ∑_{i=1}^{n} ∫ Ent_{μ_{i}} (e^{λZ(x)} )dμ(x).

Dla x = (x_{1}, …, x_{n}) ∈ E^{n} określmy

y_{i}(x) = (x_{1}, …, x_{i−1} , 0, x_{i}, …, x_{n}) ∈ E^{n}, 1 i n,

wtedy z nierówności (22),

∫ Ent_{μ_{i}} (e^{λZ(x)} )dμ(x) ∫ Φ(λ(Z(x) − Z(y_{i}(x))))e^{λZ(x)} dμ.

Określmy mierzalne rozbicie E^{n} na zbiory A_{k}, 1 k N spełniające

A_{k} ⊂ {x ∈ E^{n}: Z(x) = ∑_{i=1}^{n} x_{i}^{k}}.

Wówczas

0 Z(x) − Z(y_{i}(x)) ∑_{k=1}^{N} 𝟙_{A_{k}} (x)x_{i}^{k}.

Z wypukłości Φ, Φ(λu) uΦ(λ) dla u ∈ [0, 1], λ 0, zatem

Φ(λ(Z(x) − Z(y_{i}(x)))) ∑_{k=1}^{N} 𝟙_{A_{k}} (x)x_{i}^{k}Φ(λ).

W efekcie,

Ent_{P}(e^{λZ} ) ∑_{i=1}^{n} ∫ ∑_{k=1}^{N} 𝟙_{A_{k}} (x)x_{i}^{k}Φ(λ)e^{λZ(x)} dμ

= Φ(λ) ∫ ∑_{k=1}^{N} 𝟙_{A_{k}} (x) ∑_{i=1}^{n} x_{i}^{k}e^{λZ(x)} dμ = Φ(λ) ∫ Z(x)e^{λZ(x)} dμ

= Φ(λ)EZe^{λZ} .

Dowód Twierdzenia 4.16. Bez straty ogólności możemy założyć, że Z nie jest zdegenerowane. Niech M(λ) = Ee^{λZ} , wówczas na mocy Lematu 4.17 dostajemy dla λ > 0,

λM′(λ) − M(λ) logM(λ) = Ent_{P}(e^{λZ} ) Φ(λ)EZe^{λZ} = Φ(λ)M′(λ),

co po uwzględnieniu definicji Φ daje

(1 − e^{−λ} )M′(λ) M(λ) logM(λ).

Określmy J(λ) = logM(λ), wówczas

J′(λ) \frac{e^{λ}}{e^{λ} − 1} J(λ).

Zauważmy, że wobec Z 0, J(λ) 0 i nierówność jest ostra dla λ > 0. Poprzednia nierówność daje dla λ > 0,

(logJ(λ) − log(e^{λ} − 1))′ 0,

zatem

\frac{J(λ)}{e^{λ} − 1} lim_{λ→0+} \frac{J(λ)}{e^{λ} − 1} = EZ.

Stąd M(λ) exp((e^{λ} − 1)EZ), drugą część twierdzenia otrzymujemy w standardowy sposób z nierówności Czebyszewa:

P(Z − EZ t) inf_{λ 0} e^{−λt+EZ} Ee^{λZ} exp( − λt + (e^{λ} − λ − 1)EZ)

= exp( − EZh( \frac{t}{EZ} ) ).

Ostatnia nierówność w twierdzeniu wynika z szacowania h(x) \frac{x}{2} log(1 + x).

Twierdzenie 4.18. Załóżmy, że |f| C dla wszystkich f ∈ F. Wówczas dla t 0,

P(|Z − EZ| t) 2 exp( − \frac{1}{10} min\{ \frac{t}{C}, \frac{t^{2}}{4EΣ^{2}} \}),

gdzie Σ^{2} = sup_{f∈F} ∑ _{i=1}^{n} f^{2}(X_{i}).

Lemat 4.19. Dla dowolnej funkcji F

Ent_{μ}(e^{F}) ∫ ∫ ((F (x) − F (y))_{+} )^{2}e^{F (x)}dμ(x)dμ(y).

Dowód. Na mocy nierówności Jensena

Ent_{μ}(e^{F}) = ∫ F e^{F}dμ − ∫ e^{F}dμ log∫ e^{F}dμ ∫ F e^{F}dμ − ∫ e^{F}dμ ∫ F dμ

= \frac{1}{2} ∫ ∫ (F (x) − F (y))(e^{F (x)} − e^{F (y)})dμ(x)dμ(y).

Zauważmy, że dla dowolnych liczb a, b

(a − b)(e^{a} − e^{b}) (a − b)^{2}e^{max{a,b}} = ((a − b)_{+} )^{2}e^{a} + ((b − a)_{+} )^{2}e^{b}.

Stąd

\frac{1}{2} ∫ ∫ (F (x) − F (y))(e^{F (x)} − e^{F (y)})dμ(x)dμ(y)

\frac{1}{2} ∫ ∫ [((F (x) − F (y))_{+} )^{2}e^{F (x)} + ((F (y) − F (x))_{+} )^{2}e^{F (y)}]dμ(x)dμ(y)

= ∫ ∫ ((F (x) − F (y))_{+} )^{2}e^{F (x)}dμ(x)dμ(y).

Lemat 4.20. Załóżmy, że |f| 1 dla wszystkich f ∈ F, wówczas dla dowolnego λ ∈ ℝ,

Ent_{P}(e^{λZ} ) 2λ^{2}e^{2|λ|}(EΣ^{2}Ee^{λZ} + E(Σ^{2}e^{λZ} )).

Dowód. Bez straty ogólności możemy przyjąć, że #F = N < ∞. Jak w dowodzie Lematu 4.17 niech μ_{i} oznacza rozkład (f(X_{i}))_{f∈F} na E = [−1, 1]^{N} oraz μ = μ_{1} ⊗ ⋯⊗ μ_{n}. Określmy też

Z(x) = max_{1 k N} ∑_{i=1}^{n} x_{i}^{k} dla x = (x_{1}, …, x_{n}) ∈ E^{n}.

Wówczas rozkład Z względem P jest taki sam jak Z(x) względem μ, czyli

Ent_{P}(e^{λZ} ) = Ent_{μ}(e^{λZ(x)} ) ∑_{i=1}^{n} ∫ Ent_{μ_{i}} (e^{λZ(x)} )dμ(x).

Określmy mierzalne rozbicie E^{n} na zbiory A_{k}, 1 k N spełniające

A_{k} ⊂ {x ∈ E^{n}: Z(x) = ∑_{i=1}^{n} x_{i}^{k}}.

Dla ustalonych (x_{1}, …, x_{i−1} , x_{i+1} , …, x_{n}) ∈ E^{n−1} niech

Z_{i}(z) = Z_{i}(x_{1}, …, x_{i−1} , z, x_{i+1} , …, x_{n}) dla z ∈ E,

wówczas na podstawie Lematu 4.19,

∫ Ent_{μ_{i}} (e^{λZ(x)} )dμ(x)

∫ ∫ ∫ ((λ(Z_{i}(x_{i}) − Z_{i}(y_{i})))_{+} )^{2}e^{λZ_{i}(x_{i})} dμ_{i}(x_{i})dμ_{i}(y_{i})dμ(x).

Dla λ 0, ((λ(Z_{i}(x_{i}) − Z_{i}(y_{i})))_{+} )^{2} = λ^{2}((Z_{i}(x_{i}) − Z_{i}(y_{i}))_{+} )^{2}, zaś dla λ < 0,

((λ(Z_{i}(x_{i}) − Z_{i}(y_{i})))_{+} )^{2}e^{λZ_{i}(x_{i})} = λ^{2}((Z_{i}(y_{i}) − Z_{i}(x_{i}))_{+} )^{2}e^{λZ_{i}(x_{i})}
λ^{2}e^{2|λ|}((Z_{i}(y_{i}) − Z_{i}(x_{i}))_{+} )^{2}e^{λZ_{i}(y_{i})}

gdyż |Z_{i}(x_{i}) − Z_{i}(y_{i})| 2 wobec |f| 1. Stąd

∫ Ent_{μ_{i}} (e^{λZ(x)} )dμ(x)

λ^{2}e^{2|λ|} ∫ ∫ ∫ ((Z_{i}(x_{i}) − Z_{i}(y_{i}))_{+} )^{2}e^{λZ_{i}(x_{i})} dμ_{i}(x_{i})dμ_{i}(y_{i})dμ(x).

Zauważmy, że

Z_{i}(x_{i}) − Z_{i}(y_{i}) ∑_{k=1}^{N} 𝟙_{A_{k}} (x)(x_{i}^{k} − y_{i}^{k}),

więc

((Z_{i}(x_{i}) − Z_{i}(y_{i}))_{+} )^{2} 2 ∑_{k=1}^{N} 𝟙_{A_{k}} (x)(|x_{i}^{k}|^{2} + |y_{i}^{k}|^{2}).

Zatem

Ent_{P}(e^{λZ} )
2λ^{2}e^{2|λ|} ∑_{i=1}^{n} ∫ ∫ ∫ ∑_{k=1}^{N} 𝟙_{A_{k}} (x)(|x_{i}^{k}|^{2} + |y_{i}^{k}|^{2})e^{λZ_{i}(x_{i})} dμ_{i}(x_{i})dμ_{i}(y_{i})dμ(x)

= 2λ^{2}e^{2|λ|} ∫ ∫ ∑_{k=1}^{N} 𝟙_{A_{k}} (x) ∑_{i=1}^{n} (|x_{i}^{k}|^{2} + |y_{i}^{k}|^{2})e^{λZ(x)} dμ(x)dμ(y)
2λ^{2}e^{2|λ|} ∫ ∫ ( max_{1 k N} |x_{i}^{k}|^{2} + max_{1 k N} |x_{i}^{k}|^{2})e^{λZ(x)} dμ(x)dμ(y)
= (EΣ^{2}Ee^{λZ} + E(Σ^{2}e^{λZ} )).

Dowód Twierdzenia 4.18. Z uwagi na jednorodność możemy założyć, że C = 1. Przyjmijmy Z̃ := Z − EZ oraz M̃(λ) := Ee^{λZ̃}. Ustalmy λ_{0} > 0 takie, że c_{0} := 2e^{2λ_{0}} spełnia c_{0}λ_{0}^{2} < 1. Lemat 4.20 daje dla |λ| λ_{0},

λM̃′(λ) − M̃(λ) log M̃(λ) = e^{−λZ̃} Ent_{P}(e^{λZ} ) c_{0}λ^{2}(EΣ^{2}M̃(λ) + E(Σ^{2}e^{λZ̃})).

Oszacujmy ostatni składnik, mamy

E(Σ^{2}e^{λZ̃}) = (e − 1)EΣ^{2}Ee^{λZ̃} + E([Σ^{2} − (e − 1)EΣ^{2}]e^{λZ̃})
(e − 1)EΣ^{2}Ee^{λZ̃} + λE(Z̃e^{λZ̃}) − Ee^{λZ̃} + Ee^{Σ^{2}−(e−1)EΣ^{2}} ,

gdzie ostatnia nierówność wynika z nierówności Younga (11) uv u logu − u + e^{v} dla u = e^{λZ̃}, v = Σ^{2} − (e − 1)EΣ^{2}. Zauważmy, że 0 f^{2} 1 dla f ∈ F, więc do Σ^{2} możemy stosować Twierdzenie 4.16, aby dostać Ee^{Σ^{2}−(e−1)EΣ^{2}} 1. Z nierówności Jensena, Ee^{λZ̃} e^{λEZ̃} = 1, zatem

E(Σ^{2}e^{λZ̃}) (e − 1)EΣ^{2}M̃(λ) + λM̃′(λ).

Na podstawie wcześniejszych oszacowań dostajemy dla |λ| λ_{0},

λM̃′(λ) − M̃(λ) log M̃(λ) c_{0}λ^{2}(eEΣ^{2}M̃(λ) + λM̃′(λ)).

Określmy H(λ) = \frac{1}{λ} log M̃(λ) dla λ ≠ 0 i H(0) = 0, wówczas

H′(λ) c_{0}(eEΣ^{2} + λ\frac{M̃′(λ)}{M̃(λ)} ).  (23)

Zauważmy, że M̃′′(λ) = EZ̃^{2}e^{λZ̃} 0 oraz M̃′(λ) = EZ̃ = 0, więc dla λ 0, M̃′(λ) 0 oraz

∫_{0}^{λ} s\frac{M̃′(s)}{M̃(s)}ds λ ∫_{0}^{λ} \frac{M̃′(s)}{M̃(s)}ds = λ log M̃(λ).

Podobnie

∫_{−λ}^{0} s\frac{M̃′(s)}{M̃(s)}ds −λ log M̃(λ).

Odcałkowanie (23) daje zatem dla |λ| λ_{0},

log M̃(λ) c_{0}(eλ^{2}EΣ^{2} + λ^{2} log M̃(λ)).

Stąd

M̃(λ) e^{κ_{0}λ^{2}EΣ^{2}}

dla κ_{0} := ec_{0}(1 − c_{0}λ_{0}^{2})^{−1} . Nierówność Czebyszewa implikuje dla t 0,

P(Z − EZ t) inf_{0 λ λ_{0}} e^{−λt+κ_{0}λ^{2}EΣ^{2}} .

Wybierając λ = t/2κ_{0}EΣ^{2} dla t 2κ_{0}λ_{0}EΣ^{2} i λ = λ_{0} dla t 2κ_{0}λ_{0}EΣ^{2} dostajemy

P(Z − EZ t) exp( − min\{ \frac{λ_{0}t}{2}, \frac{t^{2}}{4κ_{0}EΣ^{2}} \}).

Podobny argument pracuje dla P(Z − EZ −t). Wybierając λ_{0} = 1/5 i sprawdzając, że wtedy κ_{0} 10 dostajemy tezę.

Twierdzenie 4.21. Załóżmy, że |f| C dla wszystkich f ∈ F. Wówczas dla t 0,

P(|Z − EZ| t) 3 exp( − \frac{t}{KC} log(1 + \frac{Ct}{EΣ^{2}} ) ),

gdzie Σ^{2} = sup_{f∈F} ∑ _{i=1}^{n} f^{2}(X_{i}), a K 640 jest stałą numeryczną.

Dowód. Bez straty ogólności możemy założyć, że C = 1. Nasz dowód będzie się opierał na Twierdzeniu 4.18 i odpowiednim obcinaniu. Dla ρ > 0 określmy

F_{ρ} := {f𝟙_{{|f| ρ}} : f ∈ F}, Z_{ρ} := sup_{f∈F_{ρ}} ∑_{i=1}^{n} f(X_{i})

oraz

W_{ρ} := sup_{f∈F} ∑_{i=1}^{n} |f(X_{i})|𝟙_{{|f(X_{i})| ρ}} .

Wówczas dla t > 0,

P(|Z − EZ| 4t) P(|Z_{ρ} − EZ_{ρ}| t) + P(W_{ρ} + EW_{ρ} 3t). Stosując Twierdzenie 4.18 do Z_{ρ} dostajemy

P(|Z_{ρ} − EZ_{ρ}| t) 2 exp( − \frac{1}{10} min\{ \frac{t}{ρ}, \frac{t^{2}}{4EΣ^{2}} \}).

By oszacować W_{ρ} załóżmy, że t EW_{ρ} i zastosujmy Twierdzenie 4.16,

P(W_{ρ} + EW_{ρ} 3t) P(W_{ρ} − EW_{ρ} t) exp( − \frac{t}{2} log(1 + \frac{t}{EW_{ρ}}) ).

Wybierzmy teraz

ρ = ρ(t) := min\{ 1, \sqrt{\frac{EΣ^{2}}{t}} \} ,

wówczas albo ρ = 1 i wtedy W_{ρ} = 0 albo ρ < 1, co wobec W_{ρ} Σ^{2}/ρ daje

EW_{ρ} \frac{EΣ^{2}}{ρ} = \sqrt{tEΣ^{2}} t.

Mamy więc dla tak dobranego ρ,

P(|Z−EZ| 4t) 2 exp(−\frac{1}{10} min\{ \frac{t}{ρ}, \frac{t^{2}}{4EΣ^{2}} \})+exp(−\frac{t}{2} log(1+\frac{t}{EW_{ρ}}) ).

Zauważmy, że

min\{u, \frac{u}{4}\} \frac{1}{16} log(1 + 4u) dla u 0,

więc

min\{ \frac{t}{ρ}, \frac{t^{2}}{4EΣ^{2}} \} t min\{ \sqrt{\frac{t}{EΣ^{2}}} , \frac{t}{4EΣ^{2}} \} \frac{t}{16} log(1 + \frac{4t}{EΣ^{2}} ).

Ponadto

log(1 + \frac{t}{EW_{ρ}}) log(1 + \sqrt{\frac{t}{EΣ^{2}}} ) \frac{1}{4} log(1 + \frac{4t}{EΣ^{2}} ).

Zatem

P(|Z − EZ| 4t) 3 exp( − \frac{t}{160} log(1 + \frac{4t}{EΣ^{2}} ) )

i zamieniając 4t na t dostajemy tezę.

Uwaga 4.5 Rozpatrując rodzinę funkcji F ∪ −F widzimy, że wszystkie udowodnione w tej części oszacowania pozostają też prawdziwe, gdy Z zamienimy na

Z̄ = | sup_{f∈F} ∑_{i=1}^{n} f(X_{i})|

By móc sensownie stosować Twierdzenia 4.18 i 4.21 potrzebujemy oszacowań EΣ^{2}. Zdefiniujmy słabą wariancję empiryczną Z jako

σ^{2} := sup_{f∈F} E ∑_{i=1}^{n} f^{2}(X_{i}).

Twierdzenie 4.22. Załóżmy, że |f| C oraz Ef(X_{i}) = 0 dla f ∈ F, wówczas

EΣ^{2} σ^{2} + 16CEZ̄.

Dowód będzie oparty na symetryzacji i zasadzie kontrakcji. By sformułować tę pierwszą wprowadźmy niezależny od pozostałych zmiennych ciąg (ε_{i})_{1 i n} niezależnych symetrycznych zmiennych losowych przyjmujących wartości ±1.

Fakt 4.23. Dla dowolnej przeliczalnej rodziny funkcji ograniczonych F,

E sup_{f∈F} | ∑_{i=1}^{n} f(X_{i})| sup_{f∈F} | ∑_{i=1}^{n} Ef(X_{i})| + 2E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f(X_{i})|.

Ponadto, jeśli Ef(X_{i}) = 0 dla f ∈ F, to

E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f(X_{i})| 2E sup_{f∈F} | ∑_{i=1}^{n} f(X_{i})|.

Dowód. Niech (X′_{i}) będzie kopią ciągui (X_{i}) niezależną od (X_{i}) oraz (ε_{i}). Wówczas z nierówności trójkąta oraz nierówności Jensena,

E sup_{f∈F} | ∑_{i=1}^{n} f(X_{i})| sup_{f∈F} | ∑_{i=1}^{n} Ef(X_{i})| + E sup_{f∈F} | ∑_{i=1}^{n} (f(X_{i}) − Ef(X_{i}))|

sup_{f∈F} | ∑_{i=1}^{n} Ef(X_{i})| + E sup_{f∈F} | ∑_{i=1}^{n} (f(X_{i}) − f(X′_{i}))|.

Z symetrii rodzina zmiennych (f(X_{i}) − f(X′_{i}))_{f∈F,i n} ma ten sam rozkład co (ε_{i}(f(X_{i}) − f(X′_{i})))_{f∈F,i n} , zatem

E sup_{f∈F} | ∑_{i=1}^{n} (f(X_{i}) − f(X′_{i}))| E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}(f(X_{i}) − f(X′_{i}))|

E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f(X_{i})| + E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f(X′_{i})|

= 2E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f(X_{i})|.

By wykazać drugie oszacowanie zauważmy, że na mocy nierówności Jensena dla A ⊂ {1, …, n},

E sup_{f∈F} | ∑_{i∈A} f(X_{i})| = E sup_{f∈F} | ∑_{i∈A} f(X_{i}) + ∑_{i∉A} Ef(X_{i})| E sup_{f∈F} | ∑_{i=1}^{n} f(X_{i})|,

stąd

E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f(X_{i})| E sup_{f∈F} | ∑_{i: ε_{i}=1} ε_{i}f(X_{i})| + E sup_{f∈F} | ∑_{i: ε_{i}=−1} ε_{i}f(X_{i})|

2E sup_{f∈F} | ∑_{i=1}^{n} f(X_{i})|.

Twierdzenie 4.24 (Zasada kontrakcji). Niech φ_{i}: ℝ → ℝ dla 1 i n będą funkcjami 1-lipschitzowskimi oraz φ_{i}(0) = 0. Wówczas dla dowolnego ograniczonego T ⊂ ℝ^{n} oraz funkcji wypukłej niemalejącej F: [0, ∞) → [0, ∞),

EF ( \frac{1}{2} sup_{t∈T} | ∑_{i=1}^{n} ε_{i}φ_{i}(t_{i})|) EF ( sup_{t∈T} | ∑_{i=1}^{n} ε_{i}t_{i} |).

Dowód Twierdzenia 4.22. Zauważmy, że na podstawie pierwszej części Faktu 4.23,

EΣ^{2} σ^{2} + 2E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f(X_{i})|.

Funkcja t → \frac{1}{2C} t^{2} jest 1-lipschitzowska na [−C, C] więc na mocy zasady kontrakcji (zastosowanej warunkowo względem X_{i}),

E sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f^{2}(X_{i})| 4CE sup_{f∈F} | ∑_{i=1}^{n} ε_{i}f^{2}(X_{i})| 8CEZ̄,

gdzie ostatnia nierówność wynika z drugiej części Faktu 4.23.

Literatura

[1] J. Jakubowski, R. Sztencel Wstęp do teorii prawdopodobieństwa, wyd II, Script, Warszawa 2001.

[2] M. Ledoux, The concentration of measure phenomenon, American Mathematical Society, Providence 2001.

[3] M. Ledoux, M. Talagrand, Probability in Banach spaces, Springer-Verlag, Berlin, 1991.