[PDF] [PDF] Continuous-time Markov chains - POLARIS

Processus de Poisson

Processus de Poisson

Processus de Poisson

Origine des Processus de Poisson

Processus de Poisson

Origine des Processus de Poisson

Problème de Siméon Denis Poisson

P(kcriminels) =

P(kcriminels) =n!k!(nk)!

1kk!e(5)

Processus de Poisson

Modélisation par des processus de Poisson

indépendant de tous les autres.morts par coups de sabot de cheval dans l"armée prussienne [Ladislaus Bortkiewicz,

1898]appels arrivant à un central téléphonique [Erlang, 1909]

Processus de Poisson

Nombre moyen d"événements

Preuve :

Processus de Poisson

Uniformité

Si l"on connaît le

Processus de Poisson

Superposition de processus de Poisson

exemple, l"arrivée de requêtes sur un serveurA, et l"arrivée de requêtes sur un serveurB.

La superposition de ces deux processus est un processus de Poisson de paramètre1+2.Preuve: Soitnl"intervalle de temps entre lenième et len+1ème événements du

Processus de Poisson

Décomposition d"un processus de Poisson

Chaînes de Markov à temps continu

Outline

1Processus de Poisson

2Chaînes de Markov à temps continu

Continuous-time modeling

3Reversibility

4Processus de Naissance et de Mort

5Conclusion

6Files d"attente classiques

Limitations of discrete-time

Consider a single FIFO server M/M/1/2

1 arrivalp= (0:5t)e0:5t=4:99104

1 arrival107

1 departureq=9:99104012p(1q)p

30:9980:9990:999

Continuous-time modeling

Discrete-time limitations

Continuous-time model

0

?[Xtn+1=jn+1jXtn=jn;:::;Xt0=j0] =?[Xtn+1=jn+1jXtn=jn]En bref, la connaissance de fragments anciens de trajectoire n"apporte pas d"information

sur la suite de la trajectoire si l"on connaît un état plus récent. Chaînes de Markov à temps continuContinuous-time modeling

Probabilités de transition

Les probabilités de transition sont définies par : ?[Xt=jjXs=i] =Pts(i;j) (si la CMTC esthomogène). La matrice de transitionPtdépend donc du tempst, comme à temps discret elle dépendait du nombre de "slots" :P(n)=Pn.Question

