Théorème de convergence pour les graphes probabilistes réguliers

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Hypothèse : M, ou l'une de ses puissances M^k, n'a aucun coefficient nul. • Conclusion : un unique état stable P, et P_n = P quel que soit P_0. • Toutes les lignes de M^n tendent vers P. • Sans l'hypothèse : absorption ou oscillation sont possibles.

Le cours

1. Théorème de convergence Soit M la matrice de transition d'un graphe probabiliste. Si M ne comporte aucun coefficient nul, ou plus généralement s'il existe une puissance M^k sans coefficient nul (graphe dit régulier), alors : 1. il existe un unique état stable P ; 2. quel que soit l'état initial P_0, la suite (P_n) converge vers P : _n + P_n = P 3. chaque ligne de M^n tend vers P : à long terme, l'état de départ est « oublié ». 2. Méthode 1. Vérifier l'hypothèse : chercher un zéro dans M ; s'il y en a, calculer M^2, M^3… 2. Déterminer l'état stable en résolvant PM = P avec la somme des coefficients égale à 1. 3. Conclure : P_n tend vers P, sans calculer P_n. Pour deux états, le théorème se démontre avec la suite arithmético-géométrique p_n+1 = (1 - a - b)p_n + b : si 0 3. Quand l'hypothèse n'est pas vérifiée État absorbant : une ligne du type pmatrix 1 & 0 pmatrix reste dans toutes les puissances de M ; le système finit souvent capturé, et la limite peut dépendre de P_0. Oscillation : avec M = pmatrix 0 & 1 \\ 1 & 0 pmatrix, un état stable existe mais la suite (P_n) peut alterner sans converger.

Dans ce chapitre

• Arbres pondérés et formule des probabilités totales de Première
• Produit scalaire et équations de droites dans le plan de Première
• Probabilités conditionnelles et suites arithmético-géométriques de Première
• Vocabulaire des graphes orientés et pondérés
• Graphes probabilistes et matrice de transition stochastique
• Distribution probabiliste à l'étape n
• Calcul explicite de l'état probabiliste par puissance de matrice
• Recherche et caractérisation de l'état stable
• Théorème de convergence pour les graphes probabilistes réguliers
• Étude complète d'une chaîne de Markov à deux états
• Modélisation de marches aléatoires et de processus stochastiques
• Graphes, matrice de transition et états probabilistes
• État stable et convergence à long terme
• Bilan : Synthèse et méthode sur Graphes probabilistes et chaînes de Markov