Médaille
N°1 pour apprendre & réviser du collège au lycée.

Graphes probabilistes

Déjà plus de

1 million

d'inscrits !

​Introduction :

Cette leçon fait le lien entre graphes et probabilités. Nous allons voir tout d’abord les définitions d’un graphe probabiliste, d’un état probabiliste et d’une matrice de transition.
Nous verrons ensuite la propriété de l’état stable et nous prendrons un exemple d’exercice afin d’en détailler la méthode de résolution.

Graphe probabiliste et matrice de transition

Graphe probabiliste

bannière definition

Définition

Graphe probabiliste :

Un graphe probabiliste est un graphe orienté et pondéré dont la somme des poids des arêtes issues de chaque sommet vaut 11.

bannière exemple

Exemple

Le graphe suivant est un graphe probabiliste :

graphe probabiliste spécialité mathématiques terminale ES

On peut voir qu’il s’agit bien d’un graphe orienté et pondéré et que :

  • la somme des poids des arêtes issues de AA est 0,7+0,3=10,7+0,3=1
  • la somme des poids des arêtes issues de BB est 0,8+0,2=10,8+0,2=1

États probabilistes

bannière definition

Définition

État probabiliste d’un système :

L’état probabiliste d’un système est une loi de probabilité sur l’ensemble des états possibles au cours d’une étape nn.

Cette loi est représentée par une matrice ligne dont la somme des termes vaut 11.

bannière exemple

Exemple

On note Pn=(anbn) ou Pn=(anbncn)\text Pn=\begin{pmatrix} an&bn \end{pmatrix}\text{ ou }\text Pn=\begin{pmatrix} an&bn&c_n \end{pmatrix} ou la matrice ligne correspondant à l’état probabiliste à l’étape nn.

graphe probabiliste spécialité mathématiques terminale ES

Le graphe probabiliste précédent correspond à l’arbre pondéré ci-contre :

graphe probabiliste arbre pondéré spécialité mathématiques terminale ES

P0=(a0b0)\text P0=\begin{pmatrix} a0&b_0 \end{pmatrix} représente l’état probabiliste initial.

L’état probabiliste P1\text P_1 peut être déterminé à l’aide de l’arbre pondéré, on a :

P1=(a1b1)=(a0×0,7+b0×0,2a0×0,3+b0×0,8)=(0,7a0+0,2b00,3a0+0,8b0)\begin{aligned}\text P1=\begin{pmatrix} a1&b1 \end{pmatrix}&=\begin{pmatrix} a0\times0,7+b0\times0,2&a0\times0,3+b0\times0,8 \end{pmatrix}\ &=\begin{pmatrix} 0,7a0+0,2b0&0,3a0+0,8b_0 \end{pmatrix} \end{aligned}

Matrice de transition

bannière definition

Définition

Matrice de transition :

La matrice de transition d’un graphe probabiliste d’ordre nn dont les sommets sont numérotés de 11 à nn est la matrice carrée d’ordre nn où le terme figurant en ligne ii et colonne jj est égal au poids de l’arête allant de ii vers jj si cette arête existe ou à 00 sinon.

bannière exemple

Exemple

graphe probabiliste spécialité mathématiques terminale ES

La matrice de transition de ce graphe probabiliste est : M=(0,70,30,20,8)\text M=\begin{pmatrix} 0,7&0,3\0,2&0,8 \end{pmatrix}.

bannière propriete

Propriété

Matrice de transition d’un graphe probabiliste

nn désigne un entier naturel non nul.
M\text{M} est la matrice de transition d’un graphe probabiliste.
P0\text P0 est la matrice ligne décrivant l’état initial.
Pn\text P
n est l’état probabiliste à l’étape nn.

On a alors : Pn=P0×Mn\boxed{\text Pn=\text P0\times \text{M}^n}

bannière exemple

Exemple

Soit M=(0,70,30,20,8)\text M=\begin{pmatrix} 0,7&0,3\0,2&0,8 \end{pmatrix}P0=(0,50,5)\text P_0=\begin{pmatrix} 0,5&0,5 \end{pmatrix} alors au bout de n=3n=3 étapes :

