Korrelationsungleichung

aus Wikipedia, der freien Enzyklopädie

Als Korrelationsungleichungen werden eine Gruppe von mathematischen Ungleichungen bezeichnet, welche den Begriff der positiven Korrelation auf partiell geordnete Mengen (POSETs) und distributive Verbände übertragen. Sie haben darüber hinaus eine wahrscheinlichkeitstheoretische Interpretation und berühren das mathematische Teilgebiet der Theorie der 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 von der FKG-Ungleichungen wurden weitere ähnliche Ungleichungen gefunden, zum Beispiel die Holley-Ungleichung nach Richard Holley im Jahr 1974, oder die sehr allgemeine Vier-Funktionen-Ungleichung von Rudolf Ahlswede und David E. Daykin von 1978, aus der die anderen genannten Ungleichungen folgen.

Assoziierte Maße

Der Begriff des assoziierten Maßes wurde 1967 von J. D. Esary, Frank Proschan und D. W. Walkup[4] eingeführt. Wegen der Analogie zu positiven Korrelationen von Zufallsvariablen wird von manchen Autoren auch die Bezeichnung Maß mit positiven Korrelationen verwendet.

Ein endliches Maß auf , wobei ein halbgeordneter topologischer[5] Raum sei, heißt assoziiert, falls

für alle beschränkten, stetigen, monoton wachsenden Funktionen von nach gilt.

Die FKG-Ungleichung

Die FKG-Ungleichung, benannt nach C. M. Fortuin, J. Ginibre und P. W. Kasteleyn (1971), ist ursprünglich eine Korrelationsungleichung auf distributiven Verbänden. Sie ist ein fundamentales Werkzeug auf den Gebieten der statistischen Mechanik und der probabilistischen Kombinatorik (speziell auf dem Gebiet der Zufallsgraphen.) Sie besagt übertragen auf ein wahrscheinlichkeitstheoretisches Setting in etwa, dass wachsende Ereignisse miteinander positiv korreliert sind.

Formulierung für endliche distributive Verbände

Sei ein endlicher distributiver Verband, und ein Maß auf , welches

für alle , im Verband erfüllt. Diese Eigenschaft heißt auch Log-Supermodularität.

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

.

Ebenfalls positiv korreliert sind zwei Funktionen und , 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 ein abzählbarer kompakter metrischer Raum ist. In diesem Fall muss 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 -finite Maße auf der (überabzählbaren) Menge . In diesem Fall wird Log-Supermodularität eines Maßes über die Dichtefunktion (bezüglich irgendeines Produktmaßes auf ) definiert, welche für alle erfüllen muss:

.

Die Griffith-Ungleichung ist eine weitere Ungleichung von 1967, welche die gleiche Aussage macht wie die FKG-Ungleichung, jedoch andere Voraussetzungen hat und Anwendung auf dem Gebiet des Ising-Modells hat.[7]

Die Harris-Ungleichung

Die Harris-Ungleichung ist im Prinzip die FKG-Ungleichung für Produktmaße, benannt nach Theodore E. Harris, welcher sie 1960 beim Studium von Perkolationen in der Ebene gefunden hat.[8]

Wenn eine totalgeordnete Menge ist, dann ist die Log-Supermodularität automatisch für jedes Maß auf erfüllt.

Es gilt zum Beispiel, dass für jede Wahrscheinlichkeitsverteilung auf , und monoton wachsende quadratintegrierbaren Funktionen und

gilt. Dies folgt aus

(die Terme in den eckigen Klammern haben das jeweils gleiche Vorzeichen.)

Die Log-Supermodularität ist auch automatisch erfüllt, wenn der Verband ein Produkt totalgeordneter Verbände ist, , und ein Produktmaß auf . In der Anwendung ist häufig die (Produkt-)Verteilung von unabhängig und identisch verteilten Zufallsvariablen auf unabhängigen Kopien eines Wahrscheinlichkeitsraumes.

Sei eine endliche Indexmenge. Sei versehen mit der koordinatenweisen Ordnung und mit den Verbands-Operationen:

sei für alle , definiert über ,
sowie entsprechend über .

Mit diesen Operationen ist eine Boolesche Algebra.

Sei ein Wahrscheinlichkeitsmaß auf . Dann schreibt sich die FKG-Ungleichung

für alle monoton wachsenden für die die Erwartungswerte existieren, wobei den Erwartungswert bezüglich bezeichne.[9]

Ein Ereignis heißt entsprechend wachsend, wenn für alle mit . (Und ein Ereignis heißt fallend, wenn das Komplement wachsend ist.)

Sind und wachsende Ereignisse, so gilt

Ein Beweis der Harris-Ungleichung, der auf dem hier verwendeten Doppelintegral-Trick auf beruht, findet sich in Grimmett 1999.

Beispiele

Wabengitter mit zufällig eingefärbten Waben.

Man färbe zufällig jedes Hexagon des unendlichen Waben-Gitters schwarz jeweils stochastisch unabhängig voneinander mit Wahrscheinlichkeit und weiß mit Wahrscheinlichkeit . Seien vier (nicht notwendig verschiedene) solche Hexagone. Seien und die Ereignisse, dass es einen schwarzen Pfad von nach respektive von nach gibt. Dann besagt die FKG-Ungleichung, dass diese Ereignisse positive korreliert sind: . 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 ist die Existenz eines Hamilton-Zyklus negativ korreliert mit der 3-Färbbarkeit des Graphen, da die Wahrscheinlichkeit der Existenz eines Hamilton-Zyklus mit der Anzahl der belegten Verbindungen steigt (steigendes Ereignis), während die Wahrscheinlichkeit von letzterem fällt (fallendes Ereignis).

Die Holley-Ungleichung

Diese von Richard Holley 1974 entdeckte und gelegentlich als Holley-Ungleichung bezeichnete Ungleichung besagt: Seien und zwei strikt positive Verteilungen auf einem endlichen distributiven Verband , welche

für alle

erfüllen. Dann gilt

.

für alle monoton wachsende integrierbaren Funktionen auf . Dies ist gleichbedeutend damit, dass größer als bezüglich der gewöhnlichen stochastischen Ordnung ist. Thomas Liggett hat einen Beweis für Räume der Form , welcher auf der Kopplung zweier Markow-Ketten in stetiger Zeit mit und 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 versehen mit der koordinatenweisen Halbordnung. Für eine Verteilung auf ist folgende Eigenschaft oft leichter zu überprüfen als die Log-Supermodularität:

Fixiert man eine Koordinate und zwei Konfigurationen und in bezüglich der anderen Koordinaten, so dass for all , die auf bedingte Verteilung von gegeben ist stochastisch größer als die auf bedingte Verteilung von gegeben .

Erfüllt diese Eigenschaft, dann ist assoziiert.

Die Vier-Funktionen-Ungleichung

Die Vier-Funktionen-Ungleichung von Ahlswede and Daykin von 1978 lässt sich wie folgt formulieren: Seien nichtnegative reellwertige Funktionen auf , welche folgende Bedingung erfüllen:

für alle

Dann gilt für jedes log-supermodulare Maß auf ,

Es lässt sich zeigen, dass aus der Vier-Funktionen-Ungleichung Holleys Ungleichung folgt, aus der wiederum die 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. 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.