I – Graphe pondéré et graphe probabiliste

1. 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 :

Graphe 1

On a :

  • Le poids de l'arête vaut .
  • Le poids du chemin vaut .

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 .
  • Il y a au plus 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 ), soit soigné (que l'on note ). On suppose que pour cette maladie :

  • La probabilité qu'une personne malade guérisse le lendemain est .
  • La probabilité qu'une personne saine tombe malade le lendemain est .

Le graphe probabiliste modélisant cette situation est le graphe suivant :

Graphe 2

On remarque que la somme des poids des arêtes issues du sommet vaut (idem pour qui vaut ).

2. Matrice de transition

Définition

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

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

Exemple

Dans l'exemple précédent (en supposant que est le 1er sommet et que est le 2ème) la matrice de transition du graphe est .

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

II – Chaînes de Markov

1. 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 une suite de variables aléatoires discrètes définies sur un même univers et à valeurs dans un ensemble . On dit que définit une chaîne de Markov sur si pour tout et tout , l'événement ne dépend que de l'événement antérieur (et pas des précédents) ; autrement dit, si .

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

En français, cela signifie que si représente l'état d'un système à un temps , alors l'état suivant ne dépend que de l'état au temps et pas des états précédents.

De plus, notez bien que nous n'avons pas fait d'hypothèse sur le cardinal de (qui peut donc être de cardinal ). En classe de Terminale, nous nous limiterons principalement au cas où possède voire éléments, mais nous allons quand-même voir très bientôt un exemple de chaîne de Markov à états.

Variable aléatoire discrète

Une variable aléatoire définie sur un univers est dite discrète si est un ensemble dénombrable.

Chaîne de Markov homogène

Soit une chaîne de Markov dont on note l'espace des états. Alors est dite homogène si pour tout et pour tout , , la probabilité est indépendante de .

En termes mathématiques, cela signifie que pour tout et pour tout , , .

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 de tomber sur le -ième joueur (pour tout compris entre et ).

Si on note par le nombre de vignettes différentes dans la collection d'Eliott après qu'il eut ouvert paquets de céréales, on a que est une chaîne de Markov homogène (commençant par ). En effet, pour tout , on a que l'événement ne dépend que de :

éééééé

Pour détailler un peu plus :

  • Si on a , alors Eliott a déjà sa collection complète. Donc la probabilité que sa collection reste complète est égale à .
  • Si on a , alors la probabilité d'avoir est égale à la probabilité de ne pas tirer de nouveau joueur (qui est ).
  • Si on a , alors la probabilité d'avoir est égale à la probabilité de tirer un nouveau joueur (qui est ).
  • Sinon, comme on ne peut pas tirer deux nouveaux joueurs d'un coup ou en enlever un de la collection, la probabilité d'avoir est égale à .
  • Notons de plus que est homogène car le calcul de est indépendant de (mais reste dépendant de , attention).

De plus, on a que l'espace des états est .

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 paquets de céréales pour compléter une collection de vignettes.

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

Matrice de transition

Soit une chaîne de Markov homogène dont on note l'espace des états. La matrice de transition de est la matrice carrée d'ordre dont le coefficient situé à la -ième ligne et à la -ième colonne est égal à .

Comme cette probabilité est indépendante de , on peut tout à fait prendre dans la définition. On a alors .

Graphe associé à une chaîne de Markov

Soit une chaîne de Markov homogène dont on note l'espace des états. On associe à cette chaîne de Markov un graphe probabiliste d'ordre dont les sommets sont les états et dont les arêtes sont pondérées par les poids .

La matrice de transition de est égale à la matrice de transition du graphe probabiliste : il s'agit donc aussi d'une matrice stochastique.

Exemple

Reprenons l'exemple précédent. Alors la matrice de transition associée à est la matrice :

Et le graphe associé à est le graphe probabiliste d'ordre :

Graphe 3

3. Distributions dans une chaîne de Markov

Proposition

Soit une chaîne de Markov homogène dont on note l'espace des états. On pose pour tout (qui représente la probabilité que la chaîne de Markov passe de l'état à l'état en étapes). On a :

$\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 est homogène, pour tout .

Démonstration

Cette formule semble un petit peu compliquée à interpréter. Elle signifie simplement que la probabilité que la chaîne de Markov passe de l'état à l'état en étapes est égale à la probabilité qu'elle passe de l'état à en une étape, puis de passer de à en é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 la matrice de transition de , on a que est le coefficient à la ligne et à la colonne de la matrice .

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

Définition

Soit une chaîne de Markov homogène dont on note l'espace des états. On appelle suite des distributions de la suite de matrices , définie pour tout par .

est donc une matrice ligne d'ordre et est appelée distribution au temps .

(la distribution au temps ) 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 donné.

Relation entre et

En reprenant les notations de la définition précédente et en notant la matrice de transition de , on a que la suite vérifie une relation de récurrence donnée pour tout par .

On en déduit que pour tout , .

Démonstration

Exemple

Intéressons-nous à l'alimentation d'un chat durant la journée. Il dispose de trois gamelles différentes , et 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 :

Graphe 4

On note par la variable aléatoire qui donne la gamelle qu'a choisi le chat à la -ième heure. On a donc que est une chaîne de Markov homogène dont l'espace des états est . Si on note la suite des distributions de , on a alors que .

Soit la matrice de transition de . Calculons quelques puissances de :

Ainsi :

Et par exemple : la probabilité que le chat passe à sa gamelle de croquettes 3 heures après le lait est d'environ 47 %.

4. Distribution invariante

Définition

Soit une chaîne de Markov homogène de matrice de transition . Une distribution est invariante si les deux conditions suivantes sont respectées :

  • (donc si est une distribution à un temps , on a et cette condition se résume à avoir ).
  • La somme des coefficients de vaut .

Existence et unicité de la distribution invariante au temps

Soit une chaîne de Markov homogène de matrice de transition .

Si ne possède aucun coefficient non nul autre que sur sa diagonale, alors admet une unique distribution invariante .

Convergence de la distribution

Soit une chaîne de Markov homogène dont on note la suite des distributions.

  • Si est une suite de matrices convergente, alors elle converge vers une distribution invariante .
  • Si le cardinal de l'ensemble des états de est , alors est convergente (et converge vers la distribution invariante ).

Exemple

Reprenons l'exemple précédent et voyons si admet une distribution invariante.

Remarquons tout d'abord que la matrice de transition ne possède aucun coefficient non nul. Donc admet une unique distribution invariante .

Posons donc et déterminons , et :

On doit avoir

(en passant en écriture fractionnaire)

Donc est de la forme . De plus, la somme des coefficients de doit faire , donc :

.

Donc l'unique distribution invariante de est .

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.