P3=P0×M3=(0,50,5)×(0,70,30,20,8)3=(0,50,5)×(0,4750,5250,350,65)=(0,41250,5875)\begin{aligned}\boxed{\text P3=\text P0\times \text M^3}&=\begin{pmatrix} 0,5&0,5 \end{pmatrix}\times\begin{pmatrix} 0,7&0,3\0,2&0,8 \end{pmatrix}^3\&=\begin{pmatrix} 0,5&0,5 \end{pmatrix}\times\begin{pmatrix} 0,475&0,525\0,35&0,65 \end{pmatrix}\&=\begin{pmatrix} 0,4125&0,5875 \end{pmatrix}\end{aligned}

Recherche d’un état stable

Définition et propriété admise

bannière definition

Définition

État probabiliste stable :

Un état probabiliste P\text P est dit stable lorsqu’il se conserve lors de la répétition de l’expérience aléatoire décrite par la matrice de transition M\text M c’est-à-dire si   P×M=P\;\boxed{\text P\times\text M=\text P}.

bannière propriete

Propriété

Pour tout graphe probabiliste connexe à 22 ou 33 sommets, de matrice de transition M\text M il existe un unique état stable P=(xy)\text P=\begin{pmatrix} x&y \end{pmatrix} ou P=(xyz)\text P=\begin{pmatrix} x&y&z \end{pmatrix} solution de l’équation matricielle P×M=P\text P\times\text M=\text P.

Cet état stable est indépendant de l’état initial.

Et si nn tend vers l’infini, alors l’état probabiliste Pn\text P_n tend vers l’état stable P\text P.

Méthode de résolution d’un problème portant sur l’état stable

Énoncé : tiré du bac 2010 de Polynésie

Dans une société, le service informatique utilise deux logiciels de gestion : Aurora, leader du marché, et Bestmath, son concurrent.

Le chef du réseau informatique enregistre chaque année, en janvier et en juillet, le nombre d’utilisateurs des deux logiciels. Lors de l’enquête de janvier 2009, le chef du réseau informatique a constaté que 32 % des informaticiens utilisaient le logiciel Aurora, les autres utilisaient Bestmath.

Lors de chaque relevé suivant (juillet 2009, janvier 2010…) le chef du réseau informatique a constaté que 20 % des utilisateurs de Aurora avaient changé de logiciel pour Bestmath, tandis que 25 % des utilisateurs de Bestmath avaient changé de logiciel pour Aurora.

Pour tout entier naturel nn on désigne par :

  • ana_n la probabilité qu’un informaticien pris au hasard utilise Aurora le semestre nn ;
  • bnb_n la probabilité qu’un informaticien pris au hasard utilise Bestmath le semestre nn.

graphe probabiliste spécialité mathématiques terminale ES

Traduire les données dans un graphe probabiliste

L’arête orientée de AA vers BB a pour poids 0,20,2 puisqu’à chaque relevé 20 % des utilisateurs d’Aurora changent au profit de Bestmath.

  • Cette donnée de l’énoncé permet également d’en déduire que la boucle orientée de AA vers AA a pour poids 0,80,8 car 10,2=0,81-0,2=0,8 (cela correspond aux 80 % des utilisateurs qui continuent d’utiliser Aurora).

L’arête orientée de BB vers AA a pour poids 0,250,25 puisqu’à chaque relevé 25 % des utilisateurs de Bestmath changent au profit d’Aurora.

  • Cette donnée de l’énoncé te permet également d’en déduire que la boucle orientée de BB vers BB a pour poids 0,750,75 car 10,25=0,751-0,25=0,75.

Déduire du graphe probabiliste la matrice de transition associée

M=(0,80,20,250,75)\text M=\begin{pmatrix} 0,8&0,2\0,25&0,75 \end{pmatrix}

bannière attention

Attention

Il faut penser à bien respecter l’ordre alphabétique des sommets en écrivant la matrice.

