[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 ( 01 ) Maintenant nous allons analyser des situations où
[PDF] 10 Les processus de Markov `a temps continu
Définissons les temps de saut successifs de X par T0 = 0 Tn = inf{t>Tn?1 Xt = XTn?1 } Alors Yn = XTn est une cha?ne de Markov de matrice P Si Sn+1 = Tn+1
[PDF] Chaînes de Markov - Institut Camille Jordan
1 7 2 Chaîne de Markov en temps continu et espace discret 27 1 7 3 Processus de Markov en temps continu 35
[PDF] Processus de Poisson Chaînes de Markov à temps continu
Processus de Poisson chaînes à temps continu Processus de Poisson Exercice 1 Paradoxe de l'autobus Vérifier expérimentalement le paradoxe de l'autobus
[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] Fiche résumée du cours de Processus de Markov par IKourkova 1
1 Chaînes de Markov à temps continu sur un espace dénombrable 1 1 loi exponentielle Définition 1 1 1 (Loi exponentielle) Une variable aléatoire T suit une
[PDF] Chaînes de Markov
Soit (Xn)n2N une chaîne de Markov de matrice de transition P et T un temps d'arrêt pour sa filtration canonique Pour toute fonction mesurable bornée f sur l'
[PDF] CHAÎNES DE MARKOV - Institut de Mathématiques de Bordeaux
Markov sont à espace d'états continu mais nous n'aborderons pas leur étude ici Soit T un temps d'arrêt à valeurs dans [0 +?] adapté à la chaîne de
[PDF] Chaînes de Markov et Processus markoviens de sauts Applications
En quelque sorte un processus markovien de saut ou encore chaîne de Markov en temps continu combine un processus de Poisson et une chaîne de Markov
[PDF] Chaˆ?nes de Markov `a temps continu - Université de Rennes
Une cha?ne de Markov `a temps continu (Xt)t?0 est déterminée par une mesure ? sur I (identifiée `a un vecteur ligne) et un générateur Q La mesure ? détermine
[PDF] chaines de markov a temps continu
CHAINES DE MARKOV A TEMPS CONTINU I Definitions E = {90 91 am} ou {am MEE} = espace des états XE:R DE 5 a Défi (XE) tert chaîne de Markov
[PDF] CHAÎNES DE MARKOV - Institut de Mathématiques de Bordeaux
Les chaînes de Markov sont des suites aléatoires sans mémoire en quelque sorte Dans l'évolution au cours du temps l'état du processus à un instant futur
[PDF] 10 Les processus de Markov `a temps continu
Définissons les temps de saut successifs de X par T0 = 0 Tn = inf{t>Tn?1 Xt = XTn?1 } Alors Yn = XTn est une cha?ne de Markov de matrice P Si Sn+1 = Tn+1
[PDF] CHAÎNES DE MARKOV - ceremade
CHAÎNES DE MARKOV Spécialité : INGENIEUR 1ère année Béatrice de Tilière La partie “Rappels de probabilités” est basée sur des notes écrites en
[PDF] Chapitre 8 Chaˆ?nes de Markov - DI ENS
Les notions de retournement de temps et de réversibilité sont tr`es productives en théorie des cha?nes de Markov Soit {Xn}n?0 une cmh de matrice de transition
[PDF] Chaˆ?nes de Markov en temps continu (CMTC)
25 mar 2020 · probabilité conditionnelle de dépend pas de s Une chaˆ?ne de Markov en temps continu (CMTC) est un processus ayant ces 2 propriétés
[PDF] Continuous-time Markov chains
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] Chaînes de Markov
Soit (Xn)n2N une chaîne de Markov de matrice de transition P et T un temps d'arrêt pour sa filtration canonique Pour toute fonction mesurable bornée f sur l'
[PDF] Chaˆ?nes de Markov en temps continu et génétique des populations
complet o`u cette méthode est appliquée Il est clair que le processus Yt est presque sûrement continu `a droite et constant par mor- ceaux et que sa cha?ne
![[PDF] Continuous-time Markov chains [PDF] Continuous-time Markov chains](https://pdfprof.com/Listes/17/28543-17RICM4_EP_CMTC.pdf.pdf.jpg)
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=1N(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 0Processus 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 exponentielleProcessus 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! 1P(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 estindé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. Parexemple, 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èmeLa 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 modelingLimitations 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.99950011 arrival107
1 departureq=9:99104012p(1q)p
q(1p)q(1p)pq+ (1p)(1q)1q(1p)1p5104510410 31030:9980:9990:999
Chaînes de Markov à temps continuContinuous-time modelingContinuous-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 t0 ?[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
?[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 modelingProbabilité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.QuestionPourt=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 modelingGé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"estle 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éfinitionQ=limt!0P
tIt Chaînes de Markov à temps continuContinuous-time modeling propriétés du générateur infinitésimalCe 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=jOn a donc
q ii=X j6=iq ij Chaînes de Markov à temps continuContinuous-time modeling Interprétation du générateur infinitésimalTaux 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 lesystè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 modelingConstruction é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 modelingExercice
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 modelingFaulty 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 model2What 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 modelingComportement asymptotique
La distribution transitoire est difficile à calculer et peu maniable (change à chaqueinstant). 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èmeQ=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 modelingExample : 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 0Define=
(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=1Finally we get :
i=i(1)8i0 (21) Chaînes de Markov à temps continuContinuous-time modeling Exercise : Balance equations for the faulty machines modelReversibility
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 liReversibility
Reversibility
Theorem
If a Markov chain is time-reversible then thedistribution is also the stationary distribution.ProofDetailed balance)global balance:
8i;j; iqij=jqji
) 8i;X j6=i iqij=X j6=i jqjiProcessus 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ésimalQ= (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+1i01i2i1ii+1
i1Lorsque le processusX(t)est dans un étati, il ne peut aller que vers ses voisins immédiatsi+1 eti1Processus de Naissance et de Mort
Générateur
Q=0 BBBBBB@000 0::: ::: :::
1(1+1)10::: ::: :::
02(2+2)20::: :::
0 03(3+3)30...
....................1 CCCCCCA
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 210(25)
Processus de Naissance et de Mort
Solving balance equations
The above equations suggest a solution of the form: (n) =01:::n112:::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+01+:::+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+1i01i2i1ii+1
i1By induction: 100=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[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] 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] chaine de markov reversible