Une vie de couples

Piste rouge Le 9 novembre 2018  - Ecrit par  Pierre Monmarché Voir les commentaires

À l’instar du couteau-suisse pour les débrouillards, le couplage est un outil élémentaire multi-fonction pour les probabilistes.

Un premier exemple [1]

Prenons la situation suivante : vous êtes au casino avec un ami, et vous décidez tous deux de tenter votre chance à la roulette. Celle-ci comporte 37 cases, dont 18 sont rouges, 18 sont noires, et l’une (le numéro 0) est verte. Chacun de vous va choisir une couleur, noir ou rouge. Si la bille tombe sur la couleur qu’un joueur a annoncée (ce qui arrive avec probabilité 18/37), il reçoit un jeton. Sinon, il perd sa mise, d’un jeton. Notons $X$ votre gain, exprimé en jeton, et $Y$ le gain de votre ami. Alors, $X$ est un nombre aléatoire, qui a une probabilité 18/37 d’être égal à $1$ et une probabilité 19/37 d’être égal à $-1$, et il en va de même pour $Y$, et ce quelles que soient les couleurs que vous choisissez.

Par exemple, vous pouvez décider de jouer tous les deux la même couleur (stratégie 1), ou de jouer des couleurs différentes (stratégie 2), ou alors de choisir indifféremment le rouge ou le noir indépendamment l’un de l’autre, par exemple en tirant chacun dans son coin à pile ou face (stratégie 3). Cela n’affecte pas vos chances de gains individuels.

X stratégie 1 stratégie 2 stratégie 3
1 18/37 18/37 18/37
-1 19/37 19/37 19/37

En revanche, le couple $(X,Y)$ peut dépendre de vos choix. Dans ces trois cas, quelle est la loi de $(X,Y)$ , c’est-à-dire quelles valeurs $(X,Y)$ peut-il prendre, et avec quelles probabilités ?

Dans la stratégie 1, avec probabilité 18/37 vous gagnez tous les deux en même temps, auquel cas $(X,Y)=(1,1)$, et avec probabilité 19/37 vous perdez de concert, c’est-à-dire que $(X,Y)=(-1,-1)$. En choisissant la stratégie 2 en revanche, avec probabilité 18/37 vous gagnez et votre ami perd, et donc $(X,Y)=(1,-1)$, avec probabilité 18/37 votre ami gagne et vous perdez, soit $(X,Y)=(-1,1)$, et enfin avec probabilité 1/37 vous perdez tous les deux, $(X,Y) = (-1,-1)$. La probabilité de gagner tous les deux simultanément est nulle. Enfin, avec la stratégie 3 pour gagner tous les deux par exemple il faut que vous ayez parié la même couleur (ce qui arrive avec probabilité 1/2) et qu’ensuite cette couleur soit sortie (probabilité 18/37), ce qui donne une probabilité 9/37 que $(X,Y)=(1,1)$. Les autres situations peuvent être calculées de même, et l’on obtient au bout du compte ce tableau de probabilités.

(X,Y) stratégie 1 stratégie 2 stratégie 3
(1,1) 18/37 0 9/37
(1,-1) 0 18/37 9/37
(-1,1) 0 18/37 9/37
(-1,-1) 19/37 1/37 10/37

Autrement dit, bien que les lois de $X$ et de $Y$ soient fixées et ne dépendent pas de la stratégie, la loi du couple $(X,Y)$, elle, peut varier. Choisir une stratégie, c’est ce qu’on appelle construire un couplage de la loi de $X$ et de la loi de $Y$. Le principe général du couplage probabiliste est le suivant : étant données deux variables aléatoires $X$ et $Y$ dont les lois sont prescrites (c’est-à-dire, dont la probabilité que chacune prenne telle ou telle valeur est fixée), il y a tout de même une marge de manœuvre, des choix possibles, pour construire des couplages $(X,Y)$ de ces deux lois [2].

