Teorema de Hammersley-Clifford

La teorema de Hammersley-Clifford és un resultat de la teoria de la provabilitat, l'estadística matemàtica i la mecànica estadística que establix les condicions necessàries i suficients baix les quals una distribució de provabilitat estrictament positiva pot representar-se com a events generats per una ret de Markov (també coneguda com camp aleatori de Markov). És la teorema fonamental dels camps aleatoris. Establix que una distribució de provabilitat que té una massa estrictament positiva o densitat estrictament positiva satisfà una de les propietats de Markov sobre un grafo no dirigit G si i solament si és un Camp aleatori de Gibbs, és dir, la seua densitat pot factorizarse sobre els cliques (o subgrafos complets) del grafo.

La relació entre els camps aleatoris de Markov i Gibbs va ser iniciada per Roland Dobrushin i Frank Spitzer en el context de la mecànica estadística. La teorema du el nom de John Hammersley i Peter Clifford, els qui varen demostrar l'equivalència en un artícul inèdit en 1971. Geoffrey Grimmett va proporcionar de forma independent proves més senzilles utilisant el principi d'inclusió-exclusió. Preston i Sherman en 1973, en una prova adicional de Julian Besag en 1974.

Esquema de la demostració

Archiu:A simple Markov network.png

Una ret de Markov simple per a demostrar que qualsevol camp aleatori de Gibbs satisfà totes les propietats de Markov.

És trivial demostrar que un camp aleatori de Gibbs satisfà totes les propietats de Markov. Com a eixemple d'este fet, vore lo següent:

En l'image de la dreta, un camp aleatori de Gibbs sobre el gràfic proporcionat té la forma $\mathrm{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)$. Si les variables $C$ i $D$ són fixes, llavors la propietat global de Markov requerix que: $A,B\perp E,F|C,D$ (vore independència condicional), ya que $C,D$ formen una barrera entre $A,B$ i $E,F$.

En $C$ i $D$ constants, $\mathrm{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)$ a on $g_1(A,B)=f_1(A,B,d)f_2(A,c,d)$ i $g_2(E,F)=f_3(c,d,F)f_4(c,E,F)$. Açò implica que $A,B\perp E,F|C,D$.

Per a establir que tota distribució de provabilitat positiva que satisfaça la propietat local de Markov és també un camp aleatori de Gibbs, és necessari demostrar el següent lema, que proporciona un mig per a combinar diferents factorización:

Archiu:Merging two factorizations of a positive mass function.png

El lema 1 proporciona un mig per a combinar factorización, com es mostra en este diagrama. Observe's que en esta image s'ignora la superposició entre conjunts.

Lema 1

Siga $U$ el conjunt de totes les variables aleatòries considerades, i siguen $\Theta ,{\Phi }_1,{\Phi }_2,\dots ,{\Phi }_n\subseteq U$ i ${\Psi }_1,{\Psi }_2,\dots ,{\Psi }_m\subseteq U$ conjunts arbitraris de variables. (Ací, donat un conjunt arbitrari de variables $X$, $X$ també denotarà una assignació arbitrària a les variables de $X$).

Si

$\mathrm{Pr}(U)=f(\Theta )\prod _{i=1}^n{g}_i({\Phi }_i)=\prod _{j=1}^m{h}_j({\Psi }_j)$

per a les funcions $f,g_1,g_2,\dots g_n$ i $h_1,h_2,\dots ,h_m$, llavors existixen funcions $h{\text{'}}_1,h{\text{'}}_2,\dots ,h{\text{'}}_m$ i $g{\text{'}}_1,g{\text{'}}_2,\dots ,g{\text{'}}_n$ tals que

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

En atres paraules, $\prod _{j=1}^m{h}_j({\Psi }_j)$ proporciona una plantilla per a la factorización adicional de $f(\Theta )$.

Demostració del Lema 1

Per a utilisar $\prod _{j=1}^m{h}_j({\Psi }_j)$ com a plantilla per a factorizar encara més $f(\Theta )$, és necessari fixar totes les variables fòra de $\Theta$. Per a això, siga $\overline{\theta }$ una assignació fixa arbitrària a les variables de $U\setminus \Theta$ (les variables que no estan en $\Theta$). Per a un conjunt arbitrari de variables $X$, siga $\overline{\theta }[X]$ l'assignació $\overline{\theta }$ restringida a les variables de $X\setminus \Theta$ (les variables de $X$, excloent les variables de $\Theta$).

