cours-modelisation

Description

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

Informations

• Publié par: Vukih
• Nombre de lectures: 15
• Langue: Français

Extrait

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 meton pour sortir des classes transitoires ?S’il y a plusieurs classesferme´es,dansquelleclasseferm´eetombeton? 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,alorsp i,i+1 =p= 1−p i,i−1 ; p 0,1 = 0 =p N,N−1 , p 0,0 =p N,N = 1. Onfaitpartirlachained’un´etatk∈[1..N−1],e´abobitilerulprlatiarclacnoteemiau k que la chaines’arrˆeteen0. ♣Exercice 1: •Trouverunoed´rceeneralitleursreuresncu k npouon.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(X n ) n∈N ensensunmbleneˆıhaecundecuri´rkrvoedaMrsdaaleue`avtibl finiSnote. OnπıˆahcalekraMedentitaisloedirnaonqieu’lnufenotcoinov.Alorspourtout f:S→Renturemuesˆerqsvop,aMkreneditindelacaleıˆahlquesouelaitiiloq, n−1 X X 1 limf(X i ) =f(s)π(s). n→+∞ n i=0 s∈S D´emonstration:nsioctleuronsfitalpo´elrevge´’edtffiuorpt´e,ilsulin´eariPraf= 1 s ,s∈Sremarque que dans ce cas,. On n−1n−1 X X f(X i ) =1 s (X i ) i=0i=0 est le nombre de visites ensnedeMarkovjusqu’a`’lnitsnatdcaleıˆahn−1. Soit doncs∈Se,e´xfitµ 0 une loi unitiale quelconque surSnote. OnT s = (1) inf{n≥0 :X n =s}pmetpedselsivientemirere`es, puisR s = inf{n > T s : X n =s}le temps de premier retour ensaprre´uc,upsienrr:ce (m+1) (m) R s = inf{n > R:X n =s}. s Enutilisantlaproprie´te´deMarkov,onpeutmontrerquetoutescesvariables (m) ale´atoiressontind´ependantes,etquelesR s dentusplustomˆlaioD.meleoe plus n−1 X 1 s (X i ) =N n−1 , i=0 ou`(N t ) t≥0 ussscerouvnoredepeltsess,ai´ocleelntmetnisarexuaepmetrriv´ees (1) (2) (T s , R s , R s ...aisvdeuesqretponrpaleuqay’nli:ditdeluiesereqemi`,)uqsiio diff´erente,maiscelanechangepaslesproprie´t´esasymptotiquestrajectoriellesdu processusderenouvellement,etdonc,presquesuˆrement, n−1 X 1 1 lim1 s (X i ) =. (1) n→+∞ n E(R s ) i=0 45

(Remarquonsqueler´esultatnede´pendenaucunemani`eredelaloiinitialeµ 0 ) Par convergencedomin´ee,onend´eduitque n−1 X 1 1 limP µ 0 (X i =s) =. (1) n→+∞ n i=0 E(R s ) Mais en prenant pour loi initialeµ 0 =π, la loi invariante, on obtient: n−1n−1 X X 1 11 = limP π (X i =s) =limπ(s) =π(s), (1) n→+∞n→+∞ n n E(R s ) i=0i=0 ce qui conclut la preuve. Remarque:Soit (X n ) n∈N ecunedenıˆ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 E s (T s ) 0 = inf{n o`uT s ≥1 :X n =s}.pourrquetoutapnetiudeilucitr´endneOs∈S, 0 E s (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 etn 1 , n 2 , . . . , n p tels que le pgcd den 1 , n 2 , . . . , n p soit 1, et tels que

46