Modélisation et Simulation des S.E.D. Master ISC David GOUYON Chaînes de Markov

Modélisation et Simulation des S.E.D. Master ISC David GOUYON Chaînes de Markov Stochastique / Déterministe • Déterministe : aucune entrée n’est de nature aléatoire • Stochastique : variables aléatoires, phénomènes aléatoires, – le comportement du système est décrit de manière probabiliste Les Chaînes de Markov • Nous considérons deux exemples de processus stochastiques à espace d’état discret – Chaînes de Markov à temps discret (CMTD) – Chaînes de Markov à temps continu (CMTC) • Chaînes de Markov : analyse préliminaire à l’étude des systèmes de files d’attente Les chaînes de Markov à temps discret • Processus stochastique à espace d’état discret et à temps discret • E est l’espace d’états – De dimension finie ou infinie (mais dénombrable car discret) X ∈ℕ 0 1 2 3 4 5 6 7 8 0 2 4 6 8 10 n E Processus stochastique à espace d’état discret et à temps discret Les chaînes de Markov à temps discret • Définition : est une chaîne de Markov à temps discret ssi • La probabilité pour que la chaîne soit dans un certain état à la nième « étape » du processus ne dépend que de l’état du processus à l’étape précédente (j = n-1), et pas des états dans lesquels il se trouvait aux étapes antérieures (j = 0, …, n-2) • Autrement dit : – Une chaîne de Markov est un système pouvant évoluer entre n états Xi définis par le repère X = (X1, X2, … Xn), – Le passage d’un état Xi à un état Xj ou transition, de dépend que de ces deux états et s’effectue selon la probabilité conditionnelle Prob(Xj/Xi) = pij • Notons que : X ∈ℕ P X  j |Xn 1 in 1, Xn 2 in 2, . . . , X i  P X  j |Xn 1 in 1  pij  1 ∈ pij  0 et Les chaînes de Markov à temps discret • Matrice de transition  ≜ , ∈ – Matrice carrée d’ordre fini ou infini, selon que l’espace d’état est fini ou infini P    . . .   . . .   . . . . . . . . . . . . . . . . . . . . . . . .  . . . . . . ij . . . . . . . . . . . . . . . . . . Les chaînes de Markov à temps discret • Représentation graphique – Graphe orienté – On associe à chaque état un nœud – On associe à chaque transition possible entre chaque état un arc pondéré par la probabilité de transition • Exemple : 1 3 2 4 p14 p41 p31 p12 p23 p33 E = {1,2,3,4} p23 = p41 = 1 P12 + p14 = 1 et p31 + p33 = 1 P  0 p 0 p 0 0 1 0 p! 0 p!! 0 1 0 0 0 Les chaînes de Markov à temps discret • Modélisation – On s’intéresse à l’état du système à des instants particuliers tn de leur évolution – Deux cas : • Intervalles de temps réguliers (tous les jours, toutes les heures …) – > l’état du système à l’étape n du processus est l’état du système au nième jour • Intervalles de temps quelconques (tn est l’instant du nième changement) – > l’état du système à l’étape n du processus correspond à l’état juste après le nième changement d’état 0 1 2 3 4 5 6 7 8 0 2 4 6 8 10 n E 0 1 2 3 4 5 6 7 8 0 2 4 6 8 10 n E CMTD à instants de changement d’états équidistants CMTD à instants de changement d’états quelconques Les chaînes de Markov à temps discret • Exemple : souris dans un labyrinthe – 5 pièces reliées entre elles par des couloirs à sens unique – 1 sortie – La souris ne peut faire demi tour dans un couloir – Une fois dans la pièce 5, la souris ne peut faire demi-tour – Tant que la souris n’est pas tombée dans la pièce 5, elle continue son chemin 5 1 2 3 4 Les chaînes de Markov à temps discret • Exemple : souris dans un labyrinthe – On s’intéresse uniquement à la succession des pièces visitées et pas au temps passé dans chacune, ni au temps passé dans les couloirs – Hypothèses : • La souris ne garde pas la mémoire des pièces précédemment visitées • Quand la souris est dans une pièce, elle choisit un couloir de façon équiprobable 1 3 2 4 5 6 1/2 1/2 1/4 1/4 1/4 1/4 1/2 1/2 5 1 2 3 4 Les chaînes de Markov à temps discret • Exemple : souris dans un labyrinthe 1 3 2 4 5 6 1/2 1/2 1/4 1/4 1/4 1/4 1/2 1/2 Sortie : état absorbant état absorbant • Les transitions modélisent les couloirs • Les probabilités associées à ces transitions modélisent un choix aléatoire d’un des couloirs de sortie parmi tous ceux possibles partant d’une pièce donnée • Le rebouclage sur l’état 6 est nécessaire pour le modèle et signifie simplement que lorsque la sourie est sortie, elle ne peut rentrer de nouveau dans le labyrinthe • Sachant que la souris est initialement dans la pièce 2 : • Quelle est la probabilité qu’elle y soit à nouveau après 4 déplacements ? (notation π2 (4)) • Combien de fois passera-t-elle en moyenne par la pièce 3 avant de sortir ou de tomber dans la pièce 5 ? (R23) • Quelle est la probabilité que la souris trouve la sortie ? (f26) • Combien fera-t-elle de déplacements en moyenne pour revenir dans la pièce 2 ? (M2) Exemple : téléphone • Considérons un téléphone (simplifié) pouvant recevoir un appel à la fois – Un seul appel peut avoir lieu dans une unité de temps, avec une probabilité α – Si le téléphone est occupé, l’appel est perdu, sinon, l’appel est pris – La probabilité qu’un appel se termine dans une unité de temps est β – Si à la fois un appel arrive et un appel se termine dans la même unité de temps, le nouvel appel est traité • Donner la représentation matricielle et graphique de la chaine de Markov représentant le comportement du téléphone Exemple : téléphone 0 1 α β(1-α) 1-β + αβ 1-α   1 " " #$1 "% 1 # & "# Les chaînes de Markov à temps discret • Analyse : Régime transitoire – L’analyse du régime transitoire d’un CMTD consiste à déterminer le vecteur π(n) des probabilités d’état pour que le processus se trouve dans l’état j à la nième étape du processus : – Ce vecteur des probabilités dépend : • De la matrice de transition P • Du vecteur des probabilités d’état initiales π(0) – Remarque : l’état initial est défini par ses probabilités • Dire qu’initialement le processus est dans un certain état i revient à considérer que et que pour tout j ≠ i – Régime transitoire : évolution du processus depuis l’état initial (caractérisé par π(0)) jusqu’à l’étape n (caractérisé par π(n)), en passant par toutes les étapes intermédiaires π $% ≜P X  j X ∈ℕ π$% ≜π $% j ∈ E  π $%, π $%, . . . π$%  π $%, π $%, . . . π $%  1 π $%  0 Les chaînes de Markov à temps discret • Analyse : Régime transitoire – Formule des probabilités totales soit Probabilité de se trouver dans l’état j à la nième étape = probabilité de passer d’un certain état i à l’état j pondérée par la probabilité d’être dans l’état i à l’étape précédente Sous la forme matricielle : (liaison de la probabilité d’état à l’étape n à celle de l’étape précédente) – Exemple de la souris dans le labyrinthe : • Probabilité de se trouver dans l’état 1 à l’instant n π$%  π$n 1%P π $%P X  j   P X  j |Xn 1 i P Xn 1  i ∈) π $%   π $n 1%pij ∈) 5 1 2 3 4 π $%  π $n 1%p11 & π $n 1%p21 & π! $n 1%p31 Les chaînes de Markov à temps discret • Analyse : Régime transitoire – En appliquant cela n fois : – On définit alors pij (m), la probabilité de transition de l’état i à l’état j en m étapes : – On définit également la matrice de transition en m étapes avec (exprime le fait que pour aller de l’état i à l’état j en m étapes, on peut aller de l’état i à un état k en m-1 étapes, puis aller de cet état k à l’état j en 1 étape et ce pour tous les états k) Sous forme matricielle : P(m) = P(m-1) P Et comme uploads/Industriel/ cm-markov-misc.pdf

Tags
Industrieltemps markov discret chaînes l’état
Documents similaires
  • 31
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager