Stochastique / Déterministe

Modélisation et Simulation des S.E.D. • Déterministe : aucune entrée n’est de nature aléatoire

• Stochastique : variables aléatoires, phénomènes aléatoires,

Chaînes de Markov
– le comportement du système est décrit de manière probabiliste

Master ISC David GOUYON

Les Chaînes de Markov Les chaînes de Markov à temps discret

• Processus stochastique X ∈ℕ à espace d’état discret et à temps discret

• Nous considérons deux exemples de processus stochastiques à espace
d’état discret • E est l’espace d’états
– De dimension finie ou infinie (mais dénombrable car discret)
– Chaînes de Markov à temps discret (CMTD)
– Chaînes de Markov à temps continu (CMTC) 8 E
7
6
• Chaînes de Markov : analyse préliminaire à l’étude des systèmes de 5
4
files d’attente 3
2
1
0 n
0 2 4 6 8 10

Processus stochastique à espace d’état discret et à temps discret

 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

X ∈ℕ ≜
, ∈
• Définition : est une chaîne de Markov à temps discret ssi • Matrice de transition

PX j |X n 1 in 1 , X n 2 in 2 , . . . , X i PX j |X n 1 in 1
– Matrice carrée d’ordre fini ou infini, selon que l’espace d’état est fini ou infini
• La probabilité pour que la chaîne soit dans un certain état à la nième
« étape » du processus ne dépend que de l’état du processus à l’étape
précédente (j = n-1), et pas des états dans lesquels il se trouvait aux ... ...
étapes antérieures (j = 0, …, n-2) ... ... ...
P ... ... ... ... ...
... ... ...
• Autrement dit :
ij
... ... ... ... ...
– Une chaîne de Markov est un système pouvant évoluer entre n états Xi
définis par le repère X = (X1, X2, … Xn),
– Le passage d’un état Xi à un état Xj ou transition, de dépend que de ces
deux états et s’effectue selon la probabilité conditionnelle Prob(Xj/Xi) = pij
• Notons que :

pij 1 et pij 0
∈

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Représentation graphique • Modélisation

– Graphe orienté – On s’intéresse à l’état du système à des instants particuliers tn de leur
– On associe à chaque état un nœud évolution
– On associe à chaque transition possible entre chaque état un arc pondéré – Deux cas :
par la probabilité de transition • Intervalles de temps réguliers (tous les jours, toutes les heures …)
– > l’état du système à l’étape n du processus est l’état du système au nième jour
• Intervalles de temps quelconques (tn est l’instant du nième changement)
• Exemple : E = {1,2,3,4} – > l’état du système à l’étape n du processus correspond à l’état juste après le nième
changement d’état
p23 = p41 = 1
P12 + p14 = 1 et p31 + p33 = 1
2 8 E 8 E
p12 p23

0 p 0 p
7 7
6 6

0 0 1 0
p31

P
1 3 5 5
p33

p! 0 p!! 0
p41 4 4

1 0 0 0
3 3
2 2
p14 4 1 1
0 n 0 n
0 2 4 6 8 10 0 2 4 6 8 10
CMTD à instants de changement d’états équidistants CMTD à instants de changement d’états quelconques
 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Exemple : souris dans un labyrinthe • Exemple : souris dans un labyrinthe

– 5 pièces reliées entre elles par des couloirs à sens unique – On s’intéresse uniquement à la succession des pièces visitées et pas au
– 1 sortie temps passé dans chacune, ni au temps passé dans les couloirs
– La souris ne peut faire demi tour dans un couloir – Hypothèses :
– Une fois dans la pièce 5, la souris ne peut faire demi-tour • La souris ne garde pas la mémoire des pièces précédemment visitées
• Quand la souris est dans une pièce, elle choisit un couloir de façon équiprobable
– Tant que la souris n’est pas tombée dans la pièce 5, elle continue son
chemin

1/2 1/2

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

1/4
5 3 4
5 3 4 5 3 4
1/4

Les chaînes de Markov à temps discret Exemple : téléphone

