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

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

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

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

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

$\alpha (\epsilon )=\sup \{\mu (X\setminus A_{\epsilon })\mid \mu (A)⩾1/2\},$

где

$A_{\epsilon }=\{x\mid d(x,A)<\epsilon \}$

есть $\epsilon$-окрестность множества $A$.

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

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

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

$\mathrm{\forall }\epsilon >0{\alpha }_n(\epsilon )\to 0\text{при}n\to \mathrm{\infty }.$

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

$\mathrm{\forall }\epsilon >0{\alpha }_n(\epsilon )\le C\cdot \exp (-c\cdot n\cdot {\epsilon }^2)$

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

Замечания

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

  $\alpha (\epsilon )=\sup \{\mu (\{F\ge M+\epsilon \})\},$

где точная верхняя грань по всем 1-липшицевым функцям $F:X\to ℝ$ и $M$ медиана $F$ определяемая следующей парой неравенств

$\mu \{F\ge M\}⩾1/2,\mu \{F\le M\}⩾1/2.$

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

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

$B(x_0,R{)}_{{𝕊}^n}=\{x\in {𝕊}^n\mid \mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(x,x_0)⩽R\}$

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

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

${\sigma }_n(A_{\epsilon })⩾1-C\cdot \exp (-c\cdot n\cdot {\epsilon }^2),$

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

Применения

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

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

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

См. также

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

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

• Шаблон:Книга
• A. A. Giannopoulos, V. Milman, Concentration property on probability spaces, Advances in Mathematics 156 (2000), 77—106.