ФКГ неравенство

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

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

Неравенство

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

\mu (x\wedge y)\mu (x\vee y)\geq \mu (x)\mu (y)

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

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

\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 уменьшаются. Если одно увеличивается, а другое уменьшается, то они отрицательно коррелируют, и вышеуказанное неравенство меняется на противоположное.

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

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

Вариации в терминологии

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

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

Таким образом, теорему ФКГ можно перефразировать так: «Из сильного условия ФКГ следует слабое условие ФКГ».

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

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

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

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

\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),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\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}}

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

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

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

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

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

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

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

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

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

Чтобы восстановить неравенство ФКГ : если µ удовлетворяет условию решетки и ƒ и g являются возрастающими функциями на $X$ , то µ ₁ ( x ) = g ( x ) µ ( x ) и µ ₂ ( x ) = µ ( x ) будут удовлетворять условию решеточного типа неравенства Холли. Тогда неравенство Холли утверждает, что

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

это и есть неравенство ФКГ.

Что касается ФКГ, то неравенство Холли следует из неравенства Альсведе–Дайкина .

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

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

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

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

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

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

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

См. также

Ссылки

Итон, Моррис Л. (1987), «Неравенство и ассоциация FKG», Лекции по темам вероятностных неравенств , Амстердам, стр. 111–151, ISBN 90-6196-316-8 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
Фишберн, ПК (2001) [1994], «Неравенство ФКГ» , Энциклопедия математики , EMS Press
Фортуин, CM; Кастелейн, П.В.; Джинибре, Дж. (1971), «Корреляционные неравенства на некоторых частично упорядоченных множествах» , Communications in Mathematical Physics , 22 (2): 89–103, Бибкод : 1971CMaPh..22...89F , doi : 10.1007/BF01651330 , MR 0309498 , S2CID 1011815
Фридли, С.; Веленик, Ю. (2017). Статистическая механика решетчатых систем: конкретное математическое введение . Кембридж: Издательство Кембриджского университета. ISBN 9781107184824 .
Георгий, ГО.; Хэггстрем, О.; Мэйс, К. (2001), «Случайная геометрия равновесных фаз», Фазовые переходы и критические явления , том. 18, Academic Press, Сан-Диего, Калифорния, стр. 1–142, arXiv : math/9905031 , doi : 10.1016/S1062-7901(01)80008-2 , ISBN 9780122203183 , МР 2014387 , S2CID 119137791
Гриметт, Г.Р. (1999), Перколяция. Издание второе , Основы математических наук, т. 1, с. 321, Springer-Verlag, номер домена : 10.1007/978-3-662-03981-6 , ISBN. 3-540-64902-6 , МР 1707339
Харрис, TE (1960), «Нижняя граница критической вероятности в определенном процессе перколяции», Mathematical Proceedings of the Cambridge Philosophical Society , 56 (1): 13–20, Bibcode : 1960PCPS...56...13H , doi : 10.1017/S0305004100034241 , MR 0115221 , S2CID 122724783
Холли, Р. (1974), «Замечания о неравенствах ФКГ» , Communications in Mathematical Physics , 36 (3): 227–231, Bibcode : 1974CMaPh..36..227H , doi : 10.1007/BF01645980 , MR 0341552 , S2CID 73649690
Лайонс, Р. (2000), «Фазовые переходы на безымянных графах», J. Math. Физ. , 41 (3): 1099–1126, arXiv : math/9908177 , Bibcode : 2000JMP....41.1099L , doi : 10.1063/1.533179 , MR 1757952 , S2CID 10350129
Шеффилд, С. (2005), «Случайные поверхности», Asterisque , 304 , arXiv : math/0304049 , Bibcode : 2003math......4049S , MR 2251117