Концентрація міри — принцип, за яким за певних досить загальних і не дуже обтяжливих обмежень значення функції великої кількості змінних майже стале. Наприклад, більшість пар точок на одиничній сфері великої розмірності розташовані на відстані, близькій до один від одного.
Принцип концентрації міри ґрунтується на ідеї Поля Леві. На початку 1970-х років його дослідив Віталій Мільман у його роботах з локальної теорії банахових просторів. Цей принцип набув подальшого розвитку в роботах Мільмана та Громова, Море, [en], Шехтмана, Талаграна, [en] та інших.
Основні визначення
Нехай — метричний простір з імовірнісною мірою . Нехай
де
є - околом множини .
Функцію називають профілем простору .
Неформально кажучи, простір задовольняє принципу концентрації міри, якщо його профіль швидко зменшується при зростанні .
Формальніше, сімейство метричних просторів із мірами називають сімейством Леві, якщо для відповідних профілів виконується таке
Якщо понад це
для деяких констант , то послідовність називають нормальним сімейством Леві.
Зауваження
- Таке визначення профілю еквівалентне:
- де точна верхня грань за всіма 1-ліпшицевими функціями і медіана , визначена такою парою нерівностей
Концентрація міри на сфері
Перший приклад запропонував Поль Леві. Відповідно до сферичної ізопериметричної нерівності, серед усіх підмножин сфери із заданою сферичною мірою сферичний сегмент
для будь-якого має найменший -окіл для будь-якого фіксованого .
Застосовуючи це спостереження для однорідної імовірнісної міри на і множини такої, що , отримуємо таку нерівність:
де — універсальні константи. Тому послідовність є нормальним сімейством Леві, і принцип концентрації міри виконується для цієї послідовності просторів.
Застосування
- Припустимо, позначає множину всіх опуклих многокутників у одиничному квадраті з вершинами в -ґратці . Тоді за малих більшість многокутників з лежать близько до деякої опуклої множини .
- Точніше, описується нерівністю
- Лема про мале спотворення
- Теорема Дворецького
Див. також
Примітки
- Michel Talagrand, A New Look at Independence, The Annals of Probability, 1996, Vol. 24, No.1, 1-34
- 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. — .
- A. A. Giannopoulos, V. Milman, Concentration property on probability spaces, Advances in Mathematics 156 (2000), 77—106.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Koncentraciya miri princip za yakim za pevnih dosit zagalnih i ne duzhe obtyazhlivih obmezhen znachennya funkciyi velikoyi kilkosti zminnih majzhe stale Napriklad bilshist par tochok na odinichnij sferi velikoyi rozmirnosti roztashovani na vidstani blizkij do p 2 displaystyle tfrac pi 2 odin vid odnogo Princip koncentraciyi miri gruntuyetsya na ideyi Polya Levi Na pochatku 1970 h rokiv jogo doslidiv Vitalij Milman u jogo robotah z lokalnoyi teoriyi banahovih prostoriv Cej princip nabuv podalshogo rozvitku v robotah Milmana ta Gromova More en Shehtmana Talagrana en ta inshih Osnovni viznachennyaNehaj X d m displaystyle X d mu metrichnij prostir z imovirnisnoyu miroyu m displaystyle mu Nehaj a e sup m X A e m A 1 2 displaystyle alpha varepsilon sup left mu X setminus A varepsilon mid mu A geqslant 1 2 right de A e x d x A lt e displaystyle A varepsilon left x mid d x A lt varepsilon right ye e displaystyle varepsilon okolom mnozhini A displaystyle A Funkciyu a displaystyle alpha nazivayut profilem prostoru X displaystyle X Neformalno kazhuchi prostir X displaystyle X zadovolnyaye principu koncentraciyi miri yaksho jogo profil a e displaystyle alpha varepsilon shvidko zmenshuyetsya pri zrostanni e displaystyle varepsilon Formalnishe simejstvo metrichnih prostoriv iz mirami X n d n m n displaystyle X n d n mu n nazivayut simejstvom Levi yaksho dlya vidpovidnih profiliv a n displaystyle alpha n vikonuyetsya take e gt 0 a n e 0 pri n displaystyle forall varepsilon gt 0 quad alpha n varepsilon to 0 quad text pri quad n to infty Yaksho ponad ce e gt 0 a n e C exp c n e 2 displaystyle forall varepsilon gt 0 quad alpha n varepsilon leq C cdot exp c cdot n cdot varepsilon 2 dlya deyakih konstant c C gt 0 displaystyle c C gt 0 to poslidovnist X n d n m n displaystyle X n d n mu n nazivayut normalnim simejstvom Levi Zauvazhennya Take viznachennya profilyu a displaystyle alpha ekvivalentne a e sup m F M e displaystyle alpha varepsilon sup left mu F geq mathop M varepsilon right de tochna verhnya gran za vsima 1 lipshicevimi funkciyami F X R displaystyle F colon X to mathbb R i M displaystyle M mediana F displaystyle F viznachena takoyu paroyu nerivnostejm F M 1 2 m F M 1 2 displaystyle mu F geq M geqslant 1 2 quad mu F leq M geqslant 1 2 dd Koncentraciya miri na sferiPershij priklad zaproponuvav Pol Levi Vidpovidno do sferichnoyi izoperimetrichnoyi nerivnosti sered usih pidmnozhin A displaystyle A sferi S n displaystyle mathbb S n iz zadanoyu sferichnoyu miroyu s n A displaystyle sigma n A sferichnij segment B x 0 R S n x S n d i s t x x 0 R displaystyle B x 0 R mathbb S n left x in mathbb S n mid mathrm dist x x 0 leqslant R right dlya bud yakogo R displaystyle R maye najmenshij e displaystyle varepsilon okil A e displaystyle A varepsilon dlya bud yakogo fiksovanogo e gt 0 displaystyle varepsilon gt 0 Zastosovuyuchi ce sposterezhennya dlya odnoridnoyi imovirnisnoyi miri s n displaystyle sigma n na S n displaystyle mathbb S n i mnozhini A displaystyle A takoyi sho s n A 1 2 displaystyle sigma n A 1 2 otrimuyemo taku nerivnist s n A e 1 C exp c n e 2 displaystyle sigma n A varepsilon geqslant 1 C cdot exp c cdot n cdot varepsilon 2 de C c displaystyle C c universalni konstanti Tomu poslidovnist X n S n displaystyle X n mathbb S n ye normalnim simejstvom Levi i princip koncentraciyi miri vikonuyetsya dlya ciyeyi poslidovnosti prostoriv ZastosuvannyaPripustimo P e displaystyle mathcal P varepsilon poznachaye mnozhinu vsih opuklih mnogokutnikiv u odinichnomu kvadrati z vershinami v e displaystyle varepsilon gratci e Z 2 displaystyle varepsilon cdot mathbb Z 2 Todi za malih e gt 0 displaystyle varepsilon gt 0 bilshist mnogokutnikiv z P e displaystyle mathcal P varepsilon lezhat blizko do deyakoyi opukloyi mnozhini L displaystyle L Tochnishe L displaystyle L opisuyetsya nerivnistyu 1 x 1 y 1 displaystyle sqrt 1 x sqrt 1 y geq 1 Lema pro male spotvorennya Teorema DvoreckogoDiv takozhMartingal DubaPrimitkiMichel Talagrand A New Look at Independence The Annals of Probability 1996 Vol 24 No 1 1 34 Barany Imre The limit shape of convex lattice polygons Discrete amp Computational Geometry 13 1 1995 279 295 LiteraturaLedoux 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