Graphe pondéré et graphe probabiliste

Définition

Graphe pondéré

Un graphe est dit pondéré si chacune de ses arêtes est affecté d’un nombre positif (ou nul) que l’on appelle poids.

Le poids d’une chaîne (ou d’un chemin) est la somme des poids de ses arêtes.

Exemple

On considère le graphe orienté et pondéré suivant : image On a :

  • Le poids de l’arête ABA-B vaut 00.

  • Le poids du chemin ABCADA-B-C-A-D vaut 0+4+2+7=130+4+2+7 = 13.

Graphe probabiliste

On appelle graphe probabiliste un graphe orienté et pondéré tel que :

  • Pour chaque sommet, la somme des poids des arcs issus de ce sommet vaut 11.

  • Il y a au plus 11 arrête orientée reliant chaque sommet.

Il peut être utile de faire l’analogie entre les graphes probabilistes et les arbres de probabilité vus en classe de Première.

Exemple

Faisons un exemple concret. On souhaite étudier l’évolution d’une maladie chez un certain individu. À un jour donné, cet individu est soit malade (que l’on note MM), soit soigné (que l’on note SS). On suppose que pour cette maladie :

  • La probabilité qu’une personne malade guérisse le lendemain est 0,40,4.

  • La probabilité qu’une personne saine tombe malade le lendemain est 0,10,1.

Le graphe probabiliste modélisant cette situation est le graphe GG suivant : image On remarque que la somme des poids des arêtes issues du sommet SS vaut 0,9+0,1=10,9+0,1 = 1 (idem pour MM qui vaut 0,6+0,4=10,6+0,4 = 1).

Matrice de transition

Définition

Soit GG un graphe probabiliste d’ordre nn. On appelle matrice de transition du graphe GG, la matrice carrée d’ordre nn dont le coefficient à la ligne ii et à la colonne jj est égal au poids de l’arête reliant le sommet ii au sommet jj.

Une telle matrice est qualifiée de stochastique car la somme des coefficients de chacune de ses lignes vaut 11.

Exemple

Dans l’exemple précédent (en supposant que SS est le 1 sommet et que MM est le 2ème) la matrice de transition du graphe GG est (0,90,10,40,6)\displaystyle{\begin{pmatrix} 0,9 & 0,1 \\ 0,4 & 0,6 \end{pmatrix}}.

Attention cependant à ne pas confondre matrice de transition et matrice d’adjacence.

Chaînes de Markov

Qu’est-ce qu’une chaîne de Markov ?

Il vous est fortement conseillé de relire (et de maîtriser) le cours sur les variables aléatoires avant d’aborder cette section. De plus, sachez que cette partie est sans doute la plus difficile du programme de Terminale. Mais ne vous découragez pas car elle reste parfaitement accessible !

Définition

Soit (Xn)(X_n) une suite de variables aléatoires discrètes définies sur un même univers Ω\Omega et à valeurs dans un ensemble EE. On dit que (Xn)(X_n) définit une chaîne de Markov sur EE si pour tout nNn \in \mathbb{N} et tout x0,x1,x2,,xnEx_0, x_1, x_2, \dots, x_n \in E, l’événement (Xn=xn)(X_n = x_n) ne dépend que de l’événement antérieur (Xn1=xn1)(X_{n-1} = x_{n-1}) (et pas des précédents) ; autrement dit, si P(Xn1=xn1)(X0=x0)(Xn=xn)=P(Xn1=xn1)(Xn=xn)P_{(X_{n-1} = x_{n-1}) \, \cap \dots \cap \, (X_0 = x_0)}(X_n = x_n) = P_{(X_{n-1} = x_{n-1})}(X_n = x_n).

De plus, l’ensemble EE est appelé espace des états de la chaîne de Markov.

En français, cela signifie que si XnX_n représente l’état d’un système à un temps nn, alors l’état suivant Xn+1X_{n+1} ne dépend que de l’état au temps nn et pas des états précédents. De plus, notez bien que nous n’avons pas fait d’hypothèse sur le cardinal de EE (qui peut donc être de cardinal mNm \in \mathbb{N}).

En classe de Terminale, nous nous limiterons principalement au cas où EE possède 22 voire 33 éléments, mais nous allons quand-même voir très bientôt un exemple de chaîne de Markov à 1212 états.

