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

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

Previous PDF

Next PDF

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, 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.

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

Dans ce genre de situation, on peut r´eduire la taille de la chaˆıne en fusionnant tous les ´etats

deAen un seul´ etatabso rbant, disons∆ . Quand la chaˆıne atteint cet ´etat, 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 0 0

1/2 0 1/2 0

1/2 0 0 1/2

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

On peut ainsi calculer toute la distribution deN.

Draft12

Contraintes sur les trajectoires

Sii,j̸∈ A, la probabilit´e queXm=jet que la chaˆıne n'ait pas visit´e l'ensembleAjusqu'`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

: Prenonsmetktels queP(m) j,i>0 etP(k) i,j>0, i.e.,i↔j. Siiest r´ecurrent, 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=∞.

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 visiteiinifiniment

souvent. On a donc une inifinit´e d'occasions d'aller `aj, chaque fois avec probabilit´e de succ`es

au moinsp. Le nombre de ces occasions que l'on va rater avant le premier succ`es est une v.a. g´eom´etrique(p), donc ce nombre est ifini avec probabilit´e 1.□

Draft21

Soitjun´ etatr ´ecurrentet X0=j. Letemps de p remierretour ` ajest R j= min{n≥1 :Xn=j}, Le temps de r ´ecurrencemo yen est m j=E[Rj|X0=j].quotesdbs_dbs28.pdfusesText_34

[PDF] chaine de markov résumé

[PDF] chaine de markov matrice de transition

[PDF] chaine d'acquisition de données

[PDF] chaine de mesure audioprothèse

[PDF] acquisition de données du capteur ? l ordinateur

[PDF] chaine de mesure pdf

[PDF] chaine d'acquisition capteur

[PDF] les capteurs exercices corrigés

[PDF] chaine de markov apériodique

[PDF] chaine de markov apériodique exemple

[PDF] chaine de markov reversible

[PDF] chaine de markov récurrente

[PDF] chaine de markov exemple

[PDF] chaine de markov irreductible exemple

[PDF] chaine de markov exercice corrigé