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 et matrice de transition
Graphe probabiliste
Graphe probabiliste
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$.
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
États probabilistes
É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$.
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$.
Le graphe probabiliste précédent correspond à l’arbre pondéré ci-contre :
$\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
Matrice de transition
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.
La matrice de transition de ce graphe probabiliste est : $\text M=\begin{pmatrix} 0,7&0,3\\0,2&0,8 \end{pmatrix}$.
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}$
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
Recherche d’un état stable
Définition et propriété admise
Définition et propriété admise
É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}$.
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
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}$
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}$
La somme des termes d’une matrice ligne associée à un état probabiliste est toujours égale à $1$.