FKG неравенство

Неравенство корреляции

В математике неравенство Фортуина–Кастелейна–Жинибра (FKG) — это корреляционное неравенство, фундаментальный инструмент в статистической механике и вероятностной комбинаторике (особенно случайных графах и вероятностном методе ), созданный Сисом М. Фортуэном, Питером В. Кастелейном и Жаном Жинибрем  (1971). Неформально оно гласит, что во многих случайных системах возрастающие события положительно коррелируют, в то время как возрастающие и убывающие события отрицательно коррелируют. Оно было получено путем изучения модели случайного кластера .

Более ранняя версия для особого случая переменных iid , называемая неравенством Харриса , принадлежит Теодору Эдварду Харрису  (1960), см. ниже. Одним из обобщений неравенства FKG является неравенство Холли (1974) ниже, а еще более обобщённым является теорема Алсведе–Дэйкина о «четырех функциях» (1978) . Более того, она имеет тот же вывод, что и неравенства Гриффитса , но гипотезы различны.

Неравенство

Пусть — конечная дистрибутивная решетка , а μ — неотрицательная функция на ней, которая, как предполагается, удовлетворяет условию решетки ( FKG ) (иногда функция, удовлетворяющая этому условию, называется логсупермодулярной ), т.е. ${\displaystyle X}$

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

для всех x , y в решетке . ${\displaystyle X}$

Тогда неравенство FKG гласит, что для любых двух монотонно возрастающих функций ƒ и g на справедливо следующее неравенство положительной корреляции: ${\displaystyle X}$

${\displaystyle \left(\sum _{x\in X}f(x)g(x)\mu (x)\right)\left(\sum _{x\in X}\mu (x)\right)\geq \left(\sum _{x\in X}f(x)\mu (x)\right)\left(\sum _{x\in X}g(x)\mu (x)\right).}$

То же неравенство (положительная корреляция) справедливо, когда и ƒ , и g уменьшаются. Если один увеличивается, а другой уменьшается, то они отрицательно коррелируют, и указанное выше неравенство меняется на противоположное.

Подобные утверждения справедливы и в более общем случае, когда не обязательно конечна, даже не счетна. В этом случае μ должна быть конечной мерой, а условие решетки должно быть определено с использованием событий цилиндра ; см., например, раздел 2.2 работы Grimmett (1999). ${\displaystyle X}$

Для доказательств см. Fortuin, Kasteleyn & Ginibre (1971) или неравенство Alswede–Daykin (1978) . Также ниже приведен грубый набросок, принадлежащий Holley (1974), с использованием аргумента связи цепей Маркова .

Различия в терминологии

Условие решетки для μ также называется многомерной полной положительностью , а иногда и сильным условием FKG ; в старой литературе также используется термин ( мультипликативное ) условие FKG .

Свойство μ , заключающееся в том, что возрастающие функции положительно коррелируют, также называется наличием положительных ассоциаций или слабым условием FKG .

Таким образом, теорему FKG можно перефразировать так: «сильное условие FKG влечет слабое условие FKG».

Частный случай: неравенство Харриса

Если решетка полностью упорядочена , то условие решетки выполняется тривиально для любой меры μ . В случае, если мера μ равномерна, неравенство FKG является неравенством суммы Чебышева : если две возрастающие функции принимают значения и , то ${\displaystyle X}$ ${\displaystyle a_{1}\leq a_{2}\leq \cdots \leq a_{n}}$ ${\displaystyle b_{1}\leq b_{2}\leq \cdots \leq b_{n}}$

${\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}}.}$

В более общем случае для любой вероятностной меры μ и возрастающих функций ƒ и g , ${\displaystyle \mathbb {R} }$

${\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),}$

что следует непосредственно из

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

Условие решетки тривиально выполняется также, когда решетка является произведением полностью упорядоченных решеток, и является мерой произведения. Часто все факторы (и решетки, и меры) идентичны, т. е. μ является распределением вероятностей случайных величин iid . ${\displaystyle X=X_{1}\times \cdots \times X_{n}}$ ${\displaystyle \mu =\mu _{1}\otimes \cdots \otimes \mu _{n}}$

Неравенство FKG для случая меры произведения известно также как неравенство Харриса в честь Харриса (Harris 1960), который нашел и использовал его в своем исследовании перколяции на плоскости. Доказательство неравенства Харриса, которое использует указанный выше двойной интегральный трюк, можно найти, например, в разделе 2.2 Grimmett (1999). ${\displaystyle \mathbb {R} }$

Простые примеры

Типичным примером является следующее. Раскрасим каждый шестиугольник бесконечной сотовой решетки в черный цвет с вероятностью и в белый цвет с вероятностью независимо друг от друга. Пусть a, b, c, d — четыре шестиугольника, не обязательно различные. Пусть и — события, что существует черный путь из a в b и черный путь из c в d соответственно. Тогда неравенство Харриса гласит, что эти события положительно коррелируют: . Другими словами, предположение о наличии одного пути может только увеличить вероятность другого. ${\displaystyle p}$ ${\displaystyle 1-p}$ ${\displaystyle a\leftrightarrow b}$ ${\displaystyle c\leftrightarrow d}$ ${\displaystyle \Pr(a\leftrightarrow b,\ c\leftrightarrow d)\geq \Pr(a\leftrightarrow b)\Pr(c\leftrightarrow d)}$