• Exemple : souris dans un labyrinthe • Considérons un téléphone (simplifié) pouvant recevoir un appel à la fois
– Un seul appel peut avoir lieu dans une unité de temps, avec une probabilité α
• Les transitions modélisent les couloirs
1/2 1/2 – Si le téléphone est occupé, l’appel est perdu, sinon, l’appel est pris
• Les probabilités associées à ces transitions modélisent – La probabilité qu’un appel se termine dans une unité de temps est β
1/2 un choix aléatoire d’un des couloirs de sortie parmi tous
1 2 ceux possibles partant d’une pièce donnée – Si à la fois un appel arrive et un appel se termine dans la même unité de
1/4 temps, le nouvel appel est traité
1/4 1/2 • Le rebouclage sur l’état 6 est nécessaire pour le modèle
1/4 et signifie simplement que lorsque la sourie est sortie, elle
5 3 4 ne peut rentrer de nouveau dans le labyrinthe • Donner la représentation matricielle et graphique de la chaine de Markov
1/4 représentant le comportement du téléphone
• Sachant que la souris est initialement dans la pièce 2 :
état absorbant 6
• Quelle est la probabilité qu’elle y soit à nouveau après 4
déplacements ? (notation π2(4))
• Combien de fois passera-t-elle en moyenne par la pièce 3
avant de sortir ou de tomber dans la pièce 5 ? (R23)
Sortie : état absorbant • Quelle est la probabilité que la souris trouve la sortie ? (f26)
• Combien fera-t-elle de déplacements en moyenne pour
revenir dans la pièce 2 ? (M2)
 Exemple : téléphone Les chaînes de Markov à temps discret

• Analyse : Régime transitoire

π(n) des probabilités d’état π ≜ P X j pour que le processus X ∈ℕ

$ %
– L’analyse du régime transitoire d’un CMTD consiste à déterminer le vecteur

1 " "
se trouve dans l’état j à la n ième étape du processus :

π ≜ π π ,π ,...
$ % $ % $ % $ %
#$1 "% 1 # & "# j∈E
– Ce vecteur des probabilités dépend :
• De la matrice de transition P

– Remarque : l’état initial est défini par ses probabilités π π ,π ,...

$ % $ % $ %
α • Du vecteur des probabilités d’état initiales π(0)

que π$ % 1 et que π 0 pour tout j ≠ i

$ %
• Dire qu’initialement le processus est dans un certain état i revient à considérer
1-α 0 1 1-β + αβ
– Régime transitoire : évolution du processus depuis l’état initial (caractérisé
β(1-α) par π(0)) jusqu’à l’étape n (caractérisé par π(n)), en passant par toutes les
étapes intermédiaires

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : Régime transitoire • Analyse : Régime transitoire

π π P
$ % $ %
– Formule des probabilités totales – En appliquant cela n fois :
π PX j PX j |X n 1 i P Xn 1 i
$ %
– On définit alors pij(m), la probabilité de transition de l’état i à l’état j en m
$n 1%
pij ≜ P Xn&m j|X
∈)
i ∀. ∈ ℕ
$+%
soit π π pij
$ %
étapes :
∈)
– On définit également la matrice de transition en m étapes P $+% ≜ P $1%
, ∈
 Probabilité de se trouver dans l’état j à la nième étape = probabilité de
$m 1 %
pij pik pkj
passer d’un certain état i à l’état j pondérée par la probabilité d’être dans avec $+%
l’état i à l’étape précédente
$n 1%
0∈)
 Sous la forme matricielle : π π P
$ %
(exprime le fait que pour aller de l’état i à l’état j en m étapes, on peut aller de
(liaison de la probabilité d’état à l’étape n 1 2
l’état i à un état k en m-1 étapes, puis aller de cet état k à l’état j en 1 étape
à celle de l’étape précédente) et ce pour tous les états k)

– Exemple de la souris dans le labyrinthe :  Sous forme matricielle : P(m) = P(m-1) P

• Probabilité de se trouver dans l’état 1
 Et comme P(1) = P  P(n) = Pn
à l’instant n 5 3 4

$n 1% $n 1% $ n 1%
π π p11 & π p21 & π! p31
$ %
 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Exemple de la souris dans le labyrinthe : • Analyse : distribution du temps de séjour dans un état
