Chaines de Markov execrices corrigée

Les chaines de Markov

RAPPELLE DU COUS + EXERCICES CORRIGES.

1

Rappelle du cours :

Dfinition dun processus stocastique : un processus stocastique est une chaine de variables alatoires.

La chaine de Markov (ou encore chaine Markovienne) est un cas particulier de processus stocastique.

Chaine de Markov temps discret : cest une chaine fini et dnombrable (c'est--dire que lensemble des tats not en gnrale E est fini et dnombrable).

On dit quune chaine de variable alatoire est une chaine de Markov si elle vrifie deux conditions :

1. P[ Xn+1= xn+1 , Xn = xn , Xn-1= xn-1 ,., X1= x1 ,X0= x0 ] = P[ Xn+1= xn+1 / Xn = xn ] quelque soit x0, x1, xn, xn+1 E (ensemble des tats). Ce qui veut dire que ltat future de la chaine (ltat de la chaine linstant n+1) ne dpend que dun prsent proche (ltat de la chaine linstant n) en dautre terme il ya absence de mmoire. Cette premire condition est propre aux chaines Markovienne.

2. Si P = P = P(Xn+1= j / Xn= i) Ce qui veut dire que la probabilit de passer ltat j linstant n+1 en 1 seul transition sachant qu linstant n on t ltat i est indpendant de n. En dautre terme quelque soit la valeur de n cette probabilit de passage en une seule tape de ltat i ltat j est la mme. On dit que les probabilits de transitions sont stationnaires et que la chaine est homogne.

Matrice des probabilits de transition en une seule tape not P (ou not encore (Pi,j)i,j E ) : Pour chaque chaine de Markov est associ une matrice des probabilits de transition not P (et vis-ver-a). Cette matrice est Carre et est stocastique (on dit quelle est stocastique car la somme des lments dune ligne de la matrice P =1).

Matrice des probabilits de transition en n tape not P(n) (ou not encore (Pi,j (n)) i,j E ) :

Il existe pour une chaine de Markov une matrice de probabilit de transition en n tapes not P(n), les lments dune telle matrice nous donne la probabilit de passage dun tat i linstant m ltat j linstant m+n en n transitions (ou n tapes). La aussi nous avons une matrice stocastique. Attention a ne pas confondre la matrice des probabilits de transition en n tape (P(n)) et la matrice des probabilits de transition en une seul tape puissance n ( (P)n ).

La probabilit de passer ltat j linstant n partant de ltat i linstant 0 en n tapes est not comme suite :

P = P[Xn=j / X0=i] = P[Xn+m=j / Xm=i]= la probabilit de transition en n tapes.

Lquation de Chapman et Kolmogorov : lide retenir pour cette quations est que le passage dun tat i un tat j en n tapes ou en n transitions tq n >1 ne se fait que par le passage obligatoire par un ou plusieurs tats intermdiaires. Lquation de Chapman et Kolmogorov est la suivante :

P = P * P tq L+m = n.

n,n+1 i,j i,j

i,j (n)

(n) i,j i,k k,j

(m) (L)

K E

2

Exemple :

P = la probabilit de passer de ltat i ltat j en deux transition.

P = P * P = P * P tq k est le seul tat transitoire entre les tats i et j.

La probabilit dtat not (n) : cest la probabilit que le systme ce trouve un tat donn un instant n donn ( diffrencier avec la probabilit de passage dun tat un autre).

(n) = cest la probabilit que le systme se trouve ltat j linstant n = P (Xn = j).

i j : on dit que ltat i accde ltat j si on arrive trouver un chemin direct ou indirect (indirect si on passe par des tats intermdiaires) qui nous permet de passer de ltat i ltat j en dautre terme :

n tq P > 0.

ij : on dit que ltat i communique avec ltat j si on arrive trouver un chemin direct ou indirect de ltat i vers ltat j et de ltat j vers ltat i. En dautre terme :

n tq P > 0 (on peut accder ltat j en partant de ltat i en n tapes) et m tq P > 0 (on peut accder ltat i en partant de ltat j en m transitions).

La relation communique est une relation dquivalence car si i j alors forcement j i. Les tats qui communiquent forment une seule classe. La classification des tats :

- On dit quun tat est rcurrent si et seulement sil ne contient que des arcs entrants (cet tat ne nous permet pas de passer dautres tats).

- Si Pii = 1 (la probabilit certaine) on dira que ltat i est un tat absorbant, car une fois arriv cet tat on ne peut plus sortir de celui-ci (une lampe une fois quelle passe ltat de panne elle ne peut plus revenir ltat de marche donc ltat de panne est un tat absorbant).

- On dit quun tat est transitoire si et seulement sil ne contient que des arcs sortants (cet tat nous permet de faire des transitions vers dautre tats).

- Deux tats qui communiquent sont de mme nature. Classification des classes : une classe est un ensemble dtats qui communiquent entre eux

- Une classe est dite rcurrente si une fois rentrer dans cette classe on ne peut plus sortir de celle-ci (on peut dire aussi quelle est absorbante car elle absorbe le systme).

- Une classe est dite transitoire si elle nous fait passer vers une autre classe (une fois sortie dune classe transitoire on ne peut plus revenir celle-ci).

La probabilit du premier passage en n tapes (n transitions): La probabilit de passer pour la premire fois de ltat i ltat j en n transitions (ou en n tapes) scrit :

f = P [Xn = j, Xn-1 j, Xn-2 j,, X1 j / X0 = i] et on lit quelle est la probabilit de passage ltat j pour la premire fois et aprs n transition sachant que initialement on t ltat i. Pour trouver cette probabilit il faut chercher ou se trouvait le systme linstant 1, linstant 2,.,linstant n-1 car ces instants la chaine ntait pas ltat j.

Probabilit du premier passage ( diffrencier avec la probabilit du premier passage aprs n tapes qui donne le nombre exacte dtapes parcourir pour arriver ltat final) :

(2) i,j

i,j (2) (1)

i,k (1) k,j i,k k,j

j

(n) i,j

(m) j,i

(n)

i,j

(n) i,j

3

f = f le n > =1 car pour passer de ltat i ltat j pour la premire fois il faut au moins faire une seule transition. Lorsque i=j on parle de la probabilit de retour un tat.

Si fii =1 on dira que ltat i est un tat absorbant car la probabilit de retour cette tat est certaine.

Si fii < 1 on dira que ltat i est un tat transitoire (ou un tat de transition). Soit i,j (certain la note mi,j) la variable alatoire qui symbolise le temps moyen du premier

passage : si fi,i = 1 et i,i < , on dira que ltat i est rcurent positif. Si fi,i = 1 et i,i =, on dira que ltat i est rcurent nulle. Dfinition de la chaine irrductible : une chaine est irrductible si tous les tats communiquent

entre eux et forme une seule classe dite une classe dquivalence (bien videment dans une chaine irrductible tous les tats sont de mme nature).

Dfinition de la priodicit dun tat i not d(i) : la priodicit dun tat i not d(i) est le plus grand commun des diviseurs (PGCD) de lensemble B tq lensemble B est dfinie comme :

B={n / P > 0}. - Si deux tats communiquent alors ils ont la mme priodicit (thorme de solidarit). - Si d(i) =1 alors ltat i est apriodique.

La distribution stationnaire : - Avant de prouver que cette distribution stationnaire existe ou pas il faut construire la

matrice des probabilits de transition, le graphe des tats, tudier la nature de chaque tat (priodicit et nature : transitoire, rcurrent ), tudier la nature de la chaine (est ce quelle est irrductible, dans le cas contraire quelles sont les diffrentes classes quelle renferme : transitoires, rcurrentes ou absorbantes ,).

- Ensuite il faut prouver que cette distribution stationnaire existe, pour cela il suffit de montrer que lensemble des tats E est fini.

- en montrant que E est fini nous avons prouv quil existe au moins une distribution stationnaire mais cette distribution stationnaire est-elle unique ou il existe une infinit de distribution stationnaire (cela dpend du nombre des classes rcurrentes dans la chaine).

- Sil existe une seule classe rcurrente alors il existe une seule et unique distribution stationnaire dfini par le systme dquations :

P = i = 1

- Si nous avons le nombre de classes rcurrentes suprieurs 1 alors il existe une infinit de distributions stationnaires calcules par la formule : (n+1) = (n) * P

- Sil existe une seul classe dquivalence on est certain quil existe une seule et unique distribution stationnaire.

- Lexistence de plusieurs classes rcurrentes veut dire quil ya une infinit de distributions stationnaires.

La distribution limite : une condition est ncessaire pour lexistence dune distribution limite. Cette condition ce traduit par le faite que la distribution limite ne doit en aucun cas tre

(n) i,j i,j

n>=1

(n) i,i

i

tq = (1,2,., n) , 0 donn et n le nombre de lignes de la matrice carr P (matrice des probabilits de transition).

4

dpendante de la distribution initiale not 0 (si elle dpend de la distribution initiale alors la lim (n) dite distribution limite nexiste pas).

Si la chaine est ergodique alors : - Il existe une seule et unique distribution stationnaire. - Il existe une seule et unique distribution limite. - La distribution stationnaire concide avec la distribution limite (donc il est plus facile de

calculer la distribution limite qui est en gnrale difficile calculer : il suffit de calcul la distribution stationnaire).

Une chaine est dite ergodique ssi : - Elle est irrductible (elle contient une seule classe dquivalence). - Rcurrente positif (lensemble des tats not E est fini). - Apriodique (quelque soit i un tat de lensemble E alors d(i) =1).

La probabilit du premier retour ltat i en n transition not Rii :

Rii = P [X11, X2 i, X3 i,, Xn-2 i, Xn-1 i, Xn= i/ X0=i]. La probabilit de se trouver tt ou tard dans un tat i note Fii ( fii qui reprsente la

probabilit du premier retour un tat) : Fii = fii

Le nombre de retour un tat i = indicatrice de 1 {Xn = i / X0 = i}. Le temps de sjour dans un tat i not P{Si = n / X0 = i} :

P{Si = n / X0 = i} =P [X1= 1, X2 = i, X3 = i,, Xn-2 = i, Xn-1 = i, Xn i/ X0=i] P{Si = n / X0 = i} =P [Xn i/ Xn-1=i]* P [Xn-1= i/ Xn-2=i]*...* P [X1= i/ X0=i] =P [Xn i/ Xn-1=i]* (Pii)

n = (1-la probabilit de pass de ltat i ltat i) *(Pii)n

P{Si = n / X0 = i}= (1-Pii)(Pii)n (cest la probabilit de rester dans 1 tat i de linstant initiale 0

jusqu' linstant n-1 puis quitter cet tat i linstant n). Le temps moyen de sjour (attention faire la diffrence entre le temps moyen de sjour et le

temps de sjour : deux notion diffrentes lune de lautre). Le temps moyen de sjour dans un tat i not E {Si / X0 = i} = 1/ (1- Pii).

Le temps moyen de passage dun tat i un tat j = la dure moyenne de passage dun tat i un tat j = la frquence moyenne de passage de ltat i ltat j = qui dit temps moyen de

passer de ltat i ltat j dit ij, qui dit la dure moyenne de passer de ltat i ltat j dit ij, qui dit la frquence moyenne de passer de ltat i ltat j dit aussi ij :

ij = 1 + Pik kj.

Cette formule reste valable sauf dans un seul cas ou ltat i appartient une classe transitoire et ltat j appartient une classe rcurrente. On parle dans ce cas de temps moyen dabsorption (gnralement dans lnonc des exercices on nindique pas si cest un temps moyen de passage dun tat i un tat j ou si cest un temps moyen dabsorption, on se contente de dire calculer le temps moyen de passer de ltat i ltat j et cest vous de faire attention la nature de tats). Dans ce cas la formule utiliser est la suivante :

ij = 1 + Pik (Aik/ AiC) kj

n

(n)

(n)

(n)

n >= 1

kj et kE

kT

5

telle que T est la classe transitoire la quelle ltat i appartient, C est la classe rcurrente la quelle ltat j appartient et AiC cest la probabilit que le systme soit absorber par la classe rcurrente C partant dun tat i appartenant une classe transitoire.

Attention si on vous demande de calculer la probabilit de passer dun tat i un tat j telle que ltat i appartient une classe transitoire et ltat j appartient une classe rcurrente il faut calculer la probabilit dabsorption(cest la probabilit que la chaine passe dun tat appartenant une classe transitoire une classe rcurrente autrement dit cest la probabilit que la chaine soit absorber par une classe rcurrente travers ltat j appartenant cette classe partant dun tat i qui est transitoire (qui appartient une classe transitoire) on note cette probabilit AiC : on remarque bien quon na pas crit Aij car ce nest pas ltat j qui absorbe la chaine mais plus tt la classe la quelle il appartient (la classe C) malgr le fait que cest travers le passage ltat j que la chaine sera absorber). La probabilit de passer de ltat i ltat j (tq j C et i T) = AiC telle que :

AiC = Pij + Pik AkC telle que i T (classe transitoire).

On remarque que si T= {i, e, a} alors AiC dpendra de AeC et AeC dpendra de AaC

Notons : ce rappelle du cours est loin dtre complet. Le plus important est dacqurir quelques notions de bases pour la suite. Certaines notions (ou astuces) ont t volontairement enlev de ce rsum car il nya que des applications directes qui peuvent illustrer ou claircir ces notions (si vous navez pas compris ce quil ya dans ce rsum, pas grave car vous allez tout comprendre dans les exercices qui suivent : ne vous dcouragez pas ).

Les exercices sont classifis en trois niveaux :

Niveau zro : application simple (le but de ce premier niveau est dapprendre tudier la nature dune chaine Markovienne et de tirer le maximum dinformations possible pour tre la hauteur de rpondre nimporte quelle question par la suite).

Niveau un (cest le niveau le plus important) : exercices dexamens (le but est dapprendre pleins dastuces pour tre en mesure de rpondre nimporte quelle question).

Niveau deux : exemples rels (le but et dapprendre lire entre les lignes dun texte exprimant un cas concrets et de pouvoir a partir dun texte tirer la matrice de probabilit de transition, le graphe des tats.)

Remarque : ce document est ralis par un tudiant (jai essay dtre le plus sur possible sur des ides qui figurent dans ce document.ceci dit lerreur est humaine, donc sil ya des ambigits il faut consulter lavis dun enseignant dans le module : madame SAGOU ou madame TALEB serons la hauteur de rpondre nimporte quelle question et denlever nimporte quelle ambigit).

K T j C

Niveau zro

l iJ .l :j

l ,1 it ,1 :Il ii ri 'i '{i ii l: l;**iL o ,

r li it ,, lj :r ); n .

t * t A \ 'l t t t ^ \

I 1\ );,1aL