Ademés, per a factorizar sol $f(\Theta )$, els atres factors $g_1({\Phi }_1),g_2({\Phi }_2),\mathrm{...},g_n({\Phi }_n)$ deuen quedar sense efecte per a les variables de $\Theta$. Per a això, la factorización

$\mathrm{Pr}(U)=f(\Theta )\prod _{i=1}^n{g}_i({\Phi }_i)$

es reexpresará com

$\mathrm{Pr}(U)=(f(\Theta )\prod _{i=1}^n{g}_i({\Phi }_i\cap Theta,\overline{\theta }[{\Phi }_i]))\left(\prod _{i=1}^n\frac{g_i({\Phi }_i)}{g_i({\Phi }_i\cap \Theta ,\overline{\theta }[{\Phi }_i])}\right)$

Per a cada $i=1,2,\mathrm{...},n$: $g_i({\Phi }_i\cap \Theta ,\overline{\theta }[{\Phi }_i])$ és $g_i({\Phi }_i)$, a on totes les variables fòra de $\Theta$ s'han fixat en els valors prescrits per $\overline{\theta }$.

Siga $f^{\prime }(\Theta )=f(\Theta )\prod _{i=1}^n{g}_i({\Phi }_i\cap \Theta ,\overline{\theta }[{\Phi }_i])$ i $g{\text{'}}_i({\Phi }_i)=\frac{g_i({\Phi }_i)}{g_i({\Phi }_i\cap \Theta ,\overline{\theta }[{\Phi }_i])}$ per a cada $i=1,2,\dots ,n$, de modo que

$\mathrm{Pr}(U)=f^{\prime }(\Theta )\prod _{i=1}^{n}g{\text{'}}_i({\Phi }_i)=\prod _{j=1}^m{h}_j({\Psi }_j)$

Lo més important és que $g{\text{'}}_i({\Phi }_i)=\frac{g_i({\Phi }_i)}{g_i({\Phi }_i\cap \Theta ,\overline{\theta }[{\Phi }_i])}=1$ quan els valors assignats a ${\Phi }_i$ no entren en conflicte en els valors prescrits per $\overline{\theta }$, fent que $g{\text{'}}_i({\Phi }_i)$ «desaparega» quan totes les variables que no estan en $\Theta$ es fixen en els valors de $\overline{\theta }$.

Fixar totes les variables que no estan en $\Theta$ en els valors de $\overline{\theta }$ dona

$\mathrm{Pr}(\Theta ,\overline{\theta })=f^{\prime }(\Theta )\prod _{i=1}^{n}g{\text{'}}_i({\Phi }_i\cap \Theta ,\overline{\theta }[{\Phi }_i])=\prod _{j=1}^m{h}_j({\Psi }_j\cap \Theta ,\overline{\theta }[{\Psi }_j])$

Ya que $g{\text{'}}_i({\Phi }_i\cap \Theta ,\overline{\theta }[{\Phi }_i])=1$,

$f^{\prime }(\Theta )=\prod _{j=1}^m{h}_j({\Psi }_j\cap \Theta ,\overline{\theta }[{\Psi }_j])$

Si $h{\text{'}}_j(\Theta \cap {\Psi }_j)=h_j({\Psi }_j\cap \Theta ,\overline{\theta }[{\Psi }_j])$ s'obté:

$f^{\prime }(\Theta )=\prod _{j=1}^{m}h{\text{'}}_j(\Theta \cap {\Psi }_j)$ lo que finalment dona:

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

Archiu:Neighborhood Intersections.png

El clique format pels vèrtiços $x_1$, $x_2$ i $x_3$ és l'intersecció de $\{x_1\}\cup \partial x_1$, $\{x_2\}\cup \partial x_2$ i $\{x_3\}\cup \partial x_3$.

El Lema 1 proporciona un mig per a combinar dos factorización diferents de $\mathrm{Pr}(U)$. La propietat local de Markov implica que, per a qualsevol variable aleatòria $x\in U$, existixen factors $f_x$ i $f_{-x}$ tals que:

$\mathrm{Pr}(U)=f_x(x,\partial x)f_{-x}(U\setminus \{x\})$

a on $\partial x$ són els veïns del nodo $x$. L'aplicació repetida del Lema 1 acaba factorizando $\mathrm{Pr}(U)$ en un producte de potencials de clique (vore l'image de la dreta).

Fi de la prova

Vore també

• Camp aleatori de Markov
• Camp aleatori condicional

Bibliografia

• (2018).«Probability on Graphs».Cambridge University Press.
• «The Hammersley–Clifford Theorem and its Impact on Modern Statistics».Department of Mathematical Sciences, Norwegian University of Science and Technology.