Graphes et chaînes de Markov
2 CHAÎNE DE MARKOV Propriété 1 : La matrice de transition d’une chaîne de Markov homogène est une matrice stochastique À une matrice d’une chaîne de Markov homogène, on peut associer un graphe probabiliste dont les sommets sont les états de l’espace E et les arcs reliant l’état i à l’état j sont affectés des
Chaînes de Markov - Université Paris-Saclay
chaque ligne de la matrice de transition Exemple On représente usuellement une chaîne de Markov d’espace d’états X par un graphe orienté étiqueté G =(V,E
GRAPHES (Partie 2) - Maths & tiques
3) Matrice de transition Définition : Soit G un graphe probabiliste d'ordre n dont les sommets sont numérotés de 1 à n La matrice de transition de G est la matrice carrée d'ordre n dont le coefficient situé sur la ligne i et la colonne j est la probabilité portée par l'arc reliant le sommet i vers le sommet j s'il existe et 0 dans le
Matrices et Graphes - Académie de Versailles
La matrice de transition P associée à cette chaîne de Markov est la matrice carrée d'ordre ntelle que, pour tout i2Eet pour tout j2E, le coe cient p ij correspond à la probabilité de transition de l'état ià l'état j Remarque : Cette année on se limitera au cas où n= 2 ou n= 3 Exemples : B V 0;8 0; 2 0; 4 0;6
E Les graphes probabilistes
La situation précédente peut être schématisée par le graphe probabiliste ci-dessous et sa matrice de transition M= 0,6 0,4 0,2 0,8 Page 3/4 2012-2013
CHAPITRE 3 GRAPHES PROBABILISTES 1 Graphe probabiliste
Définition : la matrice de transition d'un graphe probabiliste d'ordre n est la matrice carrée d'ordre n telle que le coefficient a i, j est égal au poids de l'arête orientée allant de i vers j si cette arête existe, 0 sinon
Graphes et matrices
La matrice de transition de ce graphe est : M = 0,8 0,2 0,3 0,7 * L'information (2) donne la répartition initiale de cette situation Cette répartition initiale s'appelle par l'état probabiliste initial On le note à l'aide d'une matrice ligne ( noté P0) et on a donc P0 = ( 0,35 0,65 )
introduction aux chaînes de Markov et aux martingales
Table des matières I Chaînes de Markov 9 1 De la marche aléatoire aux jeux de cartes 11 2 Propriété de Markov 17 2 1 Propriété de Markov et matrice de
Chaines de Markov et application au Pagerank
Consid erez une des matrices de transitions vue en TD On rappelle le Lemme vu en cours : Lemme 1 Soit Pune matrice de transition irr eductible et ap eriodique Alors Pn converge vers une matrice dont toutes les lignes sont egales a la mesure invariante Estimer la probabilit e invariante par la m ethode de la puissance
[PDF] matrice de transition markov
[PDF] matrice de transition d'état
[PDF] journal anne frank résumé
[PDF] querelle des anciens et des modernes dates
[PDF] wikipedia la querelle des anciens et des modernes
[PDF] matrice de transition exercices corrigés
[PDF] definition generale des coefficients techniques de production
[PDF] fiche technique café
[PDF] intensité du café
[PDF] modèle fermé de leontief
[PDF] tableau intensité café nespresso
[PDF] exercices corrigés de comptabilité nationale sur le tableau entrée sortie pdf
[PDF] principales étapes transformation café pdf
[PDF] arômes du café
2012-2013
Spécialité Mathématiques
Term ES
E. Les graphes probabilistes
1 PrésentationDéfinition 1Un grapheprobabilisteest un grapheorientéetpondérédans lequel :
•il y a au plus un arc d"un sommet à l"autre; •la somme des poids des arcs issus d"un même sommet est égale à 1.REMARQUES :
1. Le sp oidsdes arcs son talors des probabilités (nom bresréels compris en tre0 et 1). 2.Un gra pheprobabiliste indique les différen tsétats p ossiblesd"un système (sommets du graphe) et
les probabilités de passage d"un état à l"autre (poids des arcs).Exemple 1
•Le graphe n°1 est un graphe probabiliste d"ordre 2. •Le graphe n°2 est un graphe probabiliste d"ordre 3.•Le graphe n°3 n"est pas un graphe probabiliste car la somme des poids des arcs issus du sommet C
est égale à 0,9 et non à 1.2 État probabiliste et matrice de transitionDéfinition 2
Soit une expérience aléatoire à deux issues possibles A et B. A chacune de ces issues est affectée une probabilité,pAetpB.Lorsque l"on répète cette expérience, dans les mêmes conditions, on se retrouve après chaque réali-
sation dans un état donné. Cet état à l"issue de chacune des réalisations de l"expérience est appelé
état probabiliste.
Il peut être représenté par une matrice lignePn=?a nbn?qui traduit la probabilité d"obtenir l"issue A ou l"issue B aprèsnréalisation de l"expérience aléatoire.On aan+bn= 1, pour tout entier natureln.Page 1/4
2012-2013
Spécialité Mathématiques
Term ES
REMARQUE :
On généralise sans difficulté cette définition à une expérience aléatoire ayant un nombrenfini d"issues
possibles (n≥2).Définition 3 Soit G un graphe probabiliste d"ordrendont les sommets sont numérotés de 1 àn. Lamatrice de transitionM de G est la matrice carrée d"ordrentelle quemijest égal à la probabilité portée par l"arc reliant le sommetiau sommetjs"il existe et 0 sinon.REMARQUE :
La matrice de transition M permet d"étudier l"évolution du système que schématise le graphe probabi-
liste.Exemples 1
•La matrice de transitionM1associée au graphe ci-contre est (en supposant les sommets rangés dans l"ordre alphabétique) :M1=?0,55 0,450,8 0,2?
•La matrice de transistionM2associées au graphe ci-contre est (en supposant les sommets rangés dans l"ordre alphabétique) : M 2=( (0,75 0,1 0,150,4 0,4 0,2
0,6 0,1 0,3)
)Propriété 1 SoitMla matrice de transition d"un graphe probabiliste associé à un système donné. SoitP0la matrice-ligne décrivant l"état initial du système étudié.SoitPnla matrice-ligne décrivant l"état probabiliste à l"étapendu système étudié.
On a les relations :
P n+1=Pn×M Pn=P0×MnDémonstration(pour un graphe d"ordre 2) :
Soit un graphe probabiliste d"ordre 2 de matrice de transitionM=?α1-αβ1-β?
traduisant un système à deux étatsAetB, et soitnun entier naturel. •SoitAnl"évènement : "on obtientAà l"étapen". •SoitBnl"évènement : "on obtientBà l"étapen". •SoitPn=?a nbn?la matrice-ligne décrivant l"état probabiliste à l"étapen. •SoitPn+1=?a n+1bn+1?la matrice-ligne décrivant l"état probabiliste à l"étapen+ 1.Page 2/42012-2013
Spécialité Mathématiques
Term ES
On considère l"arbre pondéré suivant :On a les relations (formule des probabilités totales) :
a n+1=P(An+1) =PAn(An+1)×P(An) +PBn(An+1)×P(Bn) =αan+βbn b n+1=P(Bn+1) =PAn(Bn+1)×P(An) +PBn(Bn+ 1)×P(Bn) = (1-α)an+ (1-β)bn Cela se traduit en écriture matricielle par :Pn+1=Pn×M.On a alors :P1=P0×M
P2=P1×M=P0×M×M=P0×M2
P3=P2×M=P0×M2×M=P0×M3
P n=Pn-1×M=P0×Mn-1×M=P0×MnREMARQUE :
La matriceMnpermet de trouver l"état probabiliste à l"étapen.Exemple(d"après Bac ES La Réunion 2008)
Les joueurs d"un club de football sont partagés en deux équipes : une équipeAet une équipeB.
L"entraîneur change la composition de ces équipes après chacun des matchs, suivant les performances
des joueurs. Une étude statistique menée au cours des saisons précédentes permet d"estimer que :•si un joueur fait partie de l"équipeA, la probabilité qu"il reste dans cette équipe pour le match suivant
est 0,6;•si un joueur fait partie de l"équipeB, la probabilité qu"il change d"équipe le match suivant est 0,2.
La situation précédente peut être schématisée par le graphe probabiliste ci-dessous et sa matrice de
transition.M=?0,6 0,40,2 0,8?Page 3/4
2012-2013
Spécialité Mathématiques
Term ES
Pour une entier naturelndonné, on notePn=?a
nbn?la matrice-ligne décrivant l"état probabiliste lors du matchn. Enzo vient d"arriver dans le club et la probabilitéa0qu"il joue dans l"équipeApour le match de préparation (match 0) est 0,1. •L"état probabiliste initial est doncP0=?0,1 0,9?. •On a donc, par exemple,P1=P0×M=?0,24 0,76?. La probabilitéa1qu"Enzo joue dans l"équipeApour le match 1 est 0,24. •On a aussi, par exemple,P2=P0×M2=?0,296 0,704? La probabilitéa2qu"Enzo joue dans l"équipeApour le match 2 est 0,296.3 État stableDéfinition 4
Soit un graphe probabiliste d"ordrenassocié à une expérience donnée.On appelleétat stableun état probabiliste qui n"évolue pas lors de la répétition de l"expérience.
Exemple
Soit l"état initialP0=?0,4 0,6?et la matrice de transitionM=?0,7 0,30,2 0,8?
On vérifie aisément queP1=P0et, de proche en proche que,Pn=P0pour tout entier natureln. L"état décrit par la matriceP0est donc un état stable.Propriété 2(admise)Soit un graphe probabiliste d"ordre 2 dont la matrice ne comporte pas de 0. L"état probabilistePnà
l"étapenconverge vers un étatPindépendant de l"état initialP0. L"étatPest appeléétat stable du système: il vérifie l"égalitéPM=P.Page 4/4quotesdbs_dbs26.pdfusesText_32