Nerovnost FKG - FKG inequality

V matematice je Fortuin – Kasteleyn – Ginibre (FKG) nerovnost je korelace nerovnost, základní nástroj v EU statistická mechanika a pravděpodobnostní kombinatorika (zvláště náhodné grafy a pravděpodobnostní metoda ), kvůli Cees M. Fortuin, Pieter W. Kasteleyn, a Jean Ginibre  (1971 ). Neformálně to říká, že v mnoha náhodných systémech jsou rostoucí události pozitivně korelované, zatímco rostoucí a klesající událost jsou negativně korelované. Bylo získáno studiem model náhodného klastru.

Starší verze, pro zvláštní případ i.i.d. proměnné, tzv Harrisova nerovnost, je kvůli Theodore Edward Harris  (1960 ), viz níže. Jedním zobecněním nerovnosti FKG je Holley nerovnost (1974) níže a ještě další zobecnění je Ahlswede – Daykinova věta o „čtyřech funkcích“ (1978). Dále má stejný závěr jako Griffithovy nerovnosti, ale hypotézy jsou odlišné.

Nerovnost

Nechat ${displaystyle X}$ být konečný distribuční mříž, a μ nezáporná funkce, o které se předpokládá, že splňuje (FKG) mřížkový stav (někdy se nazývá funkce splňující tuto podmínku log supermodulární) tj.,

${displaystyle mu (xwedge y) mu (xvee y) geq mu (x) mu (y)}$

pro všechny X, y v mříži ${displaystyle X}$.

Nerovnost FKG pak říká, že pro libovolné dvě monotónně rostoucí funkce ƒ a G na ${displaystyle X}$, platí následující pozitivní korelační nerovnost:

${displaystyle left (sum _ {xin X} f (x) g (x) mu (x) ight) left (sum _ {xin X} mu (x) ight) geq left (sum _ {xin X} f (x ) mu (x) ight) left (součet _ {xin X} g (x) mu (x) ight).}$

Stejná nerovnost (pozitivní korelace) platí, když obě ƒ a G ubývají. Pokud jedna roste a druhá klesá, pak negativně korelují a výše uvedená nerovnost je obrácena.

Podobné výroky platí obecněji, když ${displaystyle X}$ není nutně konečný, ani započítatelný. V tom případě, μ musí být konečným měřítkem a mřížková podmínka musí být definována pomocí válec Události; viz např. část 2.2 Grimmett (1999).

Důkazy najdete v originále Fortuin, Kasteleyn a Ginibre (1971) nebo Ahlswede – Daykinova nerovnost (1978). Dále je uveden hrubý náčrt, kvůli Holley (1974), používat Markovův řetězec spojka argument.

Rozdíly v terminologii

Mřížková podmínka pro μ je také nazýván vícerozměrná celková pozitivita, a někdy silný stav FKG; termín (multiplikativní) Stav FKG je také používán ve starší literatuře.

Vlastnost μ že rostoucí funkce pozitivně korelují, se také nazývá mít pozitivní asociace, nebo slabý stav FKG.

Věta o FKG tedy může být přeformulována jako „podmínka silného FKG implikuje podmínku slabého FKG“.

Zvláštní případ: Harrisova nerovnost

Pokud mříž ${displaystyle X}$ je úplně objednané, pak je mřížková podmínka pro každé opatření triviálně splněna μ. V tomto případě je nerovnost FKG Čebyševova nerovnost součtu: pokud dvě rostoucí funkce nabývají hodnot ${displaystyle a_ {1} leq a_ {2} leq cdots leq a_ {n}}$ a ${displaystyle b_ {1} leq b_ {2} leq cdots leq b_ {n}}$, pak (můžeme předpokládat, že opatření μ je jednotný)

${displaystyle {frac {a_ {1} b_ {1} + cdots + a_ {n} b_ {n}} {n}} geq {frac {a_ {1} + cdots + a_ {n}} {n}}; {frac {b_ {1} + cdots + b_ {n}} {n}}.}$

