[PDF] [PDF] TD 12 – Chaînes de Markov (distributions invariantes) (corrigé)

View - Download [PDF] TD 12 – Chaînes de Markov (distributions invariantes) (corrigé)

Previous PDF

Next PDF

L3- Probabilités (Année2018/2019) Tien-Nam Le & Alice Pellet--MaryTD12- Chaînes de Markov (distributions invariantes) (corrigé)Exercice1.Proposition utiles

Le but de cet exercice est de démontrer les propriétés observées sur les exemples de chaînes de Markov.

1.On regroupe les états d"une chaîne de markov en classes d"équivalence pour la relation d"acces-

sibilité : deux étatsietjsont dans la même classe si et seulement siiest accessible depuisjetj

est accessible depuisi. Une classeCd"états est ditecloseouferméesi pour touti2 Cet pour tout

j/2 C,pi,j=0 (où(pi,j)i,jest la matrice de transition). Autrement dit, il n"y a aucune arête sortant

de cette classe. Démontrez que :

Une classe non close est transitoir e.

Une classe close finieest récurrente.

En particulier, pour les chaînes de Markov à espace d"états fini, les classes récurrentes sont les

???C?????? P j2CN j=¥jX0=i) =1 .

2.Démontrez que sipest une loi de probabilité stationnaire et siiest un état transitoire, alors

p(i) =0. j,i? ?? ??i j,ij 1??åjpj=1?? ?? ?? ?????? p i=0?

Exercice2.Classification des états

On dispose de trois chaînes de Markov définies par les matrices de transition suivantes : A=0 @2/3 0 1/3

1/4 1/2 1/4

1/2 0 1/21

A B=0 B

B@0 2/3 0 1/3

0 0 1/2 1/2

1/4 0 0 3/4

0 0 0 11

C CAC=0 @1/2 1/4 1/4

0 1/2 1/2

1/4 0 3/41

A

Pour chacune d"entre elles :

Donner sa r eprésentationgraphique.

Partitionner les états en composantes irr éductibles. Pour chaque état, dir es"il est transitoir eou r écurrent. Pour chaque état, dir es"il est périodique ou apériodique.

Donner la distribution stationnair e.

Pour chaque état, donner le temps de r etourmo yen.+???? ? ? ????? ? ??? ?????? ??????f1,3g???f2g ????? ? ??? ?????? ??????f1,2,3g???f4g? 1 ? ????? hi,i=¥???i2 f1,2,3g???h4,4=1? ?? ? h11=7/2?h22=7??h33=7/4?

Exercice3.Marche aléatoire dans un graphe

On considère une marche aléatoire sur le graphe suivant (c"est à dire qu"à chaque étape, on choisi le

sommet suivant uniformément au hasard parmi les voisin du sommet courant).0 12 34

1.On suppose que la distribution initiale estp0= (1,0,0,0,0)(i.e.X0=0 avec probabilité 1). Le

vecteur de distributionpnconverge-t-il lorsquentend vers l"infini? Si oui, déterminer sa limite.

