Déjà plus de
1 million
d'inscrits !
Graphes probabilistes
Déjà plus de
1 million
d'inscrits !
Avant de commencer, regarde les vidéos suivantes
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
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 .
Le graphe suivant est un graphe probabiliste :
On peut voir qu’il s’agit bien d’un graphe orienté et pondéré et que :
É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 .
Cette loi est représentée par une matrice ligne dont la somme des termes vaut .
On note ou la matrice ligne correspondant à l’état probabiliste à l’étape .
Le graphe probabiliste précédent correspond à l’arbre pondéré ci-contre :
représente l’état probabiliste initial.
L’état probabiliste peut être déterminé à l’aide de l’arbre pondéré, on a :
Matrice de transition
Matrice de transition :
La matrice de transition d’un graphe probabiliste d’ordre dont les sommets sont numérotés de à est la matrice carrée d’ordre où le terme figurant en ligne et colonne est égal au poids de l’arête allant de vers si cette arête existe ou à sinon.
La matrice de transition de ce graphe probabiliste est : .
Matrice de transition d’un graphe probabiliste
désigne un entier naturel non nul.
est la matrice de transition d’un graphe probabiliste.
est la matrice ligne décrivant l’état initial.
est l’état probabiliste à l’étape .
On a alors :
Soit où alors au bout de étapes :
Recherche d’un état stable
Définition et propriété admise
État probabiliste stable :
Un état probabiliste 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 c’est-à-dire si .
Pour tout graphe probabiliste connexe à ou sommets, de matrice de transition il existe un unique état stable ou solution de l’équation matricielle .
Cet état stable est indépendant de l’état initial.
Et si tend vers l’infini, alors l’état probabiliste tend vers 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 on désigne par :
Traduire les données dans un graphe probabiliste
L’arête orientée de vers a pour poids puisqu’à chaque relevé 20 % des utilisateurs d’Aurora changent au profit de Bestmath.
L’arête orientée de vers a pour poids puisqu’à chaque relevé 25 % des utilisateurs de Bestmath changent au profit d’Aurora.
Déduire du graphe probabiliste la matrice de transition associée
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 l’état initial en janvier 2009, alors on peut écrire .
On peut calculer , l’état de la société en juillet 2009 :
On peut calculer ainsi tous les états de la société comme par exemple qui correspond à janvier 2010 :
On appelle l’état stable. Pour le déterminer, on utilise la propriété .
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 .
Ce qui mène au système suivant :
L’état probabiliste stable est donc
La somme des termes d’une matrice ligne associée à un état probabiliste est toujours égale à .