1 2
– Sachant que la souris est placée initialement dans – Propriété : le « temps » (nombre d’étapes) passé dans un état d’une CMTD
la pièce 2, quelle est la probabilité qu’elle y soit à a une distribution géométrique
nouveau après 4 déplacements ? – Preuve : on s’intéresse au nombre d’étapes passées dans un certain état j :
5 3 4
 Revient à calculer π2(4) sachant que π2(0) = 1 • Si pjj = 0, on ne reste jamais dans l’état j
– Il faut calculer P4 • Si pjj ≠ 0, on a, à chaque étape, une probabilité pjj de rester dans l’état j et une
– π2(4) est la deuxième composante du vecteur π(4) probabilité (1-pjj) d’en sortir :
1/2 1/2
– π(4) = π(0) P4 avec π(0) = [0,1,0,0,0,0]
1/2
1 2 1-pjj i≠j étape 1
1/4
1/4 1/2
j 1-pjj i≠j étape 2
1/4
5 3 4
pjj 1-pjj i≠j étape 3
– Ou π2(4) = π2(0) p22(4) j
1/4
étape 0
Avec pour calculer p22(4), 3 chemins possibles : pjj j
6
•2  4  3  1  2 : probabilité associée = ½ * 1 * ¼ * ½ = 1/16 pjj j
•2  1  2  1  2 : probabilité associée = ½ * ½ * ½ * ½ = 1/16 …
•2  1  1  1  2 : probabilité associée = ½ * ½ * ½ * ½ = 1/16 • La distribution du nombre m d’étapes passées dans l’état j est donc donnée par :
(1-pjj)pjjm
La probabilité associée est donc 3/16
 Distribution géométrique

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : irréductibilité • Analyse : périodicité d’un état

– Définition : une CMTD est dite irréductible ssi de tout état i on peut atteindre – Définition : un état j est périodique si on ne peut revenir qu’après un nombre
tout état j (en un nombre fini d’étapes) : d’étapes multiples de k > 1

∀i,j ∈ E, ∃ m 3 1 tel que pij 90 ∃ k 3 1 tel que pii 0 pour m non multiple de k
$+% $+%

– Exemple : – La période de l’état j est alors le plus grand entier k vérifiant cette propriété
 Cette CMTD n’est pas irréductible ! – Exemple :
0,5 2 0,5
0,25
0,25 0,5 2 0,5

6 1 0,5 0,5
3 6 0,5
1 3 0,5
0,5
7 0,25 4 5 0,5
7 0,25 4 5

Sous-chaîne absorbante 1
L’état 6 est périodique de période 2
Sous-chaîne absorbante 2

 Toute CMTD non irréductible possède au moins une chaîne absorbante L’état 4 est apériodique
 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : périodicité d’une CMTD • Analyse : périodicité d’une CMTD

– Définition : la période d’une CMTD est égale au plus grand dénominateur – Exemples :
commun de la période de chacun de ses états.
• Une CMTD est dite périodique si sa période est supérieure à 1 2
• Une CMTD est dite apériodique si sa période est égale à 1
Non périodique car l’état 3 n’est pas périodique.
Le rebouclage sur cet état implique qu’on peut
1 3 revenir en une étape. Le cycle de longueur 1
– Exemple : CMTD apériodique implique que le PGCD de tous les cycles du
4 graphe est égal à 1
0,25 0,5 2 0,5

6 1 0,5 0,5
3 2
Périodique de période 3. En quittant l’un
0,5
7 0,25 4 5 1 3
quelconque des états, on ne peut y revenir qu’en
un nombre d’étapes multiple de 3. Sur cet
exemple, tous les cycles élémentaires sont de
4 longueur 3
– Propriété : la période d’une CMTD est égale au PGCD de la longueur de
tous les circuits du graphe associé

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : périodicité d’une CMTD • Classification des états transitoires / récurrents

– Exemples :
– Définition : soit fjj(n) la probabilité que le premier retour en j ait lieu n étapes
>

• Soit fjj, la probabilité de revenir en j après l’avoir quitté : fjj ≜ fjj

après l’avoir quitté
$ %
2
Non périodique. En quittant l’état 3, on peut y
revenir en 2 ou 3 étapes. On peut aussi > ?
1 3 constater que le graphe comporte deux circuits • Soit Mj, le « temps » moyen de retour en j : M ≜ n fjj
$ %

