Cours : Graphes probabilistes

Graphe probabiliste et matrice de transition

Graphe probabiliste

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

Exemple

Le graphe suivant est un graphe probabiliste :

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 $A$ est $0,7+0,3=1$
• la somme des poids des arêtes issues de $B$ est $0,8+0,2=1$

États probabilistes

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 $n$.

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

Exemple

On note $\text P$n=\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 $n$.

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

$\text P$0=\begin{pmatrix} a0&b_0 \end{pmatrix} représente l’état probabiliste initial.

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

$\begin{aligned}\text P$1=\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

Définition

Matrice de transition :

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

Exemple

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

Propriété

Matrice de transition d’un graphe probabiliste

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

On a alors : $\boxed{\text P$n=\text P0\times \text{M}^n}

Exemple

Soit $\text M=\begin{pmatrix} 0,7&0,3\0,2&0,8 \end{pmatrix}$ où $\text P_0=\begin{pmatrix} 0,5&0,5 \end{pmatrix}$ alors au bout de $n=3$ étapes :

$\begin{aligned}\boxed{\text P$3=\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

Définition

État probabiliste stable :

Un état probabiliste $\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 $\text M$ c’est-à-dire si $\;\boxed{\text P\times\text M=\text P}$.

Propriété

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

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

Et si $n$ tend vers l’infini, alors l’état probabiliste $\text P_n$ tend vers l’état stable $\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 $n$ on désigne par :

• $a_n$ la probabilité qu’un informaticien pris au hasard utilise Aurora le semestre $n$ ;
• $b_n$ la probabilité qu’un informaticien pris au hasard utilise Bestmath le semestre $n$.

Traduire les données dans un graphe probabiliste

L’arête orientée de $A$ vers $B$ a pour poids $0,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 $A$ vers $A$ a pour poids $0,8$ car $1-0,2=0,8$ (cela correspond aux 80 % des utilisateurs qui continuent d’utiliser Aurora).

L’arête orientée de $B$ vers $A$ a pour poids $0,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 $B$ vers $B$ a pour poids $0,75$ car $1-0,25=0,75$.

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

$\text M=\begin{pmatrix} 0,8&0,2\0,25&0,75 \end{pmatrix}$

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 $\text P$0=\begin{pmatrix} a0&b0 \end{pmatrix}P0​=(a0​​b0​​) l’état initial en janvier 2009, alors on peut écrire $\text P$0=\begin{pmatrix} 0,32&0,68 \end{pmatrix}.

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

$\begin{aligned}\boxed{\text P$1=\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 $\text{P}_2$ qui correspond à janvier 2010 :

$\begin{aligned}\boxed{\text P$2=\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 $\text P\begin{pmatrix} x&y \end{pmatrix}$ l’état stable. Pour le déterminer, on utilise la propriété $\text P\times\text M=\text P$.

$\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=1$.

Ce qui mène au système suivant :

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

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

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

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

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

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

$\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 $\text P=\begin{pmatrix} \dfrac59&\dfrac49 \end{pmatrix}$

À retenir

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