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

13 avr 2018 · Chaînes de Markov à temps continu 3 Reversibility 4 Processus de Naissance et de Mort 5 Conclusion 6 Files d'attente classiques 



Previous PDF Next PDF





[PDF] Chaˆınes de Markov `a temps continu

(Yn)n≥0 est une chaıne de Markov `a temps discret de loi initiale λ et de matrice de transition Π, 2 conditionnellement `a Y0 = i0, ,Yn−1 = in−1, les temps d' 



[PDF] Modèles stochastiques Chaîne de Markov en temps continu

Dans le chapître précédent sur les chaînes de Markov, les moments (temps) etaient discrets ( 0,1, ) Maintenant, nous allons analyser des situations où



[PDF] Chaˆınes de Markov en temps continu et génétique des populations

12 mar 2015 · (i) sa chaıne incluse (Yn)n≥0 est une CMTD de loi initiale λ et de matrice de probabilités de transition Π; (ii) pour tout n ≥ 1, conditionnellement 



[PDF] Processus de Poisson Chaînes de Markov à temps continu

Polytech Lyon M2 Statistique des processus TP 2 Processus de Poisson, chaînes à temps continu Processus de Poisson Exercice 1 Paradoxe de l' autobus



[PDF] Chaînes de Markov - Institut Camille Jordan

1 7 1 Chaîne de Markov en temps discret et espace quelconque 26 1 7 2 Chaîne de Markov en temps continu et espace discret 27 1 7 3 Processus de 



[PDF] Continuous-time Markov chains - POLARIS

13 avr 2018 · Chaînes de Markov à temps continu 3 Reversibility 4 Processus de Naissance et de Mort 5 Conclusion 6 Files d'attente classiques 



[PDF] 1 Chaˆınes `a temps continu, espace détat fini