de longueur 3 et un circuit de longueur 2. Le ?

4 PGCD de 1 indique alors que la chaîne est
apériodique – Définition : un état j est dit :
• Transitoire si fjj < 1
• Récurrent si fjj = 1
– Récurrent nul si le temps moyen de retour est infini : Mj = ∞
– Récurrent non nul si le temps moyen de retour est fini : Mj < ∞
 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Classifications des états : bilan • Propriétés fondamentales :

– En fonction de leur périodicité

états – Tous les états d’une CMTD irréductible sont de même nature :
• Soit tous transitoires
• Soit tous récurrents nuls
• Soit tous récurrents non nuls
apériodiques périodiques
Si de plus les états sont périodiques, ils sont tous de même période
– En fonction de leur récurrence
états – Tous les états d’une CMTD irréductible finie sont récurrents non nuls
 Un état récurrent nul ne peut donc exister que dans une CMTD infinie.
Lorsque le chaîne est finie, elle ne peut comporter que des états transitoires
ou récurrents non nuls
transitoires récurrents

nuls non nuls

– Notons qu’un état apériodique et récurrent non nul est appelé « ergodique »

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : paramètres de performance d’une CMTD • Exemple :

1 2
– Sachant que la souris est en 2 initialement, combien
en moyenne de déplacements fera-t-elle pour revenir
>
– Définition : : soit fij(n) la probabilité d’aller de i à j en exactement n étapes
M n f22
$ %
(donc sans passer par l’état j de façon intermédiaire) dans la pièce 2 ?

$n 1 %
5 3 4
 Calcul de M2, temps moyen de retour en 2
?
fij pij et fij pik fkj pour n 2
$ %  Calcul de f22(n) probabilité d’aller de 2 à 2 en
0A exactement n étapes
1/2 1/2

– Cette équation exprime le fait que pour aller de l’état i à l’état j en

f22(1) = p22 = 0
1/2
1 2
exactement n étapes, il suffit d’aller en une étape à un état k différent de j,
puis d’aller à l’état j en exactement n-1 étapes f22(n) = p21 f12(n-1) + p24 f42(n-1) = 0,5 f12(n-1) + 0,5 f42(n-1) 1/4 1/4 1/2

... (Calculs !)
1/4
5 3 4

f22(1) = 0 1/4

f22(2) = ¼ 6

f22(n) = 1/(2n-1) pour n ≥ 3

 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret
• Exemple :
• Exemple (résultat) :
– Ou alors de façon intuitive, on constate qu’il y a : 1 2

• 1 seul chemin pour aller de 2 en 2 en 2 étapes :

>
2  1  2 : probabilité associée = ½ * ½ = ¼

M n f22
Donc f22(2) = ¼ $ %

n 1
5 3 4

$n 1%
• 2 chemins pour aller de 2 en 2 en 3 étapes :
>
1 1
M 2 & n
2  4  3  2 : probabilité associée = ½ * 1 * ¼ = 1/8

4 2
n 3
1/2 1/2
2  1  1  2 : probabilité associée = ½ * ½ * ½ = 1/8
1/2

>
Donc f22 = ¼
(3)

1 C
1 2

M & D
• 2 chemins pour aller de 2 en 2 en 4 étapes :
2 CD
1/4 1/4 1/2

n 3 x
2  4  3  1  2 : probabilité associée = ½ * 1 * ¼ * ½ = 1/16 5
1/4
3 4

...
2  1  1  1  2 : probabilité associée = ½ * ½ * ½ * ½ = 1/16 1/4

M 2,5
Donc f22(4) = 1/8
6
• 2 chemins pour aller de 2 en 2 en n étapes :
2  4  3  1 … 1  2 : probabilité associée = ½ * 1 * ¼ * 1/(2n-4) * ½ = 1/2n
2  1  1  1 … 1  2 : probabilité associée = ½ * 1/(2n-2) * ½ = 1/2n
Donc f22(n) = 1/2n-1

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret
• Exemple :
• Analyse : paramètres de performance d’une CMTD
– Sachant que la souris est initialement en 2, quelle est 1 2
– Définition : Soit fij la probabilité d’aller de i à j en un nombre quelconque
la probabilité pour qu’elle trouve un jour la sortie ?
>
d’étapes (soit la probabilité d’atteindre j en partant de i) :

