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

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

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

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

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

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

где

[math]\displaystyle{ A_\varepsilon = \left\{\, x \mid d(x, A) \lt \varepsilon \,\right\} }[/math]

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

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

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

Более формально, семейство метрических пространств с мерами [math]\displaystyle{ (X_n, d_n, \mu_n) }[/math] называется семейством Леви, если для соответствующих профилей [math]\displaystyle{ \alpha_n }[/math] выполняется следующее

[math]\displaystyle{ \forall \varepsilon \gt 0 \quad \alpha_n(\varepsilon) \to 0 \quad \text{при}\quad n\to \infty. }[/math]

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

[math]\displaystyle{ \forall \varepsilon \gt 0 \quad \alpha_n(\varepsilon) \leq C\cdot \exp(-c\cdot n\cdot \varepsilon^2) }[/math]

для некоторых констант [math]\displaystyle{ c,C\gt 0 }[/math], то последовательность [math]\displaystyle{ (X_n, d_n, \mu_n) }[/math] называется нормальным семейством Леви.

Замечания

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

  [math]\displaystyle{ \alpha(\varepsilon) = \sup \left\{\, \mu( \{\, F \geq \mathop{M} + \varepsilon \,\}) \,\right\}, }[/math]

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

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

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

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

[math]\displaystyle{ B(x_0,R)_{\mathbb{S}^n}= \left\{\, x \in \mathbb{S}^n \mid \mathrm{dist}(x, x_0) \leqslant R \,\right\} }[/math]

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

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

[math]\displaystyle{ \sigma_n(A_\varepsilon) \geqslant 1 - C \cdot \exp(- c\cdot n\cdot \varepsilon^2), }[/math]

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

Применения

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

  [math]\displaystyle{ \sqrt{1-|x|}+\sqrt{1-|y|}\ge 1. }[/math]

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

См. также

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

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

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