[PDF] IFT-3655 Modèles Stochastiques orange Chaînes de Markov en





Previous PDF Next PDF



Exemple: États Exemple: Matrice de transition

passivement la matrice de transition fixe on va à chaque état de probabilités de transition et minimisera le coût du processus. 3. Exemple: États.



Chapitre 1 - Dynamiques aléatoires : chaines de Markov

Dans ces diagrammes chaque état est représenté par un point et chaque coefficient pij non nul de la matrice de transition par une fl`eche allant de l'état i `a 



Réponse temporelle : solution de léquation détat

Résolution de l'équation d'état. ? Cas scalaire. ? Cas matriciel. ? Mise en évidence de la matrice de transition. ? Calcul de la matrice de transition.



E. Les graphes probabilistes

2 État probabiliste et matrice de transition. Définition 2. Soit une expérience aléatoire à deux issues possibles A et B.



IFT-3655 Modèles Stochastiques orange Chaînes de Markov en

chaˆ?ne o`u Xn est le nombre de balles rouges dans l'urne `a l'étape n. L'espace d'états est. {01



CHAÎNES DE MARKOV

A toute matrice de transition on peut associer un graphe dirigé



Chaînes de Markov

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 



Feuille dexercices 3

card(X) est invariante par P. (b) Application. Soit P la matrice de transition d'une chaîne de Markov sur un espace d'états fini 



Chapitre 2 - Chaines de Markov : compléments

Il n'y aurait plus moyen alors de définir de matrice de transition. Une cha?ne de Markov est dite irréductible lorsque tous ses états communiquent ...



? ? ? ? /

P = (( pij )). On vérifie immédiatement que P est une matrice stochastique . Le graphe des transitions a pour sommets les états du processus les arcs.



Chapitre 8 Chaˆ?nes de Markov - ENS

Une matrice de transition P est parfois repr·esent·ee par son graphe de transition G un graphe dont les nœuds sont les ·etats de E et qui a une arˆete orient·ee de i vers j si et seulement si pij > 0 auquel cas cette arˆete est orn·ee de l’·etiquette pij



MODÈLES DE DURÉE

Matrices related to linear transformations We have encountered several ways in which matrices relate to linear transformations In this note I summarize the important facts and formulas we have encountered The matrix of a linear transformation from Rn to Rm: Theorem 1 Given a linear transformation T: Rn!Rm;there is an m nmatrix Afor



Searches related to matrice de transition détat PDF

opérations dans un processus de Markov à temps discret de sorte à optimiser ces performances Ainsi au lieu d’accepter passivement la matrice de transition fixe on va à chaque état de la chaîne déterminer la décision à prendre qui affectera les probabilités de transition et minimisera le coût du processus 3 Exemple: États

  • Point de Sortie

    Point auquel un objet quitte l'état composite ou l'automate, symbolisé par un cercle barré d'une croix. En règle générale, on l'utilise si le processus n’est pas terminé mais doit être quitté en raison d'une erreur ou d'un autre problème.

  • Garde

    Condition booléenne qui autorise ou bloque une transition, inscrite au-dessus de la flèche de transition.

Quels sont les États de la matrice de transition?

Une matrice de transition, contenant quatre états (sain, incapable, invalide, décédé), et dépendant de l’âge à l’entrée et de l’ancienneté est une modélisation possible. 1.3. Principales tables à estimer Les tables permettent le calcul des probabilités de maintien ou des probabilités de

Qu'est-ce que le diagramme d'état transition ?

Dans cet exemple, « Problème avec la réservation » est l’élément déclencheur qui enverrait la personne à l’agence de voyage de l’aéroport au lieu de l'acheminer vers l'étape suivante du processus. Cet exemple de diagramme d'état transition montre le processus par lequel une personne fixe un rendez-vous dans son agenda.

Comment transposer une matrice ?

Vous pouvez transposer n'importe quelle matrice, quel que soit son nombre de lignes et de colonnes. Les matrices carrées, celles qui ont autant de lignes que de colonnes, sont peut-être plus faciles à transposer quand on débute : c'est pourquoi nous commencerons avec une matrice de ce type [2] . . Inversez les lignes et les colonnes de la matrice.

Quelle est la matrice de transition d'une marche aléatoire?