fij ≜ fij
$ %
 Calcul de f26, la probabilité d’atteindre 6 depuis 2 en

n 1
un nombre quelconque d’étapes 5 3 4

f26 = p21 f16 + p24 f46 = 0,5 f16 + 0,5 f46

– En sommant toutes les équations du système d’équations précédent on
f16 = p11 f16 + p12 f26 = 0,5 f16 + 0,5 f26  f16 = f26
obtient la relation reliant les fij :
f46 = p43 f 36 = f36
> > > >
$n 1% $n 1%
1/2 1/2

fij fij fij & fij pij & pik fkj pij & pik fkj
$ % $ % $ % f36 = p36 + p31 f16 + p32 f26 + p35 f56 1/2

n 1 n 2 n 2 n 2
1 2
0A 0A = 0,25 + 0,25 f16 + 0,25 f26 + 0,25 f56 1/4 1/4 1/2

soit : fij pij & pik fkj

État 5 absorbant : f56 = 0 5
1/4
3 4

0A
f36 = 0,25 + 0,5 f26 1/4

Finalement : f26 = 0,5 f26 + 0,5 (0,25 + 0,5 f26)

– Interprétation : pour aller de i à j, soit on y va directement, soit on va à un 6

état k différent de j et il reste à aller de k à j f26 = 1/2

 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret
• Exemple :
• Analyse : paramètres de performance d’une CMTD
– Sachant que la souris est initialement en 2, combien de 1 2
– Définition : soit Rij le nombre moyen de passages par l’état j sachant que
fois passera-t-elle en moyenne par la pièce 3 avant de
>
l’on vient de l’état i :
sortir ou de tomber définitivement dans la pièce 5 ?
R ij ≜ n ProbaLexactement n passages par j | état initial iP  Calcul de R23, le nombre moyen de passages par l’état 5 3 4

? 3 sachant que l’on vient de l’état 2

f23
R 23
1 f33
– Si on note Pij(n) les probabilités intervenant dans cette expression, on a : Il faut donc calculer f23 et f33
Pij $n% Proba aller de i à j Proba aller de j à j R
Proba ne pas revenir en j
1/2 1/2

f23 = p21 f13 + p24 f43 = 0,5 f13 + 0,5 f43 1/2

fij $fjj %n 1 $1 fjj %

1 2

Soit Pij $n%

f13 = p11 f13 + p12 f23 = 0,5 f13 + 0,5 f23  f13 = f23 1/4 1/4 1/2
f43 = p43 = 1  f23 = 0,5 f13 + 0,5  f23 = 1
>
1/4

n $fjj %n 1
5 3 4

On en déduit R ij fij $1 fjj %

f33 = p31 f13 + p32 f23 = 0,25 f13 + 0,25 f23 = 0,5 1/4

n 1
1
6

fij R 23 2
Soit R ij 1 0,5
1 fjj

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : régime permanent • Exemple :

0,6 0,4 0
– Limite lorsque n tend vers l’infini du vecteur des probabilités π(n)

P 0,2 0,6 0,2

0,4 0,6 0,2
– Questions : cette limite existe-elle ? Si oui, comment la calculer ?

0 0,4 0,6
0,6 0,6
1 2 3
– Possibilité : calculer le vecteur π(n) = π(0) Pn et faire tendre n vers l’infini
• Diagonalisation de matrice … fastidieux … !!! -> autre possibilité 0,2 0,4

– Propriété : dans une CMTD irréductible et apériodique le vecteur π des – Cette chaîne est finie, irréductible et apériodique
probabilités limites π j = nlim
(n)
π existe toujours et est indépendant de la
→+∞ j
 tous les états sont récurrents non nuls
distribution des probabilités initiales π(0)
 La limite lorsque n tend vers l’infini de π(n) existe, est indépendante de π(0)
• Soit tous les états sont transitoires ou récurrents nuls (CMTD infinies) et πj=0

π πP
pour tout j ∈ E et est solution de