Pourt=0, que devient la matrice de transitionPt?C"est l"identité (le processus ne peut pas changer d"état en un temps nul)

lim t!0Pt=IChapman-Kolmogorov à temps continu Pour tout couple d"états (i,j) et pour tous instantstets: P t+s(i;j) =X k2SP t(i;k)Ps(k;j) soit sous forme matricielle : P t+s=PtPs Chaînes de Markov à temps continuContinuous-time modeling

Générateur infinitésimal

Puisque la matrice de transitionPtest une fonction du temps, il est plus simple de travailler avec une autre matrice, constante, représentant la dynamique du système. C"est

le rôle du générateur infinitésimal, défini (pour l"instant) comme la dérivée de la matrice

de transition en 0 (rappel:limt!0Pt=I)Définition

Q=limt!0P

tIt Chaînes de Markov à temps continuContinuous-time modeling propriétés du générateur infinitésimal

Ce générateurQ=qijvérifie également :

?[Xt+dt=jjXt=i] =qijdt+o(dt)toutes ses lignes sont àsomme nulle : X j2Sq ij=0tous ses coefficients sontp ositifs(ou nuls) sauf les co efficientsdiagonaux , qui du coup sont forcément négatifs. q ii0;qij0 sii6=j

On a donc

q ii=X j6=iq ij Chaînes de Markov à temps continuContinuous-time modeling Interprétation du générateur infinitésimal

Taux de transition

Les coefficientsqijdu générateurQ= (qij)représentent letaux de transition de iversj lorsquej6=i. On peut les voir comme la "vitesse" de l"événement qui fait passer le

système de l"étativers l"étatj.Interprétation deqijtemps de séjour eni: variable aléatoire de loiExp(qii)puis saut instantané versjavec probabilitéqijq

iiIl n"y a doncjam aisde "taux de transition d"un état ivers lui-même" : la CMTC reste sur place un temps exponentiellement distribué de paramètreqii=P j6=iqij Chaînes de Markov à temps continuContinuous-time modeling

Construction équivalente de la CMTC

à l"instanttoù le processusXtentre dans l"étati:on tire pour chaque étatj6=iune durée aléatoireTijde loiExp(qij)Si le minimum desTijest réalisé pour un état donnék, le processus restera eniun

tempsTikpuis sautera directement dans l"étatk.

Cela peut être vu comme une

comp étition entre les différents événements p ouvantse produire à partir d"un état.temps de séjour Le temps de séjour est le minimum desTij: c"est donc une variable aléatoire exponentielle de paramètreP j6=iqij=qii Chaînes de Markov à temps continuContinuous-time modeling

Exercice

Modéliser la M/M/1 avec une CMTC (i.e., définirfXtgainsi que son espace d"états) et calculer son générateur infinitésimal ainsi que son graphe de transition. Chaînes de Markov à temps continuContinuous-time modeling

Faulty machines model

1 main serverM, high qualityUp time: E()Repair time: E()1 secondary serverSfor backup (and, why not, increased service rate)Up time: E()Repair time: E()Exercise

The goal is to estimate theavailabilityof the system,i.e.the probability that at least one server is up and running.1Define a CTMC model

2What is the state space?

3Determine the transition diagram

4Compute the infinitesimal generator

How can the model be simplified when=and=?

Chaînes de Markov à temps continuContinuous-time modeling

Comportement asymptotique

La distribution transitoire est difficile à calculer et peu maniable (change à chaque

instant). On s"intéresse à la probabilité que le système soit dans un état donné en régime

stationnaire : c"est ladistribution limite.Théorème SifXtgest irréductible (tous les états communiquent)et sile système

Q=0 ( Balance equations)

admet une unique solution strictement positivetelle queP i(i) =1 (vecteur de probabilités)

Alors la distributionest la distribution limite

lim t!+1?[Xt=i] =(i) Chaînes de Markov à temps continuContinuous-time modeling

Équations d"équilibre

On peut voir l"équationQ=0 comme une conservation des flux: On cherche= (1;:::;i;:::)un vecteur de probabilités tel que: 8i;X j6=iq iji=X k6=i kqkiP j6=iqiji: fluxso rtantde l"état iP k6=ikqki: fluxentrant dans l"état iiqi iq k1i q k2i q k3iq i j1 q i j2 q i j3Comme dans le cas du temps discret, on a besoin d"une équation supplémentaire: l"équation de normalisation:X i i=1 Chaînes de Markov à temps continuContinuous-time modeling

Example : Balance equations for the M/M/1 model

1Define a CTMC :X(t) =number of clients in the system2Determine transition rates:

birth rate:qi;i+1=death rate:qi;i1=ifX(t)1 (the server only works if there is at least 1 client)3Write balance equations (to find stationary distribution)

outgoing rate...(+)i=i1+i+1...incoming ratei-1ii+1 Chaînes de Markov à temps continuContinuous-time modeling Example : Balance equations for the M/M/1 model (cont"d)

4Solve balance equations (up to a factor, namely0):

i= i 0

Define=

(system load). Then i=i05Determine0(and its existence condition) using thenormalizationequation X i i=1) <1o requiv alently <

If this stability condition is verified then

1=X i i=Xi0=011,0=1

Finally we get :

i=i(1)8i0 (21) Chaînes de Markov à temps continuContinuous-time modeling Exercise : Balance equations for the faulty machines model

Reversibility

Outline

1Processus de Poisson

2Chaînes de Markov à temps continu

3Reversibility

4Processus de Naissance et de Mort

5Conclusion

6Files d"attente classiques

Reversibility

Reversibility

Definition

A continuous-time Markov chainX(t)istime-reversible if and only i fthere exist a probability distributionsuch that8(i;j)2 S2, iqij=jqji(Detailed balance)jikl q kiq ijq ikq jiq ilq li

Reversibility

Reversibility

Theorem

If a Markov chain is time-reversible then thedistribution is also the stationary distribution.Proof

Detailed balance)global balance:

8i;j; iqij=jqji

) 8i;X j6=i iqij=X j6=i jqji

Processus de Naissance et de Mort

Outline

1Processus de Poisson

2Chaînes de Markov à temps continu

3Reversibility

4Processus de Naissance et de Mort

5Conclusion

6Files d"attente classiques

Processus de Naissance et de Mort

Processus de Naissance et de Mort

Definition

Un processus de naissance et de mort est une CMTC dont le générateur infinitésimal

Q= (qij)est une matrice tridiagonale:8i2 E;

q i;i+1=i q i;i1=i q i;j=0 ifj=2 fi1;i;i+1g(22). . .01. ..i-1ii+1 i+212i+1i

01i2i1ii+1

i1Lorsque le processusX(t)est dans un étati, il ne peut aller que vers ses voisins immédiatsi+1 eti1

Processus de Naissance et de Mort

Générateur

Q=0 B

BBBBB@000 0::: ::: :::

1(1+1)10::: ::: :::

02(2+2)20::: :::

0 03(3+3)30...

....................1 C

CCCCCA

Processus de Naissance et de Mort

Balance equations

Global balance

00=11(23)

(i+i)i=i1i1+i+1i+1(24)eq.(23))1=0 1 0 and eq.(24)fori=1)(1+1)1=00+22 )22= (1+1)0 1 000 )22=10 1 0 )2=10 21
0(25)

Processus de Naissance et de Mort

Solving balance equations

The above equations suggest a solution of the form: (n) =01:::n1

12:::n(0)Exercice

Prove by induction that the above expression satisfies the balance equations. Then0can be computed using the normalization equationP ii=1if the system is stable (finite sum) (0) =11+0

1+:::+01:::n1

12:::n

Processus de Naissance et de Mort

Reversibility for BDP

Proposition

An ergodic birth and death process is time-reversible.

Proof. . .01. ..i-1ii+1

i+212i+1i

01i2i1ii+1

i1By induction: 1

00=112Supposei1i1=ii. Then

i(i+i) =i+1i+1+i1i1Which givesii=i+1i+1.We geti+1=i i+1i, which directly gives the previous result !

Processus de Naissance et de Mort

Théorème pour les processus de naissance et de mort (Condition de stabilité)

Si la série Cn=1+0

1+:::+01:::n1

quotesdbs_dbs29.pdfusesText_35