Graphes probabilistes

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

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

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

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

bannière exemple

Exemple

On note $\text P_n=\begin{pmatrix} a_n&b_n \end{pmatrix}\text{ ou }\text P_n=\begin{pmatrix} a_n&b_n&c_n \end{pmatrix}$ ou la matrice ligne correspondant à l’état probabiliste à l’étape $n$.

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

$\text P_0=\begin{pmatrix} a_0&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} a_1&b_1 \end{pmatrix}&=\begin{pmatrix} a_0\times0,7+b_0\times0,2&a_0\times0,3+b_0\times0,8 \end{pmatrix}\\ &=\begin{pmatrix} 0,7a_0+0,2b_0&0,3a_0+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 $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.

bannière exemple

Exemple

graphe probabiliste spécialité mathématiques terminale ES

La matrice de transition de ce graphe probabiliste est : $\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

$n$ désigne un entier naturel non nul.
$\text{M}$ est la matrice de transition d’un graphe probabiliste.
$\text P_0$ 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 P_0\times \text{M}^n}$

bannière exemple

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 P_0\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 $\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}$.

bannière propriete

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

graphe probabiliste spécialité mathématiques terminale ES

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}$

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 $\text P_0=\begin{pmatrix} a_0&b_0 \end{pmatrix}$ 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 P_0\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 P_0\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}$

bannière à retenir

À retenir

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