Mät koncentrationen

Måttkoncentration är principen enligt vilken, under vissa ganska generella och inte alltför betungande restriktioner, värdet av en funktion av ett stort antal variabler är nästan konstant [1] . Till exempel är de flesta par av punkter på en högdimensionell enhetssfär på ett avstånd nära varandra. ${\tfrac {\pi }{2}}$

Måttkoncentrationsprincipen är baserad på idén om Paul Levy . Det utforskades i början av 1970-talet av Vitaly Milman i hans arbete med den lokala teorin om Banach-utrymmen . Denna princip utvecklades vidare i verk av Milman och Gromov , Moret, Pisier , Shekhtman, Talagran , Ledoux och andra.

Grundläggande definitioner

Låta vara ett metriskt utrymme med sannolikhetsmått . Låta $(X,d,\mu )$ $\mu$

\alpha (\varepsilon )=\sup \left\{\,\mu (X\setminus A_{\varepsilon })\mid \mu (A)\geqslant 1/2\,\right\},

var

{\displaystyle A_{\varepsilon }=\left\{\,x\mid d(x,A)<\varepsilon \,\right\))

är en -grannskap av uppsättningen . $\varepsilon$ $A$

Funktionen kallas rymdprofilen . $\alfa$ $X$

Informellt sett kommer ett utrymme att uppfylla måttkoncentrationsprincipen om dess profil minskar snabbt som . $X$ $\alpha (\varepsilon )$ $\varepsilon$

Mer formellt kallas en familj av metriska utrymmen med mått en Levy-familj om följande gäller för motsvarande profiler : $(X_{n},d_{n},\mu _{n})$ $\alpha_{n}$

\forall \varepsilon >0\quad \alpha _{n}(\varepsilon )\to 0\quad {\text{at))\quad n\to \infty .

Om mer än så

\forall \varepsilon >0\quad \alpha _{n}(\varepsilon )\leq C\cdot \exp(-c\cdot n\cdot \varepsilon ^{2})

för vissa konstanter kallas sekvensen för en normal Levi-familj . $c,C>0$ $(X_{n},d_{n},\mu _{n})$

Anteckningar

Följande profildefinition är likvärdig: $\alfa$ $\alpha (\varepsilon )=\sup \left\{\,\mu (\{\,F\geq \mathop {M} +\varepsilon \,\})\,\right\},$

där den minsta övre gränsen över alla 1-Lipschitz-funktioner och medianen bestäms av följande olikhetspar

F\colon \,X\to \mathbb {R}

M

F

\mu \{\,F\geq M\,\}\geqslant 1/2,\quad \mu \{\,F\leq M\,\}\geqslant 1/2.

Koncentration av ett mått på en sfär

Det första exemplet går tillbaka till Paul Levy . Enligt den sfäriska isoperimetriska olikheten , bland alla delmängder av en sfär med ett givet sfäriskt mått , det sfäriska segmentet $A$ ${\mathbb {S}}^{n}$ $\sigma _{n}(A)$

B(x_{0},R)_{\mathbb {S} ^{n))=\left\{\,x\in \mathbb {S} ^{n}\mid \mathrm {avstånd} (x,x_{0})\leqslant R\,\right\}

för alla har den minsta - grannskap för någon fast . $R$ $\varepsilon$ ${\displaystyle A_{\varepsilon ))$ $\varepsilon >0$

Genom att tillämpa denna observation för ett homogent sannolikhetsmått på och en uppsättning så att vi får följande olikhet: $\sigma _{n}$ ${\mathbb {S}}^{n}$ $A$ $\sigma _{n}(A)=1/2$

\sigma _{n}(A_{\varepsilon })\geqslant 1-C\cdot \exp(-c\cdot n\cdot \varepsilon ^{2}),

var finns universella konstanter. Därför är sekvensen en normal Lévy-familj , och måttkoncentrationsprincipen gäller för denna sekvens av utrymmen. $C,c$ $X_{n}=\mathbb {S} ^{n}$

Applikationer

Antag, betecknar mängden av alla konvexa polygoner i enhetskvadraten med hörn i -gittret . Sedan, för små, ligger de flesta polygonerna från nära någon konvex uppsättning . ${\mathcal {P}}_{\varepsilon }$ $\varepsilon$ ${\displaystyle (\varepsilon \cdot \mathbb {Z} )^{2))$ $\varepsilon >0$ ${\mathcal {P}}_{\varepsilon }$ $L$
- Mer exakt beskrivs det av ojämlikheten [2] $L$
${\sqrt {1-|x|}}+{\sqrt {1-|y|}}\geq 1.$
Small Distortion Lemma
Dvoretskys teorem

Se även

Martingale Duba

Anteckningar

↑ Michel Talagrand, A New Look at Independence, The Annals of Probability, 1996, Vol. 24, nr 1, 1-34
↑ Barany, Imre. "Gränsformen för konvexa gitterpolygoner." Discrete & Computational Geometry 13.1 (1995): 279-295.

Ytterligare läsning

Ledoux, Michel. Mätkoncentrationsfenomenet (neopr.) . - 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.