Концентрація міри

Концентрація міри — принцип, за яким за певних досить загальних і не дуже обтяжливих обмежень значення функції великої кількості змінних майже стале. Наприклад, більшість пар точок на одиничній сфері великої розмірності розташовані на відстані, близькій до ${\tfrac {\pi }{2}}$ один від одного.

Принцип концентрації міри ґрунтується на ідеї Поля Леві. На початку 1970-х років його дослідив Віталій Мільман у його роботах з локальної теорії банахових просторів. Цей принцип набув подальшого розвитку в роботах Мільмана та Громова, Море, Пізьє, Шехтмана, Талаграна, Леду та інших.

Основні визначення

Нехай $(X,d,\mu )$ — метричний простір з імовірнісною мірою $\mu$. Нехай

$\alpha (\varepsilon )=\sup \left\{\,\mu (X\setminus A_{\varepsilon })\mid \mu (A)\geqslant 1/2\,\right\},$

де

$A_{\varepsilon }=\left\{\,x\mid d(x,A)<\varepsilon \,\right\}$

є $\varepsilon$ - околом множини $A$ .

Функцію $\alpha$ називають профілем простору $X$.

Неформально кажучи, простір $X$ задовольняє принципу концентрації міри, якщо його профіль $\alpha (\varepsilon )$ швидко зменшується при зростанні $\varepsilon$.

Формальніше, сімейство метричних просторів із мірами $(X_{n},d_{n},\mu _{n})$ називають сімейством Леві, якщо для відповідних профілів $\alpha _{n}$ виконується таке

$\forall \varepsilon >0\quad \alpha _{n}(\varepsilon )\to 0\quad {\text{при}}\quad n\to \infty .$

Якщо понад це

$\forall \varepsilon >0\quad \alpha _{n}(\varepsilon )\leq C\cdot \exp(-c\cdot n\cdot \varepsilon ^{2})$

для деяких констант $c,C>0$, то послідовність $(X_{n},d_{n},\mu _{n})$ називають нормальним сімейством Леві.

Зауваження

• Таке визначення профілю $\alpha$ еквівалентне:

  $\alpha (\varepsilon )=\sup \left\{\,\mu (\{\,F\geq \mathop {M} +\varepsilon \,\})\,\right\},$

де точна верхня грань за всіма 1-ліпшицевими функціями $F\colon \,X\to \mathbb {R}$ і $M$ медіана $F$, визначена такою парою нерівностей

$\mu \{\,F\geq M\,\}\geqslant 1/2,\quad \mu \{\,F\leq M\,\}\geqslant 1/2.$

Концентрація міри на сфері

Перший приклад запропонував Поль Леві. Відповідно до сферичної ізопериметричної нерівності, серед усіх підмножин $A$ сфери $\mathbb {S} ^{n}$ із заданою сферичною мірою $\sigma _{n}(A)$ сферичний сегмент

$B(x_{0},R)_{\mathbb {S} ^{n}}=\left\{\,x\in \mathbb {S} ^{n}\mid \mathrm {dist} (x,x_{0})\leqslant R\,\right\}$

для будь-якого $R$ має найменший $\varepsilon$-окіл $A_{\varepsilon }$ для будь-якого фіксованого $\varepsilon >0$.

Застосовуючи це спостереження для однорідної імовірнісної міри $\sigma _{n}$ на $\mathbb {S} ^{n}$ і множини $A$ такої, що $\sigma _{n}(A)=1/2$, отримуємо таку нерівність:

$\sigma _{n}(A_{\varepsilon })\geqslant 1-C\cdot \exp(-c\cdot n\cdot \varepsilon ^{2}),$

де $C,c$ — універсальні константи. Тому послідовність $X_{n}=\mathbb {S} ^{n}$ є нормальним сімейством Леві, і принцип концентрації міри виконується для цієї послідовності просторів.

Застосування

• Припустимо, ${\mathcal {P}}_{\varepsilon }$ позначає множину всіх опуклих многокутників у одиничному квадраті з вершинами в $\varepsilon$-ґратці $(\varepsilon \cdot \mathbb {Z} )^{2}$. Тоді за малих $\varepsilon >0$ більшість многокутників з ${\mathcal {P}}_{\varepsilon }$ лежать близько до деякої опуклої множини $L$.
  • Точніше, $L$ описується нерівністю

  ${\sqrt {1-|x|}}+{\sqrt {1-|y|}}\geq 1.$

• Лема про мале спотворення
• Теорема Дворецького

Див. також

• Мартингал Дуба

Література

• Ledoux, Michel. The Concentration of Measure Phenomenon. — American Mathematical Society, 2001. — ISBN 0-8218-2864-9.
• A. A. Giannopoulos, V. Milman, Concentration property on probability spaces, Advances in Mathematics 156 (2000), 77—106.