Obecněji pro jakékoli měřítko pravděpodobnosti μ na ${displaystyle mathbb {R}}$ a zvyšování funkcí ƒ a G,

${displaystyle int _ {mathbb {R}} f (x) g (x), dmu (x) geq int _ {mathbb {R}} f (x), dmu (x), int _ {mathbb {R}} g (x), dmu (x),}$

který bezprostředně vyplývá z

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

Podmínka mřížky je triviálně splněna, i když je mřížka produktem zcela uspořádaných mřížek, ${displaystyle X = X_ {1} jsou cdots jsou X_ {n}}$, a ${displaystyle mu = mu _ {1} další cdoty další časy _ (n)}$ je míra produktu. Všechny faktory (mřížky i míry) jsou často totožné, tj. μ je rozdělení pravděpodobnosti i.i.d. náhodné proměnné.

Nerovnost FKG pro případ míry produktu je známá také jako Harrisova nerovnost po Harris (Harris 1960 ), který jej našel a použil ve své studii o perkolace v letadle. Důkaz Harrisovy nerovnosti, který používá výše uvedený dvojitý integrální trik ${displaystyle mathbb {R}}$ lze nalézt např. v oddíle 2.2 Grimmett (1999).

Jednoduché příklady

Typickým příkladem je následující. Vybarvěte každý šestiúhelník nekonečna voštinová mříž černá s pravděpodobností ${displaystyle p}$ a bílé s pravděpodobností ${displaystyle 1-p}$, nezávisle na sobě. Nechat abeceda být čtyři šestiúhelníky, nemusí být nutně odlišné. Nechat ${displaystyle aleftrightarrow b}$ a ${displaystyle cleftrightarrow d}$ být událostmi, ze kterých vede černá cesta A na ba černá cesta z C na d, resp. Harrisova nerovnost pak říká, že tyto události pozitivně korelují: ${displaystyle Pr (aleftrightarrow b, cleftrightarrow d) geq Pr (aleftrightarrow b) Pr (cleftrightarrow d)}$. Jinými slovy, předpokládání přítomnosti jedné cesty může pouze zvýšit pravděpodobnost druhé.

Podobně, pokud náhodně vybarvujeme šestiúhelníky uvnitř ${displaystyle n imes n}$ ve tvaru kosočtverce šestihranná deska, potom události, u nichž dochází k černému přechodu z levé strany desky na pravou stranu, pozitivně korelují s černým křížením z horní strany na spodní část. Na druhou stranu mít křížení zleva doprava doprava negativně koreluje s přechodem shora dolů, protože první je rostoucí událost (v množství temnoty), zatímco druhá klesá. Ve skutečnosti se při jakémkoli vybarvení hexadecimální desky stane přesně jedna z těchto dvou událostí - proto je hex přesně definovaná hra.

V Erdős – Rényi náhodný graf, existence a Hamiltonovský cyklus je negativně korelován s 3-barvitelnost grafu, protože první je rostoucí událost, zatímco druhá klesá.

Příklady ze statistické mechaniky

Ve statistické mechanice je obvyklým zdrojem měr, které splňují podmínku mřížky (a tedy nerovnost FKG), následující:

Li ${displaystyle S}$ je objednaná sada (např ${displaystyle {-1, + 1}}$), a ${displaystyle Gamma}$ je konečný nebo nekonečný graf, pak sada ${displaystyle S ^ {Gamma}}$ z ${displaystyle S}$-hodnotové konfigurace je a poset to je distribuční mříž.

Teď když ${displaystyle Phi}$ je submodulární potenciál (tj. skupina funkcí

${displaystyle Phi _ {Lambda}: S ^ {Lambda} longrightarrow mathbb {R} cup {infty},}$

jeden pro každou konečnou ${displaystyle Lambda podmnožina Gamma}$, tak, že každý ${displaystyle Phi _ {Lambda}}$ je submodulární ), pak jeden definuje odpovídající Hamiltonians tak jako

