Концентрация меры
Концентрация меры — принцип, согласно которому при определённых достаточно общих и не слишком обременительных ограничениях значение функции большого числа переменных почти постоянно[1]. Например, большинство пар точек на единичной сфере большой размерности находятся на расстоянии, близком к друг от друга.
Принцип концентрации меры основан на идее Поля Леви. Он был исследован в начале 1970-х годов Виталием Мильманом в его работах по локальной теории банаховых пространств. Этот принцип получил дальнейшее развитие в работах Мильмана и Громова, Морэ, Пизье, Шехтмана, Талаграна, Леду[англ.] и других.
Основные определения
Пусть — метрическое пространство с вероятностной мерой . Пусть
где
есть -окрестность множества .
Функция называется профилем пространства .
Неформально говоря, пространство удовлетворят принципу концентрации меры, если его профиль быстро убывает при возрастании .
Более формально, семейство метрических пространств с мерами называется семейством Леви, если для соответствующих профилей выполняется следующее
Если сверх того
для некоторых констант , то последовательность называется нормальным семейством Леви.
Замечания
- Следующее определение профиля эквивалентно:
- где точная верхняя грань по всем 1-липшицевым функцям и медиана определяемая следующей парой неравенств
Концентрация меры на сфере
Первый пример восходит к Полю Леви. Согласно сферическому изопериметрическому неравенству, среди всех подмножеств сферы с заданной сферической мерой сферический сегмент
для любого имеет самую маленькую -окрестность для любого фиксированного .
Применяя это наблюдение для однородной вероятностной меры на и множества такого, что , получаем следующее неравенство:
где — универсальные константы. Поэтому последовательность является нормальным семейством Леви, и принцип концентрации меры выполняется для этой последовательности пространств.
Применения
- Предположим, обозначает множество всех выпуклых многоугольников в единичном квадрате с вершинами в -решётке . Тогда при малых большинство многоугольников из лежат близко к некоторому выпуклому множеству .
- Точнее говоря, описывается неравенством[2]
- Лемма о малом искажении
- Теорема Дворецкого
См. также
Примечания
Дальнейшее чтение
- 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.