Kopplung (Stochastik)

Kopplung (von engl. coupling) ist eine Beweismethode im mathematischen Teilgebiet der Wahrscheinlichkeitstheorie. Eine Kopplung zweier Zufallsvariablen $X$ und $Y$ ist dabei ein Zufallsvektor, dessen Randverteilungen gerade den Verteilungen von $X$ und $Y$ entsprechen. Die Methode wurde 1938 von Wolfgang Doeblin im Zusammenhang mit Markow-Ketten entwickelt, erst ca. 1970 führte Frank Spitzer den Begriff coupling ein.^[1]

Definition

Hinweis: Hier werden nur reelle Zufallsvariablen betrachtet. Das Konzept lässt sich aber auf beliebige messbare Funktionen übertragen.

Es seien ${\displaystyle X\colon (\Omega _{1},{\mathcal {A}}_{1},\mu )\to \mathbb {R} }$ und ${\displaystyle Y\colon (\Omega _{2},{\mathcal {A}}_{2},\nu )\to \mathbb {R} }$ zwei Zufallsvariablen. Die beiden Wahrscheinlichkeitsräume brauchen nicht notwendig gleich zu sein. Durch ${\displaystyle \mu _{X}=\mu \circ X^{-1}}$ wird ein Wahrscheinlichkeitsmaß auf dem Messraum ${\displaystyle (\mathbb {R} ,{\mathcal {B}}(\mathbb {R} ))}$ der reellen Zahlen versehen mit der Borel-σ-Algebra erklärt. Dieses wird Bildmaß oder Verteilung von $X$ genannt, in Zeichen ${\displaystyle X\sim \mu _{X}}$. Für ${\displaystyle \nu _{Y}=\nu \circ Y^{-1}}$ gilt entsprechendes.

Eine Kopplung von $X$ und $Y$ ist ein gemeinsamer Wahrscheinlichkeitsraum ${\displaystyle (\Omega ,{\mathcal {A}},\gamma )}$ mit zwei Variablen ${\displaystyle {\hat {X}},{\hat {Y}}\colon \Omega \to \mathbb {R} }$ derart, dass ${\displaystyle {\hat {X}}\sim \mu _{X}}$ und ${\displaystyle {\hat {Y}}\sim \nu _{Y}}$ gilt.

Man schreibt auch ${\displaystyle {\hat {X}}\,{\stackrel {\mathcal {D}}{=}}\,X}$ und ${\displaystyle {\hat {Y}}\,{\stackrel {\mathcal {D}}{=}}\,Y}$ um anzudeuten, dass die neuen Zufallsvariablen genauso verteilt sind wie die ursprünglichen.

Konventionen

Für die meisten Anwendungen genügt es, das kartesische Produkt ${\displaystyle \Omega =\Omega _{1}\times \Omega _{2}}$ und die Produkt-σ-Algebra ${\displaystyle {\mathcal {A}}={\mathcal {A}}_{1}\otimes {\mathcal {A}}_{2}}$ zu verwenden. Sind $\pi _{1}$ und $\pi _{2}$ die jeweiligen Projektionen auf den ersten bzw. zweiten Faktor, so bieten sich außerdem die Variablen ${\displaystyle {\hat {X}}=X\circ \pi _{1}}$ und ${\displaystyle {\hat {Y}}=Y\circ \pi _{2}}$ an. Das Maß $\gamma$ muss dann so gewählt werden, dass die eindimensionalen Randverteilungen der gemeinsamen Verteilung des Vektors ${\displaystyle ({\hat {X}},{\hat {Y}})}$ die Verteilungen von $X$ und von $Y$ sind. Ein solches Maß ist in der Regel nicht eindeutig. Der Kern der Beweistechnik besteht gerade darin, $\gamma$ für den jeweiligen Zweck geeignet zu wählen.

Beispiele

Unabhängigkeit

Eine triviale Kopplung ergibt sich aus der Annahme, die Variablen $X$ und $Y$ seien stochastisch unabhängig. Die Verteilung von ${\displaystyle ({\hat {X}},{\hat {Y}})}$ ist dann durch ${\displaystyle P[({\hat {X}},{\hat {Y}})\in A_{1}\times A_{2}]=\mu _{X}(A_{1})\cdot \nu _{Y}(A_{2})}$ für alle Borel-Mengen ${\displaystyle A_{1},A_{2}\in {\mathcal {B}}(\mathbb {R} )}$ eindeutig bestimmt. Zieht man diese Verteilung auf den Urbildraum ${\displaystyle \Omega =\Omega _{1}\times \Omega _{2}}$ zurück, so ergibt sich das Produktmaß ${\displaystyle \gamma =\mu \otimes \nu }$ von $\mu$ und $\nu$.

Diese Kopplung wird selten verwendet, da die meisten Beweise eine irgendwie geartete Abhängigkeit zwischen den gekoppelten Variablen benötigen.

Unfaire Münzen

Seien ${\displaystyle 0\leq p<q\leq 1}$ zwei reelle Zahlen. Angenommen, man hat zwei Münzen, die erste zeigt mit Wahrscheinlichkeit $p$ Kopf, die andere mit Wahrscheinlichkeit $q$. Intuitiv sollte also die zweite Münze „öfter“ Kopf zeigen. Genauer ist zu beweisen, dass bei $n$ Würfen für jedes $k\leq n$ die Wahrscheinlichkeit, dass die erste Münze $k$-mal Kopf zeigt, kleiner ist als die Wahrscheinlichkeit des gleichen Ereignisses für die zweite Münze. Es kann relativ schwierig sein, dies mit klassischen Zählargumenten zu zeigen.^[2] Eine einfache Kopplung leistet dagegen das Gewünschte.

