Twierdzenie Hammersleya-Clifforda

Hammersleya -Clifforda jest wynikiem teorii prawdopodobieństwa , statystyki matematycznej i mechaniki statystycznej , który daje konieczne i wystarczające warunki, w których ściśle dodatni rozkład prawdopodobieństwa (zdarzeń w przestrzeni prawdopodobieństwa ) ^{[ wymagane wyjaśnienie ]} może być przedstawiony jako zdarzenia generowane przez Sieć Markowa (znana również jako pole losowe Markowa ). Jest to podstawowe twierdzenie pól losowych . Stwierdza, że rozkład prawdopodobieństwa, który ma ściśle dodatnią masę lub gęstość , spełnia jedną z właściwości Markowa w odniesieniu do nieskierowanego wykresu G wtedy i tylko wtedy, gdy jest polem losowym Gibbsa , to znaczy, że jego gęstość można rozłożyć na czynniki przez kliki ( lub kompletne podgrafy ) wykresu.

Związek między polami losowymi Markowa i Gibbsa został zapoczątkowany przez Rolanda Dobrushina i Franka Spitzera w kontekście mechaniki statystycznej . Twierdzenie nosi imię Johna Hammersleya i Petera Clifforda, którzy udowodnili równoważność w niepublikowanym artykule w 1971 r. Prostsze dowody wykorzystujące zasadę włączenia-wyłączenia zostały podane niezależnie przez Geoffreya Grimmetta , Prestona i Shermana w 1973 r., Z dalszym dowodem Juliana Besaga w 1974 roku.

Zarys dowodu

Prosta sieć Markowa do wykazania, że dowolne pole losowe Gibbsa spełnia każdą właściwość Markowa.

własność Markowa, jest trywialną sprawą . Jako przykład tego faktu, patrz:

Na obrazku po prawej pole losowe Gibbsa nad podanym wykresem ma postać ${\ Displaystyle \ Pr (A, B, C, D, E, F) \ propto f_ {1} (A, B, D) f_ {2} (A, C, D) f_ {3 }(C,D,F)f_{4}(C,E,F)}$ . $B \ perp E, F | C, D}$ zmienne są $ustalone$ , to globalna właściwość Markowa wymaga, $aby$ ${\ displaystyle C, D}$ (patrz warunkowa niezależność ), ponieważ do tworzy barierę między ${\ Displaystyle A, B}$ i ${\ displaystyle E, F}$ .

ze $stałą$ , $ZA , do {\ displaystyle$ i ${\ Displaystyle \ Pr (A, B, E, F | C = c ,D=d)\propto [f_{1}(A,B,d)f_{2}(A,c,d)]\cdot [f_{3}(c,d,F)f_{4}( c,E,F)]=g_{1}(A,B)g_{2}(E,F)}$ gdzie ${\ Displaystyle g_ {1} (A, B) = f_ {1} (A, B, d) f_ {2} (A, c, re)}$ i ${\ Displaystyle g_ {2} (E, F) = f_ {3} (c, d, F) f_ {4} (c, E, F)}$ . Oznacza to, że ${\ Displaystyle A, B \ sprawca E, F | C, D}$ .

Aby ustalić, że każdy dodatni rozkład prawdopodobieństwa, który spełnia lokalną własność Markowa, jest również polem losowym Gibbsa, należy udowodnić następujący lemat, który zapewnia środki do łączenia różnych faktoryzacji:

Lemat 1 zapewnia środki do łączenia faktoryzacji, jak pokazano na tym diagramie. Zwróć uwagę, że na tym obrazie nakładanie się zestawów jest ignorowane.

Lemat 1

Niech ${\ displaystyle U}$ oznacza zbiór wszystkich rozważanych zmiennych losowych i niech ${\ Displaystyle \ Theta, \ Phi _ {1}, \ Phi _ { 2}, \ kropki, \ Phi _ {n} \ subseteq U}$ i ${\ Displaystyle \ Psi _ {1}, \ Psi _ {2}, \ kropki, \ Psi _{m}\subseteq U}$ oznaczają dowolne zestawy zmiennych. (Tutaj, biorąc pod uwagę dowolny zestaw zmiennych , $}$ $X$ będzie również oznaczać dowolne przypisanie do zmiennych z ${\ displaystyle X}$ )

Jeśli

${\ Displaystyle \ Pr (U) = f (\ Theta) \ prod _ { i=1}^{n}g_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j})}$

dla funkcji ${\ Displaystyle f, g_ {1}, g_ {2}, \ kropki g_ {n}}$ i ${\ Displaystyle h_ {1},h_{2},\dots ,h_{m}}$ , to istnieją funkcje ${\ Displaystyle h'_ {1}, h'_ {2}, \ kropki, h'_ {m}}$ $Displaystyle g'_ {1} ,g'_{2},\kropki ,g'_{n}}$ sol takie, że

${\ Displaystyle \ Pr (U) = {\ bigg (} \ prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n }g'_{i}(\Phi _{i}){\bigg )}}$

Innymi słowy, ${\ Displaystyle \ prod _ {j = 1} ^ {m} h_ {j} (\ Psi _ {j})$ } ${\ Displaystyle f (\ Theta)}$ .

Dowód lematu 1

$\ prod _ {j = 1} ^ {m} h_ {j} (\ Psi _ {j})}$ Displaystyle jako szablon do dalszego rozkładu na czynniki ${\ Displaystyle f (\ Theta)}$ , wszystkie zmienne poza ${\ Displaystyle \ Theta}$ muszą zostać naprawione. W tym celu niech będzie dowolnym ustalonym przypisaniem do zmiennych z ${\ Displaystyle {\ bar {\ theta}}}$ ${\ Displaystyle U \ setminus \ Theta}$ (zmienne nie w ${\ Displaystyle \ Theta}$ ). Dla dowolnego zestawu zmiennych niech oznaczają przypisanie $\ bar {\ theta}} [X]}$ ${$ $\ Displaystyle {\ bar {\ theta}} }$ ograniczone do zmiennych z (zmienne z $\ setminus \ Theta}$ $Displaystyle X$ , wyłączając zmienne z ${\ displaystyle \ Theta}$ ).

