Korrelationsungleichung

Als Korrelationsungleichungen werden e​ine Gruppe v​on mathematischen Ungleichungen bezeichnet, welche d​en Begriff d​er positiven Korrelation a​uf partiell geordnete Mengen (POSETs) u​nd distributive Verbände übertragen. Sie h​aben darüber hinaus e​ine wahrscheinlichkeitstheoretische Interpretation u​nd berühren d​as mathematische Teilgebiet d​er Theorie d​er stochastischen Ordnungen.

Die Entwicklung wurde angestoßen durch die FKG-Ungleichung aus dem Jahr 1971, benannt nach C. M. Fortuin, Jean Ginibre und P. W. Kasteleyn, welche auf verschiedensten Gebieten Anwendung gefunden hat, unter anderem auf den Gebieten statistische Mechanik, Partikelsysteme, Kombinatorik und Perkolationstheorie.[1] Eine frühere Version dieser Ungleichung für unabhängige und identisch verteilte Zufallsvariablen wurde 1960 von Theodore Edward Harris bewiesen[2], wurde jedoch zunächst nicht von Mathematikern anderer Disziplinen rezipiert[3] und erst durch die Veröffentlichung von Fortuin, Kasteleyn und Ginibre bekannt. In diesem Zusammenhang spielt der Begriff des assoziierten Maßes (auch Maß mit positiven Korrelationen) eine Rolle.

Ausgehend v​on der FKG-Ungleichungen wurden weitere ähnliche Ungleichungen gefunden, z​um Beispiel d​ie Holley-Ungleichung n​ach Richard Holley i​m Jahr 1974, o​der die s​ehr allgemeine Vier-Funktionen-Ungleichung v​on Rudolf Ahlswede u​nd David E. Daykin v​on 1978, a​us der d​ie anderen genannten Ungleichungen folgen.

Assoziierte Maße

Der Begriff d​es assoziierten Maßes w​urde 1967 v​on J. D. Esary, Frank Proschan u​nd D. W. Walkup[4] eingeführt. Wegen d​er Analogie z​u positiven Korrelationen v​on Zufallsvariablen w​ird von manchen Autoren a​uch die Bezeichnung Maß m​it positiven Korrelationen verwendet.

Ein endliches Maß ${\displaystyle \mu }$ auf ${\displaystyle (X,{\mathfrak {B}})}$, wobei ${\displaystyle X}$ ein halbgeordneter topologischer[5] Raum sei, heißt assoziiert, falls

${\displaystyle \int fg\;\mathrm {d} \mu \geq \int f\mathrm {d} \mu \cdot \int g\mathrm {d} \mu }$

für alle beschränkten, stetigen, monoton wachsenden Funktionen ${\displaystyle f,g}$ von ${\displaystyle X}$ nach ${\displaystyle \mathbb {R} }$ gilt.

Die FKG-Ungleichung

Die FKG-Ungleichung, benannt n​ach C. M. Fortuin, J. Ginibre u​nd P. W. Kasteleyn (1971), i​st ursprünglich e​ine Korrelationsungleichung a​uf distributiven Verbänden. Sie i​st ein fundamentales Werkzeug a​uf den Gebieten d​er statistischen Mechanik u​nd der probabilistischen Kombinatorik (speziell a​uf dem Gebiet d​er Zufallsgraphen.) Sie besagt übertragen a​uf ein wahrscheinlichkeitstheoretisches Setting i​n etwa, d​ass wachsende Ereignisse miteinander positiv korreliert sind.

Formulierung für endliche distributive Verbände

Sei ${\displaystyle X}$ ein endlicher distributiver Verband, und ${\displaystyle \mu }$ ein Maß auf ${\displaystyle X}$, welches

${\displaystyle \mu (\{x\wedge y\})\mu (\{x\vee y\})\geq \mu (\{x\})\mu (\{y\})}$

für alle ${\displaystyle x}$, ${\displaystyle y}$ im Verband ${\displaystyle X}$ erfüllt. Diese Eigenschaft heißt auch Log-Supermodularität.