Variable aléatoire discrète

Une variable aléatoire XX définie sur un univers Ω\Omega est dite discrète si X(Ω)X(\Omega) est un ensemble dénombrable.

Chaîne de Markov homogène

Soit (Xn)(X_n) une chaîne de Markov dont on note EE l’espace des états. Alors (Xn)(X_n) est dite homogène si pour tout nNn \in \mathbb{N} et pour tout xx, yEy \in E, la probabilité P(Xn=x)(Xn+1=y)P_{(X_n = x)}(X_{n+1} = y) est indépendante de nn.

En termes mathématiques, cela signifie que pour tout nNn \in \mathbb{N} et pour tout xx, yEy \in E, P(Xn=x)(Xn+1=y)=P(X0=x)(X1=y)P_{(X_n = x)}(X_{n+1} = y) = P_{(X_0 = x)}(X_1 = y).

Exemple

Eliott fait la collection des vignettes des 11 joueurs titulaires de l’Équipe de France de football qu’il trouve dans des paquets de céréales. À chaque fois qu’il achète un paquet, il a donc une probabilité de 111\frac{1}{11} de tomber sur le kk-ième joueur (pour tout kk compris entre 11 et 1111).

Si on note par XnX_n le nombre de vignettes différentes dans la collection d’Eliott après qu’il eut ouvert nn paquets de céréales, alors (Xn)(X_n) est une chaîne de Markov homogène (commençant par X0=0X_0 = 0). En effet, pour tout k{0,1,,11}k \in \{0, 1, \dots, 11\}, on a que l’événement (Xn+1=k)(X_{n+1} = k) ne dépend que de XnX_n :

