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

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

M1-Processus Année2011–2012 Corrigé de l’examen du 26 avril Dessiner le graphe de la chaîne de Markov associée en précisant les probabilités de transitions

Exercices - Laboratoire de Probabilités, Statistique et

propri et e de Markov au temps 1 permet d’a rmer par ailleurs que E 1[T 0] = 1 2 (1 + 2E 1[T 0]); ce qui implique que E 1[T 0] = +1, de sorte que la marche simple sym etrique sur Z est r ecurrente nulle 3 La marche reste en son point de d epart un nombre g eom etrique de pas de param etre

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

Processus de Markov et applications - Association Tremplin

di˙usion, qui sont encore des processus de Markov, mais cette fois à la fois en temps continu, et à valeurs dans l’espace euclidien IRd Chaque chapitre est suivi d’un certain nombre d’exercices Certains de ces exercices sont suivis de la mention (en gras) Programmation Cela veut

Corrigé de l’examen du 18 avril 2013 (durée 2h)

M1-Processus Année2012–2013 Corrigé de l’examen du 18 avril 2013 (durée 2h) n 0 une chaîne de Markov associée à la matrice de transition Q,

Processus al eatoires et applications

Cha^ nes de Markov sur un ensemble ni 1 1 Exemples de cha^ nes de Markov Les cha^ nes de Markov sont intuitivement tr es simples a d e nir Un syst eme peut admettre un certain nombre d’ etats di erents L’ etat change au cours du temps discret A chaque changement, le nouvel etat est choisi avec une distribution de probabilit e x ee au pr

Processus markoviens de sauts - lpsmparis

Dans de nombreux modèles, les transitions entre deux instants t et t′ ne dépendent pas des dates t et t′, mais seulement du temps écoulé entre ces deux dates, c’est-à-dire de (t′ −t) C’est ce qu’on appelle l’homogénéité (temporelle) de la chaîne Déﬁnition 1 2 (Chaîne de Markov homogène) La chaîne de Markov (X t)

MAT-3071 Processus Stochastiques - univ-rennes1fr

3 Processus de Poisson Rappels sur les lois exponentielle et de Poisson, processus de comptage, d´eﬁnition d’un processus de Poisson, Processus de Poisson compos´e, Processus de renouvellement, application a la ruine d’une compagnie d’assurance 4 Chaˆınes de Markov `a temps continu

Recherche Opérationnelle - LORIA

Recherche Opérationnelle: Programmation dynamique, chaînes de Markov, ﬁles d’attente Cours de Tronc Commun Scientiﬁque FICM 2A Notes de cours et exercices corrigés

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

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