Inégalité FKG

L’inégalité FKG, due à Fortuin, Kasteleyn et Ginibre^[1] est une version généralisée de l'inégalité de Tchebychev pour les sommes. C'est une inégalité de corrélation utilisée, par exemple, en théorie de la percolation, et dans l'étude du modèle de graphes aléatoires dû à Erdős et Rényi.

Énoncé

Sous la forme due à Harris, l'inégalité FKG concerne un ensemble fini ou dénombrable J dont chaque élément j est soit dans l'état 0, avec probabilité 1-p, soit dans l'état 1 avec probabilité p. L'état global du système J est donc décrit par un élément de $\scriptstyle\ \Omega=\{0,1\}^J.\$ Comme les états des différents sites j de J sont supposés indépendants, l'ensemble $\scriptstyle\ \Omega=\{0,1\}^J\$ des états, ou des configurations, est muni d'une loi de probabilité qui est une mesure produit de lois de Bernoulli. L'ensemble Ω peut-être identifié à l'ensemble des parties de J, via la correspondance entre ensemble et fonction indicatrice. L'inégalité FKG stipule que

Inégalité FKG —

Soit deux variables aléatoires X et Y croissantes sur $\scriptstyle\ \Omega.\$ Alors

$\mathbb{E}\left[XY\right] \geq \mathbb{E}\left[X\right] \mathbb{E}\left[Y\right].\,$

Soit deux parties croissantes A et B de $\scriptstyle\ \Omega.\$ Alors

$\mathbb{P}(A\cap B) \geq \mathbb{P}(A) \mathbb{P}(B).\,$

Cela revient à dire qu'il y a une corrélation positive entre les variables concernées, puisqu'on peut reformuler la première inégalité sous la forme

$\text{Cov}\left(X,Y\right)\ \ge \ 0.$

Le deuxième point de l'inégalité FKG est obtenu comme conséquence immédiate du premier point, en spécialisant au cas particulier où X est la fonction indicatrice de A et où Y est la fonction indicatrice de B.

L'inégalité vaut aussi pour des variables ou des parties décroissantes, mais le sens des inégalités change lorsque les variables ou les parties concernées ont des sens de monotonie opposés.

Il y a des formes plus générales de l'inégalité FKG, avec les mêmes conclusions, mais pour des espaces produits plus généraux, munis d'une mesure qui n'est pas nécessairement une mesure produit (voir FKG inequality).

Ordre et croissance

On définit une relation d'ordre partielle sur Ω comme suit : pour $\scriptstyle\ (a,b)\in\Omega,\ a=(a_j)_{j\in J},\ b=(b_j)_{j\in J},\$ on pose

$\{a\le b\}\quad\Leftrightarrow\quad\{\forall j\in J,\ a_j\le b_j\}.\$

Si on identifie Ω à l'ensemble des parties de J, la relation d'ordre ci-dessus s'interprète comme la relation d'inclusion. Ce parallèle ne tient plus si l'on veut généraliser de $\scriptstyle\ \Omega=\{0,1\}^J\$ à $\scriptstyle\ \Omega=E^J,\$ pour un espace d'états E plus général que {0,1}.

Comme d'ordinaire, une application X définie sur Ω, à valeurs réelles, est dite croissante si

$\{a\le b\}\quad\Rightarrow\quad\{X(a)\le X(b)\}.\$

Une partie A de Ω est dite croissante si

$\{a\le b\ \text{et}\ a\in A\}\quad\Rightarrow\quad\{b\in A\}.\$

De manière équivalente, une partie A de Ω est dite croissante si sa fonction indicatrice est croissante.

La propriété de décroissance d'une application ou d'une partie a une définition analogue.

Exemples :

Percolation : J est l'ensemble des arêtes du réseau arêtes ouvertes avec probabilité p et fermées avec probabilité 1-p, indépendamment les unes des autres.
- l'ensemble A des configurations possédant un amas infini est croissant (on dit que la propriété d'existence d'un amas infini est croissante) ;
- pour deux sites donnés, x et y, la propriété "x est relié à y" est croissante ;
- la propriété "x appartient à un amas infini" est croissante.
Modèle d'Erdős-Rényi : J est l'ensemble des n(n-1)/2 arêtes potentielles entre n sommets numérotés de 1 à n, arêtes présentes avec probabilité p et absentes avec probabilité 1-p, indépendamment les unes des autres. L'ensemble des arêtes présentes définit un graphe aléatoire, noté G(n,p), dont Erdős et Rényi ont étudié certaines propriétés (évènements) et certains paramètres (variables aléatoires). Parmi ces propriétés et paramètres,
- la connexité est croissante ;
- la planarité est décroissante ;
- le nombre chromatique est croissant ;
- la taille de l'ensemble indépendant de taille maximale (independence number) est décroissante ;
- la propriété triangle-free est décroissante.