,-7 :

i li :: ;t !Ji ,i :

l t /t ;

d"* 'ele?^,4/e : l

; ** i, i r, lr j! r

- -#sp

;;.n.'w

e'**" c*lc0,r,r* ry\&a qr6.,.r &l ,!n*los JLsth rh /;^" dn- ,--:-.li' cu*Vn :*.^^rre clask ha, u.G.. ,,.-lU r= 1 4qgl . eW A)

, -o.l/r- !^+ J,b (nua6re,a^, *,r'-{o' .d,C"tr" evr no ;rarf & aW._o .

,

r-r^n_e ,9

t,4:

k;

i i-- -l--t4ri i ' i ' i" f

'

, - ' * * ; ' ' - . 'L ' *. I

\14. r,W,.*-[oi : ' t I:

' " -

:

" - ' " * ' ; " ' * - - ' i - - " * @ - - * e - - . : - - * . ,

ryf,*"* l-i"* **. i ; i r

: " " - " '

,/:4q*,& A,n aa+o atlL3,Wq

'_j[+hlicrn,*crnr "l ' \; -tf ."" i- * ;

.

h* *fttnhm,^djw'-Agnd*\MtdW-lg' {ora*_t

)/ -

I * l t r ' 1 1 Irlr #* E5-rn.u & 1; q dkt #* d*& cfir"^^" E"t nru,l"aa,fu*u crtni*''iil"*A Pl iu (t,t * G) *'*

O0jni^, 'lro-ma a* ryq;i , . i

i jj

i - i . '-i I T*,1I, , lt1 ,ltt) ,

l /i

F-L1-L+-il*tlr ffiq*ii ;

t . . . -lffn f*tu,' 'ttnr.Wffi,^

/,ti-'5 t'nuonn*-{. Srl .ty" #^?

,Ta 1'- r,'*M-;d.l*?rrb;a,lin

,,Ut ,!

!

I

Wi,fu'-h"ffihW -uvt*t* *t, ,vwb drt.k,*[V)*.qb_rSli i| "'

Qa*ilff i Crnnr (l- . ^ r . \L;' i L'ud+ "(,p pd*""l,+:* "f in46i* U,

ftbrlrb:

*

ir

ir

F-*"., '

*V

aF

*tr

r,f,uL" hl*l= qti ;, 4 "*t*$ b' . .

i

t:ii

$J{c,:en**i

d

* * .

.{f

-a,#

"xs

&.-*ti*,rNF

"*

,',8

"*s

**#

-"#

***

*-**

*' #

" \_ 1 J

I**X

.r{*oil*#

t{

lrl

s,"s'q*;.

@

""tr

d

,r*tr

-*m

4* \n\pJE^Lc4- Aa- ff.t.JdelH ttr Y\P-b.rn, J*'I ! , . 1

" r " i I lI ;

- l I ' - l , i

pc'U*loUlds

:*ir#

:rit#

:"fln"f

**&{S

-**fr'#

***dr$'

""**.ffit#

*"*ffi#

**.ffi.{S

*s\**

&.#

"",ffidS

-."*'*

,*-Jffi*

*",,ffi"ll

*.,tffi'{1

*.*

*,s1*

*;ffi',ry

--.Jffi

**ffi

**ffi

,",.ffi

W arWfe* Q;re' ,foFtufeu atr

. :n

qffit& tX 4o'^* Qae-n t

'AE Swnrn e C ea' or-c

*r , *g:--r *t Cst b r) x tl , .". - 4 Uq

:r "*q,* q C,; rr'\: 'L / tbtn': L

/hn$cr,.h 6k c"&ory*-

- '. r -Jr\ c4*) .f;f'v-a& ffit ?oq i &Y'?. ah Pu*' la

"*i-vX

I

;

,S" ^! *.un atn b hr*f. Fnne- Gfr "uQ- n* tgf;e^t Q-rre Ce,{}c{ t\{1)kx ( ar^Cy\ tt^c* n',/{A+ el,-r{rD$b l'ffif*d

i!x,tc* .-'dol- Y L c{Tnrnl.tnLq^gtf,Qle-c* (J^r.c-r'r-n l*nf) -' i{*: La^ #". ,?^ q Pnf';t *,,-?.?''$r'

"4* l,\q-- lntrrrru-^-nerQ*ue- p. arJe *L'tt *; *"0'o '( gUfi v\{ [xvn (tutnLcs,ttt.. /:c:a run P4! clrJe;c* Pi(hl*y

" t.i'.i 4+ v.rt"I& olrfi P" l.'utrl- / q^ v\-s-{-.,rryyr*io?*"{" rur ,r/ec l'&* "4 t ry i{* '(hhb*)top"t. Aw lh,c!:sq*i k].1 4.1leak lrf^e- ^u.n*dn'W',,,, j.r,.f \.. , "8 | g),*b + a.-k" {t iJo*,-

'-!rnen-t .,tl=1a**' td;[..

-{La**s* (-r- ^ 4q"{ vter^{rer J-'d

*''Y

W -i{ f r 1 '4i^* .. t,(. a

rf,#

-f

*dt{'tJ

# l l

rN*l#t,d#

"dif

riffi.

".dt -w

* * f f i ! ' - '

.t|}#

' _ : i - ! * r ' i ! i - !

e.ffi!,

-**y#

*; -'

*"fl. *riF

*rll|ft;*n

!f,f

**f$r-"*t

f

.",ifr*?t: -

*ffftf

#4.{4n-;e#

*-*

*{tfl"t

,e*1&

"lilr,

-**r.it

q*$*

*d: a'l$

s.aLt.

*

-"r.,t

"4#

rqi6**br

.-c*.d

&i*at{

"-d*

**.*

P'i.q t

rLr) r)f ,)Y x y

p

\ . :, l ;

i 1

I I , r { r i

. i

j

i

'a

Pv)kY =*

ilrr.t*d*

*ct#

*#$,

,rr*kfltr

*!it*fs

"*d' { r

.#'{,t*t

rs .

/ ^ r \(4* 1\*-/

t l ,

t"fi- 4

\ r qt 4

d {4

s

**# .rdit

i*i*dr-;,{*,xFr*6{

-*i*:

,.nt. # r

.{n*l*t

'-*tr{sj.ri{{*fe_#

ih*d&.$tr;-fi

.rf

-scfs

t-*t*

-#"r#1'

-

iqF

-

,rGl

*"{t{i:

"tr. :1p-

,4'".rur!6aiit.t

.tr!r-

F{cdi""tr'il||tl

r*#.JN

*

*,!e.'-"1K

w

,"dr{it

"itry;... -...,,. ..

FX'

; ' t ; ; i i i i: : i l l i i i :

n ' J r r I ^ ; - i i i[\rrr. Uor, \,{.! C66(r1{y\rqre$X- S-f\^c- AS'l'| , O.g naa 4^nal/\J atl

, t ) l t - , - n . . l r - , 1 A ^ . ^ / , ^ ' . , : ICga/Kn diII dl*le d eqi+tva-Un Q. = {,\ {, J ? , ilI

* \ \ = d',,i 4-n',c e4 e,air\- "S -^cucrenlr- S+Suet \ I r , J - \ -

;^iii*ei!4.,

s*

"i*ld

;il-tr,"dr

${ & c"0'-r\0, 0^- ir:rs-tdUHe- ""j-ln",LJzu *$xj

* -e&r^lI-

Ii r :l r1 1 :i****-*.*.i-i : i 1 . . "

1:-1",Jn

,"lf

;*d*r,..*-#

*a*.

ht

;,#*d#'

"*raf'

*-.ru.*flr

-.ln

{6..*'l,&*-#

*df**

sw{&.-.df

{trf

;-*l

.rf

t rt|*.*",ff,

i;,a$r

-cffi

x l \= fr^' &cvrr- ii-AKikn*''h-,-t rt.;-X6rnrru0r"sq-. (

J *Tf i= -lr p\ zo,*L.

L"L.Q' "

I' J

ffih.*ndt,

*#'

ry4f*r.

"ffi:if. ..

s*tst

r$*s,-*fl

#

sds#l

*{{;r

? Itts o o\ls|l*trko0lI o ,t4{ alt o ILo'o ^t(Wl

|*r**ffi".+o' a

o \,{* \

fri s/

*4,"f:

"***"d

Th

'.**

lrt, .

,-**

As di"K\",-d* rr{nxo^,*$ir,{" M'*,#x*"t: JT:7f-P *:1r ih,# _=

tzE; = 4*

, { vr, nlg"&t(

*fbf(" f*r- s..* -{g c

I r * llc l : qi

I

r2o,t fw*lnt tr,ff(li

v"

-x,*

*,

f

t ,TI

*c'

" ' .

$

dfr4t. r #

{{s

*qrflh

"n{*t"{&.-f**{#

*#ilib,

* *. #

*{d*.

-s#

- t .

*n*.f

4lfl

r " w: . - . , ,

*tidTt!' * f f

r#

ffiffiti4sffiffiffiw

*fuot o ffi*,* "n,$-&*--o4l*q{,vtc",O &+a;,f,"

F.dfih".

*tr{ldid&-

*ffi#

*rur#

*ffi

tr#*.;*{}

4p.d&-^*ffi

: *f ,* 4", I 0i o i*,:!lgt i i -jg*J 4*r.'*y'SF, j, ,t/,1 'o', W,{, s--; ,-l*}--i *--j -;--*1 ri - - it , i l t ) I i i i I I i : i ' , io Ty ?, TY :!;,

:o ; o l l la i Q, Y" i . . , * . - *** ;* -**- -J- -* l " i . - r - - - - { " -* -J- - - : . - . i: / , i Y i i i i i i i i i i i ,4 , o, o ,

"i -p--l--*-r**-1"*'r-*-r**:-*---i--}**i--.i i

, . ; : i "*-"1 I i I i i r i i i I l4 e: 0 ei

i - " - - ' t r ii l ! t l ii i ' i t i

i i l i i i , :i i i i i i r ii r l , i i i ;r i l ; t : i i i :

Lh-T'j;\/\,:I.\4:;-i--u-;--j-|].-;*i' : ; l i ; i l 1 : ; l

',"d

i l ; \ : t i i i i i : r l

i e ) I i, l),,,*''*[*+ ;i.ii*1I:

I

j{I

-"-r * i -T*- *- l, i i i i ' i

\ / f a/*\',yry /i j r I --i*is.*i....*@ ^d.*..-*--< -...-'-*. ..-?'","..."a.t t i ii i l ii i r i 't i i li i l l

| | ' t ' r t l t .f^,av u',aWfu- d& i ' , 1 :

: .l ' { = ' 'Al"bh^i^le, drrrX

U :

-^'

at

l';il;l;;;r;,ffirc,Jl'W ,i . t F | |

; !|.#^*iS 6t-r"c L!" &h att M,w{-r^r dhs fu#. d,jbtkq* dlffir*oni &&',a*uff*-cq& d*,W fi"t*(ftv'h (, ;

lr*'i",i*^I nI ",*o' "'2 ",[t+L i:^%; il',{,

"0t* f * q"n,n"a"X-.e'ft3 y ybd:ia.u*"!q*th4" Y,44- ,--i4 rna'd a^rru &.m. t*+.rLml,- i---- ,-

.-lr. r -, - i^-r-- -,

r-,l i 11 t' :: !,ff#:'*ifuffi '

**t

. s '

f

' '

! F .

ffie

:

ffi.1r\ ,f"-^i

{ro,,igJ

ff. 1^eo r e*ft'& pabntea*o*e- h'4d-:M*l(^ l' oht- 4

par'AU)#ql \.,'utF T1.

**sq /- ' F

s

; ; ,*e*

.n

{

,*##

.#.tTP

***{r

*dflr*qr

-,*W,rl*,'

*w**dBr_dr**d&&*#

*

kd*hdqtr

*-a*$S

*-*{f

" "ffif,#

-"c*#

*d**#'

*is..S$e**.****g}{rfr

*rlnr{*c5?

*.f;$tl#

*fl*i:f

*ur&is.

"-$f,tif

x**&{tr"-#n*r#

i

r l

i r

fu- rnq,fu.Qq-

f=4,

rxQ,I

I

' i4&f*ba)6ltG. A* hor^t-,b.r; --

I

. 1 - t t - , ^ A I^, l4/z o o o 4/zlV.lA OD O ot t" . / , / / gIr= Iq ? P o ol c1 /,t/a

,lo1oP ollooqo P I: L 1 o o o 'o)

2u %^*f.J-. bh* = /LtJ- it nah {" h tb* = 4Z4- 'd/ner^t, C" i4 !'il= 4,f .J% -&'^rr"t 4" "|t"'/n* =t-t !* &!^r+ l" -/4 tni,*=4-

T^PEHfHEr--{faL--auHfUur---ur---ur---uf---ufr--fur--e

l-L.-e

ljr--r

l_r---

l-r.-.rr

l-f-.-

l_f-.-

l--r--r

l-

d" 0* c0a...s 8)^ (A*Fcan;,c-Qn,wra)-,."

.

dl -ut;

/' "xigto',co

-(ta.lc, -"-,t.e ek h ilL -LyLeGA+ -rt"ofe

it t l f l(fnW.tLg rwltrve

Peri-{tfs 4a' /1,.^^r /\tL^tr;

^ '" ' QM'-{Ae.^: tI

d,ufi.,11 prenre-m.^t n^a.yno-"t n"abt, , ,^-lurt ,s E

-l' d"s,*U" *- ebr. 6,

={4, J,3, q, (1"I t L f

! | ' f J

Q-

ffifnt, ,1,-#*^?*, IE fr?r,1#y 9't&alapreyau,ul

,S-(t h 4 -h,4

q ftu*i,tG ? e^Fn.e./

{t,

01t0-

4/a 0 0 o4b o %oo {t o%o 0 /s0

-4 0 o 0

6 q^PnL 4" ^ 0^r,..o ^&/no,Mma,ts4'or* h"ffifu;nw3,{uM7;

I

l_-)__J

l--)__.J

l_]-al_a'-J

l-f-.J

l_f--a

l_f---a

Ll+-J

l_l - l

l_]J=

Ll . +J

l_f-J

Ll--a

l_f-J

l-'f-.J

L.-J

LL--a

Ll-.4

l_r-J

l_^f-J

l_l _ r

l-'

W / a . - - o l \././ ) \' _t 5 \/

'rllo\

\

s 3++q

4/z-

... fu,pg^rr ,a'c,;6"*..f'

tqot &egt"qp.e/z'

.1+ rtrceito'qQ,,/' '4""* q-. 0n" ,

V' tr"''rn.' &" pd"Jdq-r &e. e+cj,6lF* h- t' t

trftor rr't"gnh l-cntAd * fltr'^" fs** lacaoi,{ K

e {o).

n 4

=- {G) 9 AW + o J,uc Ia .Q^, a, ge..,eJ\., e .lel, K,.,. d{u,,.- .A &-;* tot .c,.ffenh- p"+,c/ {rl9j tq dk) #+ ".,. .!a cA,a\* 6). z* p

l_)--al_)-al_)-tl_|-,-ra

l_|--l

l_.--t-.-

l_a-,-,--

l_l---if

l_l---f

l_ff-.-

l_r-4

l_I--r

l_L-'--

l-.Hr-.I---

l_HU.E--rLr--fuf--f

L.G-rufrftI -

Q*U- 4*p/"r, e'\,te,t te :'

,,ohuL; /,^ lt^l=I

,, p.rn t '. ns{^ oîo^ y'-a- a"ÛlU" /?oks""t-r< q^^'

-Zxnrt e* ettU.,,,q-r,e cl*c cn .gr.t Ji.e +., 2'id.rhf"r. ^ra&6i"e- Ae*t$x" g-Q-i s',;w lS' / \ t -:n-I V OJ{g,u'.l- 6\'o' ni

-#)--T:h"lr"W"lT,,pa.W,Y

ra!^Q*n L^ P*)=v'l+ bo

nJ b

1?

t

i

î /'n \n I ' r ,H - /f :- )

r'r-lfflrrf IFJ

}L;-TCaJLO

Xo-

F*t*6QrLt

T- - { .

l-- 1uE-IuErur--Iuf-.rtur--Iuf-.IuI-.rlur--rtur--rtuL.rtuf--IuI--Iur--rtu---tlur-.rtur--IuI-.Iur--Iuf--II-

Ltrofe" {eq tb-F,,

orl

I

Pe{ Ai oztt-u e*"'nILFofu %r-CoCrPrf. d &^* e-rêlgSe,*rrne 4u orQzt*+o4 d" c0na^^rh? s6"1- SaLr'16 Cl) .

-

) 4. -e* Pu!) 7.lt S gaf -*, ab.t int+-,bn.e car 1.,{-^ Cmlueht grre_ Jea

crrcs S-ot{o*r.tss ( a^Cwt Ct*c nt{q1I en*rot';. -Q'phfd-rn. !'olbl- Y o- c4b,rtutîq-uet6)sec- cl.,,LtL^ irnt) -

* +#z .o,,. O n ,?nn Q Pn?,i. *.P*9) >-r -.,",4 y\{- cv'1pr.!ruq-rre- ry * 4'} a-, o2po,/lntAyl GmttvnLgttc- pc.i ^^ pq c!^)er- Qionf y( .& eaf voCoe" it-a+i ft"} .(.'obt- c/tnz-

Ltnw^nuq-^ê vtt- ctttec'I'eb+ 4 , ;+ ^trr_ -tinf

t | | ')/W,t7enr\o-\f,8 .Tuu-.--L---quan,-ILf-^rlLI--IuI--IuI-.rtuI-IuL--ILI--rlur.-IuI-Iurr-rrur-.rlur-.rlucrluG-rluG..ITurr-.rrI J

* Is\'{iî r tt I \ | t l | .&^ fn-srA5 rr^.L ddFLl6r^fo,r

x Qa iArltiL,"ba. ffihc"A^xz n'a,al po'a "uniq^^z co-'t u0 ax-G\r{"" J'.^r.,.,- w(- clnU. -ta.rr-entr (n-ra qrrr,^ d&{'

c[P.l4ts ots-c't-"rz C4 fu)-x l^,a-U;trfi 2tJron,.!-* n'r4'olpc ,,r,niryrr e- OJc

4,"4,J dq ",

. cpk, d;k b"f.o,.' jft-,tt*i.'- erfdqj?a*p"r !n- !^.*1" '.^ [q): Et-l- D /ru''.*p"iaf+"u,r"^{ dotll p"t -8o Jt*U^m ir.i+46 ')ir+r_ryrr- po.rrftur'eltllF r. &a Cola'h pe" 6-e,u/0,--nG)- I

* J Al = JQ) : r h^ {' bo* o tntie"rt -r,..e los.^c-&.-, AG) - J (rl = a ca^ Wr Wt 4" -!.'ubl-e {'eb

s U /o^* o-^' nrusrn {.^*-' JL- k",*la;^* G ) = Z- (p- Pt 'nt f co4i-.?^ ./,^r\e- lot c!" .x {o .oiao- E")^ oat- pa;eJiry.e Lo-^ i ee

, d0)4t_ '* -(o c0,."* 6^),., ,n'aaf pa ;ftJ^&.L4 cc,t deo

:,7httt f * t-t>.m,;,g,v.ent ps.erA- u-"Y-.

* urr rypfu Aien 4-r- n '!'dera;dd /".(,

, -tr.rl-.

";) tY=zr8= , cn" /r" =

* f + f*

,*kff,

-*rq{-^=W:.; 1 for. tro*+ (e)" = o/ 6d7.

- tt . '

npu^ cLuv< -b ,r**,,aiu gob-b'&,E'A+ "r")t.,^ en 4e*x6p< fQ ,'.h^\ pe,^v/^nâ-t--uLê* fut.r. u,h'prut-.-L'Le ( clttat*e^r-

C----,uAu--fur-rlur--Iur--rruf---ftur--IuI-.Iur--Iur-,-Iur--rtuf,--flur-.Iur--rlur-rtur--rtuI--ruI--ruf--fur--rI J

TnKrhl; I lo pGb.b Lr Y I

^ I'd*

t .

. \

, / * )'/o

/' 04 b

PYI = 0-- \r*t*,b,-lH 4. Wc(r- ['drokl : ;;t

r ' \/\ 'QQ)r'"r4* ff,l+ (ry) 1

pteba b'r'!fu't

-en 1n{,Le,

'(bFi

^ '{c rn.nla".Jea pre,toU Alt*c d" harrl.,k ^ 4^n obg^de l'-' = 'L-4 r,nolr|gA?,N-.yLl"" {-tr-t,

4.n I )c*{" 2n1LIJttz) e o-r-=fxJ-= /oc(e;'^ePceSe,a&- r.e.z

?rt

r'-- c

?" =-TCy

4r P+krn J -

w/n = @t

C,ort {,'g,bF q- c^pPor.\e^cQnw JCs*to-^k cr

r,t ttaj' q o4qontr-e^t r^\ .%+t **r^t-^,G ca"q

, cr* qQ-,(Ja,,.rtlLIid

r-.-'faur-rfLI_IuI--uI--truI-ITuI-rruL-IuI--rruL-Iur--rrur-.rrur-,-

ff.--Iur - l

ur--Ilur--rturr--rluf--Iur--rlur - lI-

. *\c^rte,,. Jo^ caq-^re co{ -[ o**tn-c. ;.*

dr= o, { Co.,.- &r*1nlC&o** E- ftr.kw ,S h**e J*ik^e^fr -* -{^X.,. art +'t"'o--1L= or 6

E = 14, {,3?qL

WWu"*:ffi*

(-"

ib.arer q 'yr-ofrtce- Jg .Aoi*a (dr,n"+coh r p*,.todla

d*i.6o*) drn,..t ,p^ Q^ rnq.l,.."cq $c preb-laCIr-* Pr,Q,l

@

i

ir l/fu;Vcntr-s,i

ott

t

:I . L . t I _ - r r l _ n .

dr\A \jqL^-$n -l(t-ojLhnD^q-f

orl 94 p(i,4o 'or4 q3

4E;{ c.^5 n=4( b-^=Jt"- V?\ V"'7t ekz q 4 l . 4 _' - 9 ^

' ) o 2 t l '\ S L

ol L PL't",ldr',; 1-

o-l'c.! /y6rfo&f = I

#)oq) )oor"t

*

)k

x 4 z:^ P er a, c I 3 '. Q>^ fr^r.r't^ u:t{ tl I ..2

OJ-rQn.t

^

.0*

r-\,l tAtlen Qrcr\fe

"

brl M z\oXt c-omgur1.-r-enJi So"- ^.eLu o-d cw ^^r\e-4pC%/Kz dilr dCI,i{c J e!*.v-ZB.nco ={r,+,3t.

x \e\ =t',i 4.r, c & .gd,r.' o.* -,tc,rc.e,.r^ F+Vue '*

-0g ce,.-* a*f icre&ct{o Co b. !ea,. e!t3 cocnrnurJ+ J Gl = A1+; - J[.) (.. L8.sr..." a. ,a4d-,,rb:) = -u

A*.. -L'ahob t, *tae"L ^^n!- k"*.4" )x & ;ce.oi* ea\- oprie{:,R$a- ro-,Lrc E JQt--* -Qp- pRornn ea{ erg.a;T" C.u nflo t.l ,

'r Cedqctit& .- .+irJe

* l=l= fid {*iffiPsbl'J. o-rr rrusrnr. rrn{h,"6,f r&tn-bsrno^ry. c&, J-rrf,-Wt "

't6-bsr't^,1ft ,"r.iq.-ore- b^ Ll, l k- 4 kt"(t -Ia !'eo,ruo

Cq; orf iar"pgv.t. - agt"J" at .^..^iq{, t Jn-taau^

'=) 0 {ubn^t-h* a,Lo,ksnM1 p ,".o,*u) .+ Qo- {h',b^b; 2G/rarnn;rt aa+ {p'ar p

T--4u---lua-tur--rluI---uL-rl

fI--rfuG-rluL--fluI-rrur--rluf--.fluI-rl

fI---luI-.Ilur--rluL.ItuI-..rruI--lruf--qur--II -

o tls]o 0l44[$ c I4 'tl

kI4(0

z) )ls e'- 14 ,&,1 tt fe"l{a

,/i

'll4Sn'tt/,tS

4+& co.-3 "=3 of m=LCg fnl'>. * f'r-

**,3 to^ 3 n= g {t 3 m.)- Q, l >. t[-r>o3e lg cor 3 n:3 e -=4b, W >. (rT,> "p^!ru-,qt-v,ia"

Tu',r-4ua]--uI-rl

fI-rlLI---ruL--fluf--fuI-.rlur-rur--rrur-^rlur--rlur--I

fr--rlur--rlur--rtur--rluf--Iur-.rluf:-a:

\ ri\? \ , YJ I + 3

.-/ II

I

i

iI

i

, h,t, kU'e-boh G>nrutntqrle^t

L---u4fI-tIu--a

fru---

f--fu--au--auI--rur-rrur-.rt

Lr--

f--!-

fr--lur-rlLr-Itur--rlur.-rruI--rruf--f

IJ

-0e J;[t.^h- ^.(r",k rna^,-r {i" &t (lot=#^\ a} QzF;,rvr.'rr.re tp.t Ll" {X,{b ru\^L ruQ ctr"rtp.4'ng*VxQuG,

0e Jiv;b"k* 4hw*,,nice paf /"' {^,* p2^;i)T=T,e'-.(LZ u yl c"^ 3 n= 4, .=r Q '8T,>-

a* Pn!>.|o.9 po* l;q.'e';trvitl -2*-V (2"--il a* =e6,'ff"'zo4t P,t?>.,L 42 i^ #,n , a ' =t

'q 9? >l*t 6'};- :

al {, r*-clnnm-^r."q-*eu.t p:s aiac-*'. "Lnn

!.'Jbl-4 ruq-m,.Qlu.@+ oW oate-c-' ,t'ihlr s e,t -?.'lo*v,

t';";U;ir^.-*^ ;. -Io-lu6r

g 3,v "4u" lrbr

Snc (*,nn*^'r"^e 14^ lrn /t" Qnec l^ 6h/g Qr 3, ? .au^ cdt^ &nn- lro x' c.lurltur',c=1L,5if : -uru ,-ln,u. oLSqL*,r" &^v d||ru

T. \q,3, u(ll : ,u^4 cta*t

b *V\ = #+,{4 .,^* U ^) " O, ::*tm,+e * A(t) )a\ti,r po' f^ev'+= "

l"rt , ) 4- =Ak) c,^ lt,hl'4 cmf*,'k** h,c

E :#U^8:ilYi rT,,=T^!:nqUa,';; h. ,",./*,* u'- ,o'n*:'n'n* ,^'.'Un

v\'c-4f (od ?frdzdL?*.)II

urr-.rt Iurur-.-t Iur-rt IuE--uE--t Iurr- I

uiIu-.-u--rf I

uiE-I) iur-.rt iu--d r-a^

Ih,,4ft(.. lr\ =f'

t( -lt)'/ A-VlM

Egl:4I -

Er.-I -

l:r-l

l=r--l

l:vlI -

r-

l=r-

l:r.{r=r-

l:r.-

l:r-

l-:r-

l=r.{|

E

f-rr -

I.I

l=L.flE_r{rr-rr-fIv

Niveau un 1

Niveau un :

Exo 1 :

Soit (Xn)nN une chaine de Markov espace dtats E = {1, 2, 3, 4, 5, 6} et de matrice des probabilits de transition (P) donne par :

1 2 3 4 5 6 1 0 0.8 0.2 0 0 0 2 0.3 0 0 0 0.2 0.5 3 0 0 0 1 0 0 4 0 0 1 0 0 0 5 0 0 0 0 1 0 6 0 0 0 0 0 1

1. Etudier la chaine (graphe, nature des tats, priodicit). 2. Calculer les probabilits dabsorption.

3. Dterminer Lim Pi,j ; i et j E.

4. Supposons que les tats 3, 4, 5, 6 ne forment quun seul tat que lon notera e. - Donner la matrice des probabilits de transition associe E = {1, 2, e}. - Dterminer le temps moyen jusqu' absorption.

Solution :

1/ tude de la chaine :

La premire information quon peut tirer est que la matrice des probabilits de transition (not P) est le fait que la matrice P est stocastique car la somme des lments dune ligne est gale 1.

1 2 3 4 5 6 1 0 0.8 0.2 0 0 0 2 0.3 0 0 0 0.2 0.5 3 0 0 0 1 0 0 4 0 0 1 0 0 0 5 0 0 0 0 1 0 6 0 0 0 0 0 1

Le graphe des tats :

(n)

(n)

des lments de la ligne =1






1

3 4 6

5 2

1 0.5

0.2 0.8

0.3

1

1

1

0.2

Rmq : pour sassurer que votre graphe est correct il faut que la somme des probabilits de lensemble des arcs sortants dun tat i soit gale 1.

1 2 car n=1, m=1 tq : P12 > 0 et P21 > 0. (1 et 2 appartiennent la mme classe)


3 1car il existe un arc orient de 1 3 et il nexiste pas darc orient de 3 1.

3 2 car il existe un arc orient de 2 1 et de 1 3 (chemin indirect entre 2 et 3) et il nexiste pas darc orient de 3 2 (on ne peut pas accder ltat 2 partant de ltat 3).

4 2 car il existe un arc orient de 2 1, de 1 3, et de 3 4 (chemin indirect entre 2 et 4) et il nexiste pas darc orient de 4 2 (on ne peut pas accder ltat 2 partant de ltat 4).

4 1 car il existe un arc orient de 1 3 et de 3 4 (chemin indirect entre 1 et 4) et il nexiste pas darc orient de 4 1 (on ne peut pas accder ltat 1 partant de ltat 4).

Les tats 5 et 6 ne communiquent avec aucun tat car il nexiste pas darc sortant de ltat 5 ou de ltat 6 (sauf pour les boucles).

En conclusion nous avons 4 classes distinctes les unes des autres :

- La classe transitoire T est forme des deux tats 1 et 2. On dit que T= {1, 2} est transitoire car une fois sortie de la classe T on ne peut plus revenir (elle nous permet de transiter dautres classes).

- La classe rcurrente C1 est forme des deux tats 3 et 4. On dit que C1= {3, 4} est rcurrente car une fois rentrer dans la classe C1 on ne peut plus sortir (elle absorbe le systme).

- Ltat 5 forme lui seule une classe car il ne communique avec aucun tat. La classe quil forme est not C2 = {5}. Cette classe est absorbante (elle absorbe le systme car une fois rentrer dans cette classe on ne peut plus sortir de celle ci).

- Ltat 6 forme lui seule une classe car il ne communique avec aucun tat. La classe quil forme est not C3 = {6}. Cette classe est absorbante (elle absorbe le systme car une fois rentrer dans cette classe on ne peut plus sortir de celle ci).

Lensemble des tats est fini car E = fini ce qui veut dire quil existe au moins une distribution stationnaire, mais puisque nous avons plus dune classe rcurrente (3 classes rcurrentes : C1, C2, C3) alors cette distribution stationnaire nest pas unique :

On applique donc la formule (n) = (n-1) P.

Notons que (n)(est ltat du systme linstant n) = ((n), (n),.., (n), (n)) et que (n) est la probabilit que le systme soit ltat i a linstant n = P[ Xn = i].

La chaine nest pas irrductible car il existe des tats qui ne communiquent pas entre eux (donc pas de classe dquivalence)..

La priodicit des tats : - d (1) = d(2) [par thorme de solidarit] = PGCD{2,4,6,..} =2. - d (3) = d(4) [par thorme de solidarit] = PGCD{2,4,6,..} =2. - d(5) = 1 car ltat 5 boucle sur lui mme. - d(5) = 1 car ltat 5 boucle sur lui mme. - Donc la chaine Xn est priodique.

(n) (m)

(n) (m)

1 5 6 2

i

La chaine est rcurrente positive car lensemble des tats est fini. Si la chaine est rcurrente positive, apriodique et irrductible elle est forcement ergodique

mais ci lune des conditions nest pas remplit (dans notre cas la chaine est priodique, et elle nest irrductible) on ne peut rien dire sur lergodicit (on ne peut ni nier, ni affirmer cette ergodicit).

2/ Calculer les probabilits dabsorption :

On dit que la chaine (Xn)n est absorber par le systme si la chaine passe dun tat transitoire une classe absorbante (on a pas dit passe dun tat transitoire un tat absorbant car ce nest pas ltat darriv qui absorbe mais plutt la classe laquelle cet tat appartient malgr que laccs cette classe absorbante se fait travers ce mme tat darriv).

Dans notre systme nous avons 3 classes absorbante (C1, C2, C3) et une seul classe transitoire not T.

Nous avons donc calculer :

- La probabilit que la chaine soit absorbe par la classe C1 partant de ltat transitoire 1

quon notera A1,C1. - La probabilit que la chaine soit absorbe par la classe C1 partant de ltat transitoire 2





quon notera A2,C3.

Mais avant de commencer faire des calcule donnant la formule de la probabilit dabsorption par une classe absorbante C partant dun tat transitoire i :

Ai,C = Pi,j + Pi,k Ak,C / tq k T (T tant la classe transitoire) et j C (C tant la

classe absorbante).

La probabilit que le systme soit absorb par la classe C1= {3, 4} :

A1,C1 = P1,j + P1,k Ak,C1= (P1,3+ P1,4)+( P1,1 A1,C1+ P1,2 A2,C1) .

...(1)

j C K T

j C1 K T

A1,C1 = P1,3+ P1,2 A2,C1

A1,C1 = 0.2+ 0.8 A2,C1

A2,C1 = P2,j + P2,k Ak,C1= (P2,3+ P2,4)+( P2,1 A1,C1+ P2,2 A2,C1) .

...(2)

Avec (1) et (2) on obtient un systme dquation 2 inconnus, simple rsoudre. Ainsi on trouve :

A1,C1 : cest la probabilit dtre absorb par la classe C1 partant de ltat transitoire 1 et cette probabilit est de 0.26.


Et la probabilit que le systme soit absorb par la classe C1 est le couple (0.26 , 0.078).

La probabilit que le systme soit absorb par la classe C2= {5} :

A1,C2 = P1,j + P1,k Ak,C2= (P1,5)+( P1,1 A1,C2+ P1,2 A2,C2) .

...(1) A2,C2 = P2,j + P2,k Ak,C2= (P2,5)+( P2,1 A1,C2+ P2,2 A2,C2) .

....(2)




Et la probabilit que le systme soit absorb par la classe C2 est le couple (0.26 , 0.26).

La probabilit que le systme soit absorb par la classe C3= {6} :

A1,C3 = P1,j + P1,k Ak,C3= (P1,6)+( P1,1 A1,C3+ P1,2 A2,C3) .

...(1) A2,C3= P2,j + P2,k Ak,C3= (P2,6)+( P2,1 A1,C3+ P2,2 A2,C3) .

.....(2)

j C1 K T

A2,C1 = 0.3 A1,C1

j C2 K T

A1,C2 = P1,2 A2,C2

j C2 K T

A1,C2 = 0.8 A2,C2

A2,C2 = 0.2+ 0.3 A1,C2

A2,C2 = P2,5+ P2,1 A1,C2

j C3 K T

A1,C2 = P1,2 A2,C3

j C3 K T

A1,C2 = 0.8 A2,C3

A2,C3 = 0.5+ 0.3 A1,C3

A2,C3 = P2,6+ P2,1 A1,C3


A1,C2 : cest la probabilit dtre absorb par la classe C3 partant de ltat transitoire 1.

A2,C2 : cest la probabilit dtre absorb par la classe C2 partant de ltat transitoire 2.

3/ Calcule de limites :

Avant de calculer ces limites il est important de connaitre les rgles suivantes :

- Lim Pi,j = 0 si ltat j appartient une classe transitoire T .

- Lim Pi,j = 0 si ltat j appartient une classe rcurrente C1 et ltat i appartient une autre classe rcurrente C2.

- Lim Pi,j = j Ai,C si ltat j appartient une classe rcurrente C et ltat i appartient une autre classe transitoire T

- Lim Pi,j = j si ltat j appartient une classe rcurrente C et ltat i appartient cette mme classe C.

- Pour les deux dernier cas on pourra pas calculer la limite car la distribution stationnaire nest pas unique ce qui veut dire que dpend fortement de n (n tant linstant) et a chaque fois que le n change on aura une nouvelle distribution stationnaire (n) = (1, 2, ,6).

- Connaissant ces lois on peut facilement avoir ces limites. Pour les limites qui ne peuvent pas tre calculs a cause de la raison cit prcdemment on ce contente dcrire la formule.

4/ on suppose maintenant que les tats 3, 4, 5, 6 ne forme quun seule tat :

Comment peut-on avoir P la matrice des probabilits de transition ? La rponse est simple :

1 2 e 1 0 0.8 0.2 2 0.3 0 0.7 e 0 0 1


1 2 e 1 0 0.8 ? 2 0.3 0 ? e 0 0 ?

n

(n)

n

(n)

n

(n)

n

(n)

La matrice P dans une chaine markovienne est stocastique ce qui veut dire que la somme des lments dune ligne =1.

1 2

e

0.8

0.3

0.2

1

0.7

Rmq : pour sassurer que votre graphe est correct il faut que la somme des probabilits de lensemble des arcs sortants dun tat i soit gale 1.


e 2 car il existe un arc orient de 2 e, mais il nexiste pas darc orient de e vers 2 (on ne peut pas accder ltat 2 partant de ltat e).

e 1 car il existe un arc orient de 1 vers e mais il nexiste pas darc orient de e vers 1 (on ne peut pas accder ltat 1 partant de ltat e).

Ltat e ne communique avec aucun tat car il nexiste pas darc sortant de ltat e vers ces tats.

Nous avons donc 2 classes distinctes lune de lautre :

- La classe transitoire T est forme des deux tats 1 et 2. On dit que T= {1, 2} est transitoire car une fois sortie de la classe T on ne peut plus revenir (elle nous permet de transiter dautres classes).

- Ltat e forme lui seule une classe car il ne communique avec aucun tat. La classe quil forme est not C = {e}. Cette classe est absorbante (elle absorbe le systme car une fois rentrer dans cette classe on ne peut plus sortir de celle ci).

Lensemble des tats est fini car E = fini ce qui veut dire quil existe au moins une distribution stationnaire, cette distribution stationnaire est unique car il nexiste quune seul classe rcurrente not C ={e}. dans ce cas on applique la formule : = (n) = P i =1 avec i {1, 2, e} (la matrice carr P ne contient que trois lments).Notons que

(n)(est ltat du systme linstant n) = ( , , )= car la distribution stationnaire est unique quelque soit linstant n.

La chaine nest pas irrductible car il existe des tats qui ne communiquent pas entre eux (donc pas de classe dquivalence).

La priodicit des tats : - d (1) = d(2) [par thorme de solidarit] = PGCD{2,4,6,..} =2. - d(e) = 1 car ltat e contient une boucle. - Donc la chaine Xn est priodique (car il existe un d(i) diffrent de 1).

La chaine est rcurrente positive car lensemble des tats est fini. Si la chaine est rcurrente positive, apriodique et irrductible elle est forcement ergodique

mais ci lune des conditions nest pas remplit (dans notre cas la chaine est priodique, et elle nest irrductible) on ne peut rien dire sur lergodicit (on ne peut ni nier, ni affirmer cette ergodicit).

Quand on parle du temps moyen ou dun dlai moyen dun passage dun tat un autre on pence directement ij. La formule du change selon le temps moyen quon veut calculer :

Si on nous demande le temps moyen (la dure moyenne ou mme la frquence moyenne) quil faut pour passer dun tat transitoire (appartenant une classe transitoire) un tat rcurrent (qui appartient une classe rcurrente ou absorbante), on sous entend le temps moyen quil faut pour passer dun tat rcurent une classe absorbante ou plus clairement le temps moyen dabsorption. A ce moment la aura comme formule

ic = 1+ Pik [Akc / Aic]. kc tq k reprsente lensemble des lments de la classe

(n) (m)

1 e 2

K T

transitoire T et C la classe absorbante qui absorbera la chaine Xn (il ne faut pas oublier que cest la classe qui absorbe la chaine donc mme si on vous demande de calculer le temps moyen pour passer dun tat transitoire i un tat rcurrent j il faut comprendre quil nous demande de calculer le temps moyen du passage de ltat transitoire i la classe absorbante C qui contient ltat j).

Si maintenant on nous demande de calculer le temps moyen quil faut pour passer dun tat i un tat j sans que i appartient une classe transitoire au mme moment que ltat j appartient une classe rcurrente alors on applique la formule suivante :

ij = 1+ Pik kj tq K sont lensemble des tats appartenant E-{i}.

Dans lnonc de cette exercice on a clairement spcifi quelle type de temps moyen faut-il calcul :

Il sagit de calculer 1C et 2C car on nous a pas spcifier ltat de dpart. Mais avant cela il faut calculer les probabilits dabsorption par la classe C partant de ltat 1 ou de ltat 2.

A1,C = P1,j + P1,k Ak,C= (P1,e)+( P1,1 A1,C+ P1,2 A2,C) .

...(1) A2,C = P2,j + P2,k Ak,C = (P2,e)+( P2,1 A1,C+ P2,2 A2,C) .

....(2)


A1,C : cest la probabilit dtre absorb par la classe C partant de ltat transitoire 1 et cette probabilit est de 1.56.

A2,C : cest la probabilit dtre absorb par la classe C partant de ltat transitoire 2 et cette probabilit est de 1.71.

Il devient trs facile de trouver 1C et 2C aprs avoir trouver les probabilits dabsorption par la classe C.

1c = 1+ P1k [Akc / A1c]. kc

1c = 1+ P11 [A1C / A1C]. 1C + P12 [A2C / A1C]. 2C

1c = 1+ 0.8 (1.71/156) 2C....(1)

2c = 1+ P2k [Akc / A2c]. kc

j C K T

A1,C = P1,e + P1,2 A2,C

j C K T

A1,C =0.2+ 0.8 A2,C

A2,C = 0.7+ 0.3 A1,C2

A2,C = P2,e+ P2,1 A1,C

K T

K T

2c = 1+ P21 [A1C / A2C]. 1C + P22 [A2C / A2C]. 2C

2c = 1+ 0.3 (156/1.71) 1C....(2)

il suffit de rsoudre le systme dquation (1) + (2) pour avoir :

1c : cest le temps moyen quil faut pour tre absorber par la classe C partant de ltat 1.

2c : cest le temps moyen quil faut pour tre absorber par la classe C partant de ltat 2.

Question supplmentaire :

Calculer le temps moyen de sjour dans ltat 1 et le temps moyen de sjour dans ltat 2.

Premirement il faut faire la diffrence entre le temps moyen pour passer dun tat un autre et le temps moyen de sjour (deux notions totalement diffrentes). Revenons maintenant notre question :

Temps moyen de sjour dans ltat i = 1 / Pii de ce fait :

- temps moyen de sjour dans ltat 1 = 1 / (1-P11) = 1 / (1-0) =1 - temps moyen de sjour dans ltat 2 = 1 / (1-P22) = 1 / (1-0) =1

Exo 2 :

Soit (Xn)nN une chaine de Markov espace dtats E ={1, 2} et de matrice des probabilits de transition P donne par :

P =

Sachant que la distribution initiale de la chaine ((0) : la distribution de la chaine linstant zro) = (1/3, 2/3) :

1/ calculer P (X1=2, X2=1, X3=1 / X0=1).

2/ calculer P (X1=2, X3=1 / X0=1).

3/ calculer Lim P11 et Lim P21

4/ calculer les probabilits de premier retour ltat 1 en n transitions.

5/ calculer le temps moyen de premier retour ltat 1 de deux manire diffrentes.

6/ calculer le temps de sjour ltat2.

Solution :

1/ Question 1

P (X1=2, X2=1, X3=1 / X0=1) = P (X3=1 / X2=1) P (X2=1 / X1=2) P (X1=2 / X0=1).

P (X1=2, X2=1, X3=1 / X0=1) = P11 . P21 . P12

P (X1=2, X2=1, X3=1 / X0=1) = P11 . P21 . P12

P (X1=2, X2=1, X3=1 / X0=1) = P11 . P21 . P12 = (0.5) . (0.3) . (0.5)

1 2 1 0.5 0.5 2 0.3 0.7

n

(n) (n)

n

( 3 2 ) ( 1 0 ) ( 2 1 )

(3 2) (2 1) (1 0)

Pij = P11 Pij = P21 Pij = P12

(1) (1) (1)

i=2, j=1 i=1, j=1 i=1, j=2

2/ Question 2

P (X1=2, X3=1 / X0=1) = P (X3=1 / X1=2) P (X1=2 / X0=1) P.

P (X1=2, X3=1 / X0=1) = P21 . P12

P (X1=2, X3=1 / X0=1) = P21 . P21

A ne pas confondre entre P21 = (0.3)2 et P21 = qui est la probabilit de passer de ltat 2 ltat 1

en deux tape. Pour trouver cette probabilit il suffit dappliquer la formule suivante :

P21 = P2k . Pk1 = P21 . P11 + P22 . P21 = (0.3).(0.5) + (0.7) (0.3)

P (X1=2, X3=1 / X0=1) = [(0.3) . (0.5) + (0.7) (0.3)] . (0.3)

3/ calcule des limites :

Lim P11 = 1

Lim P21 = 1

4/ calculer les probabilits de premier retour ltat 1 en n transitions.

Cette probabilit peut tre facilement dduite car si la chaine ne se trouve pas dans ltat 1 elle se trouve forcement dans ltat 2.

Rappelons que la probabilit du premier retour ltat i aprs n transitions ou n tapes scrit comme suite :

Rii = P [X1 i, X2 i, X3 i,...., Xn-1 i, Xn= i / X0= i] = cette criture exprime les informations suivante :

- Si on parle dun retour un tat cela veut dire quinitialement ( linstant 0) on se trouvait cet tat.

( 3 1 )

i=2, j=1

( 1 0 )

(3 1) (1 0)

Pij = P21 Pij = P12

(2) (1)

i=1, j=2

2 (2)

(2)

K E

n

n

(n)

(n)

Ltat 1 et ltat 2 communiquent entre eux et forme une seul et unique classe dquivalence cette mme classe dquivalence est vu comme tant une classe rcurrente unique or comme dj vu dans lexercice 1 si ltat de dpart i et ltat darriv j appartiennent une mme classe rcurrente alors la limite est gale j.

(n)

- Aux instants 1,2,3,.n-1 on se trouvait dans dautres tats que ltat i sinon on ne peut pas parler de premier retour linstant n si on se trouvait un instant TIME (un instant prcdant linstant n) dans ltat i.

- A linstant n on se trouve forcement ltat i pour exprimer le premier retour cet tat.

R11 = la probabilit du premier retour ltat 1 en 1 tape = P11 = la probabilit de passer de ltat 1 ltat 1 en 1 tape = 0.5

R11 = la probabilit du premier retour ltat 1 en 2 tape = (P12)(P21) = (0.5)(0.3)

R11 = la probabilit du premier retour ltat 1 en 3 tapes = (P12)(P22)(P21) =

R11 = la probabilit du premier retour ltat 1 en 4 tapes = (P12)(P22)2(P21) =

R11 = la probabilit du premier retour ltat 1 en 5 tapes = (P12)(P22)3(P21) =

R11 = la probabilit du premier retour ltat 1 en n tapes = (P12)(P22)(n-2)(P21) =

5/ calculer le temps moyen de premier retour ltat 1 de deux manire diffrentes :

Premire mthode :

Calculer le temps moyen du premier retour ltat 1 revient calculer le temps moyen de sjour dans ltat 2 ( ne pas confondre le temps moyen de sjour dans un tat et le temps de sjour dans un tat).

Le temps moyen de sjour dans ltat 2 = E{S2 / X0 = 2} = 1 / (1 P22).

Deuxime mthode :

Pour pouvoir utilis cette deuxime mthode il faut que la distribution stationnaire existe et quelle soit unique.

Lensemble des tats not E est fini ce que veut dire quil existe au moins une distribution stationnaire, et puisquil existe une seule et unique classe dite classe dquivalence (et qui est forcement rcurrentes) la distribution stationnaire est unique et est dfinit par le couple :

= (n) = P i =1 avec i {1, 2}

Notons que (n) (est ltat du systme linstant n) = ( , )= car la distribution stationnaire est unique quelque soit linstant n.

Si la distribution stationnaire nest pas unique elle sera non pas dfinie par le couple

mais par la formule (n) = (n-1) P.

(1)

(2)

) (3)

(4)

(5)

(n) (0.5)(0.7)(n-2)(0.3)

(0.5)(0.7)3(0.3)

(0.5)(0.7)2(0.3)

(0.5)(0.7)2(0.3)

1 2

= (n) = P

i =1 avec i {1, 2}

Puisque la distribution stationnaire existe et est unique on peut calculer le temps moyen de premier

retour ltat 1 par la formule 11 = 1 / 1

Calculons maintenant la distribution stationnaire = (1, 2) :

(1, 2) = (1, 2)

1 + 2 = 1

0.5 1 + 0.3 2 = 1

0.5 1 + 0.7 2 = 2

1 + 2 = 1

0.5 0.5

0.3 0.7

On ce retrouve avec trois quation et deux inconnu. Un systme dquations classique et simple rsoudre (1, 2) = (0.38, 0.62)

Exo 3 :

Soit (Xn)nN une chaine de Markov despace dtats E = {1, 2, 3} et de matrice de transition

On donne la loi initiale (0) = (1, 0, 0).

A. Calculer la probabilit que la chaine quitte ltat 1 aprs n transition. B. Donner la nature des tats suivant la valeur de p et q et donner les classes de communication. C. Etudier suivant les valeurs de p lergodicit de la chaine et donner les probabilits stationnaire

dans le cas ou elle existe et est unique. D. En supposons que p = 3/5 calculer P* = Lim Pn

Solution :

A. Calculer la probabilit que la chaine quitte ltat 1 aprs n transition :

Premire mthode :

On calcule la probabilit suivante :

P[ X1 = 1, X2 = 1, X3 = 1,, Xn-1 = 1, Xn 1 / X0 = 1] =

P [Xn 1 / Xn-1 = 1].P [Xn-1 = 1 / Xn-2 = 1].P [Xn-2 = 1 / Xn-3 = 1] P[X2 = 1 / X1 = 1].P[X1 = 1 / X0 = 1]

= (P [Xn = 2 / Xn-1 = 1] + P [Xn = 3 / Xn-1 = 1]).(P [Xn-1 = 1 / Xn-2 = 1])(n-1)

= (P12+P13).(P11)(n-1) = [q+0].(p)(n-1) = q p(n-1)

Deuxime mthode :

Il suffit de calculer le temps de sjour ( diffrencier avec le temps moyen de sjour, et nous, on ne cherche pas une moyenne) dans ltat 1 :

P {S1 = n / X0=1} = [1-P11]. (P11)(n-1) (la formule gnrale P {Si = n / X0 = i} = [1-Pii]. (Pii)

(n-1)

P {S1 = n / X0=1} = [1-p]. (p)(n-1) = q p(n-1)

B. Donner la nature des tats suivant la valeur de p et q et donner les classes de communication.

1 2 3 1 p q 0 2 0 p q 3 q p 0

p, q [0,1] et p+q =1

n

Car linstant n on quitte ltat 1 pour aller un autre tat.

Si p=1 et 1-p = q = 0 :

1 2 3 1 1 0 0 2 0 1 0 3 0 1 0

1 2 car n, m tq : P12 > 0 et P21 > 0.

2 3 car n, m=1 tq : P23 > 0 et P32 > 0.

1 3 car n, m tq : P13 > 0 et P31 > 0.

Lensemble des tats E est fini donc nous avons au moins une distribution stationnaire (nous concluons aussi que la chaine est rcurrente positive).

La chaine nest pas irrductible car il existe des tats qui ne communiquent pas. La chaine est priodique car : d(1) = 1 (ltat 1 contient une boucle) ; d(2) = 1 (ltat 2 contient

une boucle) ; d(3) = 0 (P33 = 0 quelque soit n N). On ne peut rien dire sur lergodicit de la chaine. La distribution stationnaire nest pas unique et est dfinie par : (n) = (n-1) P = (0) P(n).

Si p=0 et 1-p = q = 1 :

1 2 3

1 0 1 0

2 0 0 1

3 1 0 0


2 3 car n=1, m=2 tq : P23 > 0 et P32 > 0. (3 et 2appartiennent la mme classe)

Par transitivit nous avons ltat 1 qui communique avec ltat 3.

Les trois tats communiquent et forme une seule et unique classe dquivalence (la chaine est irrductible)

Lensemble des tats E est fini ce qui veut dire quil existe au moins une distribution stationnaire.

1 3 2

1 1

1

(n) (m)

(n) (m)

(n) (m)

Aucun tat ne communique avec les autres tats. Donc chaque tat forme lui seule une classe.

Ltat 1 est rcurrent car une ne contient pas darc sortant.

Ltat 2 est rcurrent car une ne contient pas darc sortant.

Ltat 3 est transitoire car il nous permet de faire des transitions vers dautres tats.

(n)

1

3

2

1

1

1

(n) (m)

(n) (m)

La distribution stationnaire est unique car il existe une seule et unique classe dquivalence (une classe en elle-mme rcurrente) ce qui veut dire que la distribution stationnaire est dfinie par le couple : = (n) = P i =1 avec i {1, 2, 3} et =

(n) =( , , ) (la distribution stationnaire est indpendante de n).

d(1) = d(2) = d(3) par le thorme de solidarit d(1) = PGCD {3,6,.} = 3 quelque soit i E alors d(i) = 3 ce qui veut dire que la chaine est priodique et quon ne peut

rien dire sur lergodicit. Aprs avoir rsolu le systme dquation dfinissant la distribution stationnaire on trouve =

(1, 2, 3) = (1/3,1/3,1/3) Lim (n) = = (1, 2, 3) = (1/3,1/3,1/3) car la distribution stationnaire est unique (ne

change pas au changement de n) et concide avec la distribution limite.

Si 0 < p < 1 et 0 < q < 1 (on prend titre dexemple p=3/5, q=2/5):

1 2 3

1 3/5 2/5 0

2 0 3/5 2/5

3 2/5 3/5 0


2 3 car n=1, m=1 tq : P23 > 0 et P32 > 0. (3 et 2appartiennent la mme classe)

Par transitivit nous avons ltat 1 qui communique avec ltat 3.

Les trois tats communiquent et forme une seule et unique classe dquivalence (la chaine est irrductible)

Lensemble des tats E est fini ce qui veut dire quil existe au moins une distribution stationnaire.

La distribution stationnaire est unique car il existe une seule et unique classe dquivalence (une classe en elle-mme rcurrente) ce qui veut dire que la distribution stationnaire est dfinie par le couple : = (n) = P i =1 avec i {1, 2, 3} et =

(n) =( , , ) (la distribution stationnaire est indpendante de n).

d(1) = d(2) = d(3) par le thorme de solidarit quelque soit i E alors d(i) =1 ce qui veut dire que la chaine est apriodique et puisque la

chaine est irrductible, rcurrente positive, et apriodique elle est forcement ergodique. Aprs avoir rsolu le systme dquation dfinissant la distribution stationnaire on trouve =

(1, 2, 3) = (2/9,5/9,2/9)

1 3 2

n

1

3

2

2/5

3/5

2/5

(n) (m)

(n) (m)

1 3 2

2/5

3/5

3/5

Lim (n) = = (1, 2, 3) = (q/(2q+1), 1/(2q+1), q/(2q+1)) = (2/9,5/9,2/9) car la distribution stationnaire est unique (ne change pas au changement de n) et concide avec la distribution limite.

Dans ce cas :

Attention : ne pas confondre Lim P(n) quand n (qui dsigne la limite de la matrice P) et Lim P(n) quand n (qui dsigne la limite de la probabilit de passage de ltat i ltat j en une tape).

2/9 5/9 2/9 2/9 5/9 2/9 2/9 5/9 2/9

n

n Lim P(n) =

i,j

Exo 5 :

Un dispositif technique comprend deux lments monts en parallle et fonctionne indpendamment lun de lautre. Chaque lment une probabilit p de ne pas tomber en panne (et une probabilit de 1-p pour tomber en panne, cette probabilit sera not q) au cours dune journe et il nya pas de possibilit de rparation si jamais une panne survient. On sintresse au nombre dlments en panne au dbut de chaque journe.

1/ modliser le systme par une chaine de Markov dont on prcisera la matrice de transition.

2/ donner la nature des tats et dduire le comportement asymptotique.

Solution :

Le dispositif contient deux lments et on sintresse au nombre dlments en panne au dbut de chaque journe.

Au dbut de chaque journe je peux avoir :

les deux lments du dispositif qui fonctionnent (0 lments tombs en panne). Un des deux lments du dispositif qui tombe en panne (1 lment tomb en panne) Les deux lments du dispositif qui tombent les deux en panne (2 lments en panne) Conclusion : lensemble des tats contient trois tats = {0, 1, 2}.

P00 = P [Xn+1 = 0 / Xn = 0] = cest la probabilit quaucun lment du dispositif ne tombe en panne linstant n+1 sachant quinitialement aucun lment ntait en panne = p * p = p2.

P01 = P [Xn+1 = 1 / Xn = 0] = cest la probabilit quun lment du dispositif tombe en panne linstant n+1 sachant quinitialement aucun lment ntait en panne = p*q + q*p (car soit cest le premier lment du dispositif qui tombe en panne soit cest le second lment du dispositif qui tombe en panne) = 2*(p*q).

P02 = P [Xn+1 = 2 / Xn = 0] = cest la probabilit que les deux lments du dispositif tombent en panne linstant n+1 sachant quinitialement aucun lment ntait en panne = q *q (car cest le premier lment du dispositif qui tombe en panne et le second lment du dispositif qui tombe en panne) = q2.

P10= P [Xn+1 = 0 / Xn = 1] = cest la probabilit quaucun lment du dispositif ne tombe en panne linstant n+1 sachant quinitialement il ya un seul lment du dispositif qui t en panne = 0 (car un lment qui tombe en panne ne peut pas tre rpar).

P11 = P [Xn+1 = 1 / Xn = 1] = cest la probabilit quun seul lment du dispositif tombe en panne linstant n+1 sachant quinitialement il nya quun seul lment qui tait en panne (cest forcement le mme lment qui est en panne) = cest la probabilit quun lment en marche reste en marche = p.

P12 = P [Xn+1 = 2 / Xn = 1] = cest la probabilit que deux lments du dispositif tombent en panne linstant n+1 sachant quinitialement il nya quun seule lment qui tait en panne = q (cest la probabilit de passer de ltat de marche ltat de panne).

P20= P [Xn+1 = 0 / Xn = 2] = cest la probabilit quaucun lment du dispositif ne tombe en panne linstant n+1 sachant quinitialement deux lments taient en panne = 0 (car un lment qui tombe en panne nest pas rparable).

P21= P [Xn+1 = 1 / Xn = 2] = cest la probabilit quun seul lment du dispositif tombe en panne linstant n+1 sachant quinitialement deux lments taient en panne = 0 (car un lment qui tombe en panne nest pas rparable).

P22= P [Xn+1 = 0 / Xn = 2] = cest la probabilit que les deux lments du dispositif tombent en panne linstant n+1 sachant quinitialement les deux lments taient en panne = 1 cest la probabilit certaine car si les deux lments tombent en panne ils le resteront pour toujours (pas de possibilit de rparation)

La matrice des probabilits de transition est donc la suivante :

0 1 2 0 P2 2*p*q q2

1 0 p q 2 0 0 1

Il faut sassurer que la matrice P est stocastique :

Premire ligne : p2 + 2pq + q2 = (p+q)2 = (1)2 = 1.

Deuxime ligne : 0 + p + q = 1.

Troisime ligne : 0 + 0 + 1 = 1.

P =

De cette manire nous somme sur davoir mis les bonnes probabilits dans les bons endroits de la matrice (en vrifiant la proprit : dans une chaine de Markov la matrice P est stocastique).

0 1

2

P2

2*p*q

q2

1

P

q

- Ltat 0 ne communique avec aucun tat car il ne contient aucun arc entrant donc cest un tat transitoire qui forme lui seul une classe transitoire.

- Ltat 2 ne communique avec aucun tat car il ne contient aucun arc sortant vers dautres tats. Il forme lui seule une classe rcurrente.

- Ltat 1 forme une classe transitoire qui permet de passer la classe absorbante {2}.

- Lensemble E est fini donc il existe au moins une distribution stationnaire. Cette distribution stationnaire est unique car il nya quune seule et unique classe rcurrente.

- La chaine Xn est rcurrente positif car E est fini. - La chaine nest pas irrductible car il existe des tats qui ne communiquent

pas. - d(0) =1 car ltat 0 contient une boucle. - d(1) =1 car ltat 1 contient une boucle. - d(2) =1 car ltat 2 contient une boucle. - La chaine Xn est apriodique car quelque soit i E ={0, 1, 2} d(i) = 1. - On ne peut rien dire sur lergodicit de la chaine.

Exo 4 :

On donne la matrice de transition P dune chaine de Markov espace dtats E = {1, 2, 3, 4, 5, 6} par :

1 2 3 4 5 6 1 1/2 1/2 0 0 0 0 2 1/3 2/3 0 0 0 0 3 0 0 1/8 0 7/8 0 4 1/4 1/4 0 0 1/4 1/4 5 0 0 3/4 0 1/4 0 6 0 1/5 0 1/5 1/5 2/5

1/ donner la nature de chacun des tats.

2/ on donne la loi initiale (0) = (1/2, 1/2, 0, 0, 0, 0), calculer Lim (n). Mme question pour (0) = (0, 0, 1, 0, 0, 0).

3/ calculer les probabilits dabsorption (sil ya lieu) dans les classes rcurrentes.

4/ calculer Lim P(n) pour tous couple (i,j) dans E*E.

5/ donner la ou les probabilits stationnaires. Justifier vos rponses.

6/ donner une modification pour P pour avoir une chaine ergodique.

Solution :

1/ donner la nature de chacun des tats.

12 car n=1, m=1 tq P12 > 0 et P21 > 0.

46 car n=1, m=1 tq P46 > 0 et P64> 0.

35 car n=1, m=1 tq P35 > 0 et P53> 0.

n

ij n

1 2

4 6

3 5

1/2

1/3

2/3

1/5 2/5

1/4

1/5

1/2

1/4 1/4

1/5 1/4

1/4

1/8

3/4

7/8

Remarque : pour sassurer que le graphe est correct il faut que la somme des probabilits des arcs sortants de chaque tat soit gale 1.

(n) (m)

(n) (m)

(n) (m)

Ltat 1 ne communique pas avec les tats 4,6,3,5 (se qui veut dire que ltat 2 ne communique pas non plus avec les tats 4,6,3,5).



Nous avons E = (C1) union (C2) union (T).

Tel que :

C1 = {1,2} est une classe rcurrente car une fois accd a cette classe on ne peut plus sortir de celle-ci.

C2 = {3,5} est une classe rcurrente car une fois accd a cette classe on ne peut plus sortir de celle-ci.

T = {4,6} est une classe transitoire car une fois sortie de cette classe on ne peut plus revenir cette mme classe.

Lensemble des tats E est fini ce qui veut dire quil existe au moins une distribution stationnaire cependant cette distribution stationnaire nest pas unique puisquil existe 2 classes rcurrentes C1 et C2.

2/ le calcule de la Lim (n) si la distribution initiale (0) = (1/2, 1/2, 0, 0, 0, 0) (elle reprsente la distribution stationnaire de la chaine linstant t = 0).

Initialement la chaine est dans la classe C1 ={1, 2} (qui est une classe rcurrente et absorbante) or on sait bien que si la chaine ce trouve un instant dans une classe absorbante, elle ne peut plus sortir de celle- ci (elle y reste). Donc si comme si que la chaine de Markov cest restreinte la classe C1. Dans ce cas la nous avons une seule classe qui rcurrente ce qui nous permet de conclure que la distribution stationnaire cette instant existe et est unique (elle est confondue avec la distribution limite). La distribution stationnaire est calculer cet instant par :

1 2 1 1/2 1/2 2 1/3 2/3

Le calcule de la Lim (n) si la distribution initiale (0) = (0, 0, 1, 0, 0, 0) (elle reprsente la distribution stationnaire de la chaine linstant t = 0).

Initialement la chaine se trouve dans ltat 3 qui sont tour appartient une classe rcurrente C2 ={3, 5} donc obligatoirement la chaine se trouve dans la classe absorbante C2 or on sait bien que si la chaine ce trouve un instant dans une classe absorbante, elle ne peut plus sortir de celle- ci (elle y reste). Donc si comme si que la chaine de Markov cest restreinte la classe C2. Dans ce cas la nous avons aussi une seule classe qui rcurrente ce qui nous permet de conclure que la distribution stationnaire cette instant existe et est unique (elle est confondue avec la distribution limite). La distribution stationnaire est calculer cet instant par :

3 5 3 1/8 7/8 5 3/4 1/4

n

(1, 2) = (1, 2)

1 + 2 = 1

Aprs avoir rsolut le systme dquations on

obtient 1 = 2/5, 2 = 3/5.

Ce qui veut dire que la distribution limite = Lim (n) = (2/5, 3/5, 0, 0, 0, 0).

n

Aprs avoir rsolut le systme dquations on

obtient 3 = 6/13, 5 = 7/13.

Ce qui veut dire que la distribution limite = Lim (n) = (0, 0, 6/13, 0, 7/13, 0).

n

(3, 5)

3 + 5 = 1

(3, 5) =

n

3/ calculer les probabilits dabsorption (sil ya lieu) dans les classes rcurrentes.

Nous avons deux classes rcurrentes donc il faut calculer les probabilits suivantes :

La probabilit que le systme soit absorb par la classe C1 partant dun tat transitoire appartenant T.

La probabilit que le systme soit absorb par la classe C2 partant dun tat transitoire appartenant T.

Rappelle :

La probabilit que le systme soit absorber par la classe C partant dun tat transitoire appartenant

une classe transitoire = Aic = Pij + = Pik AkC .

La probabilit que le systme soit absorb par la classe C1={1,2} partant dun tat transitoire appartenant T={4, 6} :

A4,C1 = P4,j + = P4,k Ak,C1 .

A4,C1 = (P4,1+ P4,2 ) + (P4,4 A4,C1+ P4,6 A6,C1).

A4,C1 = (1/4 +1/4) + (1/4 A6,C1) = 1/8 +(1/4 A6,C1)...(1)

A6,C1 = P6,j + = P6,k Ak,C1 .

A6,C1 = (P6,1+ P6,2 ) + (P6,4 A4,C1+ P6,6 A6,C1).

A6,C1 = (1/5) + (1/5 A4,C1+ 2/5 A6,C1)...(2)

La probabilit que le systme soit absorb par la classe C2={3,5} partant dun tat transitoire appartenant T={4, 6} :

A4,C2 = P4,j + = P4,k Ak,C2 .

A4,C2 = (P4,3+ P4,5 ) + (P4,4 A4,C2+ P4,6 A6,C2).

A4,C2 = (1/4) + (1/4 A6,C2)...(1)

A6,C2 = P6,j + = P6,k Ak,C2 .

A6,C1 = (P6,3+ P6,5 ) + (P6,4 A4,C2+ P6,6 A6,C2).

A6,C2 = (1/5) + (1/5 A4,C2+ 2/5 A6,C2)...(2)

j C k T

j C1 k T

j C1 k T

De (1) et (2) on trouve :

A4,C1 : la probabilit dtre absorber par la classe C1 partant de ltat transitoire 4 = 7/11.


j C2 k T

j C2 k T




4/ calculer Lim P(n) pour tous couple (i,j) dans E*E.

Lim P(n) = 0 car ltat 4 est un tat transitoire.

Lim P(n) = 0 car ltat 6 est un tat transitoire.

Lim P(n) = Lim P(n) = 2/5 = 1

Lim P(n) = Lim P(n) = 3/5 = 2

Lim P(n) = Lim P(n) = 6/13 = 3

Lim P(n) = Lim P(n) = 7/13 = 5

Lim P(n) = A4,C1 2 = 7/11 * 3/5

Lim P(n) = A6,C1 2= 6/11 * 3/5

Lim P(n) = A4,C1 1 = 7/11 * 2/5

Lim P(n) = A6,C1 1= 6/11 * 2/5

Lim P(n) = A4,C2 3 = 4/11 * 6/13

Lim P(n) = A6,C2 3= 5/11 * 6/13

Lim P(n) = A4,C2 5 = 4/11 * 7/13

Lim P(n) = A6,C2 5= 5/11 * 7/13

Lim P(n) = Lim P(n) = 0 car ltat 5 C2 et les tats 1, 2 C1 et C1C2




5/ donner la ou les probabilits stationnaires. Justifier vos rponses.

Si on se situe au niveau de toute la chaine il existe une infinit de distribution stationnaire car nous avons C1et C2 comme classes rcurrentes.

6/ donner une modification pour P pour avoir une chaine ergodique.

Il suffit de modifier P pour avoir une chaine de Markov irrductible, apriodique, et rcurrente positive du coup une chaine ergodique.

ij n

i4 n

i6 n

11 n

42 n

62 n

n 21

12 n n 22

33 n n 53

35 n n 55

Car les tats 1 et 2 appartiennent une mme classe rcurrente C1. (2/5, 3/5) est lunique distribution stationnaire qui existe sur C1.

Car les tats 3 et 5 appartiennent une mme classe rcurrente C2. (6/13, 7/13) est lunique distribution stationnaire qui existe sur C2.

41 n

61 n

Car ltat 2 est un tat appartenant une classe absorbante C1 et les tats 4 et 6 sont des tats transitoires appartenant la classe transitoire T.


43 n

63 n

45 n

65 n


Car ltat 3est un tat appartenant une classe absorbante C2 et les tats 4 et 6 sont des tats transitoires appartenant la classe transitoire T.

15 n n 25

13 n n 23

51 n n 31

52 n n 32

Exo 5 :

Soit la chaine de Markov trois tats 1, 2, 3 et de matrice des probabilits de transition en une tape P telle que :

1 2 3 1 0.25 2 0.25 0.25 0.5 3 0.5 0.25 0.25

1/ pour quelle valeur de et , cette matrice P peut-elle servir de matrice des probabilits de transition dune chaine de Markov ?

2/ dterminer la nature de la chaine (classification, existence dune distribution stationnaire) dans les cas : (a)- = 0, (b)- = 0 (calculer dans chaque cas la distribution stationnaire si elle existe).

Solution :

1/ Pour que la matrice P puisse servir de matrice des probabilits de transition dune chaine de Markov il faut que la somme des probabilits dune ligne soit gale 1 (car, on le sait bien, une matrice des probabilits de transition dune chaine de Markov est stocastique ce qui veut dire que la

somme des probabilits dune ligne est gale 1). Autrement dit Pi,j = 1 quelque soit i {1,2,3} et Pi,j > =0, on dduit alors :

Pour que la matrice P soit une Matrice des probabilits de transition dune chaine Markovienne il faut que + = 0.75 et que , >=0.

2/ cas (a) : = 0 (ce qui veut dire que = 0.75) :

1 2 3 1 0 0.75 0.25 2 0.25 0.25 0.5 3 0.5 0.25 0.25

P =

j {1,2,3}

P =

1 2

3

0.25

0.25

0.25

0.75

0.25 0.5 0.25 0. 5

- Tout les tats communique entre eux donc la chaine est irrductible.

- Quelque soit i {1,2,3} alors d(i) =1 car d(1)=d(2)=d(3) par le thorme de solidarit et d(2) =1 (car ltat 2 contient une boucle). La chaine est apriodique.

- La chaine est rcurrente positive car lensemble des tats E est fini.

- La chaine est irrductible, apriodique, et rcurrente positive donc elle est ergodique.

- Lensemble E est fini donc il existe au moins une distribution stationnaire. Cette distribution stationnaire est unique puisquil existe une unique classe dite dquivalence.

La distribution stationnaire est calcule par le systme dquations : = P et 1 + 2 + 3 =1.

On obtient alors :

0 1 + 0.25 2 + 0. 5 3 = 1.

0.75 1 + 0.25 2 + 0.25 3 = 2.

0.25 1 + 0. 5 2 + 0.25 3 = 3.

1 + 2 + 3 =1.

2/ cas (b) : = 0 (ce qui veut dire que = 0.75) :

1 2 3 1 0.75 0 0.25 2 0.25 0.25 0.5 3 0.5 0.25 0.25

La distribution stationnaire est calcule par le systme dquations : = P et 1 + 2 + 3 =1.

On obtient alors :

0.75 1 + 0.25 2 + 0. 5 3 = 1.

0 1 + 0.25 2 + 0.25 3 = 2.

0.25 1 + 0. 5 2 + 0.25 3 = 3.

1 + 2 + 3 =1.

Il suffit de rsoudre ce systme dquations (4 quations et 3 inconnus : un systme simple rsoudre) pour avoir la valeur de lunique distribution stationnaire = (1, 2, 3).

P =

1 2

3

0.25

0.25

0.25

0.75

0.25 0.5 0.25 0. 5

- Tout les tats communique entre eux donc la chaine est irrductible.

- Quelque soit i {1,2,3} alors d(i) =1 car d(1)=d(2)=d(3) par le thorme de solidarit et d(2) =1 (car ltat 2 contient une boucle). La chaine est apriodique.

- La chaine est rcurrente positive car lensemble des tats E est fini.

- La chaine est irrductible, apriodique, et rcurrente positive donc elle est ergodique.

- Lensemble E est fini donc il existe au moins une distribution stationnaire. Cette distribution stationnaire est unique puisquil existe une unique classe dite dquivalence.

Il suffit de rsoudre ce systme dquations (4 quations et 3 inconnus : un systme simple rsoudre) pour avoir la valeur de lunique distribution stationnaire = (1, 2, 3).

Exo 6 :

Soit la chaine de Markov telle que E = {0, 1, 2, 3} et la matrice des probabilits de transition

0 1 2 3

0 1/3 2/3 0 0

1 1/2 0 1/2 0

2 0 0 1/4 3/4

3 0 0 1 0

On note Ai,B la probabilit que la chaine soit absorbe par la classe C partant de ltat i.

Calculer les probabilits suivantes : A1,B1, A1,B2, A2,B2 telle que B1 ={0, 1} , B2 = {2, 3}.

Solution :


01 car n=1, m=1 tq P01 > 0 et P10 > 0.

23 car n=1, m=1 tq P23 > 0 et P32> 0.

12car n=1, m tq P12 > 0 et P21> 0.

Ltat 0 et ltat 1 forme une classe transitoire T = {0, 1} = B1: on dit quelle est transitoire car elle nous permet de passer vers une classe rcurrente de plus une fois sortie de la classe T on ne peut plus revenir celle-ci.

Ltat 2 et ltat 3 forme une classe rcurrente (absorbante) C = {2, 3}= B2 car une fois accd cette classe on ne peut plus sortir de celle-ci.

A1,B1 = la probabilit dtre absorber par la classe T partant de ltat 1 = 0 car une classe transitoire ne peut jamais absorber le systme (cest une classe transitoire ce qui veut dire que je peut la quitter et que je ne pourrais jamais tre prisonnier de cette classe).

A2,B2 = la probabilit dtre absorber par la classe C partant de ltat 2 = 1 cest la probabilit certaine car si on se trouve dans ltat 2 qui appartient la classe C on est forcement absorber par la classe C la preuve mettez vous dans le graphe ltat 2 et essayez de passer a ltat 0 ou ltat 1.

P =

0 1 2 3

1/3

2/3 1/2

1/2

1/4

3/4

1

(n) (m)

(n) (m)

Ltat 1 ne communique pas avec 2, par transitivit ltat 1 ne communique pas non plus avec ltat 3.

Ltat 2 ne communique pas avec 1, par transitivit ltat 2 ne communique pas non plus avec ltat 0.

Ltat 0 ne communique pas avec 2, par transitivit ltat 0 ne communique pas non plus avec ltat 3

(n) (m)

Rappelle : La probabilit que le systme soit absorber par la classe C partant dun tat transitoire

appartenant une classe transitoire = Aic = Pij + = Pik AkC .

La probabilit que le systme soit absorb par la classe C={2,3} partant dun tat transitoire appartenant T={0, 1} :

A0,C= P0,j + = P0,k Ak,C .

A0,C = (P0,2+ P0,3 ) + (P0,0 A0,C+ P0,1 A1,C).

A0,C = (1/3 A0,C + 2/3 A1,C)...(1)

A1,C = P1,j + = P1,k Ak,C.

A1,C = (P1,2+ P1,3 ) + (P1,0 A0,C+ P1,1 A1,C).

A1,C= (1/2) + (1/2 A0,C)...(2)

On conclu que A1,B2 = A1,C = 1.

La probabilit dtre absorb par la classe C compos des deux tats 2 et 3 partant de ltat 0 ou ltat 1 est certaine. Ce fait est justifi par la prsence dune seule et unique classe rcurrente (absorbante) ce qui rend cette probabilit dabsorption = 1 (si il yavait plusieurs classes rcurrentes alors cette probabilit sera < 1).

j C k T

j C k T

j C k T


A0,C : la probabilit dtre absorber par la classe C partant de ltat transitoire 0 = 1.

A1,C : la probabilit dtre absorber par la classe C partant de ltat transitoire 1 = 1.

Exo 7 :

Deux joueurs A et B jouent pile ou face . Au dbut du jeu le joueur A procde a dinars et le joueur B possde b dinars. On suppose que lapparition de pile donne un gain de 1 dinars au joueur contrairement lapparition de face qui fait perdre au joueur 1 dinars (- 1 dinars).

Soit Xn lavoir du joueur A au nime lanc de la pice (ce que possde le joueur A comme montant

linstant n).

Sachant que X0 = a (le jour A possde initialement a dinars), P (pile) = p, P (face) = 1-p = q :

1/ montrer que la chaine (Xn)nN est une chaine de Markov.

2/ donner lespace des tats ainsi que la matrice des probabilits de transition.

Solution :

1/ Pour montrer quune chaine est Markovienne il faut prouver que Xn+1 ne scrit que en fonction de Xn (ce qui veut dire que le future ne dpend que dun prsent proche ou encore le prsent ne dpend que dun pass proche).

Soit Xn+1 ltat de la chaine linstant n+1, Xn ltat de la chaine linstant n :

Xn+1 =

Car si le joueur a de largent son tat linstant n+1 sera gale son tat linstant n avec un gain ou une perte de 1 dinars. Si le joueur est fauch ou si le jour a gagn tous largent de son concurrent alors le jeu sarrte et son tat linstant n+1 sera le mme qua linstant n.

Del on peut dire que ltat du joueur A linstant n+1 ne dpend que de son tat linstant n : on dira alors que (Xn)nN est une chaine de Markov.

2/ lensemble des tats du joueur A est son solde au cour du jeu (au pire des cas il est fauch et au mieux il gagne tous largent de son concurrent) : E = {0, ., a+b}.

P00 = quelle est la probabilit que le joueur A soit faucher linstant n+1 sachant quil est fauch linstant n = 1 (cest la probabilit certaine car une fois le joueur fauch il ne peut plus jouer).

Pa+b,a+b = quelle est la probabilit que le joueur A soit vainqueur linstant n+1 sachant quil est dj vainqueur linstant n = 1 (cest la probabilit certaine car une fois vainqueur on ne peut plus jouer).

Pour les autre cas nous avons les probabilits de transition suivantes :

Pi,j = p (la probabilit de russite) si j = i + 1 (si le joueur A augmente sa fortune de 1 dinars) Pi,j = 1- p = q (la probabilit dchec) si j = i - 1 (si le joueur A diminue sa fortune de 1 dinars)

Il est facile aprs avoir trouv les probabilits de transition de construire la matrice P.

Xn + n+1 si 0

Exo 8 :

Soit (Xn)nN une chaine de Markov despace dtats E = {1,2,3} et de matrice de transition P donne par :

1 2 3 1 0 2 0 3 0

On prend comme distribution initiale (0) = (1, 0,0) :

1/ calculer la probabilit que la chaine quitte ltat 1 pour la premire fois aprs n transitions.

2/ donner la nature des tats suivant les valeurs de et donner les classes de communications.

3/ tudier suivant les valeurs de lergodicit de la chaine et donner la distribution stationnaire lorsquelle existe.

4/ on pose =3/5, dterminer la distribution stationnaire si elle existe.

5/ en dduire la Lim P(n) quand n.

Solution :

1/ calculer la probabilit que la chaine quitte ltat 1 pour la premire fois aprs n transitions revient calculer le temps de sjour dans ltat 1 :

P (S1 = n / X0 =1) = sachant que linstant zro on est ltat 1, quel est la probabilit de quitter cette tat linstant n = (1-P11) (P11)

n-1 = (1-) ()n-1 = ()n-1.

Cette formule P (S1 = n / X0 =1) est tir de la probabilit P[ Xn 1, Xn-1 =1, Xn-2 =1, X1 =1/ X0 =1] et qui veut dire : quelle est la probabilit de partir de ltat 1 linstant n sachant quinitialement on t ltat 1 et on est rest dans cette tat jusqu' linstant n-1 cette probabilit est gale :

P[ Xn 1/ Xn-1 =1]*P[ Xn-1 =1/ Xn-2 =1]**P[ X3 =1/ X2 =1]*P[ X2 =1/ X1 =1]*P[ X1 =1/ X0=1] =

P[ Xn 1/ Xn-1 =1] * (P11)(n-1) = (la probabilit que je ne soit pas ltat 1) * (P11)

(n-1)

= (1-P11) (P11)n-1.

(2+3+4) / Premier cas si =0 (donc est gale 1) :

1 2 3 1 0 1 0 2 0 0 1 3 0 1 0

P = , [0,1] et + = 1

P =

1 2 3 1

1

1

23 car il existe n= 1 et il existe m=1 telle que P23 >=0 et P32 >=0. 2 ne communique pas avec 1 car il existe un arc orient de ltat 1 vers ltat 2 et il nexiste

aucun chemin direct ou indirect qui peut relier ltat 2 a ltat 1 dans cet ordre. Ltat 1 forme lui seule une classe transitoire T = {1} : cest une classe transitoire car une

fois quon quitte cette classe vers une autre classe on ne peut plus revenir celle-ci. Les tats 2 et 3 forment classe rcurrente (absorbante) C = {2,3} : cest une classe rcurrente

car une fois arriver cette classe on ne peut plus sortir de celle-ci. La chaine Xn net pas irrductible car il existe des tats qui ne communiquent pas. La chaine est rcurrente positive car lensemble des tats E est fini. d(2) = d(3) (par thorme de solidarit) = PGCD {2, 4, 6,8,..} = 2. d(1) = 0 (car il contient quun arc sortant, aucun arc entrant et aucune boucle). Il existe au moins un i E telle que d(i) 1 la chaine est priodique. Si la chaine est priodique, nest pas irrductible, est rcurrente positive : on ne peut rien dire

sur lergodicit de la chaine. La chaine admet au moins une distribution stationnaire car lensemble des tats E est fini, de

plus cette distribution stationnaire est unique car il existe une seule et unique classe rcurrente. La distribution stationnaire est calcule partir du systme dquations : = P et 1 + 2 +

3 =1. On obtient alors : 0 1 + 0 2 + 0 3 = 1. 1 1 + 0 2 + 1 3 = 2. 0 1 + 1 2 + 0 3 = 3. 1 + 2 + 3 =1.

Deuxime cas si =1 (donc est gale 0) :

1 2 3 1 1 0 0 2 0 1 0 3 1 0 0

3 ne communique pas avec 1 car il existe un arc orient de ltat 3 vers ltat 1et il nexiste aucun chemin direct ou indirect qui peut relier ltat 1 a ltat 3 dans cet ordre.

Lta

Documents

Chaines de Markov execrices corrigée