D’après l’énoncé, 32 % des informaticiens utilisent Aurora en janvier 2009 ce qui signifient que 68 % utilisent Bestmath. Si l’on note P0=(a0b0)\text P0=\begin{pmatrix} a0&b0 \end{pmatrix} l’état initial en janvier 2009, alors on peut écrire P0=(0,320,68)\text P0=\begin{pmatrix} 0,32&0,68 \end{pmatrix}.

On peut calculer P1\text{P}_1, l’état de la société en juillet 2009 :

P1=P0×M1=(0,320,68)×(0,80,20,250,75)=(0,4260,574)\begin{aligned}\boxed{\text P1=\text P0\times\text M^1} &=\begin{pmatrix} 0,32&0,68 \end{pmatrix}\times \begin{pmatrix} 0,8&0,2\0,25&0,75 \end{pmatrix}\&=\begin{pmatrix} 0,426&0,574 \end{pmatrix}\end{aligned}

On peut calculer ainsi tous les états de la société comme par exemple P2\text{P}_2 qui correspond à janvier 2010 :

P2=P0×M2=(0,320,68)×(0,80,20,250,75)2=(0,48430,5157)\begin{aligned}\boxed{\text P2=\text P0\times\text M^2} &=\begin{pmatrix} 0,32&0,68 \end{pmatrix}\times \begin{pmatrix} 0,8&0,2\0,25&0,75 \end{pmatrix}^2\&=\begin{pmatrix} 0,4843&0,5157 \end{pmatrix}\end{aligned}

On appelle P(xy)\text P\begin{pmatrix} x&y \end{pmatrix} l’état stable. Pour le déterminer, on utilise la propriété P×M=P\text P\times\text M=\text P.

P×M=P(xy)×(0,80,20,250,75)=(xy)(0,8x+0,25y0,2x+0,75y)=(xy)\begin{aligned} \boxed{\text P\times\text M=\text P} &\Leftrightarrow\begin{pmatrix} x&y \end{pmatrix}\times\begin{pmatrix} 0,8&0,2\0,25&0,75 \end{pmatrix}=\begin{pmatrix} x&y \end{pmatrix}\ &\Leftrightarrow\begin{pmatrix} 0,8x+0,25y&0,2x+0,75y \end{pmatrix}=\begin{pmatrix} x&y \end{pmatrix}\end{aligned}

Les deux équations de ce système sont identiques ; il est donc impossible de résoudre le système puisque nous ne disposons pour le moment que d’une seule équation à deux inconnues. Donc x+y=1x+y=1.

Ce qui mène au système suivant :

{0,2x=0,25yx+y=1\bigg\lbrace \begin{aligned}0,2x&=0,25y\x+y&=1\end{aligned}

{0,2x=0,25yx=1y\Leftrightarrow\bigg\lbrace \begin{aligned}0,2x&=0,25y\x&=1-y\end{aligned}

{0,2(1y)=0,25yx=1y\Leftrightarrow\bigg\lbrace \begin{aligned}0,2(1-y)&=0,25y\x&=1-y\end{aligned}

{0,20,2y=0,25yx=1y\Leftrightarrow\bigg\lbrace \begin{aligned}0,2-0,2y&=0,25y\x&=1-y\end{aligned}

{0,2=0,45yx=1y\Leftrightarrow\bigg\lbrace \begin{aligned}0,2&=0,45y\x&=1-y\end{aligned}

{y=0,20,45=49x=1y\Leftrightarrow\bigg\lbrace \begin{aligned}y&=\dfrac{0,2}{0,45}=\dfrac{4}{9}\x&=1-y\end{aligned}

{y=49x=149=59\Leftrightarrow\bigg\lbrace \begin{aligned}y&=\dfrac{4}{9}\x&=1-\dfrac{4}{9}=\dfrac{5}{9}\end{aligned}

L’état probabiliste stable est donc P=(5949)\text P=\begin{pmatrix} \dfrac59&\dfrac49 \end{pmatrix}

bannière à retenir

À retenir

La somme des termes d’une matrice ligne associée à un état probabiliste est toujours égale à 11.