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

Концентрация меры —  принцип, согласно которому при определённых достаточно общих и не слишком обременительных ограничениях значение функции большого числа переменных почти постоянно[1]. Например, большинство пар точек на единичной сфере большой размерности находятся на расстоянии, близком к ${\displaystyle {\tfrac {\pi }{2}}}$ друг от друга.

Принцип концентрации меры основан на идее Поля Леви. Он был исследован в начале 1970-х годов Виталием Мильманом в его работах по локальной теории банаховых пространств. Этот принцип получил дальнейшее развитие в работах Мильмана и Громова, Морэ, Пизье, Шехтмана, Талаграна, Леду^[англ.] и других.

Основные определения

Пусть ${\displaystyle (X,d,\mu )}$ — метрическое пространство с вероятностной мерой ${\displaystyle \mu }$. Пусть

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

где

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

есть ${\displaystyle \varepsilon }$-окрестность множества ${\displaystyle A}$.

Функция ${\displaystyle \alpha }$ называется профилем пространства ${\displaystyle X}$.

Неформально говоря, пространство ${\displaystyle X}$ удовлетворят принципу концентрации меры, если его профиль ${\displaystyle \alpha (\varepsilon )}$ быстро убывает при возрастании ${\displaystyle \varepsilon }$.

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

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

Если сверх того

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

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

Замечания

• Следующее определение профиля ${\displaystyle \alpha }$ эквивалентно:

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

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

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

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

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

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

для любого ${\displaystyle R}$ имеет самую маленькую ${\displaystyle \varepsilon }$-окрестность ${\displaystyle A_{\varepsilon }}$ для любого фиксированного ${\displaystyle \varepsilon >0}$.

Применяя это наблюдение для однородной вероятностной меры ${\displaystyle \sigma _{n}}$ на ${\displaystyle \mathbb {S} ^{n}}$ и множества ${\displaystyle A}$ такого, что ${\displaystyle \sigma _{n}(A)=1/2}$, получаем следующее неравенство:

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

где ${\displaystyle C,c}$ — универсальные константы. Поэтому последовательность ${\displaystyle X_{n}=\mathbb {S} ^{n}}$ является нормальным семейством Леви, и принцип концентрации меры выполняется для этой последовательности пространств.

Применения

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

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

• Лемма о малом искажении
• Теорема Дворецкого

См. также

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

Примечания

1. Michel Talagrand, A New Look at Independence, The Annals of Probability, 1996, Vol. 24, No.1, 1-34
2. Bárány, Imre. "The limit shape of convex lattice polygons." Discrete & Computational Geometry 13.1 (1995): 279-295.

Дальнейшее чтение

• 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.