[PDF] [PDF] Exercices sur les chaînes de Markov

View - Download [PDF] Exercices sur les chaînes de Markov

Previous PDF

Next PDF

Préparation Agrégation

2012 - 2013

Exercices sur les chaînes de Markov

1.Exemples à espace d"états finis

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 (de manière uniforme) et ensuite on lance

celle-là une infinité de fois.

(1) On observe "Face" au n-ième lancer. Quelle est la probabilité qu"on obtienne "Face" au (n+1)-ième

lancer?

(2) On observe "Pile" au n-ième lancer. Quelle est la probabilité qu"on obtienne "Face" au (n+1)-ième

lancer?

(3) On observe "Pile" au (n-1)-ième lancer et "Face" au n-ième lancer. Quelle est la probabilité qu"on

obtienne "Face" au (n+1)-ième lancer? (4) La suite des résultats des lancers obtenus forme-t-elle une chaîne de Markov? Exercice 2.Soit(Xn)n0une chaîne de Markov surf1;2;3gde matrice de transition P=0 @0 1 0 0 23
13 p1p01 A Dessiner le graphe de cette chaîne de Markov. Combien y a-t-il de composantes irréductibles? CalculerP(X1= 1jX0= 1),P(X2= 1jX0= 1),P(X3= 1jX0= 1),P(X4= 1jX0= 1),

P(X1= 2jX0= 2),P(X2= 2jX0= 2),P(X3= 2jX0= 2).

Quelle est la loi deX1siX0suit une loi uniforme surf1;2;3g?

Exercice 3.On suppose qu"un trait est gouverné par deux gènes, qui peuvent être de deux types,Get

g. On suppose queGest dominant (c"est-à-dire que c"est lui qui s"exprime si la paire estGg) etgrécessif.

L"étatGgest appeléhybride, l"étatGGdominant, l"étatggrécessif.

(1) Un éleveur adopte la stratégie suivante : à chaque fois, il apparie l"individu de la n-ième génération

avec un hybride. Modéliser la situation par une chaîne de Markov, et classer les états.

(2) Un éleveur adopte la stratégie suivante : à chaque fois, il apparie l"individu de la n-ième génération

avec un dominant. Modéliser la situation par une chaîne de Markov, et classer les états. (3) Comparer qualitativement l"évolution des deux chaînes. Exercice 4.Soit(Xn)n0une chaîne de Markov homogène à valeurs dans l"ensembleE=f1;2;3;4;5g et de matrice de transition0 B

BBB@1=2 0 1=2 0 0

1=4 1=2 1=4 0 0

1=2 0 1=2 0 0

0 0 0 1=2 1=2

0 0 0 1=2 1=21

C CCCA

1.Dessiner le graphe de cette chaîne de Markov.

2.Déterminer la ou les composantes irréductibles de cette chaîne.

3.Déterminer le(s) états transitoires.

4.Donner la période de chaque élément deE.

5.Vérifier que siX0suit une loi uniforme surf4;5g,X1également. Voyez-vous d"autres mesures de

probabilité invariantes?

6.Qu"est-ce qui change siP33est changé en12

etP34en? Exercice 5.Soit(Xn)n0une chaîne de Markov surf1;2;3;4;5;6gde matrice de transition P=0 B

BBBBB@1=2 1=2 0 0 0 0

1=4 3=4 0 0 0 0

1=4 1=4 1=4 1=4 0 0

1=4 0 1=4 1=4 0 1=4

0 0 0 0 1=2 1=2

0 0 0 0 1=2 1=21

C

CCCCCA

1.Déterminer la ou les composantes irréductibles de cette chaîne.

2.Quels sont les états transitoires?

3.On suppose queX0= 1. Quelle est la probabilité qu"on ne repasse jamais par 1? Quelle est la

probabilité pour qu"on repasse pour la première fois en 1 à l"instantn? Quelle est l"espérance du temps

de premier retour en1? Exercice 6.Soit(Xn)n0une chaîne de Markov surf1;2;3;4gde matrice de transition P=0 B

B@1 0 0 0

12 012 0 0 12 012

0 0 0 11

C CA

0.Dessiner le graphe correspondant.

1.Classer les états de la chaîne.

2.Quelle est la probabilité que la chaîne issue de 2 soit absorbée en 4?

3.Quel est le temps moyen d"absorption de la chaîne issue de 2?

Exercice 7.Un fumeur décide d"arrêter de fumer. Le premier jour suivant cette bonne résolution (jour

0), il ne fume pas. On suppose que la probabilité qu"il fume le jourj+1s"il n"a pas fumé le jourjest,

