[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 Type BS Série Européenne - Anciens Et Réunions
[PDF] Chaînes uni - Anciens Et Réunions
[PDF] Chaines-courroies - Conception
[PDF] Chainfix
[PDF] CHAIR COVER ESSENTIALS: Included
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 discrètes - Stephan ROBERT-NICOUD