Die FKG-Ungleichung besagt dann, dass das Maß ${\displaystyle \mu }$ assoziiert ist, also dass für zwei beliebige bezüglich der von den Verbandsoperationen induzierten Halbordnung stetige, monoton wachsende, quadratintegrierbare Funktionen ${\displaystyle f}$ und ${\displaystyle g}$ von ${\displaystyle X}$ nach ${\displaystyle \mathbb {R} }$ gilt, dass sie positiv korreliert sind:

${\displaystyle \int fg\;\mathrm {d} \mu \geq \int f\mathrm {d} \mu \cdot \int g\mathrm {d} \mu }$.

Ebenfalls positiv korreliert sind zwei Funktionen ${\displaystyle f}$ und ${\displaystyle g}$, wenn man die Bedingung „monoton steigend“ durch „monoton fallend“ ersetzt. Ist die eine Funktion monoton wachsend, die andere monoton fallend, dann sind sie negativ korreliert. Ein Beweis befindet sich in der Originalarbeit.

Eine ähnliche Aussage gilt im allgemeineren Fall, dass ${\displaystyle X}$ ein abzählbarer kompakter metrischer Raum ist. In diesem Fall muss ${\displaystyle \mu }$ ein strikt positives endliches Maß sein und die Log-Supermodularität muss über Randereignisse (Zylindermengen) definiert werden.[6]

Weitere Formulierungen

In Rinott, Saks findet sich der Beweis für eine Form der FKG-Ungleichung für ${\displaystyle \sigma }$-finite Maße auf der (überabzählbaren) Menge ${\displaystyle \mathbb {R} ^{d}}$. In diesem Fall wird Log-Supermodularität eines Maßes über die Dichtefunktion ${\displaystyle \varphi }$ (bezüglich irgendeines Produktmaßes auf ${\displaystyle \mathbb {R} ^{d}}$) definiert, welche für alle ${\displaystyle x,y\in \mathbb {R} ^{d}}$ erfüllen muss:

${\displaystyle \varphi (x)\varphi (y)\leq \varphi (x\wedge y)\varphi (x\vee y)}$.

Die Griffith-Ungleichung i​st eine weitere Ungleichung v​on 1967, welche d​ie gleiche Aussage m​acht wie d​ie FKG-Ungleichung, jedoch andere Voraussetzungen h​at und Anwendung a​uf dem Gebiet d​es Ising-Modells hat.[7]

Die Harris-Ungleichung

Die Harris-Ungleichung i​st im Prinzip d​ie FKG-Ungleichung für Produktmaße, benannt n​ach Theodore E. Harris, welcher s​ie 1960 b​eim Studium v​on Perkolationen i​n der Ebene gefunden hat.[8]

Wenn ${\displaystyle X}$ eine totalgeordnete Menge ist, dann ist die Log-Supermodularität automatisch für jedes Maß ${\displaystyle \mu }$ auf ${\displaystyle X}$ erfüllt.

Es gilt zum Beispiel, dass für jede Wahrscheinlichkeitsverteilung ${\displaystyle \mu }$ auf ${\displaystyle \mathbb {R} }$, und monoton wachsende quadratintegrierbaren Funktionen ${\displaystyle f}$ und ${\displaystyle g}$

${\displaystyle \int _{\mathbb {R} }f(x)g(x)\,d\mu (x)\geq \int _{\mathbb {R} }f(x)\,d\mu (x)\,\int _{\mathbb {R} }g(x)\,d\mu (x),}$

gilt. Dies f​olgt aus

${\displaystyle \int _{\mathbb {R} }\int _{\mathbb {R} }[f(x)-f(y)][g(x)-g(y)]\,d\mu (x)\,d\mu (y)\geq 0}$

(die Terme i​n den eckigen Klammern h​aben das jeweils gleiche Vorzeichen.)

