[PDF] [PDF] CCM_TD2pdf - Ceremade Contrôle des chaînes

View - Download [PDF] CCM_TD2pdf - Ceremade

Previous PDF

Next PDF

Université Paris-Dauphine Master 1, Mathématiques et applications Contrôle des chaînes de Markov Année : 2022-2023

Feuille d"exercices2:Arrêt optimal

Exercice 1.SoitXune v.a. intégrable etTun temps d"arrêt d"une filtration(Fn)n0. 1. Mon trerque FT, la tribu du passé jusqu"à l"instantT, est une tribu. 2.

Mon trerque TestFT-mesurable.

3.

Soit k0et supposons queTk. Montrer qu"alorsFT=Fk.

4. Mon trerque si T <1p.s. et si(Xn)n0est un processus adapté, alorsXTestFT- mesurable. 5. Mon trerque si SetTsont des temps d"arrêts tels queSTp.s., alorsFSFT.

Exercice 2.

Soient(Xn)n0une martingale etTun temps d"arrêt (de la filtration(Fn)n0). 1. Rapp elerl"énoncé du th éorèmed"arrêt. 2. On se prop osede mon trerune v ariantede ce théorème. Supp osonsque Tvérifie (H1)P(T <+1) = 1;(H2)E[jXTj]<1;(H3) limn!1E[jXnjIfT>ng] = 0: (a)

Mon trerque limn!1E[jXTjIfT>ng] = 0.

(b)

Mon trerque limn!1E[jXn^TXTj] = 0.

(c)

En déduire que E[XT] =E[X0].

Exercice 3.[Partiel 2013 - 2014]

SoitTun temps d"arrêt d"une filtration(Fn)n0. On suppose qu"il existe" >0tel que, pour toutn0, on a

P(Tn+ 1jFn)> "p.s.

Montrer queE[T]<1; en déduire queTest fini p.s. Indication : on rappelle que pour une v.a.Xà valeurs dansN,E[X] =P1 n=1P(Xn):

Exercice 4.[Partiel 2016 - 2017]

SoientSetTdeux temps d"arrêt d"une filtration(Fn)n0. 1 Montrer que l"événementfSTgest dans la tribuFS\FT.

Exercice 5.[Problème de Moser]

Chaque minute, une machine tire au hasard un nombre réel positif. On noteXnle réel obtenu à la minutenet on suppose que les(Xn)n1sont des v.a. i.i.d. positives d"espérance finie. Vous pouvez observer la machine pendantNminutes. Chaque minute, vous avez le choix entre dire "stop" ou "je continue", mais vous ne pouvez dire "stop" qu"une seule fois. Si vous décidez de

vous arrêter à la minuten, on vous remet (en euros) la sommeXnet le processus s"arrête là.

Sinon le processus continue jusqu"à ce vous disiez "stop". L"horizon est fini : si vous ne vous êtes

pas arrêtés strictement avant la minuteN, vous devez dire "stop" à la minuteN. L"objectif est

de trouver une stratégie optimale maximisant la somme reçue. 1. Rapp elerla défini tionde la fonction v aleur(Zn)1nN, solution de ce problème d"arrêt optimal et montrer que, pour tout1nN,Znest mesurable par rapport à(Xn) (utiliser une récurrence rétrograde). 2.

P ourtout 1nN, on poseVn:=E[Zn]. Montrer que,

81nN1; Vn='(Vn+1);

où, pour toutx2R,'(x) =E[max(X1;x)]. 3. Mon trerque 'est une fonction positive et croissante, telle que'(x)xest positive, décroissante etlimx!1('(x)x) = 0. Tracer l"allure de la fonction'. 4.

Mon trerqu"u ntemps d"arrêt optima lest

T inff1kN1 :XkVk+1gsi non vide

Nsinon:

5. Supp osonsque les (Xn)n1sont uniformément distribués sur[0;1]et prenonsN= 6. Montrer que la stratégie optimale est donnée par la procédure suivante : on s"arrête au temps 1 siX10:775; sinon on regardeX2et on s"arrête au temps 2 siX20:742; sinon on regardeX3et on s"arrête au temps 3 siX30:695; sinon on regardeX4et on s"arrête au temps 4 siX40:625; sinon on regardeX5et on s"arrête au temps 5 si X

51=2, sinon on s"arrête au temps 6.

Quel est le gain moyen optimal?

Exercice 6.On cherche à choisir parmiNobjets distincts le meilleur avec la plus grande

probabilité possible. Le principe est d"inspecter les objets un par un, et à chaque fois de décider

si on choisit l"objet inspecté (dans ce cas le processus d"inspection s"arrête et on ne regardera

pas les objets suivants) ou si on passe à l"inspection de l"objet suivant. On ne peut pas revenir en arrière. Si lesN1premiers objets n"ont pas été choisis, on prend alors automatiquement leN-ième objet.

L"objectif de cet exercice est de déterminer une stratégie d"arrêt nous permettant de maximiser

la probabilité de choisir le meilleur objet parmi lesNà notre disposition. Soit( ;F;P)un espace probabilisé etSNl"ensemble des permutations deNéléments. Soit !SNune variable aléatoireuniformeà valeurs dansSN. Pour1nN, la valeurn 2

représente le rang absolu dun-ième objet inspecté (on suppose que les objets ont tous une valeur

différente). Par exemple sin(!) = 1, le meilleur objet est dans la positionn. On remarque qu"on ne peut pas observer directement(!)(on ne connaît le classement absolu desNobjets qu"une fois qu"on les a tous inspectés). A chaque étapen, on observe une variable aléatoireXnqui donne le rangrelatifdun-ième objet inspecté par rapport auxn1objets inspectés auparavant. DoncX1= 1,X22 f1;2g,:::,Xn2 f1;:::;ngetXN= N: une fois qu"on a inspecté tous les objets on connaît leur classement absolu. A chaque instantn, on connaîtFn=(X1;:::;Xn), la tribu engendrée par les rangs relatifs desnpremiers objets. Par exemple : siN= 4et(!) = (3;4;1;2)alorsX1(!) =

1;X2(!) = 2;X3(!) = 1;X4(!) = 2.

Soit =f(x1;:::;xN)2?N: 16xk6k; k= 1;:::;Ngl"ensemble des valeurs possibles pour le vecteur aléatoireX= (X1;:::;XN). Remarquons queXest une fonction mesurable de. Plus précisément, l"application :SN!qui associe à une permutation la suite correspondante des rangs relatifs est bijective, doncX= et = 1X: étant donnée la suite de rangs relatifsX1(!);:::;XN(!), on peut reconstruire(!). Notre objectif est de trouver un temps d"arrêtT(pour la filtration(Fn)1nN) borné parN, qui maximise la quantité

P(T= 1) =E?fT=1g:

1.

Mon trerque

8(x1;:::;xN)2;P(X1=x1;X2=x2;:::;XN=xN) =1N!:

2. Mon trerque les v ariables(Xn)1nNsont indépendantes et que pour tout1nNet tout1jn,

P(Xn=j) =1n

3. On définit le pro cessusadapté (Yn)1nN, parYn=E?fn=1gjFn. Montrer que pour tout temps d"arrêtTborné parN,

P(T= 1) =E[YT]:

4.

Mon trerque, p ourtout 1nN,

Y n=nN ?fXn=1g; (en particulierYnest mesurable par rapport à(Xn)). 5. Mon trerque la fonc tionv aleur(Zn)1nNest bien définie et que, pour tout1nN, Z nest mesurable par rapport à(Xn). En déduire qu"un temps d"arrêt optimal est donné par T inf1kN1 :E[Zk+1]kN ;Xk= 1si cet infimum existe

Nsinon.

6. Mon trerqu eE[Zn]décroît quandncroît. En déduire qu"il existe un entier1rN1 tel queT?=Troù T r=( inffrkN1 :Xk= 1gsi cet infimum existe

Nsinon.

3

7.Mon trerque p our1< rN,

E[YTr] =r1N

N X k=r1k1:=GN(r): 8. Mon trerque GN([xN])! xlogxquandN! 1et que cette fonction limite admet un maximum enx= 1=e0:37. On en déduit que lorsque le nombre d"objetsNtend vers l"infini, la stratégie optimale consiste à laisser défiler une proportion d"environ37% d"objets sans en sélectionner, puis à choisir le premier objet meilleur que tous ceux qui l"ont précédés.

Exercice 7.[Partiel 2016 -2017]

On dispose d"une collection deNobjets distincts et ordonnés que l"on nous présente successive-

ment dans un ordre aléatoire. À chaque étape on doit décider si on choisit l"objet inspecté (dans

ce cas le processus d"inspection s"arrête et on ne regardera pas les objets suivants) ou si on passe

à l"inspection de l"objet suivant. On ne peut pas revenir en arrière. Si lesN1premiers objets n"ont pas été choisis, on prend alors automatiquement leN-ième objet.

L"objectif de cet exercice est de déterminer une stratégie d"arrêt nous permettant de minimiser

le rang absolu (i.e. dans la collection complète) de l"objet choisi. On notera donc bien que le

critère à optimiser diffère de celui vu dans l"exercice similaire traité en cours. On reprend en

revanche les mêmes notations que l"on rappelle dans le paragraphe suivant. On noteSNl"ensemble des permutations deNéléments, c"est -à-dire l"ensemble des bijections def1;:::;Ngdans lui-même. Soitune variable aléatoireuniformeà valeurs dansSN. La

valeurnreprésente le rang absolu dun-ième objet inspecté (on suppose que les objets ont tous

une valeur différente). A chaque étapen, on observe une variable aléatoireXnqui donne le rangrelatifdun-ième objet inspecté par rapport auxn1objets inspectés auparavant. On a donc

8n2 f1;:::;Ng; Xn= cardf1in;ing:

À chaque instantn, on connaîtFn=(X1;:::;Xn), la tribu engendrée par les rangs relatifs des npremiers objets. SoitN=f(x1;:::;xN)2NN: 16xk6k; k= 1;:::;Ngl"ensemble des valeurs possibles pour le vecteur aléatoireX= (X1;:::;XN). Remarquons queXest une fonction mesurable de. Plus précisément, l"application :SN!qui associe à une permutation la suite correspondante des rangs relatifs est bijective (doncX= et = 1X) : étant donnée la suite de rangs relatifsX1;:::;XN, on peut reconstruire. Notre objectif est donc de trouver un temps d"arrêtT(pour la filtration(Fn)n1) borné parN quiminimisela quantitéE[T].

Les questions signalées par une()sont un peu plus calculatoires. On n"hésitera pas à admettre

les résultats pour poursuivre le problème. 1.

Mon trerque

8(x1;:::;xN)2;P(X1=x1;X2=x2;:::;XN=xN) =1N!:

4

2.Mon trerque p ourtout en tiern2 f1;:::;Nget tout entierj2 f1;:::ng,

P(Xn=j) =1n

En déduire que les variables(Xn)1nNsont indépendantes. 3. On définit le pro cessusadapté (Yn)1nNparYn=E[njFn]. Montrer que pour tout temps d"arrêtTborné parN,

E[T] =E[YT]:

4. (*) Mon trerque p ourt outn2 f1;:::Ng;(i1;:::;in1;i)2net k2 fi;:::;N(ni)g;

P(n=kjX1=i1;:::;Xn=i) =P(n=kjXn=i) =

k1 i1 Nk ni N n 5. (*) Vérifiez que p ourtout 1nN, Y n=E[njFn] =E[njXn] =N+ 1n+ 1Xn: Indication : on pourra utiliser (il y aura quelques points bonus pour la preuve aussi!) que pourin:

N(ni)X

k=i k i Nk ni =N+ 1 n+ 1 6. Définir le pro cessusv aleur(Zn)1nNadapté au problème et montrer que, pour tout

1nN,Znest mesurable par rapport à(Xn).

7. Que v autE[ZN]? Donner la relation de récurrence permettant de passer deE[Zn+1]à

E[Zn]pour1nN1.

8.

En déduire qu"il existe une suite à v aleursen tières(si)N1i=1(que l"on caractérisera par

récurrence rétrograde) tel qu"un temps optimal soit donné par : T inff1kN1 :Xkskgsi cet infimum existe

Nsinon.

9. Dans le cas N= 4, caractériserT?en donnant la valeur de(s1;s2;s3). Puis, calculer le rang moyen sélectionné quand on adopte la stratégieT?.

Exercice 8.[Problème du parking]

Vous conduisez une voiture sur une voie infinie à la recherche d"une place de stationnement. Bien sûr, les places ne sont pas toutes libres. Votre objectif est de vous garer le plus proche

possible du théâtre, sachant que vous ne pouvez pas revenir en arrière. Vous voyez une place

libre à distanceddu théâtre. Faut-il s"y garer?

On va modéliser ce problème à l"aide d"un modèle discret. Partant de l"origine, chaque entier

positif sur la droite réelle correspond à une place de stationnement. Soient(Xn)n0des v.a. de Bernoulli i.i.d. de paramètrep2]0;1[. Lan-ième place est occupée si et seulement siXn= 1. 5 On noteNla position du théâtre. On peut donc s"arrêter à la placenssiXn= 0et si on

décide de s"y arrêter, on considère qu"on perd la quantitéNn. Étant au niveau de la place

n, on ne peut pas voir si la placen+ 1est libre et si on décide d"avancer, on ne peut plus revenir en arrière. Si on arrive au niveau de la placeNet qu"elle n"est pas libre, alors on se

garera à la première place libre trouvée en continuant, dans ce cas la perte moyenne attendue

est(1p) + 2p(1p) + 3p2(1p) + 4p3(1p) +=11p(pourquoi?). 1. F ormulerprécisémen tle problème d"arrêt opti mal: donner la filtration (Fn)0nN, les pertes(Yn)0nNet préciser la définition d"optimalité pour un t.a.T. 2. Utiliser l"h ypothèsed "indépendancedes (Xn)n0et la forme spécifique des pertes(Yn)0nN pour simplifier la forme du processus valeur(Zn)0nNet la règle d"arrêt optimal asso- ciée. 3.

Remarquer que si p12

il existe un entier0rN1tel qu"un temps d"arrêt optimal est donné parT?=Tr T r=( inffrkN1 :Xk= 0gsi cet infimum existe

Nsinon.

4. Mon trerque la p ertem oyenneC(r) =E[YTr]est donnée par la formule

E[YTr] =C(r) =Nr+ 1 +2pNr+111p:

5. T rouverl"en tierroptimal en fonction depetNlorsquep= 0:9.

Exercice 9.[Sum-of-the-odds]

SoientN>1etX1;:::;XNdes v.a. indépendantes telles queXnBer(pn)avecpn2(0;1), n= 1;:::;N. On observe les(Xn)1nNune par une (en suivant l"ordre de leurs indices) et on

peut s"arrêter à tout moment. Si on s"arrête à l"instantj, on gagne siXj= 1et siXk= 0pour

j+ 16k6N(c-à-d siXjest la dernière v.a. à valoir1). Soit

L= supf1kN:Xk= 1g

(avec la conventionsup;=1). La probabilité de gagner en s"arrêtant à un temps d"arrêtT(de

la filtration(Fn)1nNengendrée par la suite(Xn)1nN),TN, est donc

V(T) :=P(T=L) =P(XT= 1;XT+1= 0;:::;XN= 0):

On veut maximiser cette probabilité parmi tous les temps d"arrêtT(pour la filtration(Fn)1nN) bornés parN. On noteVN= supT2TNV(T)le gain optimal pour le problème d"arrêt d"horizon N. 1.

La v.a. Lest-elle un temps d"arrêt?

2. Considérons le pr ocessusadapté (Yn)1nNdéfini, pour tout1nN, par Y n=P(L=njFn). Montrer que, pour tout1nN1, Y n=IfXn=1gN Y k=n+1(1pk): 6

3.Mon trerque V(T) =E[YT]pour tout temps d"arrêtTborné parN.

4. Soit (Zn)1nNla fonction valeur du problème d"arrêt optimal associé. Montrer par un calcul explicite queE[ZNjFN1]est une constante. 5. Mon trerpar récurrence que, p ourtout 1nN1,E[Zn+1jFn] =E[Zn+1]. 6. Mon trerque (E[Zn])1nNest une fonction décroissante den. 7. Rapp elerla définition vue en cours de T?et démontrer que c"est bien un temps d"arrêt de la filtration(Fn)1nN. 8. Quelle est la propriété principale du pro cessusarrêté (Zn^T?)1nN? 9.

Mon trerque si pN12

, il existe un entier1rN1tel queT?=Troù T r=( inffrkN1 :Xk= 1gsi non vide

Nsinon:

10.

Mon trerque

G(r) =V(Tr) ="

NY k=r(1pk)# NX k=rp k1pk: et donc que la règle d"arrêt optimale estTroùrest la valeur qui maximiseG(r). 11.

Donner une expressi onde E[Z1].

12. Calculer G(r)G(r1)pourr= 2;:::;Net donner une condition explicite deren fonction des(pk). 13. Calculer retG(r)pourN= 10etpk= 0:2pourk= 1;:::;10.

Exercice 10.[Partiel 2013 - 2014]

Considérons un lac contenantN2Npoissons. On noteTile temps nécessaire pour attraper le poisson numéroiet on suppose que(Ti)Ni=1sont i.i.d. de loi exponentielle de paramètre 1. On verra ci-dessous que les tempsT1;:::;TNsont presque sûrement tous distincts. Admettons-le pour le moment. On note alors T (1)< T(2)<< T(N) leur réarrangement croissant, puis X

1=T(1)etXi=T(i)T(i1);2iN:

La variableXireprésente donc le temps qui s"est écoulé entre le(i1)-ième et lei-ième temps

de pêche. Pour1nN, on poseFn=(X1;:::;Xn), et pourn= 0,F0=f;; g.

On s"intéresse au problème d"arrêt suivant : au bout de combien de poissons péchés est-il optimal

de s"arrêter sachant qu"on gagne 1 à chaque fois qu"on attrape un poisson et qu"on payec >0 fois le temps total requis? Le processus de gain(Yn)0nNcorrespondant à ce problème est donc donné par Y n=ncT(n) (avec la conventionT(0)= 0). 7

1.Mon trerque P(Ti6=Tj) = 1lorsque1i6=jN. En déduire que

P

9(i;j)2 f1;:::;Ng2;i6=j:Ti=Tj= 0

(le réarrangement strictement croissant deT1;:::;TNa donc bien un sens presque sûre- ment). 2. (a ) Mon trerq u"unedensité (par rapp ortà la mesure de Leb esguesur RN) duNuplet (T(1);T(2);:::;T(N))est donnée par (t1;:::;tN)7!N!If0En déduire un temps d"ar rêtoptimal. (d) Ce problème est- ilà structure monoton e?Justifier v otrerép onse.

Exercice 11.[Partiel 2015]

Soit(Fn)n0une filtration et(Yn)n0un processus de gain adapté et dansL1. On considère N2NetTNl"ensemble desFtemps d"arrêt bornés parN. On étudie le problème d"arrêt optimal suivant : supfE(YT); T2TNg: On dit qu"un temps d"arrêt est optimal s"il permet d"atteindre lesup. 1. ( Question de cours) Rappeler la définition de la fonction valeur(Zn)n0. Prouver qu"il s"agit d"une sur-martingale. Rappeler, sans la redémontrer, la valeur du sup du problème considéré grâce au processus(Zn)n0. 2. Soit S2TNun temps d"arrêt optimal et0nN1. Prouver queE(Z(n+1)^S) =quotesdbs_dbs9.pdfusesText_15

[PDF] exercices tension électrique cap

[PDF] exercices texte argumentatif

[PDF] exercices théâtre mimes

[PDF] exercices théorème de rolle accroissements finis

[PDF] exercices théorème des valeurs intermédiaires pdf

[PDF] exercices théorème des valeurs intermédiaires terminale s pdf

[PDF] exercices thérapie cognitivo comportementale pdf

[PDF] exercices traitement de données 4ème

[PDF] exercices traitement de texte cycle 3

[PDF] exercices traitement du signal aléatoire

[PDF] exercices transformée de fourier+correction

[PDF] exercices triangles semblables brevet

[PDF] exercices vecteurs gaussiens

[PDF] exercices vocabulaire policier

[PDF] exercices word 2007 gratuit pdf