Seien ${\displaystyle X_{1},X_{2}\dots ,X_{n}}$ die Indikatorvariablen für die Kopf-Würfe der ersten Münze und ${\displaystyle Y_{1},Y_{2},\dots ,Y_{n}}$ die der zweiten. Die erste Folge von Zufallsvariablen wird unverändert übernommen, ${\displaystyle {\hat {X}}_{i}=X_{i}}$. Für die ${\displaystyle {\hat {Y}}_{i}}$ gelte jedoch:

• Falls ${\displaystyle X_{i}=1}$, so setze ${\displaystyle {\hat {Y}}_{i}}$ auf $1$.
• Falls ${\displaystyle X_{i}=0}$, setze ${\displaystyle {\hat {Y}}_{i}}$ auf $1$ mit Wahrscheinlichkeit ${\displaystyle {\tfrac {q-p}{1-p}}}$, ansonsten auf ${\displaystyle 0}$.

Die Werte von ${\displaystyle {\hat {Y}}_{i}}$ hängen jetzt also wirklich vom Ausgang von $X_{i}$ (und damit von ${\hat {X}}_{i}$) ab, sie sind gekoppelt. Dennoch gilt ${\displaystyle P[{\hat {Y}}_{i}=1]=q=P[Y_{i}=1]}$, also ${\displaystyle {\hat {Y}}_{i}\,{\stackrel {\mathcal {D}}{=}}\,Y_{i}}$. Die ${\displaystyle {\hat {Y}}_{i}}$ sind aber mindestens immer dann $1$, wenn es die ${\hat {X}}_{i}$ sind, also

${\displaystyle P[{\hat {X}}_{1}+{\hat {X}}_{2}+\dots +{\hat {X}}_{n}\geq k]\leq P[{\hat {Y}}_{1}+{\hat {Y}}_{2}+\dots +{\hat {Y}}_{n}\geq k]}$.

In der Sprache der Wahrscheinlichkeitstheorie gilt fast sicher ${\displaystyle {\hat {X}}_{i}\leq {\hat {Y}}_{i}}$, d. h. ${\displaystyle P[{\hat {X}}_{i}\leq {\hat {Y}}_{i}]=1}$. In diesem Fall spricht man von einer monotonen Kopplung.

Satz von Strassen

In der Theorie der stochastischen Ordnung verallgemeinert der Satz von Strassen das letzte Beispiel. Er besagt, dass eine Zufallsvariable eine andere genau dann stochastisch dominiert, wenn es eine monotone Kopplung zwischen ihnen gibt. Die entscheidende Richtung der Äquivalenz ist die hin zur Kopplung. Ihr Beweis liefert ein Beispiel, in dem $\Omega$ nicht der Produktraum ist.^[1]

Die Verteilung einer reellen Zufallsvariable $X$ über einem beliebigen Wahrscheinlichkeitsraum lässt sich durch ihre Verteilungsfunktion $F_{X}$ beschreiben:

${\displaystyle F_{X}(x)=P[X\leq x]=\mu _{X}((-\infty ,x])}$ für alle $x\in \mathbb {R}$.

$X$ heißt von $Y$ stochastisch dominiert, ${\displaystyle X\preccurlyeq _{st}Y}$, falls stets $F_{X}(x)\geq F_{Y}(x)$ gilt. (Man beachte die Umkehrung des Relationszeichens.)

Als gemeinsamer Wahrscheinlichkeitsraum dient nun das Einheitsintervall ${\displaystyle \Omega =[0,1]}$ versehen mit der Borel-σ-Algebra ${\displaystyle {\mathcal {A}}={\mathcal {B}}([0,1])}$ und dem Lebesgue-Borel-Maß ${\displaystyle \gamma =\lambda }$, das jedem Teilintervall seine Länge zuweist. Als Zufallsvariable setzt man

${\displaystyle {\hat {X}}(\omega )=\inf \,\{x\mid \omega \leq F_{X}(x)\}}$ für alle ${\displaystyle \omega \in [0,1]}$.

Ebenso wird auch ${\displaystyle {\hat {Y}}}$ aus $F_{Y}$ abgeleitet. Nach Konstruktion gilt für alle ${\displaystyle \omega \in [0,1]}$ und $x\in \mathbb {R}$

${\displaystyle \omega \leq F_{X}(x)\Leftrightarrow {\hat {X}}(\omega )\leq x}$.

Die beiden Funktionen ${\displaystyle F_{\hat {X}}=F_{X}}$ sind daher gleich, also müssen es auch die Verteilungen ${\displaystyle {\hat {X}}\,{\stackrel {\mathcal {D}}{=}}\,X}$ sein. ${\displaystyle {\hat {Y}}\,{\stackrel {\mathcal {D}}{=}}\,Y}$ folgt analog. Außerdem impliziert diese Äquivalenz zusammen mit $F_{X}(x)\geq F_{Y}(x)$ schließlich ${\displaystyle {\hat {X}}(\omega )\leq {\hat {Y}}(\omega )}$, wie gewünscht.

Einzelnachweise

1. ↑ ^{a b} Geoffrey Grimmett, David Stirzaker: Probability and Random Processes. 3. Auflage. Oxford University Press, Oxford / New York 2001. 
2. ↑ Devdatt Dubhashi, Alessandro Panconesi: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge / New York 2009. 

Literatur

• Torgny Lindvall: Lectures on the Coupling Method. Wiley, New York 1992. 
• Hermann Thorisson: Coupling, Stationarity, and Regeneration. Springer, New York 2000. 
• Hans-Otto Georgii: Stochastik – Einführung in die Wahrscheinlichkeitstheorie und Statistik. 4., überarbeitete Auflage. De Gruyter, Berlin 2009.