[PDF] TD 11 – Chaînes de Markov (récurrence/transience) (corrigé)

26 avr. 2012 Les trois parties sont indépendantes. Exercice 1 : On considère une chaîne de Markov (Xn)n?0 sur {1...

Processus aléatoires et applications

2 jan. 2010 A Solution de quelques exercices. 109. A.1 Exercices du Chapitre 1 . ... de taille N. Une cha?ne de Markov sur X de matrice de transition P ...

Les chaînes de Markov Exercices solutionnés

16 oct. 2000 H partir des trois graphes de transition suiv# ants reconstituez les chaJnes de Markov qui leur sont associées (espace dVétats et matrice de ...

Exercices sur les chaînes de Markov

Exercices sur les chaînes de Markov Exercice 2. Soit (Xn)n?0 une chaîne de Markov sur {1 2

Mary - TD 11 – Chaînes de Markov (récurrence/transience) (corrigé)

Exercice 2. Chaines de Markov ? Soit (Xn)n?N une chaîne de Markov associée à une matrice de transition P

TD 9 : Chaînes de Markov Corrigé

H = (S2n)n?0. Solution de l'exercice 1. 1. Oui. La matrice de transition est Q(x y) = 1.

Feuille dexercices n 2 : Chaînes de Markov : exemples et propriétés.

Montrer que (Yt)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ÎNES DE MARKOV

5.3.4 Graphe associé à une chaîne de Markov homogène . . . . . . . . . . . . . 82. 5.4 Exercices : Introduction aux chaînes de Markov .

TP9/10 : Chaînes de Markov - Arnaud Jobin

faire de l'exercice avec probabilité 0.3. 2) Si à l'heure n

Devoir Maison no 1 – Corrigé

Devoir Maison no 1 – Corrigé. Exercice 1. On considère la chaîne de Markov (Xn)n?0 sur Z définie par X0 = 0 et par les probabilités conditionnelles.

[PDF] CHAÎNES DE MARKOV - ceremade

5 3 4 Graphe associé à une chaîne de Markov homogène 82 5 4 Exercices : Introduction aux chaînes de Markov

[PDF] Processus-M1-2012-Examenpdf

26 avr 2012 · Corrigé de l'examen du 26 avril 2012 (durée 2h) Exercice 1 : On considère une chaîne de Markov (Xn)n?0 sur {1 7} de matrice de

[PDF] Exercices sur les chaînes de Markov

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

[PDF] TD 11 – Chaînes de Markov (récurrence/transience) (corrigé) - CNRS

Tien-Nam Le Alice Pellet--Mary TD 11 – Chaînes de Markov (récurrence/transience) (corrigé) Exercice 1 Récurrence et Transience Sur l'ensemble S = {0

[PDF] TD 10 – Chaînes de Markov (corrigé) - CNRS

TD 10 – Chaînes de Markov (corrigé) Exercice 1 Las Vegas Let A be a Las-Vegas randomized algorithm for a decision problem with an expected running time

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

Exercice 1 (Vrai ou faux) Soit (Sn) une marche aléatoire simple sur Z Lesquels des processus suivants sont des chaînes de Markov sur Z ? Pour ceux qui le sont

[PDF] Les chaînes de Markov Exercices solutionnés

16 oct 2000 · Les chaînes de Markov Exercices solutionnés Geneviève Gauthier dernière mise à jour : 16 octobre 2000 Probl?me 1 (30 points)

[PDF] Corrigé des exercices 1

Corrigé des exercices 1 Chaînes de Markov 2022-2023 1 Chaîne de Markov à deux états (a) Pour avoir une matrice stochastique il faut a b c d ? 0

[PDF] Chaines de Markov : compléments

Une cha?ne de Markov est dite irréductible lorsque tous ses états Exercice 1 : L'observation du développement d'un organisme (animal ou plante) au cours

[PDF] CORRIGÉ

CORRIGÉ Date : 30 septembre-4 octobre 2013 PRÉNOM : Groupe : Exercice 1 Donner la matrice de transition P de la cha?ne de Markov d'ensemble

[PDF] TD 11 – Chaînes de Markov (récurrence/transience) (corrigé) - CNRS

L3- Probabilités (Année2018/2019) Tien-Nam Le & Alice Pellet--MaryTD11- Chaînes de Markov (récurrence/transience) (corrigé)Exercice1.Récurrence et Transience

Sur l"ensembleS=f0,1,...,ngon considère la chaîne de Markov de matrice de transitionPdonnée pour 0xn1 par

P(x,y) =8

:psiy=x+1

1psiy=0

0 sinon

l"étatnétant absorbant (i.e.P(n,x) =1 sin=xet 0 sinon), et avec 01.Dessiner le graphe associé à cette chaîne de Markov. Quels sont les états récurrents et les états P fTn1<¥jX0=n1gPfX1=0jX0=n1g =1p <1.

2.SoitS=f1,...,6g, compléter la matrice suivante pour qu"elle soit matrice de transition d"une

chaîne de Markov 0 B

BBBBB@1/2 . 0 0 0 0

. 2/3 0 0 0 0

0 0 . 0 7/8 0

1/4 1/4 0 . 1/4 1/4

0 0 3/4 0 . 0

0 1/5 0 1/5 1/5 .1

CCCCCA

et déterminer quels sont ses états transitoires et récurrents. M=0 B

BBBB@1/2 1/2 0 0 0 0

1/3 2/3 0 0 0 0

0 0 1/8 0 7/8 0

1/4 1/4 0 0 1/4 1/4

0 0 3/4 0 1/4 0

0 1/5 0 1/5 1/5 2/51

C CCCCA

1/3 2/3

3.Montrer que la chaîne de Markov précédente contient deux ensembles fermés (i.e. aucun état en

dehors de l"ensemble n"est accessible depuis un état dans l"ensemble) irréductibles non videsC1

etC2. Calculer, pouri2 f1,2g, la probabilité P fXn2Cià partir d"un certain tempsjX0=6g. X 1 P fXn2C1? ?????? ???? ??????? ?????jX0=6g=å kP fXk=6g(1/5+1/51/4+1/51/4) =3/10å kP fXk=6g. P fXn2C2? ?????? ???? ??????? ?????jX0=6g=å kP fXk=6g(1/5+1/51/4) =5/20å kP fXk=6g. P

fXn2C2? ?????? ???? ??????? ?????jX0=6g=1? ?? ????? ?? ???? ?????? ????? ??? ?????? ????C1??C2???? ??????? ??????? ??

X åkPfXk=6g? ?????åkPfXk=6g(3/10+5/20) =1? ?? ???????åkPfXk=6g=20/11???? P fXn2C1? ?????? ???? ??????? ?????jX0=6g=6/11 P fXn2C2? ?????? ???? ??????? ?????jX0=6g=5/11.

Exercice2.Chaines de Markov?

Soit(Xn)n2Nune chaîne de Markov associée à une matrice de transitionPsur un ensemble d"étatsS.

1.S oitr2N. Est-ce que(Xr+n)n2Nest une chaîne de Markov?

2.Est-ce que (X2n)n2Nest une chaîne de Markov?

3.On suppose SZ. Est-ce que(2Xn+1)n2Nest une chaîne de Markov? Et(bXn/10c)n2N?

4.Est-ce que (Xn,Xn+1)n2Nest une chaîne de Markov?

5.On suppose les états de SnumérotésS=fS1,S2,...g. On définitS0=fT12,S3,S4,...g(on a

remplacé les deux premiers états deSpar un nouvel étatT12). On définitYn=XnsiXn2 Sn fS1,S2getYn=T12sinon (on a fusionné les deux premiers états de la chaîne). Est-ce une chaîne de Markov?

En cas de réponse positive, on précisera quelle est la matrice de transition (et on donnera une preuve

???? ?? ?????P2 0 B @P

0,0P0,10 0

0 0P1,0P1,1P

0,0P0,10 0

0 0P1,0P1,11

C A. @0 1 0 0 0 1

1 0 01

A ????? ???? ??? ?????? ?? ??????? ?? ?PfY2=3jY1=T12??Y0=T12g=16=0=PfY2=3jY1=T12??Y0=3g?

Exercice3.Marche aléatoire sur Z biaisée

Soitp2]0,1[, et considérons la chaîne de Markov d"espace d"étatsZet de matrice de transition

P(i,j) =8

:psij=i+1

1psij=i1

0 sinon

1.Cette chaîne est-elle irréductible?

2.Dans cette question on supposep6=1/2, montrer que tous les états de cette chaîne sont transients.

Indication : on pourra utiliser le lemme de Borel-Cantelli. On rappelle également l"équivalent de Stirling :

n!p2pn(n/e)n. ???? ?? ??? ???? ??????? ?? ??????? ??n=2k? ?????Pr(Xn=0jX0=0) =(2k (2k k)=O(4n)? ?????p6=1/2? ?? ?p(1p)<1/4? ?? ??????? ??? ?? ????? ???(2k k)(p(1p))k= ?? ?? ?????? ????? ?? ????? ????? ?????? ??? ?? ???? ???0? Exercice4.Marche aléatoire sur Z non biaisée

SoitfXkgdes variables aléatoires discrétes indépendantes et identiquement distribuées. ChaqueXkprend la valeur 1 avec probabilité 1/2 et1 avec probabilité 1/2. On définit alors une marche aléatoire

dansRparSn=ånk=1Xk. On s"intéresse à la probabilité d"un retour à l"origine (en un temps fini).

1.S"il y a eu un retour à l"origine au tempsm, que peut-on dire dem? Montrer qu"un retour à

l"origine au temps 2narrive avec une probabilitéu2n=(2n n)22n?

2.On définit de même la probabilitéf2nqu"un premier retour à l"origine se fasse au temps 2n. Mon-

trer que pourn>0 les probabilitésff2kgetfu2kgvérifient la relationu2n=f0u2n+f2u2n2+ +f2nu0(on poseu0=1 etf0=0).+?? ? ???? ????n>0? u

2n=PfS2n=0g=P([

02n=0\S2k=0\Si6=0????i<2k) =PfS2n=0\Si6=0????i<2ng n1å k=1S

2n=0\S2k=0\Si6=0????i<2k(par indépendance)

=u0f2n+n1å k=1u =u0f2n+u2f2n2+...+u2n2f2+f0u2n.

3.On définit les fonctions génératrices :

U(x) =¥å

m=0u

2mxmetF(x) =¥å

m=0f 2mxm

Déduire de la question précédente une relation simple entreU(x)etF(x).+?? ?U(x) =1+U(x)F(x)?

4.Montrer queU(x) =1p1x. En déduire queF(x) =1p1x.

Indication : on rappelle que(1+x)a=1++¥å

k=1a(a1)...(ak+1)k!xk. 3

1p14x= (14x)1/2=1++¥å

k=0 12 (12

1)...(12

k+1)k!(4x)k =1++¥å k=113...(2k1)(2)kk!(2)k2kxk=1++¥å k=1(2k)!k!k!xk=+¥å k=0 2k k x k

U(x) =+¥å

k=0 2k k 2

2kxk=+¥å

k=0 2k k x4 k=1p1x.

F(x) =U(x)1U(x)=1p1x.

5.Montrer quef2m=(2m

m)(2m1)22m.

Indication : considérerF0.

+?? ?F0(x) =12 p1x=U(x)2 ??????mf2m=u2(m1)2 =(2m2 m1)22m+1=m2(2m1)( 2m m)2

6.Définissonswnla probabilité qu"un retour à l"origine se fasse au plus tard au tempsn. Notre but

est de savoir si l"on va revenir en un temps fini, c"est-à-dire déterminerw=limn!¥wn. Montrer

quew=F(1). Conclure. +?? ?wn=åbn/2c 4quotesdbs_dbs29.pdfusesText_35

[PDF] [PDF] TD 11 – Chaînes de Markov (récurrence/transience) (corrigé) - CNRS

P(x,y) =8

1psiy=0

0 sinon

2.SoitS=f1,...,6g, compléter la matrice suivante pour qu"elle soit matrice de transition d"une

BBBBB@1/2 . 0 0 0 0

0 0 . 0 7/8 0

1/4 1/4 0 . 1/4 1/4

0 0 3/4 0 . 0

0 1/5 0 1/5 1/5 .1

CCCCCA

BBBB@1/2 1/2 0 0 0 0

1/3 2/3 0 0 0 0

0 0 1/8 0 7/8 0

1/4 1/4 0 0 1/4 1/4

0 0 3/4 0 1/4 0

0 1/5 0 1/5 1/5 2/51

1/3 2/3

3.Montrer que la chaîne de Markov précédente contient deux ensembles fermés (i.e. aucun état en

Exercice2.Chaines de Markov?

1.S oitr2N. Est-ce que(Xr+n)n2Nest une chaîne de Markov?

2.Est-ce que (X2n)n2Nest une chaîne de Markov?

3.On suppose SZ. Est-ce que(2Xn+1)n2Nest une chaîne de Markov? Et(bXn/10c)n2N?

4.Est-ce que (Xn,Xn+1)n2Nest une chaîne de Markov?

5.On suppose les états de SnumérotésS=fS1,S2,...g. On définitS0=fT12,S3,S4,...g(on a

0,0P0,10 0

0 0P1,0P1,1P

0,0P0,10 0

0 0P1,0P1,11

1 0 01

Exercice3.Marche aléatoire sur Z biaisée

P(i,j) =8

1psij=i1

0 sinon

1.Cette chaîne est-elle irréductible?

2.Dans cette question on supposep6=1/2, montrer que tous les états de cette chaîne sont transients.

1.S"il y a eu un retour à l"origine au tempsm, que peut-on dire dem? Montrer qu"un retour à

2.On définit de même la probabilitéf2nqu"un premier retour à l"origine se fasse au temps 2n. Mon-

2n=PfS2n=0g=P([

2n=0\S2k=0\Si6=0????i<2k(par indépendance)

3.On définit les fonctions génératrices :

U(x) =¥å

2mxmetF(x) =¥å

4.Montrer queU(x) =1p1x. En déduire queF(x) =1p1x.

Indication : on rappelle que(1+x)a=1++¥å

1p14x= (14x)1/2=1++¥å

1)...(12

U(x) =+¥å

2kxk=+¥å

F(x) =U(x)1U(x)=1p1x.

5.Montrer quef2m=(2m

Indication : considérerF0.

6.Définissonswnla probabilité qu"un retour à l"origine se fasse au plus tard au tempsn. Notre but