Marches aléatoires Définition : La matrice de transitiond'une marche aléatoire est la matrice carrée dont le coefficient situé sur la ligne iet la colonne jest la probabilité de transition du sommet jvers le sommet i. Définition : La matrice colonne des états de la marche aléatoire après nétapes

IFT-3655 Modèles Stochastiques orange Chaînes de Markov en

Draft1

IFT-3655, Mod`eles Stochastiques

Chaˆınes de Markov en temps discret

Prof. Pierre L'Ecuyer

DIRO, Universit´e de Montr´eal

Ces "diapos" sont surtout un support pour les pr´esentations en classe. Elles ne contiennent pas toutes les explications d´etaill´ees. Pour cela il est recommand´e d'´etudier le livre recommand´e, de Sheldon Ross.

Draft2

Chaˆıne de Markov en temps discret

On consid`ere un processus stochastique en

temps discret {Xn,n= 0,1,2,...}dont l'espace d'´etatsX(l'ensemble de tous les ´etats possibles) est d´enombrable. On va habituellement num´eroter les ´etats par des entiers non n´egatifs, et ainsi supposer queX={0,1,...,r} (ifini) ouX={0,1,2,...}(inifini).Ce processus est unec haˆınede Ma rkovhomog `enesi P[Xn+1=j|Xn=i,Xn-1=in-1,...,X1=i1,X0=i0] =P[Xn+1=j|Xn=i] =Pi,j. En d'autres mots, la loi de probabilit´e du prochain ´etatXn+1conditionnellement `a

l'histoire pass´ee ne d´epend que de l'´etat actuelXnet ne d´epend pas den.LesPi,jsont lesp robabilit´esde tran sitionde la cha ˆıne.

L'adjectif

homog `ene veut dire que ces p robabilit´esn ed ´ependentpas de n.

Draft3

LesPi,jdoivent n´ecessairement satisfaire:

P i,j≥0 for alli,j;∞X j=1P i,j= 1 for alli.

Ils sont les ´el´ements de la

matrice de transition

P=

P

0,0P0,1P0,2···

P

1,0P1,1P1,2···

P

2,0P2,1P2,2···

Draft4

Exemple.Deux ´etats possibles: "il pleut" (0) et "il ne pleut pas" (1). Le temps est en jours. α=P[pluie demain|pluie aujourd'hui],β=P[pluie demain|pas de pluie aujourd'hui]. On a

P=α1-α

β1-βExemple.Marche al´eatoiresur les entiers: P i,i+1=p= 1-Pi,i-1,pouri∈Z.Mod`ele de parieur: Comme ci-haut maisP0,0=PN,N= 1 pour unN>0. X nrepr´esente la fortune du joueur `a l'´etapen. QuandXn= 0, il est ruin´e; quandXn=N, il s'arrˆete de jouer.

Draft5

Risque d'assurance d'un client: mod`ele Bonus-Malus Dans ce mod`ele,Xnrepr´esente le risque d'un client pour un assureur, en fonction de son historique d'accidents. L'id´ee est de d´eifinir un nombre ifini de cat ´egoriesde risque , et une chaˆıne de Markov dont les ´etats sont ces cat´egories.

Un client dans l'´etatiqui akaccidents durant l'ann´ee passera `a l'´etatsi(k), o`u lessi(k)

sont sp´eciifi´es `a l'avance. Par exemple, on pourrait avoirsi(k) =i+k-I[k= 0] , ou bien s

i(k) =i+ 2k-I[k= 0], ou une fonction plus complexe.On suppose que le nombreYd'accidents par un client durant une ann´ee estPoisson(λ), o`u

le param`etreλ=λcpeut d´ependre du client et ˆetre inconnu. Si le client est dans l'´etati, il

auraY=kaccidents avec probabilit´ee-λλk/k!, et sa probabilit´e de passer `a l'´etatjest

P i,j=X {k:si(k)=j}e -λλk/k!

Il y a difff´erentes fa¸cons d'utiliser ce mod`ele. Id´ealement, on voudrait pouvoir "apprendre"λc

et la loi des montants de r´eclamations, pour chaque client, en fonction de son historique.

Draft6

´Equation de Chapman-Kolmogorov

Soit P(n) i,j=P[Xn=j|X0=i], la probabilit´e de passer dei`ajen exactementn´etapes.´Equation de Chapman-Kolmogorov: P (n+m) i,j=∞X k=0P[Xn+m=j|Xn=k]P[Xn=k|X0=i] =∞X k=0P(n) i,kP(m) k,j En notation matricielle, siP(n)est la matrice contenant lesP(n) i,j, cela donne P (n+m)=P(n)·P(m). En particulier,P(2)=P·P, et par induction surn, on aP(n)=P(n-1)·P=Pn. Similaire aux matrices donnant les nombres de chemins de longueurnentre chaque paire de sommets dans un graphe.

Draft7

Exemple.Dans l'exemple de "pluie" vs "non pluie", supposons queα= 0.7 etβ= 0.4, de sorte que

P=α1-α

β1-β

=0.7 0.3

0.4 0.6

les probabilit´es de transition en deux jours et en 4 jours sont: P

2=0.61 0.39

0.52 0.48

,P4=0.5749 0.4251

0.5668 0.4332

Que se passe-t-il avecPnquandn→ ∞?On a

lim n→∞Pn=4/7 3/7

4/7 3/7

Les lignes sont identiques et donnent les

p robabilit´eslimites des deux ´ etats.

Interpr´etation.

On verra plus loin des conditions p ourque cette limite existe.

Draft8

Exemple.On dispose de balles rouges et de balles bleues, et d'une urne qui contient 2 balles.`A chaque ´etape, on tire une balle de l'urne et on la remplace par une balle de la

mˆeme couleur avec probabilit´e 0.8 et de l'autre couleur avec probabilit´e 0.2. On d´eifinit une

chaˆıne o`uXnest lenomb rede balles rouges dans l'ur ne` al' ´etapen. L'espace d'´etats est

{0,1,2}et la matrice des probabilit´es de transition est

P=

0.8 0.2 0

0.1 0.8 0.1

.0120.2

0.10.1

0.20.80.80.8

SiX0= 2 (2 balles rouges au d´epart), alors lap remi`ereballe tir ´eeest certainement rouge. Soitbnla probabilit´e que la (n+ 1)-i`eme balle tir´ee est rouge. On aura b n= 1·P[Xn= 2|X0= 2] + (1/2)P[Xn= 1|X0= 2] =P(n)

2,2+P(n)

2,1/2.Par exemple, en calculantP4et on trouveP(4)

2,2= 0.4872 etP(4)

2,1= 0.4352, ce qui donne

b

4= 0.4872 + 0.4352/2 = 0.7048.Que se passe-t-ilquand n→ ∞? On peut montrer quePnconverge vers une matrice dont les 3 lignes

sont (1/4,1/2,1/4), et quebn→1/2, ce qui correspond `a l'intuition.

Draft9

Exemple 4.11 du livre: Encore le probl`eme du collectionneur de capsules. Il y aktypes de capsules.`A chaque ´etape on tire une capsule, avecp robabilit´e1 /kpour chaque type. SoitXnle nombre de types que l'on a apr`esntirages. Les probabilit´es de transition sontP0,1= 1,Pk,k= 1 (l'´etatkest absorbant), P i,i=i/k= 1-Pi,i+1pouriPest une matrice (k+ 1)×(k+ 1). La probabilit´e d'avoir exactementjtypes apr`esntirages estP(n) 0,j. La probabilit´e d'avoir une collection compl`ete apr`esntirages estP(n)

0,k.Et si les probabilit´es ne sontpas toutes 1 /k?Le mod`ele aveck+ 1 ´etats ne tient plus.

L'´etat doit indiquer quelles capsules il nous manque! Donc 2

k´etats possibles.On pourrait vouloir "apprendre" ces probabilit´es `a partir d'observations.Rendu ici, 25 sept. 2023

Draft10

Chaˆınes avec ´etats absorbants ou tabousParfois, pour une chaˆıne de Markov, on a un sous-ensemble d'´etatsA⊂ X et on s'int´eresse `a

un ´ev´enement qui d´epend deN= inf{n≥1 :Xn∈ A},l'instant de la p remi`erevisite ` aA, ou

du premier retour `aAsi on y est d´ej`a. SiXnn'atteint jamaisA, on aN=∞.On peut vouloir calculer par exemple

Si|A|>1, on peut dans ce cas r´eduire la taille de la chaˆıne en fusionnant tous les ´etats de

Aen un seul´ etatabso rbant, disons∆ . Quand la chaˆıne atteint ∆, elle y reste. La nouvelle chaˆıne{Wn,n≥0}est d´eifinie par W n=XnpournDraft11 Exemple:On tire `a pile ou face et on s'int´eresse `a laloi de p robabilit´ede N, le nombre de tirages requis pour avoirsfaces d'aiÌifiÌil´ee. SoitXnlenomb rede faces de suite que l'on vient d'obtenir r endu` al' ´etapensi on a face `a cette ´etape, etXn= 0 si on a pile. On pose ensuiteA={s},∆ = s, etN= inf{n≥1 :Xn∈ A}.

AinsiWn=Xnavant d'avoir atteints, et par la suiteWn=s= ∆.Par exemple, pours= 3, lesQi,jsont donn´es par

Q=

1/2 1/2 00

1/2 0 1/2 0

1/2 0 0 1/2

Pour chaquen>0, l'´el´ementQ(n)

0,s= 0. On peut ainsi calculertoute la distribution de N.

Draft12

Contraintes sur les trajectoires

Sii,j̸∈ AetX0=i, la probabilit´e queXm=jet que la chaˆıne n'ait pas visit´e l'ensembleA

jusqu'`a l'´etapems'´ecrit

α=P[Xm=j,N>m-1|X0=i].

Pour calculerα, il suiÌifiÌit de construireQet la chaˆıne{Wn,n≥0}comme ci-haut.

L'´el´ementQ(m)

i,jdonne la probabilit´eαcherch´ee.Pour le cas o`uj∈ A, voir Ross (2014), page 193.

Draft13

Classiification des ´etats

On dit qu'un ´etatjestacces siblede l' ´etatis'il existe unn≥0 tel quep(n) ij>0. Cela veut

dire que si on est dans l'´etati, la probabilit´e d'atteindrej´eventuellement n'est pas nulle.

Notez queiest toujours accessible dei.

Deux ´etatsietjcommuniquentsi chacun est acce ssiblede l'autre. On note cela i↔j.

La communication est une

relation d' ´equivalence : c'est r´elflexif et sym´etrique (d´ecoule directement de la d´eifinition), et aussi transitif (d´ecoule de l'´equation de

Chapman-Kolmogorov).

Les classes d'´equivalence forment une

pa rtition de l'espace d' ´etatsX.

On les appelle les

classes de communication

La chaˆıne est

irreductible

si tous les ´ etatscommuniquent (une se uleclasse d' ´equivalence).On peut repr´esenter une chaˆıne de Markov `a espace d'´etats discret par un graphe orient´e.

Les ´etats sont les

sommets , les transitions de probabilit´e positive sont les a rcs , et on peut aller dei`ajenn´etapes s'il y a un chemin dei`ajde longueurn.

Draft14

Exemple.

P=

1/2 1/2 0

1/2 1/4 1/4

0121/2

1/21/4

1/31/21/42/3

Ici, tous les ´etats communiquent. La chaˆıne est irr´eductible.

Exemple.

P=

1/2 1/2 0 0

1/2 1/2 0 0

1/4 1/4 1/4 1/4

.01231/21/21/41 1/2 1/2

1/41/41/4

Ici, on a trois classes:{0,1},{2}, et{3}. L'´etat 2 esttransitoire et l' ´etat3 est abso rbant.

Draft15

´Etats r´ecurrents et transitoires

Pour chaque ´etati, soitfila probabilit´e que si on part dei, on va y revenir ult´erieurement.

L'´etatiest ditr ´ecurrentsi fi= 1 (on est certain d'y revenir) ettransitoire si fi<1.

Voir les exemples.Sifi= 1, le processus va revenir `aiavec probabilit´e 1, puis va y revenir encore une fois avec

probabilit´e 1, et ainsi de suite. La chaˆıne va donc revenir `aiune inifinit´e de fois, et le nombre

esp´er´e de visites `aiest n´ecessairement inifini.

Par contre,

si fi<1, `a chaque passage `ai, la chaˆıne va y revenir avec probabilit´efi<1, et n'y reviendra plus jamais avec probabilit´e 1-fi. Le nombre de retours `aiest donc dans ce cas une v.a. g´eom´etrique de param`etrep= 1-fi, dont l'esp´erance est (1-p)/p<∞ (ici, chaque retour correspond `a un "´echec").