Oui, mais quel intérêt ? Ou, dit autrement, quelle est alors la bonne stratégie pour coupler $X$ et $Y$ ? Eh bien, ça dépend de ce que vous voulez obtenir. Dans le cas de la roulette, si vous faites pot commun de jetons, vous pouvez choisir de minimiser la probabilité de perdre un jeton, auquel cas la stratégie 2 est optimale [3] (il n’y a alors de perte dans le pot commun que si la bille tombe sur 0, ce qui n’arrive qu’avec probabilité 1/37). Si pour repartir avec le lot de vos rêves vous avez absolument besoin, à vous deux, de gagner deux jetons, alors la stratégie 1 est optimale, puisqu’elle maximise la probabilité que $(X,Y)$ soit égal à $(1,1)$. C’est la même chose quand on étudie des problèmes de probabilités : parfois, on va vouloir maximiser la probabilité que $X=Y$, et parfois au contraire la minimiser. Dans certaines situations, on veut que $X$ et $Y$ soient le plus proche possible, ou au contraire le plus éloigné. Dans la suite, on va s’intéresser à un exemple avec encore un autre critère : le but du couplage sera de s’assurer que $X\leqslant Y$.

Percolation

Un certain nombre d’articles d’Images des Maths traitent déjà des problèmes de percolation (par exemple , ou ). Pour faire simple, le but est de comprendre comment les propriétés microscopiques d’un matériau (par exemple, une roche) expliquent sa porosité à grande échelle. Considérons le modèle suivant. On suppose que le matériau est un carré, que l’on subdivise en petites alvéoles carrées. Ensuite, pour chaque paroi entre deux alvéoles, on tire à pile ou face, avec une pièce potentiellement biaisée (c’est-à-dire que la probabilité $p$ qu’elle fasse Pile n’est pas nécessairement 1/2 ; on parle de loi de Bernoulli de paramètre $p$). À chaque fois qu’on obtient Pile on supprime la paroi, sinon on la garde. Enfin, on verse de l’eau au-dessus du matériau, et on se demande quelle est la probabilité qu’elle s’infiltre sur toute la hauteur du matériau.

Deux grilles aléatoires : dans la première, il n’y a pas percolation (l’eau ne traverse pas), et dans la seconde, si.

Cette probabilité dépend de $ p $. Notons-la $Q(p)$. On se doute que, plus on a de chances de supprimer chaque arête, plus on a de chances que l’eau s’infiltre. Autrement dit, on s’attend à ce que $Q(p)$ soit une fonction croissante de $p$, c’est-à-dire que si $p'\geqslant p$ alors $Q(p')\geqslant Q(p)$. Comment le démontrer facilement ? La difficulté, c’est que le résultat de la suppression de parois est aléatoire. Même si $p'>p$, si on crée deux grilles, l’une en supprimant les parois avec probabilité $p'$ et l’autre avec probabilité $p$, indépendamment l’une de l’autre, on peut très bien, sur un coup de malchance, ne pas avoir percolation pour la première et avoir percolation pour la seconde. À vrai dire, pour tout $p$ strictement positif et strictement plus petit que 1, il y a toujours une petite probabilité de ne supprimer aucune paroi, ou au contraire de toutes les supprimer.

La solution, pour comparer les deux, est de ne pas créer des grilles indépendamment, mais de les coupler de telle sorte que, s’il y a percolation pour la grille de proba $p$, alors il y a percolation pour la grille de proba $p'$. On le fait de cette façon : en partant de la grille complète, on commence par supprimer chaque paroi avec probabilité $p$. Dans un second temps, en partant de la grille qu’on vient d’obtenir, on supprime chaque paroi encore fermée avec probabilité $(p'-p)/(1-p)$. La grille intermédiaire est, par construction, une grille dont chaque paroi est supprimée avec probabilité $p$, tandis que la grille finale est bel et bien une grille dont chaque paroi a été supprimée avec probabilité $p'$. En effet, pour chacune de ses parois, la probabilité d’être ouverte est égale à la probabilité d’avoir été ouverte dès le premier tour (proba $p$) plus la probabilité de n’avoir pas été ouverte au premier tour (proba $1-p$) fois la probabilité d’avoir été ouverte au second tour (proba $(p'-p)/(1-p)$), ce qui donne bien une probabilité $p'$ (et d’autre part, chaque paroi est bien traitée indépendamment des autres).

