Konzentration des Maßes

Unter der Konzentration des Maßes versteht man ein mathematisches Phänomen aus der Maßtheorie, welches an vielen Stellen in der Stochastik auftritt, aber auch in anderen Gebieten wie der Funktionalanalysis und der Kombinatorik. Das Maß konzentriert sich in hochdimensionalen Räumen in engen Regionen, sodass ein Großteil der Wahrscheinlichkeitsmasse dort liegt und der Rest exponentiell klein ist. Anschaulich kann man die Konzentration des Maßes in der Stochastik als den Effekt interpretieren, dass Funktionen mit vielen kleinen lokalen Fluktuationen sich mit großer Wahrscheinlichkeit wie Konstanten verhalten.

Wesentliche Arbeit zur Konzentration des Maßes stammt aus den 1970ern von Vitali Milman aus dem Studium der asymptotischen Geometrie von Banachräumen, welcher die Vorarbeit von Paul Lévy weiterführte.^[1]

Die isoperimetrische Ungleichung auf der Sphäre stammt von Lévy.^[2]

Wir betrachten den Raum ${\displaystyle (\mathbb {R} ^{n},\|\cdot \|,\mu )}$ wobei ${\displaystyle \|\cdot \|}$ die euklidische Norm und ${\displaystyle \mu }$ das sphärische Wahrscheinlichkeitsmaß auf ${\displaystyle \mathbb {R} ^{n}}$ bezeichnet. Dieses Maß ist normiert und rotations-invariant auf

${\displaystyle \mathbb {S} ^{n-1}:=\{x\in \mathbb {R} ^{n}:\|x\|=1\},}$

das bedeutet

• ${\displaystyle \mu (\mathbb {S} ^{n-1})=1}$,
• für jedes ${\displaystyle A\subseteq \mathbb {S} ^{n-1}}$ und jede Rotation ${\displaystyle T}$ gilt ${\displaystyle \mu (TA)=\mu (A)}$.

Für ein ${\displaystyle A\subset \mathbb {S} ^{n-1}}$, definiert man die geodäsische Distanz

${\displaystyle \operatorname {d} (x,A)=\inf \limits _{y\in A}\operatorname {d} (x,y).}$

Mit dieser Distanz lässt sich nun die ${\displaystyle \delta }$-Verfettung ${\displaystyle A_{\delta }}$ der Menge ${\displaystyle A}$ definieren

${\displaystyle A_{\delta }:=\{x\in \mathbb {R} ^{n}:\operatorname {d} (x,A)<\delta \}}$.

Anschaulich verfettet man ${\displaystyle A}$ um die Dicke ${\displaystyle \delta }$, den es gilt

${\displaystyle A\subseteq A_{\delta }}$

Mit ${\displaystyle B}$ bezeichnen wir das Kugelsegment ${\displaystyle B:=\left\{x\in \mathbb {S} ^{n-1}|\operatorname {d} (x,x_{0})\leq p\right\}}$ um einen Punkt ${\displaystyle x_{0}}$ für ein passendes ${\displaystyle p}$, so dass ${\displaystyle \mu (A)=\mu (B)}$. Dann gilt für ${\displaystyle t>0}$

${\displaystyle \mu (A_{t})\geq \mu (B_{t})}$.

Nimm nun an, dass ${\displaystyle \mu (A)=1/2}$, dann gilt

${\displaystyle \mu (A_{t})\geq \mu (B_{t})=1-\int _{t}^{\tfrac {\pi }{2}}\cdots \mathrm {d} \theta \geq 1-{\tfrac {1}{2}}e^{-(n-1){\tfrac {t^{2}}{2}}}=1-Ce^{-c(n-1)t^{2}}.}$

Daraus folgt für das Komplement ${\displaystyle A_{t}^{c}}$, dass sich dessen Maß exponentiell verkleinert, sobald ${\displaystyle \mu (A)=1/2}$ erreicht wurde, wenn ${\displaystyle t}$ wächst,

${\displaystyle \mu (A_{t}^{c})\leq Ce^{-c(n-1)t^{2}}.}$

Dies zeigt, dass sich das Maß exponentiell auf der Sphäre konzentriert, so bald die Menge ${\displaystyle A}$ die halbe Kugel (bei ${\displaystyle \mu (A)=1/2}$) erreicht hat. Es kommt zur Konzentration des Maßes auf der Sphäre.

Vitali Milman nützte dieses Resultat in seinem Beweis des Satzes von Dvoretzky.

Sei ${\displaystyle (M_{n},d_{n},\mu _{n})}$ ein Familie metrischer Wahrscheinlichkeitsräume. Definiere die Konzentrationsraten

${\displaystyle \alpha _{n}(t):=\sup \limits _{A\subset M_{n}:\mu _{n}(A)\geq 1/2}\mu _{n}(d_{n}(M_{n},A)\geq t)=\sup \limits _{A\subset M_{n}:\mu _{n}(A)\geq 1/2}\mu _{n}(A_{t}^{c})}$

wobei ${\displaystyle A_{t}}$ das ${\displaystyle t}$-Verfetten der Menge ${\displaystyle A}$ bezeichnet

${\displaystyle A_{t}:=\{x\in \mathbb {R} ^{n}:\operatorname {d} (x,A)<t\}}$

für ${\displaystyle \operatorname {d} (x,A):=\inf \limits _{y\in A}\operatorname {d} (x,y)}$.

Dann wird ${\displaystyle (M_{n},d_{n},\mu _{n})}$ Lévy-Familie genannt, falls ${\displaystyle \forall t>0}$

${\displaystyle \alpha _{n}(t)\to 0\ {\text{wenn }}n\to \infty }$

und normale Lévy-Familie, falls ${\displaystyle \forall t>0}$ und ${\displaystyle n\geq 1}$ (oder ${\displaystyle n}$ groß genug)

${\displaystyle \alpha _{n}(t)\leq Ce^{-cnt^{2}}}$

für zwei Konstanten ${\displaystyle c,C>0}$.

1. ↑ Michel Ledoux: The Concentration of Measure Phenomenon. American Mathematical Society, 2001, ISBN 978-0-8218-2864-9. 
2. ↑ Stephane Boucheron, Gabor Lugosi, Pascal Massart: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, USA 2013, ISBN 978-0-19-953525-5.