2.Même question si la distribution initiale estp0= (0,14

,14 ,14 ,14

Exercice4.Absorption

On considère une chaîne de Markov donnée par la matrice suivante : P=0 B

BBBBBBBBBBBBB@0 0 0 0 0 1/2 0 1/2 0 0

0 0 0 0 1 0 0 0 0 0

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

0 0 0 0 0 0 1 0 0 0

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

1/2 0 0 0 0 0 0 1/2 0 0

0 0 0 1/2 0 0 0 0 0 1/2

1/2 0 0 0 0 1/2 0 0 0 0

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

0 0 0 0 0 0 1 0 0 01

C

CCCCCCCCCCCCCA

1.Représenter le graphe de cette chaîne.

2.Déterminer les classes de communication, leur nature et leur périodicité.

2

On noteAetBles deux classes récurrentes obtenues. Pour chaque état transitoirei, on noteai(resp.

b

i) laprobabilité d"absorptiondeiparA(resp.B), c"est-à-dire la probabilité, en partant dei, d"aller dans

A(resp.B) en une ou plusieurs étapes, et donc d"y rester carA(resp.B) est récurrente.

3.Quel est le système d"équation vérifié par lesai? Le résoudre. Idem pour les probabilités d"ab-

sorption parB.

+???? ??? ?????? ?????? ????a2=a5=a9???a3,a5?????? ??????? ??? ??????a5=1/2+ (1/4)a3,a3= (1/2)a3+ (1/4)a5? ????

????? ?? ????a5=4/7???a3=2/7?

4.Quelles sont les distributions stationnaires?

Exercice5.Triangles monochromatiques

Unek-coloration d"un graphe est un assignement pour chaque sommet d"une couleur parmikcouleurs

au total. Elle estpropresi deux sommets adjacents ne reçoivent jamais la même couleur. Un graphe est

k-colorable s"il existe unek-coloration propre. SoitGun graphe3-colorable.

1.Prouver qu"il existe une2-coloration (non propre) telle qu"aucun triangle n"est monochroma-

tique (un triangle est monochromatique si les trois sommets qui le composent reçoivent la meme couleur).

On considère maintenant l"algorithme suivant dont le but est de trouver une telle2-coloration : on

commence avec une2-coloration arbitraire. Tant qu"il y a un triangle monochromatique, on choisit uniformément un sommet parmi les trois sommets qui le composent, et on change sa couleur. On veut étudier l"espérance du nombre de recolorations avant de s"arrêter. CommeGest3-colorable, il existe une coloration propre Rouge, Bleu, Vert (mais que l"on ne connaît pas). On noteR(resp.B,V) l"ensemble des sommets colorés rouge (resp. bleu, vert) dans cette3- coloration. Considérons maintenant une2-coloration arbitrairecdeG(en rouge et bleu, disons). Soit m(c)le nombre de sommets deRqui ne sont pas colorés rouge dansc, plus le nombre de sommets de

Bqui ne sont pas colorés bleu dansc.

2.Que dire sim(c) =noum(c) =0?

3.En s"inspirant de l"exemple du cours sur2-SAT, modéliser l"évolution dem(c)par une chaîne de

Markov surf0,...,ng. Quels sont le ou les sommets à atteindre pour terminer? Que pouvez-vous dire de l"étatjpar rapport à l"étatnjpourj2 f0,...,ng?

m(c)?m(c)1? ?? ?????? ?? ?????? ??? ???? ????? ? ????j6=0,n? ???? ????? ??? ?? ????? ?j1? ???? ????? ??? ?? ????? ???j??

4.Soithjl"espérance du nombre de recolorations à effectuer pour terminer, en partant d"une2-

colorationcpour laquellem(c) =j. Exprimerhjen fonction dehj1ethj+1pourj=1...(n1).

Determinerh0ethn.+?? ?h0=0??hn=0? ?? ????? ?? ? ?

h j=13 (1+hj1+1+hj+1+hj+1) h j=32 +12 (hj1+hj+1) 3

5.Montrer quehj=hj+1+f(j)pour une certaine fonctionfà déterminer, avecf(0) =h1.

+?? ?h0=h1+f(0) =h1h1=0? ??? h j=32 +12 (hj1+hj+1) =32 +12 (hj+f(j1) +hj+1) 12 hj=32 +12 f(j1) +12 hj+1 ????hj=hj+1+3+f(j1) =hj+1+f(j)????f(j) =3+f(j1)????f(j) =3jh1?

6.Prouver quehn/2=O(n2)et conclure.(On pourra utiliser la relation h1=hn1que l"on obtient par

symétrie, pour finir de résoudre la récurrence). +?? ?hn1=hn+f(n1) =0+f(n1)? ?????h1=hn1??f(n1) =3(n1)h1? ?? ??????? ?h1=3(n1)h1???? h

1=3(n1)/2? ????h(j) =hj+1+3j3(n1)/2?

h j=hn+n1å k=j(3j32 (n1)) =0+3n1å k=jj3(n1)(nj)2 =3(n1+j)(nj)2

3(n1)(nj)2

=3(nj)2 (n1+j(n1)) =3j(nj)2 h n/2=3(n/2)22 =O(n2) 4quotesdbs_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