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.

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.

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.

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}).

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).

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).

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.

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}.

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.

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).