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

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

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

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

Нехай $(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.