Die Log-Supermodularität ist auch automatisch erfüllt, wenn der Verband ein Produkt totalgeordneter Verbände ist, ${\displaystyle X=X_{1}\times \dots \times X_{n}}$, und ${\displaystyle \mu =\mu _{1}\otimes \dots \otimes \mu _{n}}$ ein Produktmaß auf ${\displaystyle X}$. In der Anwendung ist ${\displaystyle \mu }$ häufig die (Produkt-)Verteilung von unabhängig und identisch verteilten Zufallsvariablen auf unabhängigen Kopien ${\displaystyle X_{i}}$ eines Wahrscheinlichkeitsraumes.

Sei ${\displaystyle E}$ eine endliche Indexmenge. Sei ${\displaystyle X=\prod _{e\in E}\{0,1\}}$ versehen mit der koordinatenweisen Ordnung ${\displaystyle \leq }$ und mit den Verbands-Operationen:

${\displaystyle \xi \vee \eta }$ sei für alle ${\displaystyle \xi ,\eta \in X}$, ${\displaystyle e\in E}$ definiert über ${\displaystyle \xi (e)\vee \eta (e):=\max\{\xi (e),\eta (e)\}}$,

sowie ${\displaystyle \xi \wedge \eta }$ entsprechend über ${\displaystyle \xi (e)\wedge \eta (e):=\min\{\xi (e),\eta (e)\}}$.

Mit diesen Operationen ist ${\displaystyle X}$ eine Boolesche Algebra.

Sei ${\displaystyle \mu }$ ein Wahrscheinlichkeitsmaß auf ${\displaystyle (X,\wp (X))}$. Dann schreibt sich die FKG-Ungleichung

${\displaystyle \mathbf {E} _{\mu }fg\geq (\mathbf {E} _{\mu }f)(\mathbf {E} _{\mu }g)}$

für alle monoton wachsenden ${\displaystyle f,g}$ für die die Erwartungswerte existieren, wobei ${\displaystyle \mathbf {E} _{\mu }}$ den Erwartungswert bezüglich ${\displaystyle \mu }$ bezeichne.[9]

Ein Ereignis ${\displaystyle A\in \wp (X)}$ heißt entsprechend wachsend, wenn ${\displaystyle \mathbb {I} _{A}(x)\leq \mathbb {I} _{A}(y)}$ für alle ${\displaystyle x,y\in X}$ mit ${\displaystyle x\leq y}$. (Und ein Ereignis heißt fallend, wenn das Komplement ${\displaystyle \Omega \setminus A}$ wachsend ist.)

Sind ${\displaystyle A}$ und ${\displaystyle B}$ wachsende Ereignisse, so gilt

${\displaystyle \mathbf {P} _{\mu }(A\cap B)\geq \mathbf {P} _{\mu }(A)\mathbf {P} _{\mu }(B).}$

Ein Beweis der Harris-Ungleichung, der auf dem hier verwendeten Doppelintegral-Trick auf ${\displaystyle \{0,1\}}$ beruht, findet sich in Grimmett 1999.

Beispiele

Honigwabengitter mit zufällig eingefärbten Waben.

Man färbe zufällig jedes Hexagon des unendlichen Honigwaben-Gitters schwarz jeweils stochastisch unabhängig voneinander mit Wahrscheinlichkeit ${\displaystyle p}$ und weiß mit Wahrscheinlichkeit ${\displaystyle 1-p}$. Seien ${\displaystyle A,B,X,Y}$ vier (nicht notwendig verschiedene) solche Hexagone. Seien ${\displaystyle A\leftrightarrow B}$ und ${\displaystyle X\leftrightarrow Y}$ die Ereignisse, dass es einen schwarzen Pfad von ${\displaystyle A}$ nach ${\displaystyle B}$ respektive von ${\displaystyle X}$ nach ${\displaystyle Y}$gibt. Dann besagt die FKG-Ungleichung, dass diese Ereignisse positive korreliert sind: ${\displaystyle \mathbf {P} (A\leftrightarrow B,\ X\leftrightarrow Y)\geq \mathbf {P} (A\leftrightarrow B)\mathbf {P} (X\leftrightarrow Y)}$. In anderen Worten, wird vorausgesetzt, dass es bereits den einen schwarzen Pfad gibt, wird die Existenz des anderen Pfades wahrscheinlicher.