et que la probabilité qu"il ne fume pas le jourj+ 1s"il a fumé le jourjest, avecetindépendants

dej, et qu"on peut modéliser le problème à l"aide d"une chaîne de Markov.

a) Commenter la modélisation de ce problème par une chaîne de Markov; donner son graphe et sa matrice

de transition.

Remarque : la même chaîne (avec=) est aussi utilisée pour modéliser la transmission de l"information

par plusieurs intermédiaires, lorsqu"une erreur peut se produire à chaque étape avec probabilité.

b) Calculer la probabilitépnqu"il ne fume pas le journ. Quelle est la limitedepnquandn!+1?

Vérifier queest une probabilité invariante pour la chaîne, c"est-à-dire que siXnsuit la loi,Xn+1

aussi. c) TrouverA >0et0< B <1tels que pour toutxdans l"espace d"étatsjP(Xn=x)(x)j ABn. d) Quelle est la loi du premier jour où il se remet à fumer? e) Quelle est la loi du premier jour (suivant le jour 0) où il ne fume pas?

f) Calculer l"espérance du nombre de joursNnoù il fume entre le jour 1 et le journ. Déterminer la limite

N nn

Exercice 8.Modèle de Wright Fisher

Pour modéliser l"évolution de configurations génétiques dans une population, on est amené à considérer

la chaîne de Markov suivante. SoitPla matrice de transition suivante surE=f0;1;:::Ngdéfinies par

P(i;j) =Cj

NiN j 1iN Nj

1) DéterminerP(0;j)etP(N;j). La chaîne est-elle irréductible? Quels sont les états récurrents?

2) Décrire qualitativement le comportement asymptotique de la chaîne.

On a déjà examiné ce modèle dans le cadre du cours sur les martingales.

Exercice 9.On considère une chaîne de Markov(Xn)n0à valeurs dansE=f1;2;3;4;5;6;g, de matrice

de transition : P=0 B

BBBBB@:1=2 0 0 0 0

1=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

C

CCCCCA

1) Déterminer les termes diagonaux de la matrice de transitionP.

2) Déterminer les classes d"équivalences de la chaîne. En déduire que la chaîne admet une infinité de

probabilités stationnaires.

3) Montrer que les états4et6sont transitoires et que l"ensemble des autres états se décompose en

deux classes récurrentes que l"on précisera. Dans la suite, on noteraT=f4;6g,Cla classe récurrente

contenant1etC0l"autre classe récurrente. Pour toutx;y2E, on définitx=Px(T <+1) =P(T < +1jX0=x)oùT= inffn0;Xn2 Cg.

4) Montrer que

x=1;six2 C

0;six2 C0

et que0< x<1, six2 T.

5) En posantfT <+1g=fT= 0g [ fT= 1g [ f2T <+1get en conditionnant dans le calcul

P x(2T <+1)par la valeur deX1, établir la formule x=X y2Ep x;yysix2 T

6) Calculer4et6.

7) En déduire les valeurs deP4(TC0<1)et deP6(TC0<1), oùTC0= inffn0;Xn2 C0g.

8) Que vaut la fréquence limite du nombre de passages dans l"état1? Calculer l"espérance du temps

de retour de chaque état récurrent.

Exercice 10. EhrenfestSoientdballes (d >1) numérotées de1àdet réparties dans deux urnesAet

B. On tire un nombreiau hasard entre1etdon change la balle numéroid"urne. SoitXnle nombre de

balles dans l"urneAaprèsntirages indépendants. La chaîne(Xn)n0est appelée chaîne d"Ehrenfest.

1.Montrer que(Xn)n0est une chaîne de Markov homogène. Déterminer sa matrice de transition. La

chaîne d"Ehrenfest est-elle irréductible? Récurrente? Apériodique?

2.On rappelle qu"une loi de probabilitéest dite invariante (ou stationnaire) pour une chaîne de Markov

si P=. a.Dire pourquoi on saita priorique la chaîne d"Ehrenfest a une unique probabilité invariante. b.SiX0est distribuée suivant la loi binomialeB(d;12 ), déterminer la distribution deX1, et constater que la loi=B(d;12 )est la probabilité invariante par la chaîne d"Ehrenfest.

3.Dans cette question on supposed= 3. SoitT0le nombre de tirages nécessaires pour viderA. Déterminer

pour tout étatxet pourn= 1;2ou3,Px(T0=n).

