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

View - Download TD 9 : Chaînes de Markov Corrigé

Previous PDF

Next PDF

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

4

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] chaine énergétique barrage hydraulique

[PDF] chaine énergétique d'une éolienne

[PDF] exercice corrigé centrale hydraulique

[PDF] chaine énergétique centrale thermique

[PDF] chaine énergétique pile

[PDF] chaine énergétique exercices

[PDF] chaine énergétique éolienne

[PDF] chaine énergétique panneau solaire

[PDF] chaine energetique definition

[PDF] chaine énergétique exemple

[PDF] cours de logistique de distribution pdf

[PDF] introduction logistique

[PDF] cours management de la chaine logistique pdf

[PDF] logistique et supply chain management

[PDF] supply chain management livre pdf