Chaˆınes de Markov Exercices 4 1 Chaˆınes `a temps continu, espace d'état fini Exercice 1 On consid`ere la chaıne `a temps continu sur l'espace {1,2,3}, 



[PDF] Processus markoviens de sauts - Laboratoire de Probabilités

On peut donc voir une chaîne de Markov en temps continu comme une famille de matrices de transition (P(t))t≥0 satisfaisant l'équation ci-dessus Néanmoins, il 



[PDF] Introduction aux processus dexclusions - Index of

La loi exponentielle va jouer un rôle fondamental dans les chaînes de Markov en temps continu grâce à la propriété suivante : Proposition 1 7 : Propriété sans 



[PDF] Chaînes de Markov et Processus markoviens de sauts Applications

Exemple 3 (File d'attente en temps discret) On considère une file d'attente à un gichet On note (Xn)n≥0 le nombre de personnes dans la file à l'instant n Entre l'  

[PDF] examen corrigé file d'attente

[PDF] file d'attente m/m/1 exercice corrigé

[PDF] file d'attente m/m/c

[PDF] chaine de markov pour les nuls

[PDF] chaine de markov résumé

[PDF] chaine de markov matrice de transition

[PDF] exercice corrigé chaine de markov a etat absorbante

[PDF] chaine d'acquisition de données

[PDF] chaine de mesure audioprothèse

[PDF] acquisition de données du capteur ? l ordinateur

[PDF] chaine de mesure pdf

[PDF] chaine d'acquisition capteur

[PDF] les capteurs exercices corrigés

[PDF] chaine de markov apériodique

[PDF] chaine de markov apériodique exemple

[PDF] Continuous-time Markov chains - POLARIS

Continuous-time Markov chains

Florence Perronnin

Performance evaluation

April 13, 2018

Processus de Poisson

Outline

1Processus de Poisson

2Chaînes de Markov à temps continu

3Reversibility

4Processus de Naissance et de Mort

5Conclusion

6Files d"attente classiques

Processus de Poisson

Processus de Poisson

définition 1time0=1

N(4) =5

N(2) =3N(2) =2N(2) =0N(4) =4

N(2) =4N(2) =2Processus de comptage

SoitN(t)le nombre d"événements dans l"intervalle[0;t).8k2?; ?[N(T) =k] =(T)kk!eTLoi de Poisson (1)

Processus de Poisson

Processus de Poisson

définition 2Définition infinitésimale On considère un processus stochastique à temps discret et à espace d"états continus ftngn2?tel que 0d"événements. Les 4 conditions suivantes doivent être remplies simultanément :1?[1 seul év. dans intervalle de durée h] =h+o(h)2?[plusieurs év. dans intervalle de durée h] = +o(h)3Le nombre d"événements dans des intervallesd isjointssont des va riablesaléatoires

indépendantes

Processus de Poisson

Processus de Poisson

définition équivalenteInterarrivées L"intervalle de tempsn=tn+1tnentre 2 événements consécutifs est une variable aléatoire exponentielle de paramètre. De plus8n;m=n6=m, les variablesnetmsont indépendantes.Preuve: ?[n] =1?[n] =1?[aucune arrivée entretnettn+] =1?[N() =0] =1()00!e =1eloi exponentielle

Processus de Poisson

Origine des Processus de Poisson

Processus de Poisson

Origine des Processus de Poisson

Problème de Siméon Denis Poisson

Trouver la loi du nombre de criminels par région. Modèle: chaque individu est un criminel potentiel avec probap. Donc sur une population denindividus,

P(kcriminels) =

n k! p k(1p)nk(2) En supposant constante la criminalitémoyenne?[N] =np=on obtientp==nce qui permet de faire le calcul asymptotique suivant pourn! 1

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

n k 11n k 1n n (3) n!(nk)!(n!)kkk! 1n n (4)

1kk!e(5)

Processus de Poisson

Modélisation par des processus de Poisson

Limite asymptotique de la loi binomiale :superposition d"un grand nombre (idéalement illimité) de comportement indépendants.L"idée principale est que chaque événement est

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]

défauts de crédit arrivées de particules radioactives sur un compteur Geiger arrivées de connexions TCP [Paxon & Floyd 1994] En revanche, les arrivées depaquetsTCP ne suivent pas un processus de Poisson, car ces arrivées sont corrélées. (6)

Processus de Poisson

Nombre moyen d"événements

On considère un processus de Poisson de paramètre. Le nombre moyen d"événements dans un intervalle de duréetest : ?[N(t)] =t:

Preuve :

?[N(t)] =1X k=0k(t)kk!et(7) 1X k=1(t)k(k1)!et(8) =t1X k=1(t)k1(k1)!et(9) =t1X j=0(t)jj!et(10) =tetet(11) =t:(12)

Processus de Poisson

Uniformité

Soit un processus de Poisson de paramètreet un intervalle de tempsI= [t;t+s].

Si l"on connaît le

nomb re d"événements q uise sont p roduitsd ansl"intervalle I, alors les instants d "occurrenced eces événements dans l"in tervalleIsont distribuésunifo rmément sur I. Par exemple, pour 1 seul événement : on notet1l"instant d"arrivée de cet événement unique dansI. ?[t1xjN(I) =1] =?[t1xetN(I) =1]?[N(I) =1](13) ?[1 ev. dans[t;t+x]et aucun dans[t+x;t+s]]s es(14) x exe(sx)s es(15) xs c.d.f de la loi uniforme sur[t;t+s](16)

Processus de Poisson

Superposition de processus de Poisson

On considère 2 processus de Poisson indépendants, de paramètres respectifs1et2. Par

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

On s"intéresse au processus total, i.e. l"ensemble des requêtes arrivant dans le système composé des serveursAetB.Théorème

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 superposé (total). ?[nx] =1?[nx](17) =1?[N1(x) =0]?[N2(x) =0](18) =1e1xe2x(19) =1e(1+2)x(20)

Processus de Poisson

Décomposition d"un processus de Poisson

SoitfN(t)gun processus de Poisson de paramètre. On construit un second processus fN0(t)gde la façon suivante : Pour chaque événement du processus d"origine, on garde l"événement dansfN0(t)gavec une probabilitép, et on ignore cet événement avec probabilité 1p. Les tirages pour chaque événements sont indépendants.théorème Le processus résultatfN0(t)gest un processus de Poisson de paramètrep.Exemple On considère les arrivées de jobs à un serveur. Elles suivent un processus de Poisson de paramètre. Chaque client, avec une probabilitép, décide d"abandonner sa requête. Le processus d"arrivée réel est un processus de Poisson de paramètrep.

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

Chaînes de Markov à temps continuContinuous-time modeling

Limitations of discrete-time

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

arrivals: Poisson(0:5)variable service-time:E(1) discrete-time model fXng=number of jobs attime slot nof durationt=103s.We cansimplify the mo delb y neglecting multiple arrivals / multiple departures in a single time slot:Event probabilities:

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

no arrival0.9995001

1 arrival107

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

q(1p)q(1p)pq+ (1p)(1q)1q(1p)1p5104510410 310

30:9980:9990:999

Chaînes de Markov à temps continuContinuous-time modeling

Continuous-time modeling

Discrete-time limitations

time-slot granularity approximations (neglect some unlikely transitions)

Continuous-time model

012 Chaînes de Markov à temps continuContinuous-time modeling Définition des Chaînes de Markov à temps continu (CMTC) fXtgt2?processus stochastique à temps continu : transitions à instantstquelconques (non dénombrables). L"espace d"étatsS, lui, reste discret.Propriété de Markov Pour toutn(taille d"observation) et pour toutn+2-uplet(t0;:::;tn+1)tel que t

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