4.On revient àdquelconque. Montrer qu"il existe deux constantes réellesaetbtelles que pour tout

x2 S:X y2SyP(x;y) =ax+b:

En déduire E(XnjX0)etlimE(XnjX0).

5.a.On rappelle que Ex(Tx) =1(x).

On supposedpair etX0=d2

. Quelle est l"espérance du nombre de tirages nécessaires pour revenir

dans cet état? Même question si initialement toutes les balles sont dansA. Comparer les deux résultats.

Application pourd= 10. (EstimerC510par la formule de Stirling, qui donne un ordre de grandeur

correct.) Et pourd= 1023. (La chaîne d"Ehrenfest est un modèle simplifié de la théorie cinétique des

gaz, visant à illustrer l"interprétation probabiliste - proposée par Boltzmann - du second principe de

la thermodynamique.)

6.On modifie légèrement le modèle : lorsque la balle a été extraite d"une urne suivant la procédure

décrite, on tire au sort (avec des probabilités égales) l"urne dans laquelle on la replace. Déterminer la

matrice de transition et la distribution stationnaire.

2.Exercices plus théoriques

Exercice 11.SoientA,Bdeux ensembles finis ou dénombrables (disons deux parties deN), et f:AB!Aune fonction. SoientX0une variable aléatoire (v.a.) à valeurs dansA, et(Yn)une

suite de v.a. à valeurs dansB. On suppose que lesYnsont indépendantes et de même loi, et queX0est

indépendante desYn. À partir deX0et de(Yn), on définit une suite(Xn)de v.a. à valeurs dansApar la relation de récurrence : X n+1=f(Xn;Yn): Montrer que(Xn)est une chaîne de Markov homogène.

Exercice 12. Application de la propriété de MarkovSoitXnune chaîne de Markov d"espace d"états

E, de matrice de transitionP. Montrer les propriétés suivantes : (1)Pn(x;y) =Pn m=1Px(Ty=m)Pnm(y;y)pour toutn1. (2) Siaest absorbant,Pa(Xn=a) =Px(Tan) (3)Px(Ty=n+ 1) =P x6=yP(x;z)Pz(Ty=n) (4)Px(Ty<1) =P(x;y) +P z6=yP(x;z)Pz(Ty<1).

Exercice 13.Soit(Xn)une chaîne de Markov d"espace d"étatsS, de matrice de transitionP. Pour deux

étatsxetyon posexy=P(Ty<+1jX0=x).

1) Montrer quexy>0si et seulement si il existen1tel queP(n)(x;y)>0.

2) Soitn0le plus petit entier1tel queP(n0)(x;y)>0, et soientx1;:::;xn01des états tels que

P(x;x1)P(x1;x2):::P(xn01;y)>0:

Montrer que les étatsx;x1;:::;xn01;ysont distincts.

3) Lorsque l"espace des états est fini avecdéléments, montrer quen0d1et queP(Tyd1jX0=

x)>0siP(n0)(x;y)>0.