Im Erdős-Rényi-Zufallsgraph i​st die Existenz e​ines Hamilton-Zyklus negativ korreliert m​it der 3-Färbbarkeit d​es Graphen, d​a die Wahrscheinlichkeit d​er Existenz e​ines Hamilton-Zyklus m​it der Anzahl d​er belegten Verbindungen steigt (steigendes Ereignis), während d​ie Wahrscheinlichkeit v​on letzterem fällt (fallendes Ereignis).

Die Holley-Ungleichung

Diese von Richard Holley 1974 entdeckte und gelegentlich als Holley-Ungleichung bezeichnete Ungleichung besagt: Seien ${\displaystyle \mu _{1}}$ und ${\displaystyle \mu _{2}}$ zwei strikt positive Verteilungen auf einem endlichen distributiven Verband ${\displaystyle X}$, welche

${\displaystyle \mu _{1}(\{x\wedge y\})\mu _{2}(\{x\vee y\})\geq \mu _{1}(\{x\})\mu _{2}(y\})}$ für alle ${\displaystyle x,y\in X}$

erfüllen. Dann gilt

${\displaystyle \int f\;\mathrm {d} \mu _{2}\geq \int f\;\mathrm {d} \mu _{1}}$.

für alle monoton wachsende integrierbaren Funktionen ${\displaystyle f}$ auf ${\displaystyle X}$. Dies ist gleichbedeutend damit, dass ${\displaystyle \mu _{2}}$ größer als ${\displaystyle \mu _{1}}$ bezüglich der gewöhnlichen stochastischen Ordnung ist. Thomas Liggett hat einen Beweis für Räume der Form ${\displaystyle \Omega =\prod _{s\in S}\{0,1\}}$, welcher auf der Kopplung zweier Markow-Ketten in stetiger Zeit mit ${\displaystyle \mu _{1}}$ und ${\displaystyle \mu _{2}}$ als stationären Verteilungen beruht. Er gibt darüber hinaus an, wie der Beweis auf abzählbare Produkträume zu erweitern wäre.[10] Aus der Holley-Ungleichung lässt sich die FKG-Ungleichung durch geschicktes Einsetzen folgern.[11]

Alternative Voraussetzung für die FKG-Ungleichung

Sei ${\displaystyle \mathbb {R} ^{d}}$ versehen mit der koordinatenweisen Halbordnung. Für eine Verteilung ${\displaystyle \mu }$ auf ${\displaystyle \mathbb {R} ^{d}}$ ist folgende Eigenschaft oft leichter zu überprüfen als die Log-Supermodularität:

Fixiert man eine Koordinate ${\displaystyle i\in \{1,\dots ,d\}}$ und zwei Konfigurationen ${\displaystyle \varphi }$ und ${\displaystyle \psi }$ in ${\displaystyle \mathbb {R} ^{d}}$ bezüglich der anderen Koordinaten, so dass ${\displaystyle \varphi _{j}\geq \psi _{j}}$ for all ${\displaystyle w\not =v}$, die auf ${\displaystyle \mu }$ bedingte Verteilung von ${\displaystyle \varphi _{i}}$ gegeben ${\displaystyle \{\varphi (j):j\not =i\}}$ ist stochastisch größer als die auf ${\displaystyle \mu }$ bedingte Verteilung von ${\displaystyle \psi }$ gegeben ${\displaystyle \{\psi _{j}:j\not =i\}}$.

Erfüllt ${\displaystyle \mu }$ diese Eigenschaft, dann ist ${\displaystyle \mu }$ assoziiert.

Die Vier-Funktionen-Ungleichung

Die Vier-Funktionen-Ungleichung von Ahlswede and Daykin von 1978 lässt sich wie folgt formulieren: Seien ${\displaystyle f_{1},f_{2},g_{1},g_{2}}$ nichtnegative reellwertige Funktionen auf ${\displaystyle \mathbb {R} ^{d}}$, welche folgende Bedingung erfüllen:

${\displaystyle f_{1}(x)f_{2}(y)\leq g_{1}(x\vee y)g_{2}(x\wedge y)}$ für alle ${\displaystyle x,y}$

