TD 9 : Chaînes de Markov Corrigé

Initiation aux processus : Cha^ nes de Markov (solutions) Fabrice Rossi 18 f evrier 2003 1 Espace d’ etat ni 1 1 Exercice 1 1 1 1 Question 1 Pour repr esen ter la cha^ ne, on choisit de num eroter les etats de 1 a 3, dans l’ordre des lignes (ou des

Les chaînes de Markov Exercices solutionnØs

Les chaînes de Markov Exercices solutionnØs GeneviŁve Gauthier derniŁre mise à jour : 16 octobre 2000 ProblŁme 1 (30 points) À partir des trois graphes de transition suiv-ants, reconstituez les chaînes de Markov qui leur sont associØes (espace d™Øtats et matrice de transition) Pour chacune de ces chaînes de Markov, faites-en

Exercices sur les chaînes de Markov

Exercices sur les chaînes de Markov 1 Exemples à espace d’états finis Exercice 1 On dispose de deux pièces, une non pipée, et une qui est truquée et est “Face” des deux côtés On commence par en choisir une des deux au hasard (de manière uniforme) et ensuite on lance celle-làuneinﬁnitédefois

Feuille d’exercices &# 3 : Chaînes de Markov

Master 1 Mathématiques Chaînes de Markov et martingales Feuille d’exercices # 3 : Chaînes de Markov Exercice 1 Sous-suites de chaînes de Markov 1 Soient U,V,W trois variables aléatoires à valeurs dans E ensemble dénombrable On suppose que pour tout u ∈ Nla fonction (v,w) → P(U = uV = v,W = w) est bien déﬁnie et ne dépend pas

Chaînes de Markov - Université Paris-Saclay

Chaînes de Markov Résumé Une chaîne de Markov est un processus aléatoire (Xn)n2N dont les transitions sont données par une matrice stochastique P(Xn,Xn+1) Ces processus vériﬁent la propriété de Markov, c’est-à-dire qu’observés àpartird’untemps(d’arrêt)T, (XT+n)n2N ne dépend que de XT et est de nouveau une chaîne de

Feuille d’exercices n 2 : Chaînes de Markov : exemples et

0 t n est encore une chaîne de Markov de matrice de transition Q et de mesure initiale à préciser Correction Cet exercice montre que la chaîne de Markov renversée en temps (à horizon ﬁni donc) est encore une chaîne de Markov si on la considère sous sa mesure stationnaire, un

TD 9 : Chaînes de Markov Corrigé

Solution de l’exercice 3 1 Soit i 0 Par la propriété de Markov forte, conditionnellement à F T i, le processus (S T i+n) n 0 a la loi d’une marche simple issue de i, donc Se= (S T i+n i) n 0 est une marche simple sur Z conditionnellementàF T i Deplus,ona T i+1 T i = minfn 0jSe n = 1g; donc conditionnellement à F T i, la variable T i+1

TP8/9 : Chaînes de Markov

Les chaînes de Markov aux concours (EDHEC 2017) L’épreuve EDHEC 2017 portait sur le déplacement au cours du temps d’un mobile sur les 4 sommets d’uncarré Voiciuneretranscriptiondel’énoncé

INTRODUCTION AUX CHAÎNES DE MARKOV

Corrigé de l’examen du 26 avril 2012 (durée 2h)

Corrigé de l’examen du 26 avril 2012 Exercice 1 : OnconsidèreunechaînedeMarkov(X Dessiner le graphe de la chaîne de Markov associée en précisant les

Processus aléatoiresThomas Budzinski

ENS Paris, 2016-2017 Bureau V2

thomas.budzinski@ens.fr

TD 9 : Chaînes de Markov

Corrigé

Lundi 28 Novembre

Exercice 1(Vrai ou faux)

Soit(Sn)une marche aléatoire simple surZ. Lesquels des processus suivants sont des chaînes de Markov

surZ? Pour ceux qui le sont, donner la matrice de transition.

1.A= (Sn)n0,

2.B= (Sn+n)n0,

3.C=Sn+n2

n0,

4.D= (Sn+ 10n)n0,5.E= (Sn+ (1)n)n0,

6.F= (jSnj)n0,

7.G=S2nn

n0,

8.H= (S2n)n0.

Solution de l"exercice 11.Oui. La matrice de transition es tQ(x;y) =12 sijxyj= 1et0sinon. 2.

Oui. La matrice de transition es tQ(x;y) =12

siy=xouy=x+ 2, et0sinon. 3. Non. Si Cétait une chaîne de Markov de matrice de transitionQ, on aurait d"une part

P(C0= 0;C1= 0) =Q(0;0)

soitQ(0;0) =P(S1=1) =12 , et d"autre part

P(C0= 0;C1= 0;C2= 0) =Q(0;0)2;

maisC2 2+22= 2doncP(C2= 0) = 0doncQ(0;0)2= 0etQ(0;0) = 0, d"où la contradiction. 4. Oui. La matrice de transition est la suiv ante: p ourtous n2Netk2Zde même parité quentel quejkj n, on aQ(10n+k;10n+1+k+ 1) =Q(10n+k;10n+1+k1) =12 , etQ(10n+k;y) = 0

pour tous les autresy. Cette définition a bien un sens car chaque entier peut s"écrire d"au plus une

manière comme10n+kavecjkj n. Notons que cet argument ne marche plus pour l"exemple précédent, car par exemple0peut s"écrire02+ 0, mais aussi12+ (1). 5. Oui. La matrice de transition est la suiv ante: si xest pair alorsQ(x;y) =12 siy=x1ouy=x3 et0sinon. Sixest impair alorsQ(x;y) =12 siy=x+ 1ouy=x+ 3et0sinon. 6. Oui. La matrice d etransition est la suiv ante: on a Q(0;1) = 1etQ(0;y) = 0pour touty6= 1et, pourx1, on aQ(x;y) =12 sijyxj= 1et0sinon. 7. Non. Si Gétait une chaîne de Markov de matrice de transitionQ, on aurait d"une part

Q(0;0) =P(G1= 0) =PS21= 1= 1

et d"autre part Q(0;0) =P(G5= 0jG0= 0;G1= 0;G2= 2;G3= 6;G4= 0) = 0 1 carP(G5= 0) = 0(il faudraitS25= 5), alors que P(G0= 0;G1= 0;G2= 2;G3= 6;G4= 0)P(S1= 1;S2= 2;S3= 3;S4= 2)>0: 8.

Oui. La matr icede transition es t

Q(x;y) =8

:12 six=y; 14 sijxyj= 1;

0sinon:

Exercice 2(Chaîne de Markov et indépendance) SoientSun ensemble dénombrable et(G;G)un ensemble mesurable. Soient aussi(Zn)n1une suite de variables i.i.d. à valeurs dans(G;G)et:SG!Sune application mesurable. On définit une suite de variables(Xn)n0à valeurs dansSparX0=x2SetXn+1=(Xn;Zn+1)pour toutn0. Montrer que(Xn)n0est une chaîne de Markov et déterminer sa matrice de transition. Solution de l"exercice 2Soientn0et(x0;:::;xn)2Sn. On a par indépendance : P(X0=x0;:::;Xn=xn) =P(X0=x0;(x0;Z1) =x1;(x1;Z2) =x2;:::;(xn1;Zn) =xn) =P(X0=x0)P((x0;Z1) =x1)P((x1;Z2) =x2):::P((xn1;Zn) =xn) =P(X0=x0)P((x0;Z1) =x1)P((x1;Z1) =x2):::P((xn1;Z1) =xn): On poseQ(y;z) =P((y;Z1) =z)pour tout(y;z)2S2. On peut alors écrire P(X0=x0;:::;Xn=xn) =P(X0=x0)Q(x0;x1)Q(x1;x2):::Q(xn1;xn): Cela signifie que(Xn)n0est une chaîne de Markov de matrice de transitionQ. Exercice 3Soit(Sn)n0une marche aléatoire simple surZissue de0. Pour touti0, on pose T i= minfn0jSn=ig(on rappelle que tous lesTisont finis p.s. par récurrence deS). 1.

Mon trerq ueles v ariablesTi+1Tisont i.i.d.

2. On supp osemain tenantque Sest une marche biaisée négativement, i.e. lesSn+1Snsont i.i.d. et

P(Sn+1Sn=1) = 1P(Sn+1Sn= +1)>12

Montrer sans calcul queM= maxfSnjn0gest une variable géométrique.

Solution de l"exercice 31.Soit i0. Par la propriété de Markov forte, conditionnellement àFTi, le processus(STi+n)n0

a la loi d"une marche simple issue dei, donceS= (STi+ni)n0est une marche simple surZ conditionnellement àFTi. De plus, on a T i+1Ti= minfn0jeSn= 1g; donc conditionnellement àFTi, la variableTi+1Tia la même loi queT1. Comme cette loi est toujours la même, la variableTi+1Tiest indépendante deFTi. Or, les variablesT1;T2T1;:::;Ti T i1sontFTi-mesurables, doncTi+1Tia la loi deT1et est indépendante de(Tj+1Tj)0ji1, d"où le résultat. 2. Le raisonnemen test similaire. Soit i0. Conditionnellement àFTi, siTi<+1, le processus eS= (STi+ni)n0est une marche simple surZpar la propriété de Markov forte, donc

P(Ti+1<+1jTi<+1) =P

9n0;eSn= +1

=P(T1<+1): Par récurrence, on en déduitP(Ti<+1) =P(T1<+1)ipour touti0, d"où le résultat car T i<+1équivaut àMi. 2

RemarqueLe résultat de la deuxième question a déjà été obtenu (avec le paramètre de la loi géométrique)

de manière plus calculatoire dans l"exercice 4 du TD4. Exercice 4Soit(Sn)n0la marche aléatoire simple surZ. Pourx2Zavecx6= 0, montrer que l"espérance du nombre de visites dexavant le premier retour en0vaut1. Solution de l"exercice 4Pour touti2Z, on notei= inffn >0jSn=ig. On note aussiNx([0;0[)le nombre de passages enxavant le premier retour en 0. Dire queNx([0;0[) =krevient à dire que la marche atteintxsans repasser par 0, puis en partant dexrevientk1fois surxtoujours sans repasser

par 0 et enfin en partant dexva en 0 sans repasser parx. D"après la propriété de Markov forte, on a

donc P

0(Nx([0;0[) =k) =P0(x< 0)Px(x< 0)k1Px(0< x):

Il faut donc calculer ces trois quantités. Supposonsxpositif. On a, en utilisant la propriété de Markov

simple, P

0(x< 0) =P0(S1= +1etx< 0) =P0(S1= +1)P1(x< 0) =12

1x Par symétrie, on a aussiPx[0< x] =12xetPx[x< 0] = 112x. L"espérance cherchée vaut donc E

0[Nx([0;0[) =k] =1X

k=1k12x 112x
k112x= 1: Exercice 5(h-transformée d"une chaîne de Markov) SoitSun ensemble dénombrable et(Xn)n0une chaîne de Markov surSde matrice de transitionQ. Soith:S!R+. SoitPla matrice définie surS+=fx2Sjh(x)>0gpar la formule

P(i;j) =h(j)h(i)Q(i;j):

1. Donner une h ypothèsesur hqui garantit quePest la matrice de transition d"une chaîne de Markov surS+. Que signifie cette hypothèse siXest la marche aléatoire simple sur un graphe?On dit alors quePest lah-transformée deQ. 2.

Soit Yune chaîne de Markov de matrice de transitionP. Déterminer la dérivée de Radon-NikodÞm

de la loi de(Yi)0inpar rapport à celle de(Xi)0in. 3. On c onsidèrela marc healéatoire simple SsurZ. On noteTi= inffn0jSn=ig. PourN >0et k2[[0;N]], on définit P (N) k=Pk( jTN< T0): (a)

On rapp elleque Pk(TN< T0) =kN

. Montrer que sousP(N) k,(Sn^TN)n0est une chaîne de

Markov et donner sa matrice de transition.

(b) T rouverune fonction h: [[0;N]]!R+telle que la matrice de transition de la question précé- dente soit lah-transformée de la matrice de transition de la marche aléatoire simple. (c)

Prop oserune définition de la "marc healéatoire simple s urZconditionnée à rester positive".

Solution de l"exercice 51.Il faut a voir

P j2S+P(i;j) = 1pour touti2S+, soit X j2S+Q(i;j)h(j) =h(i): Par définition deS+, le membre de droite est égal àP j2SQ(i;j)h(j)car les contributions pour j2SnS+sont nulles. Une condition suffisante est donc

8i2S+;h(i) =X

j2SQ(i;j)h(j): SiXest une marche aléatoire simple, i.e.Q(i;j) =1deg(i)?i$j, cette condition signifie quehest harmonique surS+. 3

2.Soien ty0;:::;yn2S+. On a

P(Y0=y0:::;Yn=yn) =P(X0=y0)P(y0;y1):::P(yn1;yn)

h(yn)h(y0)P(X0=y0:::;Xn=yn): La dérivée de Radon-Nikodym recherchée vaut donc h(Xn)h(X0). 3.

On calcule

P (N) k(Xn+1=xn+1jX0=x0;:::;Xn=xn)

Pk(X0=x0;:::;Xn=xn;Xn+1=xn+1etTN< T0)P

k(X0=x0;:::;Xn=xnetTN< T0): Par la propriété de Markov simple, on aPk(X0=x0;:::;Xn=xnetTN< T0) =12 nxnN , ainsi quePk(X0=x0;:::;Xn=xn;Xn+1=xn+1etTN< T0) =12 n+1xn+1N . Par conséquent, P (N) k[Xn+1=xn+1jX0=x0;:::;Xn=xn] =xn+12xn:

La marche arrêtée sous la probaP(N)

kest donc une chaîne de Markov de matrice de transition

Q(x;y) =y2x?jxyj=1etQ(N;N) = 1:

Il s"agit de lah-transformée de la marche simple stoppée enNavech(x) =x. Conditionner une marche aléatoire simple surZ(issue, par exemple, de1) à ne pas taper0n"a a

priori pas de sens. Une manière de lui donner un sens est de la conditionner à taperNavant0puis

de faire tendreNvers+1. D"après la discussion qui précède, pour tousnetx0;x1;:::;xnavec x

0= 1on a

P (N)

1(X0=x0;:::;Xn=xn)!n!+1n1Y

i=0x i+12xi?jxi+1xij=1: Un candidat naturel est donc lah-transformée de la marche simple avech(x) =x?x>0.

RemarqueL"utilisation d"uneh-transformée pour "conditionner" une marche aléatoire à un événement

de probabilité nulle (par exemple ne pas taper un état ou un ensemble d"états donné) fonctionne dans

des cas assez variés.

Exercice 6(La fourmi et la montre)

Une fourmi se promène sur une montre de la manière suivante : elle démarre sur le chiffre0et, toutes

les minutes, elle se déplace avec proba 12 d"un chiffre vers la gauche et avec proba12 d"un chiffre vers la

droite. On noteCle dernier chiffre de la montre visité par la fourmi. Montrer queCest une variable

uniforme surf1;2;:::;11g. Solution de l"exercice 6Notons d"abord queC <+1p.s. car la fourmi finit forcément par faire12

pas consécutifs vers la gauche (argument déjà vu en TD, par exemple exercice 3 du TD4). Pour tout

i2Zn12Z, on noteTile premier temps auquel la fourmi découvrei. Pour touti2(Z=12Z), on a

P(C=i) =P(Ti> Ti1;Ti> Ti+1)

=P(Ti1< Ti+1< Ti) +P(Ti+1< Ti1< Ti) =P(Ti1< Ti+1)P(Ti+1< TijTi1< Ti+1) +P(Ti+1< Ti1)P(Ti1< TijTi+1< Ti1):

Mais d"après la propriété de Markov forte, conditionnellement àFTi1, la marche de la fourmi aprèsTi1

a la même loi qu"une marche aléatoire démarrée dei1, doncP(Ti+1< TijTi1< Ti+1)est égale à la

probabilité qu"une marche démarrée eni1atteignei+ 1avanti. Par invariance par rotation, cette

probabilité ne dépend pas deidonc vautP(T2< T1). De même, on a

P(Ti1< TijTi+1< Ti1) =P(T10< T11) =P(T2< T1);

où la dernière égalité s"obtient par symétrie. On obtient donc P(C=i) =P(Ti1< Ti+1)P(T2< T1) +P(Ti+1< Ti1)P(T2< T1) =P(T2< T1): Comme cela ne dépend pas dei, on en déduit queCest bien uniforme surf1;2;:::;11g. RemarqueAu passage, au a montré queP(T2< T1) =111 , c"est-à-dire que pour la marche simple surZ on aP(T10< T1) =111 , résultat qu"on a déjà obtenu par le théorème d"arrêt. 5quotesdbs_dbs29.pdfusesText_35

[PDF] TD 9 : Chaînes de Markov Corrigé