PA(Xn+1=k)={k11 si A est l’eˊveˊnement (Xn=k)1k111 si A est l’eˊveˊnement (Xn=k1) et que k10 sinon\displaystyle{P_A(X_{n+1} = k) = \begin{cases} \frac{k}{11} \text{ si } A \text{ est l'événement } (X_n = k) \\ 1 - \frac{k-1}{11} \text{ si } A \text{ est l'événement } (X_n = k-1) \text{ et que } k \geq 1 \\ 0 \text{ sinon} \end{cases}}

Pour détailler un peu plus :

  • Si on a (Xn=k)(X_n = k) (i.e. on a déjà tiré kk joueurs différents), alors la probabilité d’avoir (Xn+1=k)(X_{n+1} = k) est égale à la probabilité de ne pas tirer de nouveau joueur (qui est k11\frac{k}{11}). Cela inclut également le cas où k=11k = 11.

  • Si on a (Xn=k1)(X_n = k-1) (i.e. on a déjà tiré k1k-1 joueurs différents), alors la probabilité d’avoir (Xn+1=k)(X_{n+1} = k) est égale à la probabilité de tirer un nouveau joueur (qui est 1k1111 - \frac{k-1}{11}).

  • Sinon, comme on ne peut pas tirer plus d’un nouveau joueur d’un coup ou en enlever de la collection, la probabilité d’avoir (Xn+1=k)(X_{n+1} = k) est égale à 00.

  • Notons de plus que (Xn)(X_n) est homogène car le calcul de P(Xn+1=k)P(X_{n+1} = k) est indépendant de nn (mais reste dépendant de XnX_n, attention).

De plus, l’espace des états EE est {0,1,,11}\{0, 1, \dots, 11\}.

Cet exemple est très connu et porte un nom : il s’agit du problème du collectionneur de vignettes. Pour votre culture, sachez qu’en moyenne, il faudra ouvrir environ nln(n)n \ln(n) paquets de céréales pour compléter une collection de nn vignettes.

Matrice et graphe associés à une chaîne de Markov

Matrice de transition

Soit (Xn)(X_n) une chaîne de Markov homogène dont on note E={x1,x2,,xm}E = \{x_1, x_2, \dots, x_m\} l’espace des états. La matrice de transition de (Xn)(X_n) est la matrice carrée d’ordre mm dont le coefficient situé à la ii-ième ligne et à la jj-ième colonne est égal à pi,j=P(Xn=xi)(Xn+1=xj)p_{i,j} = P_{(X_n = x_i)}(X_{n+1} = x_j).

Comme cette probabilité est indépendante de nn, on peut tout à fait prendre n=0n = 0 dans la définition. On a alors pi,j=P(X0=xi)(X1=xj)p_{i,j} = P_{(X_0 = x_i)}(X_1 = x_j).

Graphe associé à une chaîne de Markov

Soit (Xn)(X_n) une chaîne de Markov homogène dont on note E={x1,x2,,xm}E = \{x_1, x_2, \dots, x_m\} l’espace des états. On associe à cette chaîne de Markov un graphe probabiliste GG d’ordre mm dont les sommets sont les états xix_i et dont les arêtes xixjx_i - x_j sont pondérées par les poids pi,j=P(Xn=xi)(Xn+1=xj)p_{i,j} = P_{(X_n = x_i)}(X_{n+1} = x_j).

La matrice de transition de (Xn)(X_n) est égale à la matrice de transition du graphe probabiliste GG : il s’agit donc aussi d’une matrice stochastique.

Exemple

Reprenons l’exemple précédent. Alors la matrice de transition associée à (Xn)(X_n) est la matrice MM12(R)M \in \mathcal{M}_{12}(\mathbb{R}) :

M=(01000111000010111110001)M = \displaystyle{\begin{pmatrix} 0 & 1 & \dots & 0 & 0 \\ 0 & \frac{1}{11} & \ddots & 0 & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \ddots & \frac{10}{11} & \frac{1}{11} \\ 0 & 0 & \dots & 0 & 1 \\ \end{pmatrix}}

Et le graphe associé à (Xn)(X_n) est le graphe probabiliste d’ordre 1212 : image

Distributions dans une chaîne de Markov

Proposition

Soit (Xn)(X_n) une chaîne de Markov homogène dont on note E={x1,x2,,xm}E = \{x_1, x_2, \dots, x_m\} l’espace des états. On pose pi,j(k)=P(X0=xi)(Xk=xj)p_{i,j}^{(k)} = P_{(X_0 = x_i)}(X_k = x_j) pour tout kNk \in \mathbb{N}^* (qui représente la probabilité que la chaîne de Markov (Xn)(X_n) passe de l’état xix_i à l’état xjx_j en kk étapes). On a :

pi,j(k)=q=1mpi,q(k1)×pq,j(1)=pi,1(k1)×p1,j(1)+pi,2(k1)×p2,j(1)++pi,m(k1)×pm,j(1)\displaystyle{p_{i,j}^{(k)} = \sum_{q=1}^m p_{i,q}^{(k-1)} \times p_{q,j}^{(1)} = p_{i,1}^{(k-1)} \times p_{1,j}^{(1)} + p_{i,2}^{(k-1)} \times p_{2,j}^{(1)} + \dots + p_{i,m}^{(k-1)} \times p_{m,j}^{(1)}}.

De plus, comme (Xn)(X_n) est homogène, pi,j(k)=pi,j(n+k)p_{i,j}^{(k)} = p_{i,j}^{(n+k)} pour tout nNn \in \mathbb{N}.

Démonstration

Cette formule semble un petit peu compliquée à interpréter. Elle signifie simplement que la probabilité que la chaîne de Markov (Xn)(X_n) passe de l’état xix_i à l’état xjx_j en kk étapes est égale à la probabilité qu’elle passe de l’état eie_i à eqe_q en une étape, puis de passer de eqe_q à eje_j en k1k-1 étapes. Heureusement, il est possible de la simplifier grandement à l’aide des matrices de transition.

Lien avec la matrice de transition

En reprenant les notations précédentes et en notant MM la matrice de transition de (Xn)(X_n), alors pi,j(k)p_{i,j}^{(k)} est le coefficient à la ligne ii et à la colonne jj de la matrice MkM^k.

Enfin, donnons la définition centrale de cette section.

Définition

Soit (Xn)(X_n) une chaîne de Markov homogène dont on note E={x1,x2,,xm}E = \{x_1, x_2, \dots, x_m\} l’espace des états. On appelle suite des distributions de (Xn)(X_n) la suite de matrices (πn)(\pi_n), définie pour tout nNn \in \mathbb{N} par πn=(P(Xn=x1)P(Xn=x2)P(Xn=em))\displaystyle{\pi_n = \begin{pmatrix} P(X_n = x_1) & P(X_n = x_2) & \dots & P(X_n = e_m) \end{pmatrix}}.

πn\pi_n est donc une matrice ligne d’ordre mm et est appelée distribution au temps nn.

π0\pi_0 (la distribution au temps 00) est appelée distribution initiale.

Une propriété très sympathique des distributions, est que l’on dispose d’une relation de récurrence permettant de calculer facilement la distribution à un temps nn donné.

Relation entre πn+1\pi_{n+1} et πn\pi_n

En reprenant les notations de la définition précédente et en notant MM la matrice de transition de (Xn)(X_n), alors la suite (πn)(\pi_n) vérifie une relation de récurrence donnée pour tout nNn \in \mathbb{N} par πn+1=πnM\pi_{n+1} = \pi_n M.

On en déduit que pour tout nNn \in \mathbb{N}, πn=π0Mn\pi_n = \pi_0 M^n.

Démonstration

Exemple

Intéressons-nous à l’alimentation d’un chat durant la journée. Il dispose de trois gamelles différentes LL, CC et PP dans lesquelles se trouvent respectivement du lait, des croquettes et de la pâté. On suppose que le chat a commencé sa journée par du lait et que toutes les heures, il se dirige vers une des gamelles suivant le graphe probabiliste ci-dessous : image On note par XnX_n la variable aléatoire qui donne la gamelle qu’a choisi le chat à la nn-ième heure. On a donc que (Xn)(X_n) est une chaîne de Markov homogène dont l’espace des états est E={L;C;P}E = \{L; C; P\}. Si on note (πn)(\pi_n) la suite des distributions de (Xn)(X_n), on a alors que π0=(100)\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}.

