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

Концентрация меры —  принцип, согласно которому при определённых достаточно общих и не слишком обременительных ограничениях значение функции большого числа переменных почти постоянно. Например, большинство пар точек на единичной сфере большой размерности находятся на расстоянии, близком к ${\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.