Donc sifi<1, le nombre de visites `a l'´etatiest ifini avec probabilit´e 1, et le nombre esp´er´e

de visites `aiest ifini.

Draft16

SoitMi=P∞

n=1I[Xn=i] le nombre de retours `a l'´etati, en supposant queX0=i.

On afi= 1 ssiE[Mi|X0=i] =∞. Mais

E[Mi|X0=i] =∞X

n=1E[I(Xn=i)|X0=i] =∞X n=1P[Xn=i|X0=i] =∞X n=1P(n) i,i.Proposition.Un ´etatiestr ´ecurrentsi P∞ n=1P(n)

i,i=∞ettransitoire sinon. Corollaire.Le caract`ere r´ecurrent ou transitoire est une propri´et´e de classe: siiest r´ecurrent

[transitoire] eti↔j, alorsjest r´ecurrent [transitoire].

Preuve

: Sii↔j, il existemetktels queP(m) j,i>0 etP(k) i,j>0. On a X n=1P(n) j,j≥∞X n=1P(m+n+k) j,j≥∞X n=1P(m) j,iP(n) i,iP(k) i,j≥P(m) j,iP(k) i,j∞ X n=1P(n) i,i=∞ cariest r´ecurrent.

Draft17

Exemple

P=

1/2 1/2 0 0 0