Soit MM la matrice de transition MM de (Xn)(X_n). Calculons quelques puissances de MM :

  • M=(0,50,30,20,20,70,10,30,30,4)\displaystyle{M = \begin{pmatrix} 0,5 & 0,3 & 0,2 \\ 0,2 & 0,7 & 0,1 \\ 0,3 & 0,3 & 0,4 \end{pmatrix}}

  • M2=(0,370,420,210,270,580,150,330,420,25)\displaystyle{M^2 = \begin{pmatrix} 0,37 & 0,42 & 0,21 \\ 0,27 & 0,58 & 0,15 \\ 0,33 & 0,42 & 0,25 \end{pmatrix}}

  • M3=(0,3320,4680,20,2960,5320,1720,3240,4680,208)\displaystyle{M^3 = \begin{pmatrix} 0,332 & 0,468 & 0,2 \\ 0,296 & 0,532 & 0,172 \\ 0,324 & 0,468 & 0,208 \end{pmatrix}}

Ainsi :

  • π1=π0M=(0,50,30,2)\pi_1 = \pi_0 M = \begin{pmatrix} 0,5 & 0,3 & 0,2 \end{pmatrix}

  • π2=π0M2=(0,370,420,21)\pi_2 = \pi_0 M^2 = \begin{pmatrix} 0,37 & 0,42 & 0,21 \end{pmatrix}

  • π3=π0M3=(0,3320,4680,2)\pi_3 = \pi_0 M^3 = \begin{pmatrix} 0,332 & 0,468 & 0,2 \end{pmatrix}

Et par exemple p1,2(3)=0,468p_{1,2}^{(3)} = 0,468 : la probabilité que le chat passe à sa gamelle de croquettes 3 heures après le lait est d’environ 47 %.

Distribution invariante

Définition

Soit (Xn)(X_n) une chaîne de Markov homogène de matrice de transition MM. Une distribution π\pi est invariante si les deux conditions suivantes sont respectées :

  • πM=π\displaystyle{\pi M = \pi} (donc si π\pi est une distribution à un temps nn, on a π=πn\pi = \pi_n et cette condition se résume à avoir πn=πnM=πn+1\pi_n = \pi_n M = \pi_{n+1}).

  • La somme des coefficients de π\pi vaut 11.

Existence et unicité de la distribution invariante au temps nn

Soit (Xn)(X_n) une chaîne de Markov homogène de matrice de transition MM.

