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

Концентрація міри — принцип, за яким за певних досить загальних і не дуже обтяжливих обмежень значення функції великої кількості змінних майже стале^[1]. Наприклад, більшість пар точок на одиничній сфері великої розмірності розташовані на відстані, близькій до ${\displaystyle {\tfrac {\pi }{2}}}$ один від одного.

Принцип концентрації міри ґрунтується на ідеї Поля Леві. На початку 1970-х років його дослідив Віталій Мільман у його роботах з локальної теорії банахових просторів. Цей принцип набув подальшого розвитку в роботах Мільмана та Громова, Море, Пізьє^[en], Шехтмана, Талаграна, Леду^[en] та інших.

Основні визначення

Нехай ${\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}$ описується нерівністю^[2]

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

• Лема про мале спотворення
• Теорема Дворецького

Див. також

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