Chaînes de Markov
Si X est fini on notera N son nombre d'éléments. 1. Matrices stochastiques et propriété de Markov. 1.1. Chaînes de Markov. Une matrice stochastique sur X est
Chaînes de Markov au lycée
Dire que TP=P signifie que P est vecteur propre de T pour la valeur propre 1. Or une matrice de transition (matrice stochastique) admet 1 comme valeur propre
IFT-3655 Modèles Stochastiques orange Chaînes de Markov en
Parfois pour une chaˆ?ne de Markov
Chaînes de Markov (et applications)
???/???/???? X est une chaîne de Markov si pour tout x0
Chaînes de Markov
a) est évident : pour n = 0 1Xn=k = 1 Pk-p.s. et les autres termes de la somme sont tous nuls (n < ?k). b) Calculons le j-ième terme (?k P)j du vecteur ligne
1 Définition
est une chaîne de Markov si pour tout n ? 0
CHAÎNES DE MARKOV
Toute matrice de transition vérifie les propriétés suivantes : (1) pour tout couple (x y) de E
Stabilite de la recurrence dune chaine de markov sous ieffet dune
Considkrons une chaine de Markov sur Z rkcurrente et irrtductible
Théorème de limite centrale fonctionnel pour une chaîne de Markov
centrale fonctionnel pour une chaîne de Markov récurrente au sens de a2(s A t) si a est non nul et le processus dégénéré 0 si a est nul. Enfin pour p ...
Chapitre 8 Chaˆ?nes de Markov
fait les cha?nes de Markov sont des processus stochastiques dont l'évolution est régie N . Les termes non nuls de la matrice de transition sont donc.
[PDF] CHAÎNES DE MARKOV - ceremade
notes de cours de “Processus stochastiques” je m'en suis largement inspirée et en ai tiré tous les dessins de graphes pour les chaînes de Markov
[PDF] CHAÎNES DE MARKOV - Institut de Mathématiques de Bordeaux
Chapitre I Chaînes de Markov 5 1 Définition 5 2 Exemples 7 3 La relation de Chapman-Kolmogorov 9 4 Classification des états
[PDF] Chaînes de Markov - Institut Camille Jordan
1 7 5 Chaînes de Markov avec plusieurs pas de mémoire 37 récurrentes nulles ou de noyau récurrent nul ou transient Preuve :
[PDF] Chapitre 8 Chaˆ?nes de Markov - DI ENS
Pour introduire cette dynamique il faut tenir compte de l'influence du passé ce que font les cha?nes de Markov `a la façon des équations de récurrence dans
[PDF] Chaînes de Markov
Une chaîne de Markov sur X de matrice de transition P est une suite de variables aléatoires (Xn)n2Ndéfinies sur un espace (? b P) et à valeurs dans X telle
[PDF] Chaînes de Markov : théorie et applications
matrice stochastique sur X Une chaîne de Markov de matrice de transition P ou nuls telle que q0 = 0 et pk + qk + rk = 1 pour tout k ? N La chaîne de
[PDF] Chaînes de Markov (et applications)
22 fév 2021 · Idée : Une chaîne de Markov est une suite de variables aléatoires dans le temps ou conditionnel- lement au présent le futur ne dépend pas
[PDF] Chaînes de Markov
La loi d'une chaîne de Markov homogène est complètement dé- terminée par la donnée de sa matrice de transition et de la loi de X0 (appelée loi initiale) :
[PDF] Chaines de Markov : compléments
Une cha?ne de Markov est dite irréductible lorsque tous ses états communiquent c'est-`a-dire lorsque pour toute paire d'états (xixj) la probabilité
[PDF] Introduction aux chaines de Markov - CERMICS
Une cha?ne de Markov est une suite de variables aléatoires (Xnn ? N) qui permet de modéliser l'évolution dynamique d'un syst`eme aléatoire : Xn représente
Comment montrer qu'une chaîne est une chaîne de Markov ?
= P(Xn+1 = yXn = xn). Cette preuve permet de montrer rigoureusement que la marche aléatoire sur Zd est bien une chaîne de Markov. Dans le monde déterministe, cela revient à étudier les suites (xn)n?0 définies par ré- currence de la manière suivante : xn+1 = f(xn,n).Comment calculer la période d'une chaîne de Markov ?
Cela conduit au calcul suivant : P(X2 = s/X0 = m) = P(X2 = s/X1 = m) · P(X1 = m/X0 = m) + P(X2 = s/X1 = s) · P(X1 = s/X0 = m) = 0,15 · 0,0,55 + 0,15 · 0,1=0,0975. La cha?ne n'est pas périodique comme on peut le voir facilement sur son diagramme en points et fl`eches.Quel est le principe Sous-jacent de la technique des chaines de Markov ?
Si une chaîne de Markov est irréductible et si son espace d'états est fini, tous ses états sont récurrents positifs. La loi forte des grands nombres est alors en vigueur. Plus généralement, tous les éléments d'une classe finale finie sont récurrents positifs, que l'espace d'états soit fini ou bien infini dénombrable.- La chaîne est dite homogène si on a de plus pour tout k ? N et tout x et y dans E, P(Xk+1 = yXk = x) = P(X1 = yX0 = x).
![1 Définition 1 Définition](https://pdfprof.com/Listes/17/28547-17cours_markov.pdf.pdf.jpg)
Année universitaire 2014-2015
Cours rapide sur les chaînes de Markov1 DéfinitionDéfinitionSoitEun ensemble dénombrable (ou fini). Une suiteX= (Xn)n0de variables aléatoires à valeurs dansE
est unechaîne de Markovsi, pour toutn0, pour tousx1;:::;xn;xn+12E, ?(Xn+1=xn+1jX0=x0;:::;Xn=xn) =?(Xn+1=xn+1jXn=x); dès lors que?(X0=x0;:::;Xn=xn)>0. Eest l"espace d"étatsdeX. Laloi initialedeXest la loi deX0.Cette chaîne de Markov esthomogène(dans le temps) s"il existe(x;y)7!P(x;y)surEEtelle que : pour
toutn0, pour tousx;y2E, ?(Xn+1=yjXn=x) =P(x;y); dès lors que?(Xn=x)>0.Pest lamatrice de transitiondeX.Ainsi,(Xn)nest une chaîne de Markov si, en tout " temps »n, connaître la position " présente »Xnrenseigne
tout autant sur laloide la position " future »Xn+1que de connaître tout le " passé »X0;:::;Xn. Autrement
dit, sachantXn,Xn+1est indépendante deX0;:::;Xn.On peut voir que ceci revient aussi à dire queX0suit une certaine loi, puis que la suite(Xn)nest définie par
une récurrence de la formeXn+1=fn(Xn;Un)où la variable aléatoireUnest indépendante deX0;:::;Xn. Le
cas d"une chaîne homogène est celui où la transition est la même à chaque étape : les fonctionsfn,n0;sont
égales entre elles, et les variablesUn,n0, ont toutes la même loi. C"est donc un analogue aléatoire des suites
récurrentes d"ordre 1.Dans la suite, on ne considèrera que des chaînes de Markov homogènes, et on omettra donc de le spécifier.
La loi d"une chaîne de Markov homogène est entièrement donnée par sa loi initiale et sa matrice de transition :
LemmeSi(Xn)nest une chaîne de Markov de loi initialeet de matrice de transitionPalors, pour toutn0,
pour tousx0;:::;xn2E, ?(X0=x0;:::;Xn=xn) =(x0)P(x0;x1)P(xn1;xn):La matricePeststochastique: ses coefficients sont positifs, et la somme de chaque ligne vaut 1. Inversement,
à l"aide du lemme, on peut définir la loi d"une chaîne de Markov à partir de tout choix d"une loisurEet
d"une matrice stochastiquePsurEE.On aura constamment besoin de considérer des chaînes de Markov ayant la même matrice de transitionP
mais différentes lois initiales. Si la matricePest spécifiée dans le contexte, on notera ainsi?une probabilité
sous laquelle(Xn)n0est une chaîne de Markov de loi initialeet de matrice de transitionP. Ici,est une
probabilité surE, que l"on voit comme une fonction:E!?+: on a, pourx2E, (x) =?(X0=x):Dans le cas où=z, c"est-à-dire queX0=zp.s., on notera?zau lieu de?z. Sous?z,Xest une chaîne de
Markovissue dez:
z(X0=z) = 1: Par la définition, pour tousx;y2E, comme?x(X0=x) = 1, x(X1=y) =?x(X1=yjX0=x) =P(x;y): 1 et, pour toute loi initialeet touty2E, (X1=y) =X x2E? (X0=x;X1=y) =X x2E; (x)>0(x)?(X1=yjX0=x) =X x2E(x)P(x;y): Plus généralement, pour toute loisurE, pour tousx;y2E, pour toutn, de même, (Xn+1=y) =X x2E? (Xn=x;Xn+1=y) X x2Etel que (Xn=x)>0? (Xn=x)?(Xn+1=yjXn=x) X x2E? (Xn=x)P(x;y): Notons, pourx2Eetn2?,n(x) =?(Xn=x), c"est-à-dire quenest la loi deXnsous?. On a donc0=, et la formule précédente s"écrit, en voyant les mesures surEcomme des vecteurs-lignes, etPcomme
une matrice (éventuellement infinie), n+1=nP: On a doncn=Pn. En particulier (si=x), la lignexdePndonne la loi deXnsous?x: pour tousx;y, x(Xn=y) =Pn(x;y)DéfinitionLegraphed"une chaîne de MarkovXd"espace d"étatsEet de matrice de transitionPest le graphe orienté
dont les sommets sont les états et les arêtes sont les couples(x;y)tels queP(x;y)>0. Le graphe deXreprésente donc les transitions possibles en 1 pas.Propriété de Markov
La propriété suivante généralise la définition en exprimant que, sachant la position présenteXn, le futur
(Xn;Xn+1;:::)est indépendant du passé(X0;:::;Xn)et suit la loi?Xn.Proposition (Propriété de Markov faible au tempsn)Pour toutn, pour tousx0;:::;xn2E(tels que?(X0=x0;:::;Xn=xn)>0),
sachantX0=x0;:::;Xn=xn,(Xn+k)k0suit la loi?xn.Autrement dit,
p ourtout UEn, et toutVE?mesurable, pour toutx2E, p ourtoutes fonctions f:En!?etg:E?!?mesurables bornées, ?[f(X0;:::;Xn)g(Xn;Xn+1;:::)] =?f(X0;:::;Xn)?Xn[g(X0;X1;:::)]: Cette propriété s"étend aux temps aléatoires qui " ne dépendent pas du futur » :DéfinitionUntemps d"arrêtde(Xn)nest une variable aléatoireà valeurs dans?[ f1gtelle que, pour toutn,
f=ng 2(X0;:::;Xn):On rappelle que(X0;:::;Xn)est la tribu engendrée parX0;:::;Xn: c"est l"ensemble des événements qui ne
dépendent que deX0;:::;Xn.est donc un temps d"arrêt si, pour toutn, on peut savoir si=nà partir de la
seule connaissance deX0;:::;Xn. Si on découvreX0;X1;:::l"un après l"autre, on peut donc s"" arrêter » àX.
2Proposition (Propriété de Markov forte au temps)Pour tout temps d"arrêt, pour toutn, pour tousx0;:::;xn2E(tels que ... )
sachant=netX0=x0;:::;Xn=xn,(X+k)k0suit la loi?xn.Autrement dit,
p ourtout UEn, et toutVE?mesurable, pour toutx2E, p ourtoutes fonctions f:En!?etg:E?!?mesurables bornées, ?[1f=ngf(X0;:::;Xn)g(Xn;Xn+1;:::)] =?1f=ngf(X0;:::;Xn)?X[g(X0;X1;:::)]:2 Récurrence et transience
On s"intéresse aux états où se trouve la chaîne de Markov après un temps long : en particulier, quels états ne
seront plus visités après un certain temps, et quels états seront au contraire revisités perpétuellement?
DéfinitionSoitx2E. On notexle temps de retour enx: x= inffn1jXn=xg: L"étatx2Eestrécurrentsi?x(x<1) = 1, ettransientsinon.Ainsi,xest récurrent si, partant dex,Xrevient presque sûrement enx. Par la propriété de Markov forte au
tempsx, si un retour est presque sûr, alors un second retour sera presque sûr, etc. : PropositionSoitx2E. On noteNxle nombre de visites enx: N x=1X n=01 fXn=xg: a)xest récurrent si, et seulement si?x(Nx=1) = 1. Plus généralement, s"il existey2Etel que?y(Nx=1)>0, alorsxest récurrent. b) Si xest transient alors, sous?x,Nxsuit la loi géométrique de paramètre?x(x=1).Par b) on note que, sixest transient alors?x[Nx]<1. Ainsi,xest récurrent si, et seulement si?x[Nx] =1,
c"est-à-dire si1X n=0P n(x;x) =1:2.1 Classification des états
DéfinitionPourx;y2E, on notex!ys"il existen0tel quePn(x;y)>0. Deux étatsx;y2Ecommuniquentsix!yety!x. On note alorsx$y.$est une relation d"équivalence dont les classes sont appelées lesclasses de communicationde la chaîne
de Markov. Une classe de communicationCestferméesi, pour toutx2 C, il n"y a pas dey =2 Ctel quex!y. S"il y a une seule classe de communicationC=E, la chaîne de Markov est diteirréductible.Sur le schéma de la chaîne de Markov,x$ys"il y a un chemin (d"une certaine longueur) dexversy, et un
chemin deyversx. Une classe est fermée si aucune transition n"en sort. 3Proposition
a)Si xest récurrent etx!y, alorsyest récurrent. Par suite, les éléments d"une classe sont tous récurrents,
ou tous transients. On parle declasse récurrenteou declasse transiente. b)Si xest récurrent etx!y, alorsy!x. Par suite, si une classe n"est pas fermée, elle est transiente.
c)Une class efermée et finie est récurren te.
Démonstration:(Intuition) a) Sixest récurrent alors, partant dex,xest visité infiniment souvent; dès lors, s"il est
possible, depuisx, de suivre un chemin pour visitery(avec probabilitéPn(x;y)>0), alors ceci va se produire lors d"une
infinité de retours enx:ysera visité infiniment souvent, doncyest récurrent.b) De plus, pour quexpuisse être visité infiniment souvent, il doit être possible de revenir enxaprès la première visite
ày, doncy!x.
c) Partant dexappartenant à une classe fermée finieC, la chaîne de Markov passe tout son temps dans l"ensemble fini
C, donc il existey2 Cqui est visité infiniment souvent (avec probabilité>0). Cet étatyest alors récurrent.Cette proposition permet de déterminer la nature (récurrent ou transient) de tous les états d"une chaîne de
Markovfinie: les classes fermées sont récurrentes, et les autres transientes. En particulier, une chaîne de
Markov irréductible sur un espace fini est récurrente.En revanche, une classe fermée infinie peut être transiente ou récurrente : cela va dépendre plus finement de la
matriceP(la classification précédente ne dépend que de la position des coefficients non nuls deP).
2.2 Probabilités et temps moyens d"absorption
Dans le cas où il y a plusieurs classes fermées se pose la question de savoir dans quelle classe la chaîne de Markov
va ultimement être " bloquée ».DéfinitionSoitCune classe fermée (pour la chaîne de MarkovX). On noteCson temps d"atteinte :
C= inffn1jXn2 Cg:
Pour tout étatx2E, laprobabilité d"absorption parCpartant dexest qC(x) =?x(C<1):
On a évidemmentqC(x) = 1six2 CetqC(x) = 0sixappartient à une classe fermée différente deC.
Et sixappartient à une classes non fermée, alors sous?x,C= 1 +C1doncC<1si, et seulement siC1<1(pour atteindreCdepuisxil faut l"atteindre à partir de la positionX1). Par la propriété de Markov
au temps 1, ceci donne : qC(x) =?x(C1<1) =X
y2E? x(X1=y;C1<1) =X y2E? x(X1=y)?y(C<1);ce qui se ramène, siTest la réunion des classes non fermées (n.b. : ce sont des état transients), à
qC(x) =X
y2TP(x;y)qC(y) +X y2CP(x;y):Ces équations, d"inconnuesqC(x)pourx2 T, définissent un système linéaire dont on peut montrer, siTest
fini, qu"il admet une unique solution : on a donc une méthode de calcul des probabilités d"absorption.
43 Mesures invariantes
Dans toute cette partie, on supposera a priori la chaîne de Markov(Xn)n0irréductible. Dans le cas général,
on pourra néanmoins appliquer les théorèmes suivants à la chaîne de Markovrestreinteà une classe fermée et
en déduire alors des résultats sur certaines chaînes de Markov non irréductibles.Ayons en tête le cas récurrent : chaque état est visité infiniment souvent. Les définitions suivantes sont surtout
pertinentes dans ce cas-ci.Tandis que la question de la récurrence ou la transience ont trait au comportement asymptotique de(Xn)nde
façon qualitative (est-ce queXvisite tel état infiniment souvent?), on s"intéresse maintenant à des questions
plus quantitatives, à savoir :Com biende temps la suite (Xn)npasse-t-elle dans les divers états? (en proportion, pendant un tempsn! 1)
Com biende temps faut-il à la suite (Xn)npour revenir à son point de départ? (en espérance)
La loi de Xnadmet-elle une limite quandnest grand? Peut-on espérer une propriété de " mélange », à savoir
que la loi deXnne dépend presque plus de celle deX0et s"approche d"un équilibre?Pour toutn, on noten=?(Xn=x)
x2Ela loi deXn(on considérerancomme un vecteur-ligne). On a vu que, pour toutn2?, n+1=nP: Ainsi, sin!(et si la multiplication parPest continue),doit vérifier=P. DéfinitionUne mesuresurEestinvariante(pourP) si=P, c"est-à-dire : pour touty2E,(y) =X x2E(x)P(x;y): On parle deloi invariantesi de plusest une probabilité ((E) = 1). (On dit aussiloi/probabilité invariante/stationnaire) Vu la relationn+1=nP, on constate de suite que, siest une loi invariante etX0, alorsXnpour toutn. En revanche, sin"est pas une probabilité, alorsPn"a pas d"interprétation probabiliste.3.1 Existence et " unicité » des mesures invariantes
On va voir qu"une chaîne de Markovrécurrenteadmet toujours une mesure invariante (non nulle), et celle-ci
sera unique à un facteur près dès lors que la chaîne de Markov est irréductible. En particulier, une chaîne de
Markov finie irréductible admet toujours une mesure invariante, unique à un facteur près.Cas fini.Dans le cas fini, la relation=Psignifie queest un vecteur propreà gauchedePpour la valeur
propre 1, ou encore que test un vecteur propre (à droite) detP. Vu que 1 est valeur propre deP(la somme des lignes vaut 1), on sait que 1 est valeur propre de tP, donc il existe6= 0tel queP=. Il faut voir quel"on peut choisirà coefficients positifs; et l"unicité revient à dire que1est une valeur propre simple.
On peut donner une preuve élémentaire mais c"est aussi une conséquence d"un important théorème plus général :
Théorème (de Perron-Frobenius)SoitAune matrice carrée de tailleNà coefficients positifs. On supposeAirréductible : pour tousi;j, il
existen0tel que(An)i;j>0. Alors le rayon spectral deA,= maxfjjj2Sp(A)g, est une valeur propre simple deA, et admet un vecteur propre (non nul) à composantes positives.Cas général.On peut donner un argument probabiliste, qui donne une expression des mesures invariantes :
PropositionSiXest récurrente irréductible, alors il existe une mesure invariante (non nulle), unique à un facteur près.
Explicitement, si on se donnex02E, la mesuremx0définie par m x0(x) =?x0 x01X n=01 fXn=xg oùx0est le temps de retour enx0, est l"unique mesure invariante telle quem(x0) = 1. 5En toutes lettres,mx0(x)est, pour la chaîne de Markov issue dex0, le nombre moyen de visites àxavant de
retourner enx0.PropositionS"il y a un nombre fini d"états transients, alors toute mesure invariante est nulle sur ceux-ci.
3.2 Mesure réversible
DéfinitionUne mesuresurEestréversible(pourP) si, pour tousx;y2E, (x)P(x;y) =(y)P(y;x): La première remarque est qu"une telle mesure est invariante : pour touty2E, (P)(y) =X x2E(x)P(x;y) =X x2EP(y;x)(x) =(x): Cependant, la plupart des mesures invariantes ne sont pas réversibles.Un intérêt pour les mesures réversibles vient du fait qu"elles sont plus faciles à trouver (si elles existent) que les
mesures invariantes : le système ci-dessus se résout immédiatement (si on fixe(x), on déduit(y)pour tout
ytel queP(x;y)>0, etc., et il faut juste vérifier que ceci ne mène pas à des incohérences) Il peut donc être
bénéfique de commencer par chercher d"éventuelles mesures réversibles.L"intérêt principal est cependant théorique : on montre que, siX0suit la loi réversible (donc stationnaire), alors
la suite(X0;X1;:::;Xn)a même loi que la suite(Xn;Xn1;:::;X0), ce qui justifie l"appellation. Une chaîne de
Markov réversible a même loi, sous la probabilité stationnaire, lorsque l"on retourne le temps. Des parallèles
avec l"étude des réseaux électriques existent pour les chaînes de Markov réversibles, et une grande quantité de
résultats, souvent d"inspiration physique, leur sont spécifiques.3.3 Récurrence positive
La formule explicite (}) pour les mesures invariantes a un intérêt fondamental. Pour commencer, on note que
sa masse totale est : (échange espérance/série justifié car v.a. positives) m x0(E) =X x2Em x0(x) =?x0 X n< x0X x2E1 fXn=xg =?x0 X n< x01 =?x0[x0]: DéfinitionUn étatx2Eestrécurrent positifsi?x[x]<1. Si un état est récurrent et n"est pas récurrent positif, il est ditrécurrent nul.Par la remarque précédente, si un étatx0est récurrent positif, la mesure invariantemx0est finie (c"est-à-dire de
quotesdbs_dbs29.pdfusesText_35[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é