Si MM ne possède aucun coefficient non nul autre que sur sa diagonale, alors (Xn)(X_n) admet une unique distribution invariante π\pi.

Convergence de la distribution

Soit (Xn)(X_n) une chaîne de Markov homogène dont on note (πn)(\pi_n) la suite des distributions.

  • Si (πn)(\pi_n) est une suite de matrices convergente, alors elle converge vers une distribution invariante π\pi.

  • Si le cardinal de l’ensemble des états de (Xn)(X_n) est 22, alors (πn)(\pi_n) est convergente (et converge vers la distribution invariante π\pi).

Exemple

Reprenons l’exemple précédent et voyons si (Xn)(X_n) admet une distribution invariante.

Remarquons tout d’abord que la matrice de transition MM ne possède aucun coefficient non nul. Donc (Xn)(X_n) admet une unique distribution invariante π\pi.

Posons donc π=(xyz)\pi = \begin{pmatrix} x & y & z \end{pmatrix} et déterminons xx, yy et zz :

On doit avoir πM=π\pi M = \pi     (xyz)(0,50,30,20,20,70,10,30,30,4)=(xyz)\iff \begin{pmatrix} x & y & z \end{pmatrix} \begin{pmatrix} 0,5 & 0,3 & 0,2 \\ 0,2 & 0,7 & 0,1 \\ 0,3 & 0,3 & 0,4 \end{pmatrix} = \begin{pmatrix} x & y & z \end{pmatrix}     (0,5x+0,2y+0,3z0,3x+0,7y+0,3z0,2x+0,1y+0,4z)=(xyz)\iff \begin{pmatrix} 0,5x + 0,2y + 0,3z & 0,3x + 0,7y + 0,3z & 0,2x + 0,1y + 0,4z \end{pmatrix} = \begin{pmatrix} x & y & z \end{pmatrix}     {12x+15y+310z=x310x+710y+310z=y15x+110y+25z=z\iff \begin{cases} \frac{1}{2}x + \frac{1}{5}y + \frac{3}{10}z = x \\ \frac{3}{10}x + \frac{7}{10}y + \frac{3}{10}z = y \\ \frac{1}{5}x + \frac{1}{10}y + \frac{2}{5}z = z \end{cases} (en passant en écriture fractionnaire)     {12x+15y+310z=0310x310y+310z=015x+110y35z=0\iff \begin{cases} -\frac{1}{2}x + \frac{1}{5}y + \frac{3}{10}z = 0 \\ \frac{3}{10}x - \frac{3}{10}y + \frac{3}{10}z = 0 \\ \frac{1}{5}x + \frac{1}{10}y - \frac{3}{5}z = 0 \end{cases}     {x=25y+35z950y+1225z=0950y1225z=0\iff \begin{cases} x = \frac{2}{5}y + \frac{3}{5}z \\ -\frac{9}{50}y + \frac{12}{25}z = 0 \\ \frac{9}{50}y - \frac{12}{25}z = 0 \end{cases}     {x=25×83z+35z=53zy=509×1225z=83z\iff \begin{cases} x = \frac{2}{5} \times \frac{8}{3} z + \frac{3}{5}z = \frac{5}{3}z \\ y = \frac{50}{9} \times \frac{12}{25}z = \frac{8}{3}z \end{cases}

Donc π\pi est de la forme π=(53z83zz)\pi = \begin{pmatrix} \frac{5}{3}z & \frac{8}{3}z & z \end{pmatrix}. De plus, la somme des coefficients de π\pi doit faire 11, donc :

53z+83z+z=1    163z=1    z=316\frac{5}{3}z + \frac{8}{3}z + z = 1 \iff \frac{16}{3}z = 1 \iff z = \frac{3}{16}.

Donc l’unique distribution invariante π\pi de (Xn)(X_n) est π=(51612316)=(0,31250,50,1875)\pi = \begin{pmatrix} \frac{5}{16} & \frac{1}{2} & \frac{3}{16} \end{pmatrix} = \begin{pmatrix} 0,3125 & 0,5 & 0,1875 \end{pmatrix}.

Vous avez aimé ce cours ?

Faîtes-le nous savoir dans les commentaires !

Avatar (prévisualisation)
Il n'y a pas de commentaire sur ce cours pour le moment.