Аналогично, если мы случайным образом раскрасим шестиугольники внутри ромбовидной доски из шестиугольников , то события, что есть черное пересечение с левой стороны доски на правую сторону, положительно коррелируют с наличием черного пересечение с верхней стороны на нижнюю. С другой стороны, наличие черного пересечение слева направо отрицательно коррелирует с наличием белого пересечение сверху вниз, поскольку первое является увеличивающимся событием (по количеству черноты), а второе — уменьшающимся. Фактически, при любой раскраске доски из шестиугольников происходит ровно одно из этих двух событий — вот почему гексагон является четко определенной игрой. ${\displaystyle n\times n}$

В случайном графе Эрдёша–Реньи существование гамильтонова цикла отрицательно коррелирует с 3-раскрашиваемостью графа , поскольку первое является возрастающим событием, а второе — убывающим.

Примеры из статистической механики

В статистической механике обычным источником мер, удовлетворяющих решеточному условию (и, следовательно, неравенству FKG), является следующий:

Если — упорядоченное множество (такое как ), а — конечный или бесконечный граф , то множество -значных конфигураций представляет собой частично упорядоченное множество , являющееся дистрибутивной решеткой. ${\displaystyle S}$ ${\displaystyle \{-1,+1\}}$ ${\displaystyle \Gamma }$ ${\displaystyle S^{\Gamma }}$ ${\displaystyle S}$

Теперь, если — субмодулярный потенциал (т.е. семейство функций ${\displaystyle \Phi }$

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

по одному для каждого конечного , так что каждый из них является субмодулярным ), то соответствующие гамильтонианы определяются как ${\displaystyle \Lambda \subset \Gamma }$ ${\displaystyle \Phi _{\Lambda }}$

${\displaystyle H_{\Lambda }(\varphi ):=\sum _{\Delta \cap \Lambda \not =\emptyset }\Phi _{\Delta }(\varphi ).}$

Если μ является экстремальной мерой Гиббса для этого гамильтониана на множестве конфигураций , то легко показать, что μ удовлетворяет решеточному условию, см. Sheffield (2005). ${\displaystyle \varphi }$

Ключевым примером является модель Изинга на графе . Пусть , называемые спинами, и . Возьмем следующий потенциал: ${\displaystyle \Gamma }$ ${\displaystyle S=\{-1,+1\}}$ ${\displaystyle \beta \in [0,\infty ]}$

${\displaystyle \Phi _{\Lambda }(\varphi )={\begin{cases}\beta 1_{\{\varphi (x)\not =\varphi (y)\}}&{\text{if }}\Lambda =\{x,y\}{\text{ is a pair of adjacent vertices of }}\Gamma ;\\0&{\text{otherwise.}}\end{cases}}}$

Субмодулярность легко проверить; интуитивно, взятие минимума или максимума из двух конфигураций имеет тенденцию уменьшать количество несогласованных спинов. Затем, в зависимости от графика и значения , может быть одна или несколько экстремальных мер Гиббса, см., например, Georgii, Häggström & Maes (2001) и Lyons (2000). ${\displaystyle \Gamma }$ ${\displaystyle \beta }$

Обобщение: неравенство Холли

Неравенство Холли , предложенное Ричардом Холли (1974), утверждает, что ожидания

${\displaystyle \langle f\rangle _{i}={\frac {\sum _{x\in X}f(x)\mu _{i}(x)}{\sum _{x\in X}\mu _{i}(x)}}}$

монотонно возрастающей функции ƒ на конечной дистрибутивной решетке относительно двух положительных функций μ ₁ , μ ₂ на решетке удовлетворяют условию ${\displaystyle X}$

${\displaystyle \langle f\rangle _{1}\geq \langle f\rangle _{2},}$

при условии, что функции удовлетворяют условию Холли ( критерию )

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

для всех x , y в решетке.

Чтобы восстановить неравенство FKG: Если μ удовлетворяет решеточному условию, а ƒ и g являются возрастающими функциями на , то μ ₁ ( x ) =  g ( x ) μ ( x ) и μ ₂ ( x ) =  μ ( x ) будут удовлетворять решеточному условию неравенства Холли. Тогда неравенство Холли утверждает, что ${\displaystyle X}$

${\displaystyle {\frac {\langle fg\rangle _{\mu }}{\langle g\rangle _{\mu }}}=\langle f\rangle _{1}\geq \langle f\rangle _{2}=\langle f\rangle _{\mu },}$

что является просто неравенством FKG.

Что касается FKG, неравенство Холли следует из неравенства Алсведе–Дэйкина .

Ослабление решеточного условия: монотонность

Рассмотрим обычный случай, когда является произведением для некоторого конечного множества . Легко видеть, что условие решетки на μ подразумевает следующую монотонность , которая имеет то достоинство, что ее часто легче проверить, чем условие решетки: ${\displaystyle X}$ ${\displaystyle \mathbb {R} ^{V}}$ ${\displaystyle V}$