1/2 1/2 0 0 0

0 0 1/2 1/2 0

0 0 1/2 1/2 0

Quelles sont les classes de communication, et lesquelles sont r´ecurrentes?Il y a trois classes:{0,1},{2,3}, et{4}.

Les deux premi`eres sont

r ´ecurrentes et la troisi `emeest transitoire

Rendu ici, 23 janv. 2020

Draft18

Une marche al´eatoire sur les entiers···-2-10123···p 1-pp 1-pp 1-pp 1-pp

1-pIci, tous les ´etats communiquent (une seule classe), donc ils sont ou bien tous r´ecurrents, ou

bien tous transitoires! Pour savoir s'ils sont r´ecurrents ou pas, on va calculer

E[M0|X0= 0] =∞X

n=1P(n) 0,0.

Draft19

On sait qu'on ne peut revenir `a 0 qu'en un nombre pair de coups, donc il suiÌifiÌit de consid´erer

les termes de la formeP(2n)

0,0, i.e., allernfois `a gauche etnfois `a droite:

P (2n)

0,0=2n

n p n(1-p)n=(2n)!n!n!(p(1-p))n∼ X Mais cela est vrai ssip= 1/2, auquel cas le num´erateur est 4p(1-p) = 1 etP∞ n=11/n=∞.

Sip̸= 1/2, 4p(1-p)<1, et la s´erie est born´ee par une s´erie g´eom´etrique, qui converge.

On a donc:

La ma rcheal ´eatoireest r ´ecurrentessi p= 1/2 (la marche est sym´etrique).On peut d´eifinir aussi une marche al´eatoire sur les entiers en 2 dimensions ou plus.

On peut prouver qu'une marche sym´etrique en 2 dimensions est aussi r´ecurrente, mais une ma rcheen 3 dimensions ou plus est toujours transitoir e! Plus la dimension augmente, plus c'est facile de s'´evader!

Draft20

Fr´equences de visites et r´ecurrence positive La probabilit´e d'atteindre ´eventuellementjquand on est `ai: f i,j=P[Xn=jpour unn>0|X0=i] =P" ∞X n=1I[Xn=j]>0|X0=i# .Proposition.Siiest r´ecurrent eti↔j, alorsfi,j= 1.

Preuve.

Puisque i↔j, il existe unn>0 tel quep=P(n)

i,j>0. Donc chaque fois qu'on visitei, on visiterajdansn´etapes avec probabilit´e au moinsp. Mais on visiteiinifinimentquotesdbs_dbs30.pdfusesText_36
[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é

[PDF] l'économie d'un pays fictif dépend de trois secteurs

[PDF] coefficient technique de production définition

[PDF] input output économie