${displaystyle H_ {Lambda} (varphi): = součet _ {Delta cap Lambda ot = emptyset} Phi _ {Delta} (varphi).}$

Li μ je extrémní Gibbsova míra pro tento hamiltonián na množině konfigurací ${displaystyle varphi}$, pak je snadné to ukázat μ splňuje podmínku mřížky, viz Sheffield (2005).

Klíčovým příkladem je Isingův model na grafu ${displaystyle Gamma}$. Nechat ${displaystyle S = {- 1, + 1}}$, zvané točení, a ${displaystyle eta in [0, infty]}$. Využijte následující potenciál:

${displaystyle Phi _ {Lambda} (varphi) = {egin {cases} eta 1 _ {{varphi (x) ot = varphi (y)}} & {ext {if}} Lambda = {x, y} {ext {is dvojice sousedních vrcholů}} Gama; 0 & {ext {jinak.}} konec {případů}}}$

Submodularitu lze snadno zkontrolovat; intuitivně má minimální nebo maximální hodnota dvou konfigurací tendenci snižovat počet nesouhlasných otočení. Poté, v závislosti na grafu ${displaystyle Gamma}$ a hodnota ${displaystyle eta}$, mohlo by existovat jedno nebo více extrémních Gibbsových opatření, viz např. Georgii, Häggström & Maes (2001) a Lyons (2000).

Zevšeobecnění: Holleyova nerovnost

The Holleyova nerovnost, kvůli Richardu Holleyovi (1974 ), uvádí, že očekávání

${displaystyle langle fangle _ {i} = {frac {sum _ {xin X} f (x) mu _ {i} (x)} {sum _ {xin X} mu _ {i} (x)}}}$

monotónně rostoucí funkce ƒ na konečnou distribuční mříž ${displaystyle X}$ s ohledem na dvě pozitivní funkce μ₁, μ₂ na mřížce splňují podmínku

${displaystyle langle fangle _ {1} geq langle fangle _ {2},}$

za předpokladu, že funkce splňují Holleyův stav (kritérium)

${displaystyle mu _ {2} (xwedge y) mu _ {1} (xvee y) geq mu _ {1} (x) mu _ {2} (y)}$

pro všechny X, y v mříži.

Chcete-li obnovit Nerovnost FKG: Pokud μ splňuje podmínku mřížky a ƒ a G zvyšují funkce na ${displaystyle X}$, pak μ₁(X) = G(X)μ(X) a μ₂(X) = μ(X) splní podmínku typu mřížky Holleyovy nerovnosti. Pak to říká Holleyova nerovnost

${displaystyle {frac {langle fgangle _ {mu}} {langle gangle _ {mu}}} = langle fangle _ {1} geq langle fangle _ {2} = langle fangle _ {mu},}$

což je jen nerovnost FKG.

Pokud jde o FKG, Holleyova nerovnost vyplývá z Nerovnost Ahlswede – Daykin.

Oslabení mřížkové podmínky: monotónnost

Zvažte obvyklý případ ${displaystyle X}$ být produktem ${displaystyle mathbb {R} ^ {V}}$ pro nějakou konečnou množinu ${displaystyle V}$. Podmínka mřížky zapnuta μ lze snadno vidět z toho vyplývajícího monotónnost, který má tu ctnost, že je často snazší zkontrolovat než mřížkový stav:

Kdykoli člověk opraví vrchol ${displaystyle vin V}$ a dvě konfigurace φ a ψ mimo proti takhle ${displaystyle varphi (w) geq psi (w)}$ pro všechny ${displaystyle wot = v}$, μ-podmínečná distribuce φ(proti) daný ${displaystyle {varphi (w): wot = v}}$ stochasticky dominuje the μ-podmínečná distribuce ψ(proti) daný ${displaystyle {psi (w): wot = v}}$.

Teď když μ splňuje tuto vlastnost monotónnosti, která již stačí k tomu, aby se nerovnost FKG (pozitivní asociace) zachovala.

Zde je hrubý náčrtek důkazu kvůli Holley (1974): počínaje jakoukoli počáteční konfigurací dne ${displaystyle V}$, lze spustit jednoduchý Markovův řetězec (dále jen Algoritmus metropole ), který používá nezávislé Uniform [0,1] náhodné proměnné k aktualizaci konfigurace v každém kroku, takže řetězec má jedinečnou stacionární míru, danou μ. Monotónnost μ znamená, že konfigurace v každém kroku je monotónní funkcí nezávislých proměnných, tedy verze produktu Harris znamená, že má pozitivní asociace. Proto omezující stacionární opatření μ má také tuto vlastnost.

Vlastnost monotonicity má přirozenou verzi pro dvě míry, říká to μ₁ podmíněně bodově dominuje μ₂. Je opět snadné vidět, že pokud μ₁ a μ₂ splňují podmínku mřížového typu Holleyova nerovnost, pak μ₁ podmíněně bodově dominuje μ₂. Na druhou stranu markovský řetězec spojka argument podobný výše uvedenému, ale nyní, aniž bychom se dovolávali Harrisovy nerovnosti, ukazuje, že podmíněná bodová nadvláda ve skutečnosti znamená stochasticky nadvláda. Stochastická nadvláda se rovná tomu, že se to říká ${displaystyle langle fangle _ {1} geq langle fangle _ {2}}$ pro všechny rostoucí ƒ, tak dostaneme důkaz Holleyovy nerovnosti. (A tedy také důkaz nerovnosti FKG bez použití Harrisovy nerovnosti.)

Vidět Holley (1974) a Georgii, Häggström & Maes (2001) pro detaily.

Viz také

• Nerovnost Ahlswede – Daykin

Reference

• Fishburn, P.C. (2001) [1994], „Nerovnost FKG“, Encyclopedia of Mathematics, Stiskněte EMS
• Fortuin, C. M .; Kasteleyn, P. W .; Ginibre, J. (1971), "Korelační nerovnosti na některých částečně uspořádaných množinách", Komunikace v matematické fyzice, 22 (2): 89–103, Bibcode:1971CMaPh..22 ... 89F, doi:10.1007 / BF01651330, PAN  0309498, S2CID  1011815
• Friedli, S .; Velenik, Y. (2017). Statistická mechanika mřížových systémů: konkrétní matematický úvod. Cambridge: Cambridge University Press. ISBN  9781107184824.
• Georgii, H-O .; Häggström, O .; Maes, C. (2001), „Náhodná geometrie rovnovážných fází“, Fázové přechody a kritické jevy, 18„Academic Press, San Diego, CA, s. 1–142, arXiv:matematika / 9905031, doi:10.1016 / S1062-7901 (01) 80008-2, ISBN  9780122203183, PAN  2014387, S2CID  119137791
• Grimmett, G. R. (1999), Perkolace. Druhé vydáníGrundlehren der mathematischen Wissenschaften, 321, Springer-Verlag, doi:10.1007/978-3-662-03981-6, ISBN  3-540-64902-6, PAN  1707339
• Harris, T. E. (1960), „Dolní mez kritické pravděpodobnosti v určité perkolaci“, Sborník Cambridge Philosophical Society, 56 (1): 13–20, Bibcode:1960PCPS ... 56 ... 13H, doi:10.1017 / S0305004100034241, PAN  0115221
• Holley, R. (1974), „Poznámky k nerovnostem FKG“, Komunikace v matematické fyzice, 36 (3): 227–231, Bibcode:1974CMaPh..36..227H, doi:10.1007 / BF01645980, PAN  0341552, S2CID  73649690
• Lyons, R. (2000), „Fázové přechody na nezměnitelných grafech“, J. Math. Phys., 41 (3): 1099–1126, arXiv:matematika / 9908177, Bibcode:2000JMP .... 41,1099L, doi:10.1063/1.533179, PAN  1757952, S2CID  10350129
• Sheffield, S. (2005), „Náhodné povrchy“, Astérisque, 304, arXiv:matematika / 0304049, Bibcode:2003math ...... 4049S, PAN  2251117