Une introduction aux graphes probabilistes

Graphes probabilistes et état stable

En terminale ES et terminale S spécialité maths, 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 et des probabilités) que de leurs prolongements appliqués (chaînes de Markov).

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 de tel état à tel 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 la page graphes et matrices).

La matrice de transition et l'é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).

L’élément 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 M cette matrice et soit P0 la matrice-ligne décrivant l’état initial. On a alors P0 × M = P1. Plus généralement, si Pn est la matrice-ligne qui décrit un l’état de la période n, Pn × MPn+1. Et si l’on veut sauter les étapes, Pn = p0 × Mn. Lorsque la puissance n est infinie, M n’évolue plus. On parle d’état stable. Dans les applications pratiques, il n’est pas question d’infini mais souvent de « long terme ». On a alors PM = P.

Exemple (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 pn la probabilité qu’elle skie lors du énième hiver et qn la probabilité qu’elle pratique le snowboard lors du énième hiver.

Pn = (pn  qn) 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 P0 = (1  0).

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 pn+1 = 0,5pn + 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² et déterminer l’état probabiliste P2.
  6. Retrouver l’état stable avec un calcul matriciel.

Partie B

La probabilité de l’évènement Sn (la personne skie lors du énième hiver) est notée p(Sn). On a donc pn = p(Sn).

Soit la suite (un) définie pour tout entier naturel n par un = pn – 0,6.

  1. Démontrer que la suite (un) est une suite géométrique de raison 0,5 et préciser la valeur de u0.
  2. En déduire l’expression de un en fonction de n puis l’expression de pn en fonction de n.
  3. Déterminer la limite de la suite (pn) et interpréter le résultat.

Corrigé

Partie A

1-

graphe

2-

système

3- pn+1 = 0,8pn + 0,3(1 – pn)
pn+1 = 0,8pn + 0,3 – 0,3pn
pn+1 = 0,5pn + 0,3

4- Lorsque l’état est stable, pn+1 = pn.

Donc pn = 0,5pn + 0,3
pn = 0,6

D’où qn = 1 – pn = 0,4.

5-

M

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

M²

6- On peut élever M à une puissance très grande. À la puissance 50, la calculatrice nous donne :

M puiss 50

Nous retrouvons le résultat de la question 4, à savoir pn = 0,6 et qn = 0,4.

Partie B

1- unpn – 0,6 et donc un+1 = pn+1 – 0,6.

Or pn+1 = 0,5pn + 0,3 (partie A question 3).

Donc un+1 = 0,5pn + 0,3 – 0,6 = 0,5pn – 0,3 = 0,5un.

(un) est une suite géométrique de raison 0,5 et de premier terme u0 = p0 – 0,6 = 1 – 0,6 = 0,4.

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

Donc pn = 0,4 × 0,5n + 0,6

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

lim un = 0 et lim pn = 0,6

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

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