${\ Displaystyle g_ {1} (\ Phi _ {1}), g_ {2} (\ Phi _ {2}), ..., g_ {n} (\ Phi _ {$ , aby rozłożyć tylko $na$ inne muszą zostać uznane za dyskusyjne dla zmiennych z ${\ displaystyle \ Theta}$ . Aby to zrobić, faktoryzacja

${\ Displaystyle \ Pr (U) = f (\ Theta) \ prod _ {i = 1} ^ {n} g_ {i} (\ Phi _ {i})}$

zostanie ponownie wyrażony jako

${\ Displaystyle \ Pr (U) = {\ bigg (} f (\ Theta) \ prod _ {i = 1} ^ {n} g_ {i} (\ Phi _ {i} \ cap \Theta ,{\bar {\theta}}[\Phi _{i}]){\bigg )}{\bigg (}\prod _{i=1}^{n}{\frac {g_{i} (\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta,{\bar {\theta}}[\Phi _{i}])}}{\bigg)} }$

Dla każdego ${\ Displaystyle i = 1,2, ..., n}$ $\ Phi _ {i} \ czapka \ Theta , {\ bar {\ theta}} [\ Phi _ {i}]}}$ , jest ${\ Displaystyle g_ {i} (\ Phi _ {i})}$ gdzie wszystkie zmienne poza ${\ Displaystyle \ Theta}$ zostały ustalone na wartości określone przez ${\ Displaystyle {\ bar {\ theta}}}$ .

Niech ${\ Displaystyle f '(\ Theta) = f (\ Theta) \ prod _ { i=1}^{n}g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Fi _{i}])}$ g ${\ Displaystyle g'_ {i} (\ Phi _ {i}) = {\ Frac {g_ {i} (\ Phi _ {i} })}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])}}} dla$ każdego ${\ Displaystyle i = 1,2, \ kropki, n}$ tak

${\ Displaystyle \ Pr (U) = f '(\ Theta) \ prod _{i=1}^{n}g'_{i}(\Phi _{i})=\prod _{j=1}^{m}h_{j}(\Psi _{j}) }$

Najważniejsze jest to, że ${\ Displaystyle g'_ {i} (\ Phi _ {i})={\frac {g_{i}(\Phi _{i})}{g_{i}(\Phi _{i}\cap \Theta ,{\bar {\theta }}[\Phi _ {i}])}}} = 1}$ , gdy wartości przypisane do ${\ Displaystyle \ Phi _ {i}}$ $Φ$ $i} (\ Phi _ {i})}$ ja ) " znikają” ${\ bar {\ theta}}}$ gdy wszystkie zmienne, których nie ma , są ustalane na wartości z $Displaystyle$ .

Naprawianie wszystkich zmiennych nie w ${\ Displaystyle \ Theta}$ do wartości z daje ${\ Displaystyle {\ bar {\ theta}}}$

${\ Displaystyle \ Pr (\ Theta, {\ bar {\ theta}}) = f' (\ Theta) \ prod _ {i = 1} ^ {n} g'_ {i} (\ Phi _ { i}\cap \Theta ,{\bar {\theta }}[\Phi _{i}])=\prod _{j=1}^{m}h_{j}(\Psi _{j}\cap \Theta ,{\bar {\theta}}[\Psi _{j}])}$

ponieważ ${\ Displaystyle g'_ {i} (\ Phi _ {i} \ czapka \ Theta, {\ bar {\ theta}} [\ fi _{i}])=1}$ ,

${\ Displaystyle f '(\ Theta) = \ prod _ {j = 1} ^ {m} h_ { j}(\Psi_{j}\cap \Theta,{\bar {\theta}}[\Psi_{j}])}$

Pozwalając ${\ Displaystyle h'_ {j} (\ Theta \ cap \ Psi _ {j}) = h_ { j}(\Psi _{j}\cap \Theta ,{\bar {\theta }}[\Psi _{j}])}$ daje:

${\ Displaystyle f '(\ Theta) = \ prod _ {j = 1} ^ {m} h'_ {j} (\ Theta \cap \Psi _{j})}$ co ostatecznie daje:

${\ Displaystyle \ Pr (U) = {\ bigg (} \ prod _{j=1}^{m}h'_{j}(\Theta \cap \Psi _{j}){\bigg )}{\bigg (}\prod _{i=1}^{n }g'_{i}(\Phi _{i}){\bigg )}}$

Klika utworzona przez wierzchołki ,

i

{\ Displaystyle x_ {2}}

{\ Displaystyle \ {x_ {1} \} \ kubek \ częściowe x_ {1}}

3

Displaystyle x_ {3}}

przecięciem ,

{\ Displaystyle \ {x_ {2} \} \ kubek \ częściowe x_ {2}}

i

{\ Displaystyle \ {x_ {3} \} \ kubek \ częściowe x_ {3}}

.

Lemat 1 zapewnia sposób łączenia dwóch różnych rozkładów na czynniki ${\ Displaystyle \ Pr (U)}$ . Lokalna właściwość Markowa implikuje, że dla dowolnej zmiennej losowej istnieją takie czynniki i $}$ $\ displaystyle f_ {-x$ $U}$ jak To: