[PDF] Chaînes de Markov discrètes Donnez également les propriété

View - Download Chaînes de Markov discrètes

Previous PDF

Next PDF

Chaînes de Markov discrètes

Dr Stephan Robert

3 mars 2016

1/1 2/1

Chaînes de Markov dicrètes

3/1

Introduction

I fXng: suite de variables aléatoires prenant des valeurs dans

E=f0;1;2;:::;mg,Edénombrable.

I Propriété deMarkov:P(Xn+1=jjXn=i;Xn1=in1;:::;X0=i0) =

P(Xn+1=jjXn=i)

I

Notation :Xn=i,i2 E

I Définition :Probabilité de transition:P(Xn+1=jjXn=i) 4/1

Exemple

Somme de variables aléatoiresXi,i2N, iid :

I

Sn=X1+X2+:::+Xn

I

Sn=Sn1+Xn

AvecS0=0 nous remarquons que le processus est Markovien.5/1

Matrice et diagramme de transition

Nous pouvons écrire lamatrice de transitionde la chaîne en utilisant la notation suivante : P=0 B B@p

00p01:::p0m

p

12p11:::p1m

p m0pm1:::pmm1 C CA Il est souvent utile de dessiner lediagramme des probabilités de transition(oudiagramme de transition), par exemple pour m=2 :6/1

Exemple : ATM

Un créneau est soit vide soit plein suivant qu"il contienne ou non un paquet.Matrice de transition(oumatrice stochastique) :

P=P(Xn+1=0jXn=0) =p00P(Xn+1=1jXn=0) =p01

P(Xn+1=0jXn=1) =p10P(Xn+1=1jXn=1) =p11

1 1 7/1

Exemple : ATM (2)

Observation importante:

I

P(Xn+1=0jXn=0) +P(Xn+1=1jXn=0) =1

I

P(Xn+1=0jXn=1) +P(Xn+1=1jXn=1) =1

Généralisation :X

jP(Xn+1=jjXn=i) =X jp ij=1

D"où le nom "matrice stochastique" !

8/1

Probabilités d"état

9/1

Probabilités de transition aprèsnpas

Sujet d"intérêt: Calcul des probabilités de transition aprèsn transitions. Théorême :La matrice des probabilités de transition aprèsnpasP(n) est la puissancende la matrice des probabilités de tran- sitionP, soitP(n) =Pn. 10/1

Probabilités de transition aprèsnpas (2)

Démonstration du théorême

Probabilité de passer de l"étati(n=0) à l"étatj(n=2) en passant par l"étatk(n=1) :

P(X2=j;X1=kjX0=i)

P(X2=j;X1=k;X0=i)P(X0=i)

P(X2=jjX1=k)P(X1=kjX0=i)P(X0=i)P(X0=i)

=P(X2=jjX1=k)P(X1=kjX0=i) 11/1

Probabilités de transition aprèsnpas (3)

Finalement :

P(X2=j;X1=kjX0=i) =pik(1)pkj(1)

p ij(2)est la probabilité d"aller deiàjen sommant tous les étatsk intermédiaires : p ij(2) =X kp ik(1)pkj(1)8i;j Cet ensemble d"équations montre queP(2)est obtenue en multipliant la matriceP(1)par elle-même :

P(2) =P(1):P(1) =P:P=P2.

12/1

Probabilités de transition aprèsnpas (4)

Equation de Chapman-Kolmogorov

P(n) =P(n1):P

etP n+m=PnPm avecn;m0. 13/1

Probabilités d"état

Quelle est laprobabilitéde se trouver dans unétat donnéde la chaîne de Markov à untemps arbitrairen?

Notation :

p(n) =p1(n)p2(n):::pl(n)

Observation :

p j(n) =X iP(Xn=jjXn1=i)P(Xn1=i) =X ip ij:pi(n1)p(n) =p(n1):P 14/1

Probabilités d"état (2)

Lorsquendevient grand,

p(n)p(n1)

On va écrire

p(1) = et donc=:P avec P i i=1 15/1

Exemple

Figure:

Chaî nede Ma rkovà deux états

Matrice de transition :

P=1 1 16/1

Exemple (2)

I =0:1 I =0:3

CalculonsPn:

P

2=0:9 0:1

0:2 0:8

2 =0:28 0:72

0:24 0:76

P

4=0:9 0:1

0:2 0:8

4 =0:2512 0:7488

0:2496 0:7504

P

10=0:9 0:1

0:2 0:8

10 =0:25 0:75

0:25 0:75

17/1

Exemple (3)

Observation :Pnconverge bien quandndevient grand!

P n!1=4 3=4

1=4 3=4

quandn! 1. A chercher :Probabilités d"état stationnaires. =P ou

01=011

1 18/1

Exemple (3)

En explicitant :

0=0(1) +1

1=0+1(1)

or il y a un problème! Les deux équations sont linéairement dépendantes! Il faut se rappeler que X i i=1 19/1

Exemple (4)

En résolvant ces deux équations :

0=+ 1=+ et avec=0:1 et=0:3 : I 0=1=4 I 1=3=4 20/1

Exercice

Soit une matrice de transition

P=0 @0:6 0:2 0:2

0:4 0:5 0:1

0:6 0 0:41

A Trouvez les probabilités d"état et dessinez la chaîne de Markov. 21/1

Classification des états

22/1

Propriétés de récurrence

Définitions:

I Un étatjest ditaccessibledepuis l"étatisipij(n)>0,n0. I Si tous les états d"une chaîne de Markov sont accessibles, on dit qu"ils appartiennent à une même classe et la chaîne est dite irréductible. I Un état est ditrécurrentsi la probabilité d"y retourner est égale à 1. Dans le cas contraire l"état est dittransitoire. I Un état est ditabsorbantlorsque la probabilité de rester dans l"état est égale à 1. 23/1

Propriétés de récurrence(2)

Observations:

I Un étatrécurrentest visité unnombre infinide fois. Un état transitoiren"est visité qu"unnombre finide fois. I Si un état est récurrent alors tous les états de sa classe sont aussi récurrents. Larécurrenceest une propriété de la classe. I Si on démarre la chaîne de Markov dans un état récurrent alors on y reviendra un nombre infini de fois. 24/1

Exemple

Chaîne de Markov à trois états dont un est absorbant, avec ;; >0 :25/1

Temps d"absorbtion

Temps jusqu"à la première visite de l"étatià partir du démarrage de la chaîne : T j=inffn2N+:X(n) =jg

Etat récurrent :

P(Tj<1jX0=j) =1

Etatrécurrent positif:

E(TjjX0=j)<1

Etatrécurrent nul:

E(TjjX0=j) =1

26/1

Temps d"absorbtion (2)

Proportion de temps passé dans un état :

i=1E[TjjX0=j] Chaîne de Markovpériodique: Tous les états sont visités à des instants qui sont des multiples d"un nombre entierd>1. Définition: On dit qu"une chaîne de Markov estergodiquesi ellequotesdbs_dbs24.pdfusesText_30

[PDF] Chaînes de Markov et Google - de l`Université libre de Bruxelles

[PDF] chaines de solides - Académie d`Aix

[PDF] Chaînes de traitement et procédures pour l`exploitation de - Logiciels Graphiques

[PDF] Chaines de transmission TSUBAKI - Anciens Et Réunions

[PDF] Chaînes des énergies

[PDF] Chaînes et embrayages / Clutch and chains - Anciens Et Réunions

[PDF] Chaînes FB - FB Ketten - France

[PDF] Chaînes Industrielles

[PDF] Chaînes légères libres d`immunoglobulines et gammapathies

[PDF] Chaînes radio - Anciens Et Réunions

[PDF] Chaînes STIHL prêtes au montage pour toutes tronçonneuses - Anciens Et Réunions

[PDF] Chaînes Type BS Série Européenne - Anciens Et Réunions

[PDF] Chaînes uni - Anciens Et Réunions

[PDF] Chaines-courroies - Conception

[PDF] Chainfix