Couplage des grilles : la seconde grille correspond à une probabilité $p$ de supprimer les parois, la dernière une probabilité $p'>p$.

Le couplage est tel qu’une paroi supprimée dans la grille intermédiaire est forcément supprimée dans la grille finale. Pour faire le lien avec la première partie, posons $X=1$ si l’eau passe dans la grille intermédiaire et $X=0$ sinon, et de même $Y=1$ ou $0$ selon que l’eau passe ou non dans la dernière grille. Il est clair que, si l’eau trouve un chemin ouvert pour traverser le matériau de haut en bas dans la grille intermédiaire, alors ce chemin est également ouvert dans la grille finale, et donc $X=1$ implique que $Y=1$. Cela revient à dire qu’on a toujours $X\leq Y$ [4]. Puisque, par définition de $Q$, $X$ est une variable aléatoire telle que $\mathbb P(X=1) = Q(p)$, et de même $\mathbb P(Y=1) = Q(p')$, on en déduit que $Q(p) \leqslant Q(p')$. Ce qu’il fallait démontrer.

Plus de détails...

Pour écrire les choses un peu plus formellement : puisque $X=1$ implique que $Y=1$, on peut dire que
\[\mathbb P \big((X,Y)=(1,1)\big) = \mathbb P(X=1)\,,\]
et donc
\[\begin{array}{rcl} Q(p')& =& \mathbb P(Y=1)\\ &= & \mathbb P \big( (X,Y)=(1,1)\big ) + \mathbb P \big( (X,Y)=(0,1)\big) \\ &= & \mathbb P( X=1 ) + \mathbb P ( Y>X) \\ &= & Q(p) + \mathbb P( Y>X)\,. \\ \end{array}\]
Une probabilité étant toujours positive, $Q(p')\geqslant Q(p)$. Mais plus précisément, dès que $p'>p$, il est clair que $\mathbb P( Y>X)$ est strictement positif. En effet, pour n’importe quelle première grille (qu’elle laisse passer l’eau ou non), il y a une probabilité strictement positive que la seconde grille laisse passer l’eau (il y a même une probabilité non nulle de supprimer toutes les parois restantes). Donc $Q(p') > Q(p)$, c’est-à-dire que $Q$ est une fonction strictement croissante.

On pourrait même aller plus loin en voyant que $ \mathbb P( Y>X)$ tend vers 0 quand $p'$ tend vers $p$. En effet, on peut dire que $X=Y$ si en particulier on ne supprime aucune paroi de la première grille pour avoir la seconde, ce qui arrive toujours avec une probabilité au moins $(1-(p'-p)/(1-p))^N$ où $N$ est le nombre total de parois. Donc
\[\begin{array}{rcl} \mathbb P(Y>X) &= & 1 - \mathbb P(Y=X) \\ &\leqslant & 1 - \big(1- \frac{p'-p}{1-p}\big)^N\,, \end{array}\]
qui tend bien vers $0$ quand $p'$ tend vers $p$. On en déduit finalement que $Q$ est une fonction continue (et même dérivable) strictement croissante qui part de $Q(0)=0$ pour monter à $Q(1)=1$ (si on ne supprime aucune paroi, l’eau ne passe jamais ; si on supprime toutes les parois, l’eau passe toujours).

Et bien d’autres applications

Ce qui marche pour la percolation marche pour les épidémies : si on suppose que deux maladies se propagent de façon similaire, mais que l’une est plus virulente que l’autre (c’est-à-dire que la probabilité d’infecter un voisin quand on est soi-même infecté est plus grande), ou bien que son traitement est moins efficace que celui de l’autre, alors on s’attend à ce qu’elle contamine plus de gens. Sur des modèles mathématiques simples, on peut le montrer par un couplage tout à fait similaire à celui du paragraphe précédent. Ces couplages, qui ont pour but d’instaurer une hiérarchie entre les variables aléatoires (c’est-à-dire, assurer que l’une est plus grande que l’autre), sont dits monotones [5].

Une autre grande famille de couplages a pour but d’étudier comment des particules en mouvement, débutant à des positions différentes, peuvent finir par se rencontrer. Il s’agit alors de coupler à chaque instant les déplacements des deux particules pour maximiser leurs chances de se rencontrer, puis de rester ensemble. C’est ce qu’on appelle des couplages coalescents. On les utilise entre autres pour étudier les nombreux algorithmes qui reposent sur l’exploration aléatoire d’un grand nombre de possibilités.

Plus de détails...

Prenez deux ivrognes qui partent à minuit de deux bars différents et s’en vont errer au hasard dans les rues. À 00h05, on peut s’attendre à trouver chacun d’eux à proximité de son point de départ. En revanche, passé 2h, ils ont tous deux la même chance de se trouver à peu près n’importe où. Un couplage coalescent consiste à dire que, si les deux ivrognes se rencontrent, ils ne se quittent plus (et s’en vont bras dessus, bras dessous, vacillants...). Dans ce cas-là, le temps qu’ils mettent à se rencontrer donne une estimation du temps qu’ils mettent à se perdre (puisque, si on les croise après leur rencontre, on ne sait plus qui vient d’où), aussi appelé temps de mélange ou de relaxation à l’équilibre.

On pourrait par exemple essayer de coupler les déplacements des deux ivrognes en leur faisant faire le même mouvement : si l’un va vers l’est, l’autre aussi, et de même à l’ouest, au nord ou au sud. C’est ce qu’on appelle un couplage parallèle. Dans ce cas-là, les ivrognes ne vont jamais se rapprocher, et donc jamais se rencontrer : ainsi ce couplage ne nous donne aucune information sur le temps de mélange ! Il faut faire autrement, par exemple laisser les ivrognes se balader au hasard indépendamment l’un de l’autre jusqu’à leur rencontre (mais on peut essayer de coupler de manière plus sophistiquée pour minimiser le temps de rencontre).

Le lien avec les algorithmes basés sur une exploration aléatoire est le suivant : ces derniers ne fonctionnent que si on a laissé suffisamment de temps à l’explorateur pour avoir observé un échantillon statistiquement représentatif des possibilités, autrement dit pour s’être perdu. En construisant un couplage, on obtient une information théorique sur le temps de mélange, et donc en pratique on sait combien de temps laisser à l’algorithme.

Un exemple d’application concrète de ces algorithmes : en biochimie, on cherche à simuler sur ordinateur une protéine, qui est une grosse molécule. Sous l’effet des forces qui s’exercent entre ses atomes, la protéine va se replier et prendre une forme tridimensionnelle particulière, qui déterminera les propriétés physico-chimique de la protéine (par exemple, l’hémoglobine forme des petits réceptacles à oxygène). Mais le seul moyen qu’on a de trouver cette forme, c’est de générer une protéine et de la faire bouger au hasard (comme l’ivrogne de l’exemple précédent [6]) jusqu’à ce qu’elle finisse par tomber sur la bonne configuration.

D’autres applications basées sur des algorithmes similaires : en intelligence artificielle et statistiques, calibrer un réseau de neurones à partir d’une base de donnée d’observations ; en fiabilité, calculer la probabilité d’une défaillance d’un système (une centrale nucléaire par exemple) ; en logistique allouer des ressources de manière optimale (par exemple, dans un réseau électrique national avec des sources de production et de consommation hétérogènes, décider où acheminer ou stocker l’électricité pour minimiser les pertes), etc.

Toujours pour ce type d’algorithmes, en pratique, on peut aussi essayer de coupler deux particules pour qu’elles fassent le contraire l’une de l’autre (si l’une va à l’est, l’autre va à l’ouest, etc.) de sorte qu’elles aillent, autant que faire se peut, dans des directions opposées (couplage miroir, ou antithétique) afin de voir plus rapidement un échantillon plus large de possibilités.

Un exemple (très concret) de couplage miroir

Enfin, un domaine entier des mathématiques, le transport optimal (cf cet article ou celui-là, qui détaille des applications en traitement d’images), utilise les couplages pour quantifier à quel point deux lois de probabilité sont éloignées l’une de l’autre. Très grossièrement, le principe est le suivant : si, partant d’une variable aléatoire $X$, je peux faire, avec très peu de modifications, une variable $Y$, alors les lois de $X$ et $Y$ sont proches. Si, au contraire, il faut beaucoup de transformations, les lois sont éloignées. Pour reprendre l’exemple de la percolation : pour passer d’une grille de probabilité $p$ à une grille de probabilité $p'$, il suffit d’ouvrir (si $p'>p$) ou de fermer (si $p' < p$) des parois supplémentaires avec probabilité $|p'-p|/(1-p)$. Plus $p'$ est proche de $p$, moins on va devoir ajouter (ou enlever) de parois, et donc plus les lois des grilles sont proches.

Bref, les couplages sont (presque) partout et, si leur mise en œuvre peut parfois s’avérer subtile, ils restent un outil qui, d’un principe très simple, donne des solutions élégantes à des problèmes délicats de probabilités.

Post-scriptum :

La rédaction d’Images des mathématiques ainsi que l’auteur remercient pour leur relecture attentive et leurs remarques les relecteurs fpiou, Jean-Romain Heu, Michaël Bages et Jérémy Le Borgne.

Article édité par Pierre-Antoine Guihéneuf

Notes

[1Traduction
Personne normale : « Super, un jeu d’argent ! »
Enthousiaste des maths : « Un jeu d’argent ?! J’imagine que tu n’y connais rien en statistiques ! »
Mathématicien : « Super, un jeu d’argent ! »

[2Plus rigoureusement, si $\mu$ et $\nu$ sont deux lois de probabilité, alors par définition un couplage de $\mu$ et $\nu$ est une variable aléatoire $(X,Y)$ dont les lois marginales sont $\mu$ et $\nu$, c’est-à-dire telle que la loi de $X$ est $\mu$ (autrement dit $\mathbb P(X=k) = \mu(k)$ pour tout $k$) et la loi de $Y$ est $\nu$ (autrement dit $\mathbb P(Y=k) = \nu(k)$ pour tout $k$).

[3Ou alors de ne pas jouer du tout, mais pour les besoins de l’étude nous n’envisagerons pas cette possibilité.

[4En fait en notant $A$ la première grille et $B$ la seconde, alors $A\leqslant B$ si on dit qu’une grille est plus petite qu’une autre si toutes les parois ouvertes dans la première le sont dans la seconde. Ceci définit bien une relation d’ordre sur les grilles (non totale, c’est-à-dire qu’étant données deux grilles, il n’y en a pas nécessairement une qui est plus grande que l’autre), et l’application qui associe une grille à 0 ou 1 selon qu’il y ait percolation ou non est alors croissante, c’est-à-dire que $A\leqslant B$ implique $X\leqslant Y$.

[5Non pas parce qu’ils sont ennuyeux mais parce que, par définition, en mathématique, être monotone, c’est être, au choix, croissant ou décroissant, c’est-à-dire conserver une certaine hiérarchie.

[6Sauf qu’en réalité on explore les configurations avec un hasard un peu plus intelligent que celui de l’ivrogne.

Partager cet article

Pour citer cet article :

Pierre Monmarché — «Une vie de couples» — Images des Mathématiques, CNRS, 2018

Crédits image :

img_18865 - Zach Weinersmith http://www.smbc-comics.com/?id=2320
img_18866 - Pierre Monmarché
img_18867 - Pierre Monmarché

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM