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
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
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
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
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
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,
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
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éfinition 1 2 (Chaîne de Markov homogène) La chaîne de Markov (X t)
3 Processus de Poisson Rappels sur les lois exponentielle et de Poisson, processus de comptage, d´efinition 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: Programmation dynamique, chaînes de Markov, files d’attente Cours de Tronc Commun Scientifique FICM 2A Notes de cours et exercices corrigés
[PDF] processus de naissance et de mort exercices corrigés
[PDF] processus de naissance et de mort pdf
[PDF] processus de pilotage exemple
[PDF] processus de poisson et loi exponentielle
[PDF] processus de poisson exemple
[PDF] processus de poisson exercices corrigés
[PDF] processus de poisson pdf
[PDF] processus de prise de décision management
[PDF] processus de prise de décision pdf
[PDF] processus de réalisation d'un objet technique 6ème
[PDF] processus de réalisation d'un projet
[PDF] Processus de réalisation d’un objet technique
[PDF] processus de réalisation exemple
[PDF] processus de socialisation définition
[PDF] processus de socialisation durkheim
ProcessusdeMarkovetapplications
É.Pardoux
11septembre2006
2
Tabledesmatières
1MonteCarlo11
2ChaînesdeMarkov33
3Algorithmesstochastiques85
3
4TABLEDESMATIÈRES
4ChaînesdeMarkovetgénome111
TABLEDESMATIÈRES5
5Contrôleetltrage149
6LeprocessusdePoisson165
7Processusmarkoviensdesaut181
6TABLEDESMATIÈRES
8Filesd'attenteetréseaux239
9Mathématiquesnancières271
TABLEDESMATIÈRES7
Bibliographie329
Index333
8TABLEDESMATIÈRES
Préface
dénombrable. applicationesttraitéedanslechapitre7. 9
10TABLEDESMATIÈRES
dessatellites. d'améliorerlemanuscriptoriginal.
Marseille,Septembre2006.
Chapitre1
SimulationsetméthodedeMonte
Carlo
Introduction
Z [0;1]f(x)dx pardesformulesdutypePn i=1wif(xi),avecleswiquisontdesnombres convergence,del'ordredeK=p 11
12CHAPITRE1.MONTECARLO
dimension.
1.1Descriptiondelaméthode
IE(X)1
N(X1++XN):
I=Z [0;1]df(u1;:::;ud)du1:::dud:
1.2.THÉORÈMESDECONVERGENCE13
IE(X)=IE(f(U1;:::;Ud))=Z
[0;1]df(u1;:::;ud)du1:::dud; uneméthodedeMonteCarlo. type: I=Z
IRng(x)f(x)dx=Z
IRng(x1;:::;xn)f(x1;:::;xn)dx1:::dxn;
Quandetpourquoicetalgorithmeconvergetil?
1.2Théorèmesdeconvergence
14CHAPITRE1.MONTECARLO
avecIP(N)=0etquesi!=2N):
IE(X)=limn!+11
n(X1++Xn): pasvraimentsurprenant). l'erreur: n=IE(X)1 n(X1++Xn): gaussiennecentrée. queIE(X2)<+1.Onnote2lavariancedeX:
2=IE(X2)IE(X)2=IE(XIE(X))2;
alors: p n
Celasigniequepourtouta lim n!+1IP( pna"npnb)=Z b a ex2 2dxp2:
1.2.THÉORÈMESDECONVERGENCE15
tiragesdéjàréalisés. n,soitendonnantunintervalle def. thodedeMonteCarlo. laloideX,X1;:::;Xnona: p n=X1++Xn np+pnZ: pndel'ordre 16CHAPITRE1.MONTECARLO
E=IEeg=e
2 2: X,X1;:::;Xnona:
E n=X1++Xn nE+pnZ: L'erreurrelativemoyenneestdel'ordrede
Epn=q e21 n.Sil'onsexeun conduitàformulerune: àapprocherl'espérance.
C=IEeZK
;(1.1) 1.2.THÉORÈMESDECONVERGENCE17
IEeZK =e2=2F log(K) KF log(K) ;(1.2) avec F(x)=1
p2Z x 1 eu2=2du: simulation,soit C'N1heZ1K
+++eZNK +i put,c'estàdire: P=IEKeZ
;(1.3) donc P'N1hKeZ1
+++KeZN +i Ilestassezclairque
VarhKeZ
+i CP=e2=2K;
Carlo(cf.l'exercice1.5.10cidessous).
18CHAPITRE1.MONTECARLO
1.3Simulationdevariablesaléatoires
simulerdesv.a.deloiuniforme. sique:
Posons,pour0t1,
F
1(t)=inffx;F(x)tg:
IP(F1(U)x)=IP(UF(x))=F(x):
caspourlaloiexponentielle.
1.3.SIMULATIONDEVARIABLESALÉATOIRES19
t2IR,
IP(X>t)=exp(t):
F
1(x)=log(1x)
SiU'U[0;1],ilenestdemêmede1U,et
logU 'E(): [0;1]indépendantes: p
2log(U)cos(2V)etp2log(U)sin(2V)
IEf(X;Y)=1
2Z IRZ IRexp x2+y22 f(x;y)dxdy 1 2Z 2 0Z 1 0 rexp r22 f(rcos;rsin)drd Z 1 0Z 1 0 fp
2logucos(2v);p2logusin(2v)
dudv =IEfp
2logUcos(2V);p2logUsin(2V)
poserX=+Y,oùY'N(0;1). telleque:
IP(X=n)=en
n!;sin0
20CHAPITRE1.MONTECARLO
N t=X N N 1=X n1n1fU1U2Un+1e
8x2IRdf(x)kg(x); kg(x). X onposeX=X1. (Xp).OnposealorsX=Xp. Lav.a.Xainsisimuléeapourdensitéf.
X 1vaut p 1=P(U1(X1))=Z
P(U1(x))PX1(dx)=Z
a(x)g(x)dx Z1 kf(x)dx=1k; parl'indépendancedeU1etX1. 1.3.SIMULATIONDEVARIABLESALÉATOIRES21
kg(x)estprochede Cecisetraduitpar
IP(X2A)=Z
A f(x)(dx)Z A kg(x)(dx)=kIP(Y2A): IP(8p2INX6=Xp)=limN!1IP(\
pNfX6=Xpg) =limN!1IP(\ pNfUp>(Xp)g) =limN!1IP(U1>(X1))N =limN!1(1p1)N; 22CHAPITRE1.MONTECARLO
IP[X2A]=X
n2NIP[X=Xn;X2A] X n2NIP[\ pn1fUp>(Xp)g\fUn(Xn)g\fXn2Ag] X n2N(1p1)n1IP[fU1(X1)g\fX12Ag] 1 p1IP[fU1(X1)g\fX12Ag] =IP[X12AjU1(X1)]: IP[X2A]=1
p1Z A IP(U1(x))PX1(dx)=kZ
A (x)g(x)dx=Z A f(x)dx: 1.4Méthodesderéductiondevariance
estdel'ordrede=p IE(g(X))=Z
IRg(x)f(x)dx:
queIE(g(X))peutaussis'écrire: IE(g(X))=Z
IRg(x)f(x)
~f(x)~f(x)dx: CelasigniequeIE(g(X))=IEg(Y)f(Y)
~f(Y) ,oùYsuitlaloi~f(x)dxsousIP. Y 1;:::;YndeY,etenapprochantIE(g(X))par:
1 n g(Y1)f(Y1)~f(Y1)++g(Yn)f(Yn)~f(Yn) var(Z)=IE(Z2)IE(Z)2=Z IRg 2(x)f2(x)
~f(x)dxIE(g(X))2: delaméthode. chercheàcalculer:Z1 0 cos(x=2)dx: 24CHAPITRE1.MONTECARLO
IE(f(X))souslaforme:
IE(f(X))=IE(f(X)h(X))+IE(h(X));
Z 1 0 exdx=Z 1 0 (ex1x)dx+3 2: ment. callvérient: CP=IE(egK)=e2=2K:
réduite. I=Z 1 0 f(x)dx: 2Z 1 0 (f(x)+ par: I 2n=1 n 12(f(U1)+f(1U1))++12(f(Un)+f(1Un))
1 2n(f(U1)+f(1U1)++f(Un)+f(1Un)):
s'améliorepourvuque IEf(U)f(1U) d'uncoecientprochede2. I=IE(g(X))=Z
g(x)f(x)dx: I=mX i=1I i=mX i=1IE(1fX2Digg(X)) n m X i=1 2i ni: EtsionminimisecetteerreuràmX
i=1n i=nxé,onobtientni=ni Pm i=1i. Leminimumvautalors1
n mX i=1 i! 2 .Onpeutmontrerqu'ilestinférieurà cettetechniqueonpourraconsulter[9]. 26CHAPITRE1.MONTECARLO
IE(g(X;Y))=Z
g(x;y)f(x;y)dxdy; oùf(x;y)dxdyestlaloiducouple(X;Y). Sil'onposeh(x)=1
m(x)Z g(x;y)f(x;y)dy,avecm(x)=Rf(x;y)dy,il estfaciledevoirque: IE(g(X;Y))=IE(h(X)):
EneetlaloideXestm(x)dx,etdonc:
IE(h(X))=Z
m(x)h(x)dx=Z dxZ g(x;y)f(x;y)dy=IE(g(X;Y)): conditionnelle,que: var(h(X))var(g(X;Y)): pitredecemanuel. 1.5Exercices
IP(X=k)=p(1p)k1;k1:
ouface. loiN(0;1). 1.5.EXERCICES27
(=2)exp(jxj). ponentielledeparamètre1. laprobabilité1=2.TrouverlaloideSZ. processus. suituneloideCauchydedensitét lationdelaloiconditionnellecidessus). mulationdelaloidececouple. soninverse. 28CHAPITRE1.MONTECARLO
Z=F1(F(m)+(1F(m))U):
cetteméthodeàlaméthodedurejet. conditionnellementàaExercice1.5.7.Réductiondevariance
I=IE1f>0gexp;
1.5.EXERCICES29
thétiques. enchacunedesesvariables. ona: IE(f(X1;:::;Xn)g(X1;:::;Xn)jXn)=(Xn);
leurarguments: loiuniformesur[0;1].Montrerque: Cov(h(U1;:::;Un)h(1U1;:::;1Un))0;
riancedanscecas. 1;V0=0etpouri=0;:::;nonposei=Vi+1Vi.
pouri=0;:::;n 30CHAPITRE1.MONTECARLO
Z n=nX i=0 ih(Vi) convergepresquesûrementversI=R1 0h(u)du.
4.Montrerque:
IE(Zn)=Z
1 0 (1vn)f(v)dv constanteKavec: jZnIjKnX i=0 2 i CP=IEeZK;
lavariance. parvariableantithétique. estimationdelavariance. 1.5.EXERCICES31
PparMontecarlo.
antithétique. 32CHAPITRE1.MONTECARLO
Chapitre2
ChaînesdeMarkov
Introduction
surunespacedeprobabilité( ;F;IP),àvaleursdansunensembleEqui applicationf:INEF!E,t.q.pourn1, X n=f(n;Xn1;Yn): indépendantes. cruciales. 33
34CHAPITRE2.CHAÎNESDEMARKOV
vériéequedanslecasoùIP(B)>0. X n;i.e8x0;:::;xn;y2E, leprocessusàvaleursdansEdénipar X n+1=f(n;Xn;Yn+1);n2IN: AlorsfXn;n2INgestunechaînedeMarkov.
Preuve
IP(Xn+1=yjX0=x0;:::;Xn=xn)
IP(X0=x0;:::;Xn=xn;Xn+1=y)
IP(X0=x0;:::;Xn=xn)
X IP(X0=x0;:::;Xn=xn)
X fz;f(n;xn;z)=ygIP(Yn+1=z) IP(Xn=xn;Xn+1=y)
IP(Xn=xn)
unerelationderécurrencedutype: x n+1=f(n;xn); x n+1=f(n;xn;xn1;:::;x1;x0): P xy=IP(Xn+1=yjXn=x): deprobabilitésurE,c'estàdire: P xy0;8y2E;X y2EP xy=1: lamatricedetransitiondelachaîne. surunespacedeprobabilité(quotesdbs_dbs11.pdfusesText_17