Exercice 14.(Potentiel d"une chaîne de Markov) Soit(Xn)une chaîne de Markov homogène, à états

dans un ensembleS, et de matrice de transitionP. Pourx;y2 S, on note : (1)Ny=P n11fXn=yg(nombre de passages à l"étaty, hors l"état initial),y= minfn1; Xn=yg (l"instant du premier passage enyaprès le départ); (2)U(x;y) =Ex(Ny)(nombre moyen de passages enysi on part dex).U(x;y)est bien défini dansN[ f+1g: on l"appelle lepotentielinduit parxeny. (Noter quexest récurrentssi

U(x;x) = +1.)

(3)xy=Px(Ny1) =Px(y<+1)(probabilité qu"il existe un chemin de longueur1joignant xày); a.Montrer queU=P n1Pn. En déduire que pour toute fonctionf:S !R+[ f+1g, la fonction g=f+Uf(définie parg(x) =f(x) +P y2SU(x;y)f(y)) vérifie l"équationg=f+P g. Montrer que c"est la plus petite solution de cette équation, i.e. que sih:S !R+[ f+1gest telle queh=f+P h, on ahg. b.Soientx;ydes états tels quexy>0. Montrer que siyest un état transitoire (="transient"), on a yy<1etU(x;y) =xy1yy<+1(on pourra commencer par vérifierPx(Nyk+1) =xyPy(Ny(k))) et que siyest récurrent, on ayy= 1etU(x;y) = +1. c.SoitV=I+U(oùIest la matrice identité). Montrer que pour tousx;y2 S,U(x;y) =xyV(y;y). (On convient dans cette formule que0 1= 0.) Quel est le maximum de la fonctionx7!V(x;y)? d.On suppose que la chaîne a une probabilité invariante (=stationnaire), i.e. P=. Soity2 S.

Montrer que si(y)>0,yest récurrent.

Exercice 15.SoitXnune chaîne irréductible récurrente de matrice de transitionPsurE. Soite2E.

Soitune mesure invariante pourPtelle que(e) = 1. On pose pour(x;y)2E,Q(x;y) =P(y;x)(y)(x). (1) Montrer queQest une matrice stochastique; calculerQnet montrer queQest récurrente irréductible. Comparer les périodes deQetP. (2) Vérifier queQn(x;y) =P(XNn=yjXN=x)pour tout0nN:Qcorrespond à un renversement du temps. (3) Montrer par récurrence que pour toutx6=e, (x)Qx(Te=n) =Pe(Xn=x;Te> n) oùQdésigne la loi de la chaîne associée àQ. Exercice 16.Mesure réversibleSoitXnune chaîne de Markov de matrice de transitionP. Une me-

sure positive finie non nulle surEest dite réversible si pour tout(x;y)dansE,(x)P(x;y) =(y)P(y;x).

(1) Montrer qu"une mesure réversibleest invariante. (2) Montrer que la loi binomialeBin(1=2;d)est réversible pour le modèle d"Ehrenfest. (3) On considère la chaîne de Markov définie surNparP(k;k+1) =p,P(k;k1) = 1psik >0, etP(0;1) = 1. Montrer que la mesure définie par(k) = (p1p)k1et(0) = 1pest réversible. Pour quelles valeurs depest-elle finie? Pour quelles valeurs depla chaîne est-elle positive?

3.Chaînes à espace d"états dénombrable

Exercice 17. Marche aléatoire simple unidimensionnelle

SoitX1; X2;:::une suite de variables aléatoires indépendantes identiquement distribuées telles que

P(X1= 1) =pP(X1=1) = 1p=q

pour un certainp2[0;1]. On appelle marche aléatoire simple partant dea2Z, la suite de variables aléatoires(Sn)n0définie par S

0=a;8n1; Sn=a+nX

i=1X i:

1) Montrer que l"on définit ainsi une chaîne de Markov homogène.

2) Montrer que cette chaîne est irréductible.

3) Montrer que la chaîne est récurrente sip= 1=2.

4) Montrer que la chaîne est transiente sip6= 1=2.

Exercice 18. Marche aléatoire simple multidimensionnelle

SoitX1; X2;:::une suite de variables aléatoires indépendantes identiquement distribuées à valeurs

dans l"ensemblef~ei;i= 1:::;dget de loi uniforme, où~eiest le i-ème vecteur de la base canonique de

Z

d. On appelle marche aléatoire simple partant dea2Z, la suite de variables aléatoires(Sn)n0définie

par S

0=a;8n1; Sn=a+nX

i=1X i:

1) Montrer que l"on définit ainsi une chaîne de Markov homogène irréductible.

2) Montrer que la chaîne est récurrente sid= 2. On peut montrer que la chaîne est transiente sid3.

Exercice 19. Nombre de particules entrant et sortant dans un volume(Xn)désigne le nombre

de particules présentes à l"instantndans un volumeV. On suppose que, pendant l"intervalle de temps

[n;n+ 1[, chacune desXnparticules présentes a une probabilitép2]0;1[de quitterVet que, pendant

ce même temps, un nombre aléatoire de nouvelles particules, suivant une loi de Poisson de paramètrea,

entre dansV. On suppose que les différents phénomènes aléatoires ainsi considérés sont indépendants les

uns des autres. a.Montrer que(Xn)est une chaîne de Markov homogène et calculer sa matrice de transitionP(x;y). b.Calculer directementEx(eitX1)(=E(eitX1jX0=x)). c.En déduire la f.c. deX1lorsqueX0suit une loi de Poisson de paramètre.

d.Montrer que, pour une valeur convenable de, la loi de PoissonP()est invariante par la chaîne(Xn)

(i.e.X1;X2;:::ont la même loiP()queX0). e.Montrer que la chaîne(Xn)est irréductible, récurrente positive.

f.(Ergodicité) Soitx2 S. La fréquence des passages enxentre l"instant 1 et l"instantna-t-elle une

limite quandn!+1? Exercice 20. Marche aléatoire surf0;1;:::;Ngavec barrières réfléchissantes. SoitX= (Xn)n0une chaîne de Markov homogène d"espace d"étatsE=f0;1;:::;Nget de matrice de transition donnée par, pour1xN1,

P(x;y) =8

:psiy=x+ 1 qsiy=x1

1si(x;y)2 f(0;1);(N;N1)g

oùp; q2]0;1[etp+q= 1. Pour toutxdansEon noteTxle temps d"entrée enx, c"est-à -dire T x= inffn1; Xn=xg.

1) Déterminer la ou les classes de cette chaîne de Markov.

2) Justifier l"existence d"une unique probabilité invariante,, et la déterminer. En déduire la valeur du

