Egzamin Poprawkowy z Koncentracji Miary

Egzamin składa się z dwóch części: pisemnej i ustnej.

Część pisemna polega na samodzielnym rozwiązaniu sześciu spośród podanych poniżej zadań. Rozwiązania należy do mnie dostarczyć do dnia 10.09.2009 (drogą elektroniczną, osobiście lub np. włożyć do skrytki). W rozwiązaniach można korzystać z wszystkich faktów wyprowadzonych w czasie wykładów lub ćwiczeń. W przypadku wątpliwości co do treści zadań proszę o kontakt mailowy.

1. Funkcja koncentracji miary μ na (X, d) spełnia α_{μ}(t) \frac{1}{(1+t)^{4}} . Załóżmy, że μ(A) \frac{1}{10} . Oszacuj z góry 1 − μ(A_{t}) oraz ∫ d(x, A)dμ(x).

2. Niech X będzie wektorem jednostajnie rozłożonym na S^{n−1} . Wykaż, że dla dowolnego t ∈ ℝ^{n}, E⟨t, X⟩^{2} = |t|^{2}/n oraz

(E|⟨t, X⟩|^{p})^{1/p} min\{C\sqrt{\frac{p}{n}}, 1\}|t|

dla p 1 i pewnej stałej uniwersalnej C.

3. Niech X_{1}, X_{2}, …, X_{m} będą wektorami jednostajnie rozłożonymi na [−1, 1]^{n}, zaś ∥ · ∥ będzie pewną normą na ℝ^{n}. Wykaż, że

E max_{1 i m} ∥X_{i}∥ E∥X_{1}∥ + C\sqrt{log(m + 1)} sup_{|x|=1} ∥x∥

dla pewnej stałej uniwersalnej C.

4. Niech μ_{1} i μ_{2} będą miarami probabilistycznymi z logarytmicznie wklęsłymi gęstościami na ℝ^{n}. Które z następujących miar muszą być logarytmicznie wklęsłe: μ_{1} ⊗ μ_{2}, μ_{1} ∗ μ_{2}, \frac{1}{2}(μ_{1} + μ_{2})?

5. Załóżmy, że miara μ na ℝ^{n} spełnia nierówność Poincaré ze stałą α. Wykaż, że dla dowolnej funkcji L-lipschitzowskiej f oraz p 1

( ∫ |f(x)|^{p}dμ(x))^{1/p} ∫ |f(x)|dμ(x) + C\sqrt{α}Lp

dla pewnej stałej uniwersalnej C. Jak zmieni się odpowiedź, jeśli założymy, że μ spełnia logarytmiczną nierówność Sobolewa ze stałą α?

6. Niech μ_{p} będzie miarą probabilistyczną na prostej z gęstością c_{p}e^{−|x|^{p}} dla 0 < p < ∞, gdzie c_{p} jest odpowiednią stałą normującą. Dla jakich p miara μ_{p} spełnia nierówność Poincaré?

7. Niech μ_{p} będzie jak w poprzednim zadaniu, zaś μ_{p}^{n} = μ_{p} ⊗ ⋯⊗ μ_{p} będzie miarą produktową na ℝ^{n}. Wykaż, że istnieje stała uniwersalna C < ∞ taka, że dla dowolnego niepustego zbioru borelowskiego A i t > 0

1 − μ_{p}^{n}( A + C(\sqrt{t}B_{2}^{n} + t^{1/p}B_{p}^{n})) \frac{1}{μ_{p}^{n}(A)} e^{−t} dla 1 p 2

oraz

1 − μ_{p}^{n}( A + C(\sqrt{t}B_{2}^{n} ∩ t^{1/p}B_{p}^{n})) \frac{1}{μ_{p}^{n}(A)} e^{−t} dla p > 2,

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

8. Mówimy, że przestrzeń Banacha E ma kotyp p ze stałą T_{p} < ∞, jeśli

E∥ ∑_{i=1}^{n} x_{i}ε_{i} ∥ \frac{1}{T_{p}}( ∑_{i=1}^{n} ∥x_{i}∥^{p})^{1/p}

dla dowolnych x_{1}, …, x_{n} ∈ E (ε_{i} jak zawsze oznaczają niezależne symetryczne zmienne ±1). Wykaż, że

i) jeśli E ma kotyp p, to p 2, ii) każda przestrzeń ma kotyp ∞, iii) każda przestrzeń Hilberta ma kotyp 2, iv) przestrzeń L^{p}[0, 1] ma kotyp max{2, p}.

9. Wykaż, że jeśli przestrzeń Banacha E ma kotyp p ze stałą T_{p}, to dla każdego ε > 0 l_{2}^{k} się 1 + ε wkłada w E dla k C(ε)T_{p}^{−2} n^{2/p}.

10. Każdej krawędzi grafu pełnego o n wierzchołkach przypisujemy pewną zmienną losową o wartościach w [0, 1], przy czym zmienne przypisane różnym krawędziom są niezależne. Niech S oznacza długość najkrótszej pętli przechodzącej dokładnie raz przez każdy z wierzchołków (długością pętli nazywamy sumę zmiennych przypisanych krawędziom pętli). Wykaż, że

P(|S − ES| t) exp(−\frac{t^{2}}{8n}).

Część ustna będzie oparta na rozmowie o przedstawionych rozwiązaniach oraz o wybranych tematach spośród następujących:

• Nierówności izoperymetryczne.

• Metoda martyngałowa.

• Nierówność Poincaré.

• Logarytmiczna nierówność Sobolewa.

• Nierówność splotu infimum.

• Nierówności koncentracyjne dla funkcji wypukłych.

• Twierdzenie Dvoretzky’ego. Koncentracja procesów i wektorów gaussowskich.

• Aproksymacja przez otoczkę wypukłą.

• Oszacowania supremów procesów empirycznych.

• Zastosowania koncentracji miary w kombinatoryce, teorii macierzy loso-

wych i teorii szkła spinowego. Należy wybrać 6 tematów z których chce się odpowiadać.

Na egzamin ustny należy się umówić mailowo.