← arxiv/
arXiv:9006.0038math.PR
tr · çeviri

Rademacher Fonksiyonları İçin Talagrand'ın Sapma Eşitsizliği Üzerine Notlar

William B. Johnson, Gideon Schechtman

Texas A&M · Weizmann Institute
1990

William B. Johnson* ve Gideon Schechtman
*Kısmen NSF DMS-8703815 tarafından desteklenmiştir.

Matematik Bölümü, Texas A&M Üniversitesi, College Station, TX 77843
ve
Teorik Matematik Bölümü, Weizmann Bilim Enstitüsü, Rehovot, İsrail

arXiv:math/9201208v1 [math.PR] 16 Şub 1990

Giriş

Yakın zamanda Talagrand [T], $\{0, 1\}^n$ üzerindeki bir fonksiyonun medyanından sapmasını, $f$'nin $\ell_2^n$ uzayına dışbükey (konveks) bir genişlemesinin Lipschitz sabiti cinsinden tahmin etmiştir; yani şunu kanıtlamıştır: $$P(|f - M_f| > c) \le 4 e^{-t^2 / 4 \sigma^2}$$ burada $\sigma$, $f$'nin genişlemesinin Lipschitz sabitidir ve $P$, $\{0, 1\}^n$ üzerindeki doğal olasılık ölçüsüdür.