temps moyenE0(T0). Exercice 21. Marche aléatoire surNavec barrière quelconque. SoitX= (Xn)n0une chaîne de Markov homogène d"espace d"étatsE=Net de matrice de transition donnée par, pourx1,

P(x;y) =8

>:psiy=x+ 1 qsiy=x1 si(x;y) = (0;0)

1si(x;y) = (0;1)

oùp; q2]0;1[,p+q= 1et2]0;1[. L"étatx= 0est appelé barrière réfléchissante si= 0, barrière

élastique si2[0;1[, et barrière absorbante si= 1. Pour toutxdansEon noteTxle temps d"entrée enx, c"est-à -direTx= inffn1; Xn=xg.

1) Déterminer la ou les classes de cette chaîne de Markov.

2) Montrer, l"existence d"une probabilité invariante,, en la calculant. On discutera l"existence et

l"unicité suivant les valeurs depet deq. Lorsque2[0;1[etp < qdéterminer pourx2N,Ex(Tx).

3) Sipq, étudier la nature des états, et sip > qcalculer pourx2N,Px(T0= +1).

4) On suppose maintenant que= 1. CalculerP0(T0<+1)et en déduire la nature de l"étatx= 0.

Calculer pourx2N,Px(T0= +1). En déduire la nature de ces états. Etudier la limite de la suite (Pn(x;y))n0.

Exercice 22.File d"attenteOn considère une file d"attente devant une porte qui s"ouvre à tous les

instantsn2N, ne laissant entrer à chaque fois que la première personne de la file. SoitYnle nombre de

clients arrivant pendant l"intervalle de temps]n;n+1]. On suppose que lesYnsont des variables aléatoires

indépendantes et de même loi=PY0. NotonsXnle nombre de clients dans la file d"attente à l"instant

n(au moment où la porte s"ouvre, donc y compris celui qui franchit la porte). On suppose queX0est indépendant desYn.

a.Établir une relation de récurrence entreXn,Xn+1etYn. (On notera bien que la porte ne s"ouvre pas

entre les instantsnetn+ 1) En déduire que(Xn)est une chaîne de Markov homogène. Déterminer les

éléments de sa matrice de transition en fonction des(fng). b.Trouver une relation entreXn,X0,Pn1 k=0Yk, etPn1 k=01N(Xk). (On pourra la déduire de la relation de récurrence dua, ou l"établir indépendamment.) Interpréter. c.En déduire que siE(Y0)>1, alors presque sûrementXn!+1, et que dans ce cas la chaîne est transitoire (transiente). d.Montrer que siE(Y0)<1, l"état 0 est récurrent.

Exercice 23.Modèle de naissance et de mort

On modélise l"évolution d"une population par une chaîneXn(éventuellement non homogène) surNde

matrice de transitionP(x;x1) =qx,P(x;x) =rxetP(x;x+ 1) =pxavecpx+qx+rx= 1,px>0, q

0= 0etqx>0six6= 0.

On posei= inffn0;Xn=ig(i6=Ti), et siaxb,u(x) =Px(1< b).quotesdbs_dbs29.pdfusesText_35

[PDF] chaine énergétique barrage hydraulique

[PDF] chaine énergétique d'une éolienne

[PDF] exercice corrigé centrale hydraulique

[PDF] chaine énergétique centrale thermique

[PDF] chaine énergétique pile

[PDF] chaine énergétique exercices

[PDF] chaine énergétique éolienne

[PDF] chaine énergétique panneau solaire

[PDF] chaine energetique definition

[PDF] chaine énergétique exemple

[PDF] cours de logistique de distribution pdf

[PDF] introduction logistique

[PDF] cours management de la chaine logistique pdf

[PDF] logistique et supply chain management

[PDF] supply chain management livre pdf