[PDF] [PDF] Examen Chaînes de Markov - Université Paris-Saclay

View - Download [PDF] Examen Chaînes de Markov - Université Paris-Saclay

Previous PDF

Next PDF

MAP-PRB201 Université Paris-Saclay

Examen "Chaînes de Markov"

Mercredi 23 Octobre 2020 de 9h00 à 12h00

Les résultats serontencadrés, et toute réponse devra être justifiée (sauf exception). Les exercices sont indépendants les uns des autres. Le barème est donné à titre indicatif, pour vous permettre de proportionner vos efforts. Il pourra être marginalement modifié. Noter que la somme excède 20.

Le sujet comporte4pages.

Le devoir dure 3h00.

Les téléphones sont rangés éteints dans les sacs; en guise d"aide mémoire, vous avez droit au recto d"une feuille manuscrite (par vos soins, pas de photocopie) sur la table.Exercice 1.[Renversement du temps, 8 points] SoitPune matrice de transition irréductible sur , etson unique mesure de probabilité sta- tionnaire. On définit une matrice^Ppar : 8x;y2 ;^P(x;y) =(y)P(y;x)(x) 1.

Mon trerque

^Pest bien définie et qu"il s"agit d"une matrice stochastique. 2.

Que v aut

^PsiPest réversible par rapport à? En déduire l"unique mesure de probabilité stationnaire de^Pdans ce cas. Vérifier que cette mesure de probabilité est encore l"unique mesure de probabilité stationnaire de^Psi l"on ne suppose pas la réversibilité deP.

Dans toute la suite on choisit

=f0;:::;ng, et, avec la notationx^y= minfx;yg:

P(x;y) =12

1fy=(x+1)^ng+1fy=0g;

3. Calculer l"unique mesure de probabilité stationnaire deP. 4.

Donner la matrice de transition

^P. (On pourra faire un dessin des transitions possibles sur un graphe). 5.

Mon trerque

^P(0;) =. 6.

Calculer

^Pt(x;)pour tout0txn1. 7.

Déduire sans calcul de ce qui précède

^Pt(x;)pourt > x,0xn1. 8. Soit ^Xla chaîne de Markov de matrice de transition^P. On note n1(^X) = minft0 :^Xt=n1g le temps d"atteinte den1par cette chaîne, calculerPn(n1(^X) =k)et reconnaître cette loi. 1

9.Soit tn. En déduire^Pt(n;n1)puis plus généralement^Pt(n;). Reconnaître en parti-

culier la mesure de probabilité^Pn(n;). 10.

Déduire sans calcul de ce qui précède

^Pt(n;)pour toutt > n. Commenter ce résultat.

Correction.Pbien définie car l"irréductibilité implique que l"unique mesure stationnaire est

strictement positive en tout pointx; le fait quePsoit stochastique découle alors du fait queest stationnaire pourP: ceci assure en effet que la somme sur les lignes vaut1, (et les coefficients sont positifs ou nuls). SiPest réversible par rapport àP, alors(x)^P(x;y) =(y)P(y;x)implique^P=P, dontest

l"unique mesure stationnaire. De façon plus générale, on vérifie sans peine queest une mesure

de proba stationnaire de^P, puisque : X x(x)^P(x;y) =X x(x)(y)P(y;x)(x)=(y)X xP(y;x) =(y) Ensuite, pour l"unicité de cette mesure stationnaire il suffit de noter que ^Pest encore irréductible.

Soitx;y2

. Alors il existet2Ntel quePt(y;x)>0de l"irréductibilité dePet ceci implique que ^Pt(x;y)>0, par exemple parce que^Pt(x;y) =(y)Pt(x;y)(x). On commence maintenant la partie avec la forme explicite deP, et d"abord le calcul de. On commence par observer que(x+ 1) =(x)1=2pour toutx2 f0;:::;n2get(n) =(n1). Ainsi(x) = (1=2)x^(n1)(0)pour toutx2 f0;:::;ng. Puis 1 = X

0xn(x) =(0)X

0xn1(1=2)x^n1=(0)1(1=2)n11=2+ (1=2)n1

= 2(0): Donc (x) = (1=2)(1+x)^n:

Ensuite, on calcule :

P(x;y) =1x=0(y) +10 (1y=n1+1y=n):

On souligne que

^P(0;)est égal à

On voit que

^Pt(x;) =xt()pour tout0txn1(évolution déterministe). Aussi^Px+1(x;) =puis commeest encore une mesure stationnaire pour^P,^Pt(x;) =pour tout

t > x. Pour comprendre^P(n;), on note quePn(n1=k) = (1=2)kpour toutk1, on reconnait une loi géométrique issue de1de paramètre de succès1=2. Ainsi pourx1,^Pt(n;nx) = P(n1=t(x1)) = (1=2)tx+1d"où, pourxn1,^Pn(n;x) = (1=2)n(nx1)= (1=2)x+1), et

donc puisque^Pnest une mesure de proba qui coincide avecsurf0;:::;n1g, nécessairement,^Pn(n;) =. Puisqueest stationnaire pour^P, on en tire^Px(n;) =pour toutx > n. Ainsi la

chaîne atteint sa mesure stationnaire en temps fini. Exercice 2.[Marche aléatoire biaisée : temps d"atteinte, 10 points] Soit deux réelsp;q2]0;1[tels quep+q= 1, avecp6=q. On considère sur =f0;1;:::;ng

la marche aléatoire(Xt)t2Nbiaisée avec des conditions au bord de type réflexion, de matrice de

transition :( P(x;y) =p1fy=x+1g+q1fy=x1gsix2 f1;:::;n1g;y2 f0;:::;ng

P(0;1) =P(n;n1) = 1

2 On rappelle quex= minft0 :Xt=xg 2N[ f1gdésigne le temps d"atteinte dex. On pose f(x) =Ex[n]2[0;1]pourx2 f0;:::;ng. 1. Construire un réseau fG;cgdont la marche aléatoire associée est la chaîne de Markov (Xt)t2N 2. À l"aide de l"iden titédu temps de transp ort,c alculerla v aleurdu temps de transp ort t

0$n:=E0[n] +En[0]:

On note que le temps de transport donne une borne supérieure surE0[n]. Les questions qui suivent visent à établir une borne inférieure. 3.

Justifier l"iden titéen loi suiv ante:

nsousP0=G1X i=1T i+R; où -Gest une variable Géométrique (surN?) de paramètrep=P0(+0> n) -T1;T2;:::dont des variables i.i.d. de loiP0(+02 j+0< n) -Rsuit la loiP0(n2 j+0> n), ces variables étant toutes indépendantes. (SiG= 1, on convient que la première somme est nulle). On ne demande pas une démonstration rigoureuse. On sera concis et on pourra faire un dessin. 4.

En déduire :

E

0[n] =1P

0(+0> n)1

E

0[+0j+0< n] +E0[nj+0> n]

5. Calculer E0[+0]etP0(+0> n)à l"aide de relations vue en cours. 6. On admet que E0[+0j+0< n]!E0[+0]quandn! 1. Déduire de ce qui précède un équivalent simple deE0[n]dans le casp < q(cet équivalent ne nécessite pas de calculer E

0[nj+0> n]).

La suite de l"exercice est indépendante de ce qui précède. Elle vise à calculer de façon exacte

f:f0;:::;ng ![0;1]; k7!f(k) =Ek[n]

à l"aide de la méthode à un pas.

7. Soit k2 f1;:::;n1g. Donner un lien entren(X)etn(X)sousPkla loi de la chaîne issue dek1, et en déduire à l"aide de la propriété de Markov une expression def(k)en fonction def(k1)etf(k+ 1). 8. Exprimer f(0)en fonction def(1). Donner aussif(n). 9. On p ose`(k) =f(k+1)f(k)pour0kn1. Montrer que`(k)satisfait une équation de récurrence du type`(k) =`(k1) +,1kn1, pour des paramètreset

que l"on précisera.1. on rappelle queest l"opérateur de translation :(X)t=Xt+1, et plus généralement,s(X)t=Xt+s;t;s2N

3

10.O nrapp elleque la solution de la récurrence affine précéden teest de la forme

`(k) =1+k `(0)1 ;0kn1: Calculer la fonction`dans notre cas et en déduire la fonctionf. 11. Do nnerdes équiv alentsde E0[n]quandn! 1dans les deux cas suivants : (i)p > q (ii)p < q oùp;qsont indépendants den. 12.

O np ose,p our2Rnf0gfixé,qn= 1pn=12

+n . Montrer qu"il existe alors':R!R+ que l"on précisera, tel que, quandn! 1: E

0[n]n2'():

Correction.Le réseau associé est donné par le grapheGspécifié avec les conductances : c(x;x+ 1) = (pq )x

etc(x;x) = 0: pas de boucles. Il suffit en effet de vérifier que ce réseau donne les bonnes transi-

tions : Pourx2 f1;:::;n1g,

P(x;x+ 1) =(pq

)x( pq )x+ (pq )x1=(pq pq ) + 1=p

P(x;x1) =(pq

)x1( pq )x1+ (pq )x=11 + pq =q tandis queP(n;n1)etP(0;1)valent bien1. On fera en sorte dans les écritures suivantes que

les quantités qui interviennent soient positives quandq > pet c"est dans ce régime qu"on prendra

nos équivalents. Notons quer(x;x+ 1) = (qp )xet partant

R(0$n) =(qp

)n1q p

1;C(0$n) =qp

1( qp )n1

Il faut aussi calculer le coefficient

c G= 2X xX yc(x;y) = 2Xc(e) = 2(pq )n1p q 1 On peut aussi désormais calculer le temps de transport t

0$n= 2(pq

)n1p q 11(qp )n1qp

2pq(pq)2(qp

)nsiq > p

Le tenps de transport donne une borne pour

E

0[n]t0$n2pq(pq)2(qp

)n 4

Il suffit pour justifier la décomposition demandée de noter que les différentes excursions de la

trajectoire en dehors de0sont indépendantes : le nombre de telles excursions jusquà la première

qui atteintnsuit une loi GeométriqueGde paramètrep=P0(n< +0), et conditionnellement à cette valeur,G, lesG1premières excursions sont indépendantes de loi celle de+0sachant +0< net laG-ième excursion est de loi celle de+0sachant+0> n.En prenant les espérances on a bien : 1P

0(+0> n)1

E

0[+0j+0< n] +E0[nj+0> n] =E0[n]

Ensuite :

P

0(+0< n) =c(0)P0(+0< n) =C(0$n) =C(0$n) =qp

1( qp )n1

Aussi,

quotesdbs_dbs4.pdfusesText_7

[PDF] processus de markov pour les nuls

[PDF] temperature pdf

[PDF] la chambre des officiers résumé film

[PDF] la chambre des officiers questionnaire reponse

[PDF] la chambre des officiers contexte historique

[PDF] la chambre des officiers clemence

[PDF] procédure de délogement d'un client

[PDF] comment satisfaire un client ayant été délogé subitement

[PDF] délogement interne ou externe

[PDF] overbooking hotel definition

[PDF] lancement d'une entreprise module 1

[PDF] lancement d'une entreprise module 7

[PDF] lancement d une entreprise module 4

[PDF] présenter une entreprise dans un mémoire

[PDF] exemple de présentation d'entreprise pour rapport de stage