Preuve

Inégalité de corrélation

Modulo des hypothèses d'intégrabilité, dans le cas où l'espace de départ est muni d'une relation d'ordre totale, on a les inégalités suivantes :

Inégalité de corrélation —

Soit deux variables aléatoires réelles X et Y définies et croissantes sur un ensemble $\scriptstyle\ \mathcal{O}\$ totalement ordonné, muni d'une mesure de probabilité $\scriptstyle\ \mathbb{Q}.\$ Alors

$\mathbb{E}\left[XY\right] \geq \mathbb{E}\left[X\right] \mathbb{E}\left[Y\right].\,$

Soit Z une variable aléatoire réelle définie sur un ensemble $\scriptstyle\ \Omega\$ non nécessairement ordonné, et soit I un intervalle tel que $\scriptstyle\ \mathbb{P}(Z\in I)=1.\$ Soit deux fonctions f et g définies et croissantes sur I. Alors

$\mathbb{E}\left[f(Z)g(Z)\right] \geq \mathbb{E}\left[f(Z)\right] \mathbb{E}\left[g(Z)\right].\,$

Démonstration

On considère l'espace produit $\scriptstyle\ \mathcal{O}\times\mathcal{O}\$ muni de la probabilité produit $\scriptstyle\ \mathbb{Q}\otimes\mathbb{Q}.\$ Du fait de la monotonie de X et de Y, l'application

$(\omega,\omega^{\prime})\quad\rightarrow\quad\left(X(\omega)-X(\omega^{\prime})\right)\left(Y(\omega)-Y(\omega^{\prime})\right)$

est positive ou nulle sur $\scriptstyle\ \mathcal{O}\times\mathcal{O}.\$ Par conséquent

