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

  ${\displaystyle {\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, , Advances in Mathematics 156 (2000), 77—106.