Всякий раз, когда фиксируется вершина и две конфигурации ^{[ необходимо разъяснение ]} φ и ψ вне v таким образом, что для всех заданное μ - условное распределение φ ( v ) стохастически доминирует над заданным μ -условным распределением ψ ( v ) . ${\displaystyle v\in V}$ ${\displaystyle \varphi (w)\geq \psi (w)}$ ${\displaystyle w\not =v}$ ${\displaystyle \{\varphi (w):w\not =v\}}$ ${\displaystyle \{\psi (w):w\not =v\}}$

Теперь, если μ удовлетворяет этому свойству монотонности, этого уже достаточно для выполнения неравенства FKG (положительные ассоциации).

Вот грубый набросок доказательства, предложенный Холли (1974): начиная с любой начальной конфигурации ^{[ необходимо разъяснение ]} на , можно запустить простую цепь Маркова ( алгоритм Метрополиса ), которая использует независимые равномерные[0,1] случайные величины для обновления конфигурации на каждом шаге, так что цепь имеет уникальную стационарную меру, заданную μ . Монотонность μ подразумевает, что конфигурация на каждом шаге является монотонной функцией независимых переменных, следовательно, версия меры произведения Харриса подразумевает, что она имеет положительные ассоциации. Следовательно, предельная стационарная мера μ также обладает этим свойством. ${\displaystyle V}$

Свойство монотонности имеет естественную версию для двух мер, говоря, что μ ₁ условно поточечно доминирует μ ₂ . Снова легко видеть, что если μ ₁ и μ ₂ удовлетворяют условию решеточного типа неравенства Холли, то μ ₁ условно поточечно доминирует μ ₂ . С другой стороны, аргумент о связи цепей Маркова , аналогичный приведенному выше, но теперь без привлечения неравенства Харриса, показывает, что условное поточечное доминирование, по сути, подразумевает стохастическое доминирование . Стохастическое доминирование эквивалентно утверждению, что для всех возрастающих ƒ , таким образом, мы получаем доказательство неравенства Холли. (И, таким образом, также доказательство неравенства FKG, без использования неравенства Харриса.) ${\displaystyle \langle f\rangle _{1}\geq \langle f\rangle _{2}}$

Подробности см. в Holley (1974) и Georgii, Häggström & Maes (2001).

Смотрите также

• Неравенство Алсведе–Дэйкина
• неравенство XYZ
• неравенство БК

Ссылки

• Итон, Моррис Л. (1987), «Неравенство FKG и ассоциация», Лекции по темам в области вероятностных неравенств , Амстердам, стр. 111–151, ISBN 90-6196-316-8{{citation}}: CS1 maint: location missing publisher (link)
• Фишберн, ПК (2001) [1994], "Неравенство FKG", Энциклопедия математики , EMS Press
• Fortuin, CM; Kasteleyn, PW; Ginibre, J. (1971), "Корреляционные неравенства на некоторых частично упорядоченных множествах", Communications in Mathematical Physics , 22 (2): 89–103, Bibcode : 1971CMaPh..22...89F, doi : 10.1007/BF01651330, MR  0309498, S2CID  1011815
• Фридли, С.; Веленик, Ю. (2017). Статистическая механика решетчатых систем: конкретное математическое введение. Кембридж: Cambridge University Press. ISBN 9781107184824.
• Georgii, HO.; Häggström, O.; Maes, C. (2001), «Случайная геометрия равновесных фаз», Phase Transitions and Critical Phenomena , т. 18, Academic Press, Сан-Диего, Калифорния, стр. 1–142, arXiv : math/9905031 , doi :10.1016/S1062-7901(01)80008-2, ISBN 9780122203183, MR  2014387, S2CID  119137791
• Гримметт, Г. Р. (1999), Перколяция. Второе издание , Grundlehren der mathematischen Wissenschaften, vol. 321, Springer-Verlag, номер домена : 10.1007/978-3-662-03981-6, ISBN. 3-540-64902-6, МР  1707339
• Харрис, TE (1960), «Нижняя граница критической вероятности в определенном процессе перколяции», Математические труды Кембриджского философского общества , 56 (1): 13–20, Bibcode : 1960PCPS...56...13H, doi : 10.1017/S0305004100034241, MR  0115221, S2CID  122724783
• Холли, Р. (1974), «Замечания о неравенствах FKG», Сообщения по математической физике , 36 (3): 227–231, Bibcode : 1974CMaPh..36..227H, doi : 10.1007/BF01645980, MR  0341552, S2CID  73649690
• Lyons, R. (2000), «Фазовые переходы на неназываемых графах», J. Math. Phys. , 41 (3): 1099–1126, arXiv : math/9908177 , Bibcode : 2000JMP....41.1099L, doi : 10.1063/1.533179, MR  1757952, S2CID  10350129
• Шеффилд, С. (2005), "Случайные поверхности", Astérisque , 304 , arXiv : math/0304049 , Bibcode : 2003math......4049S, MR  2251117