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

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

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

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

Пусть метрическое пространство с вероятностной мерой . Пусть

где

есть -окрестность множества .

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

Неформально говоря, пространство удовлетворят принципу концентрации меры, если его профиль быстро убывает при возрастании .

Более формально, семейство метрических пространств с мерами называется семейством Леви, если для соответствующих профилей выполняется следующее

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

для некоторых констант , то последовательность называется нормальным семейством Леви.

Замечания

  • Следующее определение профиля эквивалентно:
где точная верхняя грань по всем 1-липшицевым функцям и медиана определяемая следующей парой неравенств

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

Первый пример восходит к Полю Леви. Согласно сферическому изопериметрическому неравенству, среди всех подмножеств сферы с заданной сферической мерой сферический сегмент

для любого имеет самую маленькую -окрестность для любого фиксированного .

Применяя это наблюдение для однородной вероятностной меры на и множества такого, что , получаем следующее неравенство:

где — универсальные константы. Поэтому последовательность является нормальным семейством Леви, и принцип концентрации меры выполняется для этой последовательности пространств.

Применения

  • Предположим, обозначает множество всех выпуклых многоугольников в единичном квадрате с вершинами в -решётке . Тогда при малых большинство многоугольников из лежат близко к некоторому выпуклому множеству .
    • Точнее говоря, описывается неравенством[2]
  • Лемма о малом искажении
  • Теорема Дворецкого

См. также

Примечания

  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.