Burada bu eşitsizliği daha genel çarpım olasılık uzaylarına genişletiyoruz; özel olarak, $((1-\eta)\delta_0 + \eta \delta_1)^n$ çarpım ölçüsü ile donatılmış $\{0, 1\}^n$ için de aynı eşitsizliği kanıtlıyoruz. Bunun rastgele seçimler içeren kanıtlarda yararlı olacağına inanıyoruz. Olası uygulamaların bir gösterimi olarak, $1 \le r < s \le 2$ ve $\varepsilon > 0$ için, $L_s$ uzayının her $n$-boyutlu alt uzayının, $N = c(r, s, \varepsilon) n$ olmak üzere $\ell_r^N$ içine $(1+\varepsilon)$-gömüldüğüne dair Bourgain, Lindenstrauss, Milman sonucunun [BLM] (her ne kadar $\varepsilon$'a olan doğru bağımlılıkla olmasa da) basit bir kanıtını sunuyoruz.

Temel Sonuçlar

$i = 1, \dots, n$ için $(X_i, \|\cdot\|_i)$ normlu uzaylar olsun, $\Omega_i$, $X_i$'nin çapı en fazla bir olan sonlu bir alt kümesi ve $P_i$, $\Omega_i$ üzerinde bir olasılık ölçüsü olsun. Şöyle tanımlayalım: $$X = \left( \sum_{i=1}^n \oplus X_i \right)_2$$ ve $$\Omega = \Omega_1 \times \Omega_2 \times \dots \times \Omega_n \subset X$$ ve $$P = P^{(n)} = P_1 \times P_2 \times \dots \times P_n$$ $\Omega$ üzerindeki çarpım olasılık ölçüsü olsun. Bir $A \subseteq \Omega$ alt kümesi ve $t \in \Omega$ için: $$\phi_A(t) = d(t, \text{conv } A)$$ $t$ noktasının $A$ kümesinin dışbükey gövdesine $X$'teki uzaklığı olsun.

Teorem 1. Herhangi bir $A \subseteq \Omega$ alt kümesi için, $$E e^{\frac{1}{4} \phi_A^2(t)} \le \frac{1}{P(A)}\ .$$

Not 2: Talagrand'ın teoremi, her bir $\Omega_i$'nin iki noktadan oluştuğu ve $P_i$'nin her birine $\frac{1}{2}$ ağırlık verdiği Teorem 1'in özel bir durumudur. Aşağıdaki uygulamada, her bir $\Omega_i$ için iki noktalı uzaylar kullanıyoruz, ancak $P_i$ her iki noktaya aynı kütleyi (ağırlığı) atamamaktadır.

Kanıt: Talagrand'ın tümevarım argümanını [T] tekrarlıyoruz; fark yalnızca analiz (kalkülüs) düzeyindedir. $n = 1$ için: $$E e^{\frac{1}{4} \phi_A^2(t)} \le P(A) + (1 - P(A)) e^{1/4} \le \frac{1}{P(A)}\ ,$$ çünkü $0 \le r \le 1$ için $r(r + (1-r)e^{1/4})$'ün en büyük değeri 1'dir. Teoremin $n$ için geçerli olduğunu varsayalım ve farz edelim ki: $$A \subseteq \Omega_1 \times \dots \times \Omega_n \times \Omega_{n+1}\ .$$ $w \in \Omega_{n+1}$ için şöyle tanımlayalım: $$A_w = \{t \in \Omega_1 \times \dots \times \Omega_n ; (t, w) \in A\}\ ,$$ burada $t = (t_1, \dots, t_n) \in \Omega_1 \times \dots \times \Omega_n$ ve $w \in \Omega_{n+1}$ için $(t, w)$ ifadesi $(t_1, \dots, t_n, w)$'yi temsil eder. $v \in \Omega_{n+1}$ ifadesi, $$P^{(n)}(A_v) = \max_{w \in \Omega_{n+1}} P^{(n)}(A_w)\ .$$ olacak şekilde bir eleman olsun. Aşağıdaki iki eşitsizliği kullanacağız: $$\phi_A^2(t, v) \le \phi_{A_v}^2(t) \quad \text{her } t \in \Omega_1 \times \dots \times \Omega_n \text{ için}\tag{1}$$ $$\phi_A^2(t, w) \le \inf_{0 \le \alpha \le 1} \left[ \alpha \phi_{A_w}^2(t) + (1-\alpha) \phi_{A_v}^2(t) + (1-\alpha)^2 \right]\tag{2}$$ tüm $t \in \Omega_1 \times \dots \times \Omega_n$ ve $w \ne v$ için.

(1) ve (2) eşitsizliklerini, Hölder eşitsizliğini ve tümevarım varsayımını (bu sırayla) kullanarak şunu elde ederiz: $$E e^{\frac{1}{4} \phi_A^2(s)} = P_{n+1}(\{v\}) E e^{\frac{1}{4} \phi_{A_v}^2(t)} + \sum_{w \ne v} P_{n+1}(\{w\}) \inf_{0 \le \alpha \le 1} E \left[ \left(e^{\frac{1}{4} \phi_{A_w}^2(t)}\right)^\alpha \left(e^{\frac{1}{4} \phi_{A_v}^2(t)}\right)^{1-\alpha} e^{\frac{1}{4} (1-\alpha)^2} \right]$$ $$\le P_{n+1}(\{v\}) \frac{1}{P^{(n)}(A_v)} + \sum_{w \ne v} P_{n+1}(\{w\}) \inf_{0 \le \alpha \le 1} \left( \frac{1}{P^{(n)}(A_w)} \right)^\alpha \left( \frac{1}{P^{(n)}(A_v)} \right)^{1-\alpha} e^{\frac{1}{4} (1-\alpha)^2}\tag{3}$$ $$= \frac{1}{P^{(n)}(A_v)} \left[ P_{n+1}(v) + \sum_{w \ne v} P_{n+1}(w) \inf_{0 \le \alpha \le 1} \left( \frac{P^{(n)}(A_v)}{P^{(n)}(A_w)} \right)^\alpha e^{\frac{1}{4} (1-\alpha)^2} \right]\ .$$

$0 \le \lambda \le 1$ için, $\alpha(\lambda)$, $\min_{0 \le \alpha \le 1} \frac{1}{\lambda^\alpha} e^{\frac{1}{4} (1-\alpha)^2}$ değerine ulaşılan nokta olsun; yani, $$\alpha(\lambda) = \begin{cases} 1 + 2 \log \lambda & \text{eğer } 2 \log \lambda > -1 \text{ ise} \\ 0 & \text{aksi takdirde} \end{cases}$$ ve şöyle tanımlayalım: $$g(\lambda) = \frac{1}{\lambda^{\alpha(\lambda)}} e^{\frac{1}{4} (1-\alpha(\lambda))^2} = \begin{cases} e^{-\log \lambda - (\log \lambda)^2} & \text{eğer } 2 \log \lambda > -1 \text{ ise} \\ e^{1/4} & \text{aksi takdirde.} \end{cases}$$

(3) ifadesinden şunu elde ederiz: $$E e^{\frac{1}{4} \phi_A^2(s)} \le \frac{1}{P^{(n)}(A_v)} \left[ P_{n+1}(v) + \sum_{w \ne v} P_{n+1}(w) g(\lambda_w) \right]\tag{4}$$ burada: $$\lambda_w = \frac{P^{(n)}(A_w)}{P^{(n)}(A_v)}\ .$$

Sav: $0 \le \lambda \le 1$ için $g(\lambda) \le 2 - \lambda$ şeklindedir.

Savı kullanarak (4) ifadesinden şunu elde ederiz: $$E e^{\frac{1}{4} \phi_A^2(s)} \le \frac{1}{P^{(n)}(A_v)} (q + (1-q)(2-t))\tag{5}$$ burada $q = P_{n+1}(v)$ ve $t = \frac{P(A) - P_{n+1}(v) P^{(n)}(A_v)}{(1 - P_{n+1}(v)) P^{(n)}(A_v)}$ şeklindedir ($0 \le q, t \le 1$ olduğuna dikkat ediniz). Şöyle ki: $$\frac{1}{P(A)} = \frac{1}{P^{(n)}(A_v)} \frac{1}{q + (1-q)t}\tag{6}$$ olduğundan, şunu kanıtlamak yeterlidir: $$q + (1-q)(2-t) \le \frac{1}{q + (1-q)t}\tag{7}$$ tüm $0 \le q, t \le 1$ için ki bu kolayca kontrol edilebilir.

Savın kanıtı elementerdir: Şöyle tanımlayalım: $$f(\lambda) = g(\lambda) + \lambda - 2\ .$$ Bu durumda $0 \le \lambda \le 1$ için $f(1) = f'(1) = 0$ ve $f''(\lambda) \le 0$ olur, bu da $0 \le \lambda \le 1$ için $f(\lambda) \le 0$ olduğunu gösterir. $\square$

Not 3: $2 < p < \infty$ olsun ve $\Omega$'yı $\left( \sum_{i=1}^n \oplus X_i \right)_p$ uzayının bir alt kümesi olarak düşünelim. Şöyle tanımlayalım: $$\phi_{A,p}(t) = \inf \left\{ \left( \sum_{i=1}^n \|t_i - s_i\|_i^p \right)^{1/p} ; s = (s_1, \dots, s_n) \in \text{conv } A \right\}\ .$$ O halde Talagrand tarafından belirtildiği gibi, şunu da elde ederiz: $$E e^{\frac{1}{4} \phi_{A,p}^p(t)} \le \frac{1}{P(A)}$$ çünkü $\phi_{A,p}^p(t) \le \phi_A^2(t)$ şeklindedir.

Sonuç 4. $2 \le p < \infty$ olsun ve $f$, $\left( \sum_{i=1}^n \oplus X_i \right)_p$ üzerinde gerçel dışbükey bir fonksiyon olsun ($f$'nin conv $\Omega$ üzerinde tanımlı olduğunu varsaymak yeterlidir). $\sigma_p$, $f$'nin Lipschitz sabiti olsun. O halde, her $c > 0$ için, $$P(|f - M_f| > c) \le 4 e^{-c^p / 4 \sigma_p^p}\tag{8}$$ burada $M_f$, $f$'nin medyanıdır. Medyan yerine beklenen değer konulduğunda da benzer bir eşitsizlik (iki adet dört sayısı yerine mutlak sabitler gelmek üzere) geçerlidir: $$P(|f - E f| > c) \le K e^{-\delta c^p / \sigma_p^p}\tag{9}$$ ($K = 8$, $\delta = \frac{1}{32}$ alınabilir).

İlk iddianın kanıtı, Talagrand'ın makalesindeki [T] Teorem 3'ün kanıtıyla tamamen aynıdır. İkinci iddia ise birinciden elde edilir; bkz. [MS], s. 142.

Not 5: Eşitsizlik (9), her bir $P_i$'nin $B_{X_i}$ üzerinde bir Radon olasılık ölçüsü olduğu daha genel duruma kolayca genişletilebilir.

Not 6: Eşitsizlik (8) ve (9)'da sol taraf yalnızca $f$'nin $\Omega$ üzerindeki değerlerini içerirken, sağ taraf $\sigma_p$ aracılığıyla $f$'nin conv $\Omega$ üzerindeki değerlerini içerir. Dolayısıyla, $\sigma_p$ yerine, $f|_\Omega$'nın conv $\Omega$ üzerindeki tüm dışbükey genişlemelerinin Lipschitz sabitlerinin infimumu (en büyük alt sınırı) konabilir. Her bir $\Omega_i$'nin iki noktalı bir küme olduğu Talagrand teoreminin özgün kurulumunda bile bu infimumun nasıl hesaplanacağını bilmiyoruz.

Bir Uygulama

Lemma 7. $\mu$, $\{1, \dots, N\}$ üzerinde bir olasılık ölçüsü olsun. $0 < r < s \le 2r$ olsun ve $X$, $L_r(\{1, \dots, N\}, \mu)$ uzayının, her $x \in X$ için $\|x\|_s \le K \|x\|_r$ koşulunu sağlayan $n$-boyutlu bir alt uzayını temsil etsin (burada $\|\cdot\|_s$, $L_s(\{1, \dots, N\}, \mu)$ normunu göstermektedir). Ayrıca her $1 \le i \le N$ için $\mu(i) \le \frac{2}{N}$ olduğunu varsayalım. O halde, her $1 > \varepsilon > 0$ ve $q = \frac{s}{r}$, $p = \frac{q}{q-1}$ olmak üzere her $k \ge c \varepsilon^{-r} r^{1/p} (\log \frac{2}{\varepsilon})^{1/p} K^r n^{1/p} N^{1/q}$ için, $\{1, \dots, N\}$ kümesinin eleman sayısı $k$ olan ve $A$'ya kısıtlaması $X$ üzerinde bir $(1+\varepsilon)$-izomorfizminin bir katı olan bir $A \subseteq \{1, \dots, N\}$ alt kümesi mevcuttur. Özel olarak, $X$ uzayı $\ell_r^k$ içine $(1+\varepsilon)$-gömülür.

Kanıt: $\delta_i$, $i = 1, \dots, N$, ortalaması $\delta$ olan bağımsız ve $\{0, 1\}$ değerli rastgele değişkenler olsun. $x \in X$, $\|x\|_r = 1$ olacak şekilde bir $x$ sabitleyelim ve $f : \mathbb{R}^N \to \mathbb{R}$ fonksiyonunu şu şekilde tanımlayalım: $$f((a_i)_{i=1}^N) = \sum_{i=1}^N a_i \mu(i) |x(i)|^r\ .$$ O halde: $$\sigma_p(f) = \sup_{\sum_{i=1}^N |a_i|^p = 1} \sum_{i=1}^N a_i \mu(i) |x(i)|^r$$ $$= \left( \sum_{i=1}^N \mu(i)^q |x(i)|^s \right)^{1/q} \le \left( \frac{2}{N} \right)^{\frac{q-1}{q}} \left( \sum_{i=1}^N \mu(i) |x(i)|^s \right)^{r/s}$$ $$\le \left( \frac{2}{N} \right)^{1/p} K^r\ .$$

Sonuç 4'ten şu elde edilir: $$P\left( \left| \sum_{i=1}^N \delta_i \mu(i) |x(i)|^r - \delta \right| > c \right) \le 4 e^{-c^p N / 8 K^{rp}}\tag{10}$$ ve sonuç olarak, $\partial B_X$ içindeki bir $\varepsilon$-ağının (net) boyutu üzerindeki alışılagelmiş tahmini kullanarak (karşılaştırınız [MS] s. 7): $$P\left( \left| \sum_{i=1}^N \delta_i \mu(i) |x(i)|^r - \delta \right| \le \varepsilon^r \delta \text{ her } x \in \partial B_X \text{ için} \right) \ge 1 - 4 \exp\left( n r \log \frac{2}{\varepsilon} - \varepsilon^{rp} \delta^p N / 8 K^{rp} \right)\ .$$

$k = 2 \delta N$ (= $\{i ; \delta_i = 1\}$ kümesinin ortalama boyutunun iki katı) olsun. O halde, $\eta = c \varepsilon^{rp} \left( r \log \frac{2}{\varepsilon} \right)^{-1}$ ($c$ evrensel bir sabit) ve $n \le \eta \delta^p N / K^{rp}$ için, yukarıdaki olasılık $\frac{1}{2}$'den büyüktür; dolayısıyla bu gereksinimi karşılayan $k$ elemanlı bir küme bulabiliriz. $k = 2 \delta N$ ve $n = \eta \delta^p N / K^{rp}$ denklemlerinden $\delta$ yok edildiğinde şunu elde ederiz: $$k \approx 2 \eta^{-1/p} n^{1/p} N^{1/q} K^r\ .$$

Teorem 8. [BLM]: $0 < r < t \le 2$ ve $T, \varepsilon > 0$ olsun. O halde, $t$-tipi sabiti $K$ olan, $L_r$'nin herhangi bir $n$-boyutlu $X$ alt uzayının, $N \le C \cdot n$ olmak üzere $\ell_r^N$ içine $(1+\varepsilon)$-gömülmesini sağlayan, yalnızca $\varepsilon, T, r, t$ değerlerine bağlı bir $C = C(\varepsilon, T, r, t)$ sabiti mevcuttur.

Kanıt: Bazı sonlu $M$ değerleri için $X \subseteq L_r^M$ olduğunu varsayabiliriz. Maurey-Nikishin-Rosenthal çarpanlara ayırma (faktorizasyon) teoremi uyarınca ([M] Teorem 8 ve Önerme 44), $\{1, \dots, M\}$ üzerinde, her $x \in X$ için $\|x\|_s \le K \|x\|_r$ olacak şekilde bir $\mu$ olasılık ölçüsü mevcuttur; burada $s = \frac{r+t}{2}$ şeklindedir ve $K$ yalnızca $r, t$ ve $T$ değerlerine bağlıdır. $\mu$'nün büyük atomlarını ölçüsü $\le \frac{1}{M}$ olan atomlara bölerek, $N \le 2M$ ve $\bar{\mu}(i) \le \frac{1}{M} \le \frac{2}{N}$ koşullarını sağlayan, $\{1, \dots, N\}$ üzerinde yeni bir $\bar{\mu}$ olasılık ölçüsü elde ederiz. Her $u$ için $L_u(\mu)$ uzayı, $L_u(\bar{\mu})$ içine eşölçülü (izometrik) olarak (bir alt kafes olarak) gömülür ve (yeni gömmede) her $x \in X$ için $\|x\|_s \le K \|x\|_r$ eşitsizliği geçerliliğini korur. Lemma 7'yi uygulayarak, $k$ sayısı $n^{1/p} M^{1/q}$ mertebesinde olmak üzere $X$ uzayının $L_r^k$ içine $(1+\delta)$-gömüldüğünü elde ederiz.

Maurey-Nikishin-Rosenthal teoremini tekrar kullanarak, $k$ sayısı $n^{\frac{1}{p} + \frac{1}{pq}} M^{\frac{1}{q^2}}$ mertebesinde olmak üzere $X$'in $L_r^k$ içine $(1+\delta)^2$-gömüldüğünü elde etmek için argümanı tekrarlayabiliriz. Yineleme (iterasyon) yapılarak aranan sonuç elde edilir. Bu kısım [BLM]'deki ile aynıdır. (Yukarıda bizim yaptığımızdan biraz daha dikkatli olunmalı ve $k$'nin kesin biçimi dikkate alınmalıdır, ancak bu yöntem çalışır.)

Not 9: Hem B. Maurey hem de M. Talagrand, (10) eşitsizliğinin bazı versiyonlarının bilinen eşitsizliklerden elde edildiğini bize belirtmişlerdir; özel olarak (10), sağ taraftaki üssün $p$ ile birlikte sonsuza giden bir $\delta_p$ sabiti ile çarpılması gerektiği durumu hariç olmak üzere, Azuma-Pisier eşitsizliğinin (bkz. [MS], s. 45) doğrudan bir sonucudur. Bu sabitin dejenere olması Teorem 8'i kanıtlamak açısından önemsiz olduğundan, aslında Talagrand'ın izoperimetrik eşitsizliğinin (kendi hafif genellememizin) iyi bir uygulamasına sahip değiliz. Öte yandan, yukarıda özetlenen yaklaşımın $L_r$'nin genel alt uzayları için kullanılması mümkündür; bu durumda Lemma 7'nin, "$p$"'yi sonsuza gitmeye zorlayan ve "$s$"nin "$r$"'ye yakın olduğu bir versiyonunun kullanılması beklenir.

Kaynakça