U
π & π & π! 1
• Soit tous les états sont récurrents non nuls (CMTD finie) et les πj sont solutions

π π pij pour tout j ∈ E $π π P sour forme matricielle%

du système :

∈) 1 1 1
π
π 1 4 2 4
∈)
• Dans le cas où les πj existent, on dit que la CMTD admet un régime stationnaire
 Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : régime permanent • Exemple :

0,25 0,5 2 0,5

– Lorsqu’une CMTD (finie) n’est pas irréductible, on s’intéressera :
6 1 0,5 0,5
3
• À la probabilité de tomber dans l’une de ses sous-chaînes absorbantes
irréductibles qu’elle contient 0,5
7 0,25 4 5
• À la probabilité stationnaire, sachant qu’on est tombé dans une de ces sous-
chaînes absorbantes, de se trouver dans un des états qu’elle comporte (à
condition que la sous chaîne soit apériodique)

– Partant de l’état initial 1, quelle est la probabilité de tomber dans la sous-

chaîne absorbante {6,7} ?
– Partant de l’état initial 1, quelle est la probabilité de tomber dans la sous-
chaîne absorbante {3,4,5} ?
– Sachant que l’on est tombé dans la sous-chaîne {3,4,5}, quelle est la
probabilité stationnaire d’être dans chacun de ces états ?

Les chaînes de Markov à temps discret Les chaînes de Markov à temps discret

• Analyse : régime permanent • Exemple : 2

– Lorsqu’une CMTD (finie et irréductible) est périodique, il n’y a pas de limite – Considérons la CMTD périodique suivante :

p pP
au vecteur des probabilités.

– Pourtant, le système V
1 3
p 1 admet une solution 0 1 0
i ∈ ) – La matrice de transition est : P 0 0 1
1 0 0
– Pj s’interprète alors comme la proportion de temps que la CMTD passe
dans l’état j
– Si le vecteur des probabilités initiales est π(0) = [1 0 0]
– On montre que : π(3k) = [1 0 0 ], π(3k+1) = [0 1 0 ], π(3k+2) = [0 0 1 ] pour tout k
– Pas de limite lorsque n tend vers l’infini de π(n), mais la résolution de p = p P
donne comme solution tout vecteur [p1, p2, p3] tel que p1 = p2 = p3
– En normalisant le solution pour avoir p1 + p2 + p3 = 1, on obtient qu’à long
terme, la CMTD passe 1/3 du temps dans chacun des états, mais en aucun cas
on ne peut dire que la probabilité stationnaire d’être dans un état est égale à 1/3
 Les chaînes de Markov à temps Les chaînes de Markov à temps
continu continu
• Processus stochastique X ∈ℕ à espace d’état discret et à temps • Définition : X$t% XY est une chaîne de Markov à temps continu ssi

j |X$t n 1 % in 1 , X$t n 2 % in 2 , . . . , X$t % i

continu
• E est l’espace d’états P X$t %

P X$t % j |X$t n 1 % in 1 ∀n et ∀t Z t Z. . . Z t
– De dimension finie ou infinie (mais dénombrable car discret)

E E
8 8

7 7
6 6

5 5
4 4

3 3
2 2

1 1
0 t 0 t
t0 t1 t2 t3 t4 t5
0 2 4 6 8 10 0 2 4 6 8 10

Processus stochastique à espace d’état discret et à temps continu Instants d’observation d’une CMTC

Les chaînes de Markov à temps

continu
• Caractérisation d’une CMTC
– L’évolution d’une CMTC peut se voir comme une répétition de deux phases :
• On reste un certain temps dans un état i (distribué selon une loi exponentielle)
• Lorsque l’on quitte un état, on choisit l’état vers lequel on sort ; or à l’instant où on
quitte un état, la destination ne dépend :
– Ni du temps passé dans l’état
– Ni du chemin par lequel on est arrivés dans l’état
– Définition :
• Une CMTC est un processus stochastique à espace d’états discret et à temps
continu tel que :
– Le temps passé dans un état i a une distribution exponentielle de taux µi
– Les transitions d’un état i vers un autre sont probabilistes. On note pij la probabilité de
se rendre dans l’état j en quittant l’état i

pij
j
µi i
pik k