cours-modelisation
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
6Chapter 5Propri´et´es asymptotiques deschaˆınes de Markov5.1 Probl´ematiques des chaˆınes de MarkovOn a distingu´e, dans notre ´etude, les classes transitoires et les classes ferm´ees. On a vu qu’onfinissait toujours par sortir d´efinitivement de l’union des classes transitoires, pour aller dansl’union des classes ferm´ees.Question Combien de temps met-on pour sortir des classes transitoires ? S’il y a plusieursclasses ferm´ees, dans quelle classe ferm´ee tombe-t-on ?Donc quand on ´etudie le comportement asymptotique d’une chaˆıne de Markov , on regarded´ej`a dans quelle classe ferm´ee on tombe, puis, cette classe ´etant stable pour la matrice detransition, on peut restreindre la matrice de transition et se ramener au cas d’une chaˆıne deMarkov irr´eductible.Question Quel comportement statistique a une chaˆıne de Markov irr´eductible ?5.2 Un exemple avec ´etats absorbantsOn consid`ere la marche al´eatoire de l’ivrogne, sur [0..N], de param`etre p∈]0,1[, de probabilit´esde transitionsi 1≤i≤N−1, alors p =p = 1−p ;i,i+1 i,i−1p = 0 =p , p =p = 1.0,1 N,N−1 0,0 N,NOn fait partir la chaine d’un ´etat k∈ [1..N−1], et on aimerait calculer la probabilit´e u que lakchaine s’arrˆete en 0.♣ Exercice 1:• Trouver une relation de r´ecurrence sur les u , et en d´eduire leur expression. On pourrak´etudier s´epar´ement les cas p = 1/2 et p = 1/2.44• En proc´edant de la mˆeme mani`ere, calculer l’esp´erance du nombre de pas, partant de k,que fait le marcheur avant ...
Voir
Publié par
Langue
Français
Chapter 5
Propri´ete´sasymptotiquesdes chaˆınes de Markov
5.1Proble´matiquesdeschaˆınesdeMarkov Onadistingue´,dansnotree´tude,lesclassestransitoiresetlesclassesferm´ees.Onavuqu’on finissaittoujoursparsortirde´finitivementdel’uniondesclassestransitoires,pourallerdans l’uniondesclassesferme´es. QuestionCombien de temps meton pour sortir des classes transitoires ?S’il y a plusieurs classesferme´es,dansquelleclasseferm´eetombeton? Doncquandone´tudielecomportementasymptotiqued’unechaıˆnedeMarkov,onregarde de´ja`dansquelleclasseferm´eeontombe,puis,cetteclassee´tantstablepourlamatricede transition,onpeutrestreindrelamatricedetransitionetserameneraucasd’unechaıˆnede Markovirre´ductible. Questiontstnemetropmoclehaecuneaqutiisatkrvori´rıˆenedaMe?Queductibl
5.2Unexempleavece´tatsabsorbants Onconsid`erelamarcheale´atoiredel’ivrogne,sur[0..N`mteapar],deerp∈]0,s1de[,obprilab´eit de transition si 1≤i≤N−1,alorspi,i+1=p= 1−pi,i−1; p0,1= 0 =pN,N−1, p0,0=pN,N= 1. Onfaitpartirlachained’un´etatk∈[1..N−1],e´abobitilerulprlatiarclacnoteemiaukque la chaines’arrˆeteen0. ♣Exercice 1: •Trouverunoed´rceeneralitleursreuresncuknpouon.Oessiexprrra,eriuruelnetede´d e´tudierse´pare´mentlescasp= 1/2 etp6= 1/2.
44
•nadtembnoderes,partpa’lre´psenareudeci`eremanlcule,caadtncoe´ˆmmeedalprEnk, quefaitlemarcheuravantdes’arrˆeter. Danslecasge´n´eral,ondoitr´esoudredessyst`emeslin´eaires,pastoujourssimples.Onpeut aussiopterpouruneapprochedetypeMonteCarlo:onsimuleungrandnombred’expe´riences (marchesdel’ivrognejusqu’al’´etatabsorbant),etoncomptelaproportiondecasquiont termin´een0. BExemple:Eatqudnoicaleelahidruscr`ete,mod`eled´’velotuoidnu’entilapupo.on
5.3The´ore`meergodique Leth´eor`emeergodiqueestuneversiondelaloifortedesgrandsnombresadapte´esauxchaıˆnes de Markov. Th´eore`me5.3.1Soit(Xn)n∈Nensensunmbleneˆıhaecundecuri´rkrvoedaMrsdaaleue`avtibl finiSnote. OnπıˆahcalekraMedentitaisloedirnaonqieu’lnufenotcoinov.Alorspourtout f:S→Renturemuesˆerqsvop,aMkreneditindelacaleıˆahlquesouelaitiiloq, n−1 X X 1 limf(Xi) =f(s)π(s). n→+∞ n i=0s∈S D´emonstration:nsioctleuronsfitalpo´elrevge´’edtffiuorpt´e,ilsulin´eariPraf= 1s,s∈Sremarque que dans ce cas,. On n−1n−1 X X f(Xi) =1s(Xi) i=0i=0 est le nombre de visites ensnedeMarkovjusqu’a`’lnitsnatdcaleıˆahn−1. Soit doncs∈Se,e´xfitµ0une loi unitiale quelconque surSnote. OnTs= (1) inf{n≥0 :Xn=s}pmetpedselsivientemirere`es, puisRs= inf{n > Ts: Xn=s}le temps de premier retour ensaprre´uc,upsienrr:ce (m+1) (m) R s= inf{n > R:Xn=s}. s Enutilisantlaproprie´te´deMarkov,onpeutmontrerquetoutescesvariables (m) ale´atoiressontind´ependantes,etquelesRsdentusplustomˆlaioD.meleoe plus n−1 X 1s(Xi) =Nn−1, i=0 ou`(Nt)t≥0ussscerouvnoredepeltsess,ai´ocleelntmetnisarexuaepmetrriv´ees (1) (2) (Ts, Rs, Rs...aisvdeuesqretponrpaleuqay’nli:ditdeluiesereqemi`,)uqsiio diff´erente,maiscelanechangepaslesproprie´t´esasymptotiquestrajectoriellesdu processusderenouvellement,etdonc,presquesuˆrement, n−1 X 1 1 lim1s(Xi) =. (1) n→+∞ n E(Rs) i=0 45
(Remarquonsqueler´esultatnede´pendenaucunemani`eredelaloiinitialeµ0) Par convergencedomin´ee,onend´eduitque n−1 X 1 1 limPµ0(Xi=s) =. (1) n→+∞ n i=0E(Rs) Mais en prenant pour loi initialeµ0=π, la loi invariante, on obtient: n−1n−1 X X 1 11 = limPπ(Xi=s) =limπ(s) =π(s), (1) n→+∞n→+∞ n n E(Rs) i=0i=0 ce qui conclut la preuve. Remarque:Soit (Xn)n∈NecunedenıˆahrivokraMelnfiienunmbserseunsda`elblavade´ritcuS. On noteπentec´edrpe´ueevalrptieddu´end.OovrkMadeenıˆahcalederianistationuniquelo’l une autre expression pour la loi stationnaire: 1 ∀s∈S µ(s) =>0, 0 Es(Ts) 0 = inf{n o`uTs≥1 :Xn=s}.pourrquetoutapnetiudeilucitr´endneOs∈S, 0 Es(T)<+∞. s
5.4Ape´riodicite´etconvergenceversl’´equilibre On appellep’eriode´eund’attxceahıˆen’dnuetonnotedeMarkovd(x) le pgcd (plus grand commun diviseur) des longueurs des circuits du grapheGcontenantxstLo.paleuqsreedoire´ 1,onditquel’´etatxestequa´preoiid. Lemme 5.4.1e.odri´eepemmˆntoslisrola,tneuqiSixuedate´ocstnumm
0 D´emonstration:Soienti, javeci↔j. Soitγun chemin dei`aj,γun chemin dej`ai. SoitCnetnoc)etnalluentveidtvenemonque(´euitquelcnuiccrj. Alors 0 0 γ−γetγ− C −γsont deux circuits contenanti. Doncd(i) divise leurs longueurs ainsiqueladiffe´rencedeleurslongueurs,soitlalongueurdeC. Ainsid(i) divise les longueurs de tous les circuits contenantj, donc divise leur pgcd, soitd(jla). De mˆememani`ere,onmontrequed(j) divised(i)d,o’u`d(i) =d(j). Siunechaˆıneirre´ductibleases´etatsdep´eriode1,onditqu’elleestioerp´aeuqid. Lemme 5.4.2Soitx´nutate´pedioerde1. Ilexiste un entierN(x)tel que pour toutn≥N(x) legrapheassocie´`alachaˆınedeMarkovposs`edeuncircuitdelongueurncontenantx
D´emonstration:SoitAl’ensemble des valeurs denei´ocsseaphraseuqlegeetll a`lachaıˆnedeMarkovposs`edeuncircuitdelongueurncontenantxest clair. Il queAestlepastabti)sS.iontina´ecuirscdeoitiddartacnoc(nxriode1,sedtpee´ il existep≥1 etn1, n2, . . . , nptels que le pgcd den1, n2, . . . , npsoit 1, et tels que
46