Dann gilt für jedes log-supermodulare Maß ${\displaystyle \mu }$ auf ${\displaystyle \mathbb {R} ^{d}}$,

${\displaystyle \int _{\mathbb {R} ^{d}}f_{1}(x)\mathrm {d} \mu (x)\int _{\mathbb {R} ^{d}}f_{2}(x)\mathrm {d} \mu (x)\leq \int _{\mathbb {R} ^{d}}g_{1}(x)\mathrm {d} \mu (x)\int _{\mathbb {R} ^{d}}g_{2}(x)\mathrm {d} \mu (x)}$

Es lässt s​ich zeigen, d​ass aus d​er Vier-Funktionen-Ungleichung Holleys Ungleichung folgt, a​us der wiederum d​ie FKG-Ungleichung folgt.[12]

Einzelnachweise

1. Rinott und Saks, S. 332.
2. Grimmet, S. 11.
3. Fortuin, Kasteleyn, Ginibre, 1971, S. 89.
4. Müller, Stoyan, S. 122.
5. Wobei Halbordnung und Topologie verträglich seien, d. h. ${\displaystyle \{(x,y)\in X\times X\colon x\leq y\}}$ sei abgeschlossen. Für diskrete Räume ist dies der Fall.
6. Liggett, S. 79.
7. Fortuin, Kasteleyn und Ginibre, S. 89.
8. Harris, S. 13–20.
9. Fishburn: FKG inequality.
10. Liggett, S. 77.
11. Liggett, S. 79.
12. Rinott und Saks, S. 333.

Literatur

• C. M. Fortuin, P.W. Kasteleyn, J. Ginibre: Correlation inequalities on some partially ordered sets. In: Comm. Math. Phys. Nr. 22, 1971, MR0309498, ISSN 0010-3616, S. 89–103.
• P.C. Fishburn: FKG inequality. In: Michiel Hazewinkel (Hrsg.): Encyclopaedia of Mathematics, Kluwer Academic Publishers, 2001, ISBN 978-1-55608-010-4.
• P.C. Fishburn: Correlation inequalities. In: Michiel Hazewinkel (Hrsg.): Encyclopaedia of Mathematics, Kluwer Academic Publishers, 2001, ISBN 978-1-55608-010-4.
• H.-O. Georgii, O. Haggstrom, C. Maes: The random geometry of equilibrium phases. In: Phase transitions and critical phenomena. Nr. 18, 2001, Academic Press, San Diego, CA, MR2014387, S. 1–142.
• G. R. Grimmett: Percolation. Second edition. Springer-Verlag, New York 1999, MR1707339, ISBN 3-540-64902-6.
• T. E. Harris: A lower bound for the critical probability in a certain percolation. In: Proceedings of the Cambridge Philosophical Society, Nr. 56, 1960, MR0115221, S. 13–20.
• R. Holley: Remarks on the FKG inequalities. In: Communications in Mathematical Physics Nr. 36, 1974, MR0341552, ISSN 0010-3616, S. 227–231.
• Thomas M. Liggett: Interacting Particle Systems. Springer-Verlag, New York, 1985. ISBN 3-540-96069-4.
• R. Lyons: Phase transitions on nonamenable graphs In: J. Math. Phys. Nr. 41, 2000, MR1757952, S. 1099–1126.
• S. Sheffield: Random surfaces. In: Asterisque, Nr. 304, 2005, MR2251117.
• A. Müller and D. Stoyan: Comparison Methods for Stochastic Models and Risk. Wiley, Chichester, 2002.
• Yosef Rinott, Michael Saks: On FKG-type and permanental inequalities. In: Moshe Shaked, Y. L. Tong (Hrsg.): Stochastic inequalities: Papers from the AMS-IMS-SIAM Joint Summer Research Conference held in Seattle, Washington. July 1991 (Hayward, CA: Institute of Mathematical Statistics, 1992), ISBN 0-940600-29-3, ISBN 978-0-940600-29-4, 332–342, MR1228073.