Une introduction aux graphes probabilistes

Graphes probabilistes et état stable

En terminale générale maths expertes, on étudie plusieurs types de graphes afin de résoudre divers problèmes d’optimisation. Les graphes probabilistes sont particulièrement intéressants tant du point de vue du programme scolaire (synthèse des graphes orientés, des systèmes d’équations, des matrices, des suites et des probabilités) que de leurs prolongements appliqués (chaînes de Markov).

Le niveau de cette page est celui d'une initiation qui peut être complétée par les suites de matrices et l'exercice sur les marches aléatoires (extrait d'épreuve du bac).

 

Les graphes probabilistes

Une expérience aléatoire est répétée de façon identique et indépendante entre chaque unité de temps. Dans la mesure où les probabilités de passer d'un état à un autre (ou de rester au même) sont connues mais où le nombre de répétitions peut être infini, une représentation sous forme d’arbre est infaisable.

D’où le graphe probabiliste, orienté et pondéré. Les poids des arcs sont les probabilités de passer d’un état (un sommet) à un autre. Le poids total des arcs issus d’un même sommet est donc égal à 1.

Sa réalisation est une première étape. Elle n’est pas indispensable mais tout de même bien pratique.

Ensuite, on réécrit les données du graphe sous forme de matrice (voir les graphes et matrices).

 

Matrice de transition et état stable

Les pondérations des arcs sont les éléments d’une matrice carrée (dont l'ordre est égal au nombre de sommets). Celle-ci est appelée matrice de transition. C'est une matrice stochastique (la somme des coefficients de chaque ligne est égale à 1).

Le coefficient situé au croisement de la première ligne et de la première colonne est la probabilité pour un état \(A\) de se maintenir à l’étape suivante, au croisement de la deuxième ligne et de la première colonne se trouve la probabilité que l’état \(A\) devienne \(B\) à la période suivante, etc.

Soit \(T\) cette matrice et soit \(P_0\) la matrice-ligne décrivant l’état initial. On a alors \(P_0 × T = P_1.\) Plus généralement, si \(P_n\) est la matrice-ligne qui décrit un l’état de la période \(n,\) \(P_n × T = P_{n+1}.\) Et si l’on saute les étapes, \(P_n = P_0 × T^n.\) Lorsque la puissance \(n\) est infinie, \(T\) n’évolue plus. On a alors \(PT = P.\) On parle d’état stable ou de distribution stationnaire. Dans les applications pratiques, il n’est pas question d’infini mais souvent de « long terme ».

Notez que l'état stable est indépendant de la situation initiale.

 

Exercice

(D’après l’épreuve du bac de novembre 2013, Amérique du Sud)

    Une étude est réalisée chaque hiver sur des pratiquants de ski ou de snowboard : si une personne skie, alors la probabilité qu’elle pratique le snowboard l’hiver suivant est égale à 0,2. Si elle pratique le snowboard, la probabilité qu’elle skie l’année suivante est égale à 0,3.
    On note \(S\) l’état « la personne pratique le ski » et \(B\) l’état « la personne pratique le snowboard ».
    On note également \(p_n\) la probabilité qu’elle skie lors du énième hiver et \(q_n\) la probabilité qu’elle pratique le snowboard lors du énième hiver.
    \(P_n = \left( {\begin{array}{*{20}{c}} p_n&q_n \end{array}} \right)\) est la matrice-ligne donnant l’état probabiliste du système lors du énième hiver.
    On suppose que la population initiale ne comporte que des skieurs. On a donc \(P_0 = \left( {\begin{array}{*{20}{c}} 1&0 \end{array}} \right)\)
    Partie A
  1. Représenter la situation à l’aide d’un graphe probabiliste de sommets \(S\) et \(B.\)
  2. Décrire la situation sous forme d’un système d’équations.
  3. Montrer que, pour tout entier naturel \(n,\) on a \(p_{n+1} = 0,5p_n + 0,3.\)
  4. Déterminer l’état stable à l’aide du système.
  5. Donner la matrice de transition \(M\) de ce graphe probabiliste, puis calculer \(M^2\) et déterminer l’état probabiliste \(P_2.\)
  6. Retrouver l’état stable avec un calcul matriciel.
    Partie B
    La probabilité de l’évènement \(S_n\) (la personne skie lors du énième hiver) est notée \(p(S_n).\) On a donc \(p_n = p(S_n).\)
    Soit la suite \((u_n)\) définie pour tout entier naturel \(n\) par \(u_n = p_n - 0,6.\)
  1. Démontrer que la suite \((u_n)\) est une suite géométrique de raison 0,5 et préciser la valeur de \(u_0.\)
  2. En déduire l’expression de \(u_n\) en fonction de \(n\) puis l’expression de \(p_n\) en fonction de \(n.\)
  3. Déterminer la limite de la suite \((p_n)\) et interpréter le résultat.

skieur

 

Corrigé

Partie A

1-

graphe

2-

\(\left\{ {\begin{array}{*{20}{c}} {p_{n+1} = 0,8p_n + 0,3q_n}\\ {q_{n+1} = 0,2p_n + 0,7q_n}\\ {p_n + q_n = 1} \end{array}} \right.\)

3- \(p_{n+1} = 0,8p_n + 0,3(1 - p_n)\)
\(⇔ p_{n+1} = 0,8p_n + 0,3 - 0,3p_n\)
\(⇔ p_{n+1} = 0,5p_n + 0,3\)

4- Lorsque l’état est stable, \(p_{n+1} = p_n.\)

Donc \(p_n = 0,5p_n + 0,3\)
\(⇔ p_n = 0,6\)

D’où \(q_n = 1 - p_n = 0,4.\)

5- \(M = \left( {\begin{array}{*{20}{c}} 0,8&0,2\\ 0,3&0,7 \end{array}} \right)\)

\(M^2\) se détermine avec la calculatrice (voir la puissance d'une matrice carrée pour utilisation d'une Casio ou l'initiation aux matrices avec calculatrice TI).

\(M^2 = \left( {\begin{array}{*{20}{c}} 0,7&0,3\\ 0,45&0,55 \end{array}} \right)\)

6- On peut élever \(M\) à une puissance très grande. À la puissance 50, la calculatrice nous donne \(\left( {\begin{array}{*{20}{c}} 0,6&0,4\\ 0,6&0,4 \end{array}} \right)\)

Nous retrouvons le résultat de la question 4, à savoir \(p_n = 0,6\) et \(q_n = 0,4.\)

Partie B

1- \(u_n = p_n - 0,6\) et donc \(u_{n+1} = p_{n+1} - 0,6.\)

Or \(p_{n+1} = 0,5p_n + 0,3\) (partie A question 3).

Donc \(u_{n+1}\) \(=\) \(0,5p_n + 0,3 - 0,6\) \(=\) \(0,5p_n - 0,3\) \(=\) \(0,5u_n.\)

\((u_n)\) est une suite géométrique de raison 0,5 et de premier terme \(u_0\) \(=\) \(p_0 - 0,6\) \(=\) \(1 - 0,6\) \(=\) \(0,4.\)

2- D’après la définition d’une suite géométrique, \(u_n = 0,4 × 0,5^n.\)

Donc \(p_n = 0,4 × 0,5^n + 0,6\)

3- La raison de la suite \((u_n)\) est strictement comprise entre 0 et 1. Donc :

\(\mathop {\lim }\limits_{n \to + \infty } u(n) = 0\) donc \(\mathop {\lim }\limits_{n \to + \infty } p_n = 0,6\)

Pour la troisième fois, nous arrivons à ce résultat de \(p_n = 0,6\) (donc \(q_n = 0,4).\)

À long terme, le pourcentage de skieurs se stabilisera à \(60\%\) si les données du modèle ne changent pas.

 

état stable