$\begin{align} 0 &\le \int_{\mathcal{O}\times\mathcal{O}}\ (X(\omega)-X(\omega^{\prime})(Y(\omega)-Y(\omega^{\prime})\ \mathbb{Q}\otimes\mathbb{Q}(d\omega,d\omega^{\prime}) \\ &= \int_{\mathcal{O}\times\mathcal{O}}\ [X(\omega)Y(\omega)+X(\omega^{\prime})Y(\omega^{\prime})-X(\omega)Y(\omega^{\prime})-X(\omega^{\prime})Y(\omega)]\ \mathbb{Q}\otimes\mathbb{Q}(d\omega,d\omega^{\prime}) \\ &=2\ \mathbb{E}\left[XY\right]-2\ \mathbb{E}\left[X\right] \mathbb{E}\left[Y\right], \end{align}$

où la première inégalité découle de la croissance de l'intégrale par rapport à une mesure. La dernière égalité provient de la linéarité de l'intégrale, et du Théorème de Fubini appliqué aux quatre intégrales obtenues à l'aide de la linéarité.

La deuxième inégalité est une conséquence de la première, en spécialisant à $\scriptstyle\ \mathcal{O}=I\$ et à $\scriptstyle\ \mathbb{Q}=\mathbb{P}_Z,\$ puis en appliquant le théorème de transfert. On peut aussi, de manière moins savante, considérer sur le même espace probabilisé Ω, deux variables indépendantes et de même loi, Z et Z', et remarquer que la variable $\left(f(Z)-f(Z^{\prime})\right)\,\left(g(Z)-g(Z^{\prime})\right)$

est positive ou nulle sur $\scriptstyle\ \Omega.\$ Par conséquent

$\begin{align} 0 &\le \mathbb{E}\left[\left(f(Z)-f(Z^{\prime}\right)\,\left(g(Z)-g(Z^{\prime}\right)\right] \\ &=\mathbb{E}\left[f(Z)g(Z)\right]+\mathbb{E}\left[f(Z^{\prime})g(Z^{\prime})\right]-\ \mathbb{E}\left[f(Z^{\prime})g(Z)\right]-\mathbb{E}\left[f(Z)g(Z^{\prime})\right] \\ &=2\ \mathbb{E}\left[f(Z)g(Z)\right]-\ \mathbb{E}\left[f(Z^{\prime})\right] \mathbb{E}\left[g(Z)\right]-\mathbb{E}\left[f(Z)\right] \mathbb{E}\left[g(Z^{\prime})\right] \\ &=2\ \mathbb{E}\left[f(Z)g(Z)\right]-\ 2\mathbb{E}\left[f(Z)\right] \mathbb{E}\left[g(Z)\right], \end{align}$

où on a utilisé à plusieurs reprises l'indépendance des deux variables Z et Z', et l'identité en loi de ces deux variables.

Là encore, on peut reformuler la deuxième inégalité sous la forme

$\text{Cov}\left(f(Z),g(Z)\right)\ \ge \ 0,$

et là encore, on peut changer le sens de monotonie d'une ou deux des variables ou fonctions concernées, quitte éventuellement à changer le sens de l'inégalité.

L'inégalité de Tchebychev pour les sommes est une conséquence immédiate de l'inégalité de corrélation ci-dessus : il suffit de considérer le cas particulier où la variable aléatoire réelle Z suit la loi uniforme discrète sur $\scriptstyle\ [\![1,n]\!].\$ De même, pour obtenir la version continue de l'inégalité de Tchebychev pour les sommes, on choisit, dans l'inégalité de corrélation ci-dessus, une variable aléatoire réelle Z suivant la loi uniforme continue sur [0,1].

Cas fini

On fait la démonstration dans le cas général où l'état global du système fini J est décrit par un élément $\scriptstyle\ \omega=(\omega_{j})_{j\in J}\$ de $\scriptstyle\ \Omega=\mathcal{O}^J.\$ L'état d'un élément j de J est décrit par un élément $\scriptstyle\ \omega_{j}\$ de l'ensemble $\scriptstyle\ \mathcal{O}\$ qui est, comme au paragraphe précédent, un ensemble totalement ordonné muni d'une mesure de probabilité $\scriptstyle\ \mathbb{Q}.\$ Comme exemple, on peut penser à $\scriptstyle\ \mathcal{O}=\mathbb{R},\$ mais l'inégalité FKG annoncée en début de page correspond au choix du cas particulier :

$\mathcal{O}=\{0,1\},\qquad \mathbb{Q}=(1-p)\delta_{0}+p\delta_{1}.$

Le résultat démontré ici est donc (du moins dans le cas où J est fini) plus fort que l'inégalité FKG annoncée.

On suppose, sans perte de généralité, que $\scriptstyle\ J=[\![1,n]\!],\$ et on fait une démonstration par récurrence. L'initialisation de la récurrence (cas n=1) a été l'objet de la section précédente : c'est la première version de l'inégalité de corrélation.

On note

$\begin{align} \widehat{X}(\omega_{n}) &=\int_{\mathcal{O}^{n-1}}\ X(\omega)\ \mathbb{Q}(d\omega_{1})\dots\mathbb{Q}(d\omega_{n-1}) \\ &=\mathbb{E}\left[X\left|\omega_{n}\right.\right] \end{align}$

l'espérance conditionnelle de X sachant la n-ème coordonnée $\scriptstyle\ \omega_{n}\$ de ω. On introduit de même $\scriptstyle\ \widehat{Y}(\omega_{n})\$ . Du fait de la croissance de X et de Y, et de la croissance de l'intégrale (ou de l'espérance conditionnelle), les variables aléatoires $\scriptstyle\ \widehat{X}\$ et $\scriptstyle\ \widehat{Y}\$ sont croissantes sur $\scriptstyle\ \mathcal{O},\$ donc, en vertu de l'inégalité de corrélation,

$\mathbb{E}\left[\widehat{X}\widehat{Y}\right] \geq \mathbb{E}\left[\widehat{X}\right] \mathbb{E}\left[\widehat{X}\right].\,$

D'autre part, par propriété de l'espérance conditionnelle (ou, dans ce cas particulier, à cause du théorème de Fubini),

$\begin{align} \mathbb{E}\left[\widehat{X}\right] \mathbb{E}\left[\widehat{Y}\right] &= \mathbb{E}\left[\mathbb{E}\left[X\left|\omega_{n}\right.\right]\right]\ \mathbb{E}\left[\mathbb{E}\left[Y\left|\omega_{n}\right.\right]\right] \\ &= \mathbb{E}\left[X\right] \mathbb{E}\left[Y\right]. \end{align}$

Considérons maintenant que la n-ème coordonnée $\scriptstyle\ \omega_{n}\$ de ω est fixée. On travaille alors sur $\scriptstyle\ \tilde{\Omega}=\mathcal{O}^{[\![1,n-1]\!]},\$ muni de l'espérance $\scriptstyle\ \tilde{\mathbb{E}}\$ correspondant à la mesure produit :

$\begin{align} \tilde{\mathbb{E}}\left[Z\right] &=\int_{\mathcal{O}^{n-1}}\ Z(\omega)\ \mathbb{Q}(d\omega_{1})\dots\mathbb{Q}(d\omega_{n-1}). \end{align}$

On considère les applications

$\begin{align}\tilde{X} :\qquad &\tilde{\Omega}\rightarrow\mathbb{R} \\ &(\omega_{1},\dots,\omega_{n-1})\rightarrow\tilde{X}(\omega_{1},\dots,\omega_{n-1})=X(\omega_{1},\dots,\omega_{n-1},\omega_{n}) \end{align}$

$\begin{align}\tilde{Y} :\qquad &\tilde{\Omega}\rightarrow\mathbb{R} \\ &(\omega_{1},\dots,\omega_{n-1})\rightarrow\tilde{Y}(\omega_{1},\dots,\omega_{n-1})=Y(\omega_{1},\dots,\omega_{n-1},\omega_{n}), \end{align}$

qui sont croissantes sur $\scriptstyle\ \tilde{\Omega}\$ et qui vérifient

$\tilde{\mathbb{E}}\left[\tilde{X}\right]=\widehat{X}(\omega_{n}) =\mathbb{E}\left[X\left|\omega_{n}\right.\right],$ $\tilde{\mathbb{E}}\left[\tilde{Y}\right]=\widehat{Y}(\omega_{n}) =\mathbb{E}\left[Y\left|\omega_{n}\right.\right].$

On a donc en vertu de l'hypothèse de récurrence (rang n-1)

$\mathbb{E}\left[XY\left|\omega_{n}\right.\right]=\tilde{\mathbb{E}}\left[\tilde{X}\tilde{Y}\right]\ge\tilde{\mathbb{E}}\left[\tilde{X}\right]\tilde{\mathbb{E}}\left[\tilde{Y}\right]=\widehat{X}(\omega_{n})\widehat{Y}(\omega_{n}).$

Finalement, avec la première inégalité,

$\mathbb{E}\left[XY\right]=\mathbb{E}\left[\mathbb{E}\left[XY\left|\omega_{n}\right.\right]\right]\ge\mathbb{E}\left[\widehat{X}\widehat{Y}\right]\ge\mathbb{E}\left[X\right]\mathbb{E}\left[Y\right].$

A ce stade on a démontré l'inégalité FKG utile au modèle d'Erdos-Renyi, mais on n'a pas encore une inégalité FKG suffisamment puissante pour la théorie de la percolation. C'est l'objet de la section suivante.

Cas infini dénombrable

La démonstration se fait à partir du cas fini, par passage à la limite, en utilisant un théorème de convergence presque sûre pour les martingales à carré intégrable. Voir Grimmett "Percolation", page 36, section 2.2.

Voir aussi

Pages liées

Bibliographie

Percolation de G.R. Grimmett chez Springer
Percolation Theory for Mathematicians de Harry Kesten chez Birkhaüser
Stauffer et Aharony, Introduction to Percolation Theory, Taylor and Francis Ed. London, 1985

Notes

↑ (en) C. M. Fortuin, P. W. Kasteleyn et J. Ginibre, « Correlation inequalities on some partially ordered sets », dans ["Communications in Mathematical Physics"], vol. 22, 1971, p. 89-103 (ISSN 0010-3616)

Portail des probabilités et des statistiques

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Inégalité FKG de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

Inégalité de Tchebychev pour les sommes — L’inégalité de Tchebychev pour les sommes est due à Pafnouti Tchebychev. Elle est un cas particulier de l inégalité FKG[1] et de l inégalité de Harris. Elle ne doit pas être confondue avec l inégalité de Bienaymé Tchebychev. Sommaire 1 Énoncé 2 … Wikipédia en Français
Inégalité de réarrangement — Sommaire 1 Énoncé 2 Démonstration 3 Applications 3.1 Job shop à une machine 3.2 … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Inégalité FKG

Sommaire