Embed Size (px)
Citation preview
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ù
les observations se font de façon continue plu
t
t = …
tôt qu'à des moments discrets.
( ) ( ) { }
1 mutuellement exclusifs: 0,1, ,
L'analyse débute au temps 0 et le temps s'écoule de façon continue
= état du système au temps : 0,1, ,
Les points de changement d'éta
1. Formulati
é
t
t s
s
at
on
M M
t
X t t X t M
+
∈
…
…
( ) ( ) ( )�
21
1 2
1 2 3
0
, , sont des points aléatoires dans le temps
(pas nécessairement entiers):
0 ttX XX
t t
t t t
…
…�������
�����������
( )Considérons trois points consécutifs dans le temps où il y a eu changement d'états:
0 temps passé
( ) temps courant (actuel)
( 0) unités de temps dans le
r r
s s r
s t t t
≥
>
+ ≥
( ) ( ) { }
( ) ( ) ( )( )
futur.
Supposons que et que , avec , 0, , .
L'évaluation de
and 0, ,
est facilité par la propriété de Markov (i.e., sans mémoire).
X s i X r l i l M
P X s t j X s i X r l j M
= = ∈
+ = = = =
…
…
( ){ }
( ) ( ) ( )( ) ( ) ( )( ){ }
propriété de
Mar
Un pro
kov
cessus stochastique en temps continu ; 0 a la
si
and
, , 0, ; 0, ,
Définiti n
.
o
0
X t t
P X s t j X s i X r l P X s t j X s i
i j l M r s r t
≥
+ = = = = + = =
∀ ∈ ∀ ≥ > >…
( ){ }
( ) ( ) ( )( ) ( ) ( )( ){ }
propriété de
Mar
Un pro
kov
cessus stochastique en temps continu ; 0 a la
si
and
, , 0, ; 0, ,
Définiti n
.
o
0
X t t
P X s t j X s i X r l P X s t j X s i
i j l M r s r t
≥
+ = = = = + = =
∀ ∈ ∀ ≥ > >…
( ) ( )( ) probabilités de tranLes probabilités sont des
similaires à celles que nous avions e
sit
n temps discr
ion
et.
P X s t j X s i+ = =
( ) ( )( ) ( ) ( )( )Les sont puisqu'elles sont indépenprobabilit dantes de és de transition stat :ionna
r
0
i e
0
s s
P X s t j X s i P X t j X i s+ = = = = = ∀ >
( ) ( ) ( )( )( )
Par symétrie avec le cas discret
0
où dénot fonction de probabilité de transition en temps ce la ontinu
ij
ij
p t P X t j X i
p t
= = =
Le processus stochastique est alors u chaîne de Markov en temps cone ntinu
( ) ( )( ) ( ) ( )( )Les sont puisqu'elles sont indépenprobabilit dantes de és de transition stat :ionna
r
0
i e
0
s s
P X s t j X s i P X t j X i s+ = = = = = ∀ >
( ) ( ) ( )( )( )
Par symétrie avec le cas discret
0
où dénot fonction de probabilité de transition en temps ce la ontinu
ij
ij
p t P X t j X i
p t
= = =
( )0
L'hypothèse suivante est faite:
1 si lim
0 si ijt
i jp t
i j→
==
≠
2. Variables aléatoires importantes
Dans l'évolution du processus, dénotons
= variable aléatoire du temps passé dans l'état avant de se déplacer
2.1 Temps
vers un
dans un état
autre état
iT i
{ } 0, ,i M∀ ∈ …
( ) [ ]
Supposons que le processus entre dans l'état au temps .
Pour toute durée 0,
, .i
i t s
t
T t X t i t s s t
′ =
>
′ ′> ⇔ = ∀ ∈ +
( ) ( )La propriété de stationnarité des probabilités de transition entraîne que
.i i iP T s t T s P T t> + > = >
( ) [ ]
Supposons que le processus entre dans l'état au temps .
Pour toute durée 0,
, .i
i t s
t
T t X t i t s s t
′ =
>
′ ′> ⇔ = ∀ ∈ +
( ) ( )La propriété de stationnarité des probabilités de transition entraîne que
.i i iP T s t T s P T t> + > = >
Propriété particulière: la distribution du temps restant d'ici la prochaine sortie
de par le processus est la même quelle que soit le temps déja pass
La variable
é dans l'
est sa
é
n
ta
s
t .
.
mémoireiT
i i
La seule distribution de variable aléatoire continue ay
d
a
i
nt
st
cet
ribu
te propr
tion exp
iété
onent
est
ie
la lle.
Propriété particulière: la distribution du temps restant d'ici la prochaine sortie
de par le processus est la même quelle que soit le temps déja pass
La variable
é dans l'
est sa
é
n
ta
s
t .
.
mémoireiT
i i
La seule distribution de variable aléatoire continue ay
d
a
i
nt
st
cet
ribu
te propr
tion exp
iété
onent
est
ie
la lle.
( )
[ ]
: La possède un seul paramètre
1 0,
et sa moyenne (espéran
distribu
ce mathé
ti
matique) est
1 .
on eRappe xponentielle l i
i i
q t
i
i
i
T q
P T t e t
E Tq
−≤ = − ∀ >
=
Ce résultat nous permet de décrire une chaîne de Markov en temps continu
d'une façon équivalente comme suit:
11. La variable aléatoire a une distribution exponentielle avec moyenne de
2. Quand le processus quitte l'état , il passe à l'état avec une probabilité de
satisfaisant les conditions s
i
i
ij
Tq
i j
p
{ }
{ }0
uivantes:
0 0, ,
1 0, ,
3. Le prochain état visité après est indépendant du temps passé dans l'état
ii
M
ij
j
p i M
p i M
i i
=
= ∀ ∈
= ∀ ∈∑
…
…
Ce résultat nous permet de décrire une chaîne de Markov en temps continu
d'une façon équivalente comme suit:
Les jouent un rôle pour les chaînes de Markov en temps
continu analogue aux probabili
2.2 Intensité
tés de transiti
intensités de tr
on dans le cas des chaînes
de Markov disc
s de tran
ansitio
s ns
n
itio
iq
( )( )
{ }
( )( )
{ }
( )
0
0
rète:
10 lim 0, ,
0 lim , 0, , ;
où est la fonction de la probabilité de transition en temps continu
ii
i iit
ij
ij ij i ijt
ij
p tdq p i M
dt t
p tdq p q p i j M i j
dt t
p t
→
→
−= − = ∀ ∈
= = = ∀ ∈ ≠
…
…
( ) ( ) ( )( )( )
( )0
fonction de probabilité de transaction en temps
Par symétrie avec le cas discret
0
où dénote la
L'hypothèse suivante est faite:
1 si lim
cont
0 s
i
i
nu
ij
ij
ijt
p t P X t j X i
p t
i jp t
i j→
= = =
==
≠
et est décrit à l'item 2. de la définition équivalente de la chaîne de Markov
en temps continu.
ijp
{ }
{ }0
2. Quand le processus quitte l'état , il passe à l'état avec une probabilité de
satisfaisant les conditions suivantes:
0 0, ,
1 0, ,
ij
ii
M
ij
j
i j
p
p i M
p i M=
= ∀ ∈
= ∀ ∈∑
…
…
et est décrit à l'item 2. de la définition équivalente de la chaîne de Markov
en temps continu.
ijp
De plus, le est en fait le paramètre définissant la distribution exponentielle
de .i
i
q
T 11. La variable aléatoire a une distribution exponentielle avec moyenne de i
i
Tq
Les jouent un rôle pour les chaînes de Markov en temps
continu analogue aux probabili
2.2 Intensité
tés de transiti
intensités de tr
on dans le cas des chaînes
de Markov disc
s de tran
ansitio
s ns
n
itio
iq
( )( )
{ }
( )( )
{ }
( )
0
0
rète:
10 lim 0, ,
0 lim , 0, , ;
où est la fonction de la probabilité de transition en temps continu
ii
i iit
ij
ij ij i ijt
ij
p tdq p i M
dt t
p tdq p q p i j M i j
dt t
p t
→
→
−= − = ∀ ∈
= = = ∀ ∈ ≠
…
…
[ ][ ]
En particulier:
a)
où = moyenne du t
1= taux de transi
emps passé à chaq
tion à part
ue visite dans l'état .
ir de i
i
iE T
q i
i
E T=
b)
nombre moyen de fois que le processus passe de à par unité
= taux
de
de transition d
temps
e
ver
passé dans l'état
s ij
i j
q i j
i
=
0
Il s'ensuit que
.M
i ij
jj i
q q=≠
=∑
[ ][ ]
En particulier:
a)
où = moyenne du t
1= taux de transi
emps passé à chaq
tion à part
ue visite dans l'état .
ir de i
i
iE T
q i
i
E T=
b)
nombre moyen de fois que le processus passe de à par unité
= taux
de
de transition d
temps
e
ver
passé dans l'état
s ij
i j
q i j
i
=
Par analogie avec , est le paramètre de la distribution exponentielle de la
variable aléatoire definie comme suit:
Chaque fois que le processus atteint , le temps passé dans avant une transiti
i ijq q
i i
{ }
on
vers (cette transition étant la première) est une variable aléatoire
, 0, , , .ij
j
T i j M i j∀ ∈ ≠…
Les variables sont indépendantes, exponentielles avec paramètres dont les
1moyennes .
ij ij
ij
ij
T q
E Tq
=
Par analogie avec , est le paramètre de la distribution exponentielle de la
variable aléatoire definie comme suit:
Chaque fois que le processus atteint , le temps passé dans avant une transiti
i ijq q
i i
{ }
on
vers (cette transition étant la première) est une variable aléatoire
, 0, , , .ij
j
T i j M i j∀ ∈ ≠…
Les variables sont indépendantes, exponentielles avec paramètres dont les
1moyennes .
ij ij
ij
ij
T q
E Tq
=
( )Le temps passé dans l'état avant une transition i.e., est le minimum sur tous
les des .i
ij
i T
j i T≠
Quand la transition se produit, la probabilité qu'elle soit vers l'état est
.ij
ij
i
j
qp
q=
3. Probabilités à l'équilibre
( ) ( ) ( )0
Nous retrouvons des propriétes similaires à celles des chaînes de Markov discrètes.
Probabilités de tr satisfont les équations de Chapman-Kolmogoansition :
o
,
r vM
ij ik kj
k
p t p s p t s i=
= − ∀∑ { }0, ; 0j M s t∈ ≤ ≤…
( ) ( )1 2
1 2
Les états et si , >0 tels que
c
ommunique
n
0 et 0
t
ij ji
i j t t
p t p t
∃
> >
Tous les états qui communiquent forment cl une asse
( ) { }
Si tous les états forment une seule classe, alors la chaîne de Markov est
(nous allons faire cette hypothèse par la suite dans notre analyse):
0
irréductible
0; , 0, , .
ijp t t i j M> ∀ > ∈ …
( ):
lim
Probabilités à
0, ,
existe et est indépendante de l'état initial de la chaîn
l'équilibre (probabilité stationnaire) de la chaîne de Ma
e de Marko
r ov
v
k
ij jt
p t j Mπ→∞
= = …
( ) { }
Si tous les états forment une seule classe, alors la chaîne de Markov est
(nous allons faire cette hypothèse par la suite dans notre analyse):
0
irréductible
0; , 0, , .
ijp t t i j M> ∀ > ∈ …
( )0
Les probabilités à l'équilibre satisfont les relations suivantes
0, , ; 0M
j i ij
i
p t j M tπ π=
= = ∀ ≥∑ …
{ }0
0
MAIS les suivantes donne un système d'équations plus
facile à résoudre pour identifier les :
équations d'équilib
0, ,
re
1
j
M
j j i ij
ii j
M
j
j
q q j M
π
π π
π
=≠
=
= ∈
=
∑
∑
…
lim 0n
ij jn
p π→∞
= >
0
M
j i ij
i
pπ π=
=∑
{ }0
0
MAIS les suivantes donne un système d'équations plus
facile à résoudre pour identifier les :
équations d'équilib
0, ,
re
1
j
M
j j i ij
ii j
M
j
j
q q j M
π
π π
π
=≠
=
= ∈
=
∑
∑
…
Interprétation intuitive:
puisque : probabilité (à l'équilibre) que le processus soit dans l'état
: taux auquel le proc
: ta
essus
ux de
part
transition po
de
ur s
j
j
j jq
j
q
j
π
π
ortir de l'état étant donné que le
processus est dans l'état
: taux de passage de l'état à l'état
puisque : taux de transition de l'état à l'état
i ij
ij
j
j
q i j
q i
π
0
: taux de pas
étant donné q
sage à l'état
ue le
quelque soit l'état dans lequel se trouve
le process
processus est dans l'éta
s
t
u
M
i ij
ii j
q j i
j
i
π=≠
∑
taux
Donc
de
il s'en
départ d
suit que
= taux d 'ae r riv ée à j j
Interprétation intuitive:
: taux auquel le processus part de
puisque : probabilité (à l'équilibre) que le processus soit dans l'état
: taux de transition pour s
j j
j
j
q j
j
q
π
π
ortir de l'état étant donné que le
processus est dans l'état
: taux de passage de l'état à l'état
puisque : taux de transition de l'état à l'état
i ij
ij
j
j
q i j
q i
π
0
étant donné que le
processus est dans l'état
: taux de passage à l'état quelque soit l'état dans lequel se trouve
le processus
M
i ij
ii j
j
i
q iπ=≠
∑
taux
Donc
de
il s'en
départ d
suit que
e = taux d'ar rivée àj j
Nous utilisons donc par la suite ces
É Q UA TION S DE BAL ANCE
ÉQUATIONS DE BA LANCE
{ }0
0
Équations d'équilibre
0, ,
1
M
j j i ij
ii j
M
j
j
q q j Mπ π
π
=≠
=
= ∈
=
∑
∑
…
0
Intensités de transiti n
.
oM
j ji
ij i
q q=≠
=∑
{ }
{ }
0 0 0
0 0
0
Remplaçons les valeurs des dans les équations d'équilibre:
0, ,
Donc les équations de balance deviennent
0, ,
1
j
M M M
j j i ij j ji i ij
i i ii j i j i j
M M
j ji i ij
i ii j i j
M
j
j
q
q q q q j M
q q j M
π π π π
π π
π
= = =≠ ≠ ≠
= =≠ ≠
=
= ⇔ = ∈
= ∈
=
∑ ∑ ∑
∑ ∑
∑
…
…
taux de départ de = taux d'arrivée à j j
: Deux machines identiques fonctionnent de façon continue à moins d'être
brisés.
Un réparateur disponible au besoin pour réparer les machines.
Temps de réparation suit une d
Exe
is
mple
tribution exponentielle avec une moyenne de
0.5 journée.
Une fois réparée, le temps d'utilisation d'une machine avant son prochain bris
suit une distribution exponentielle de moyenne de 1 journée.
Nous supposons que ces distributions sont indépendantes.
( )
Considérons le processus aléatoire défini en terme du nombre de machines en
panne. La variable aléatoire
nombre de machines en panne au temps .X t t′ ′=
( ) { }États de : 0,1,2X t′
( ){ }
Le temps de réparation suivant une distribution exponentielle et le temps jusqu'au
prochain bris suivant également une distribution exponentielle entraî
; 0 est une chaîne de
nent q
Marko
ue
v en temX t t′ ′ ≥ ps continu
( ) nombre de machines en panne au temps .X t t′ ′=
( ) { }États de : 0,1,2X t′
( ){ }
Le temps de réparation suivant une distribution exponentielle et le temps jusqu'au
prochain bris suivant également une distribution exponentielle entraî
; 0 est une chaîne de
nent q
Marko
ue
v en temX t t′ ′ ≥ ps continu
Temps de réparation suit une distribution exponentielle avec une moyenne de
0.5 journée.
1Taux de réparation = 2 machines par jour
0.5Une fois réparée, le temps d'utilisation d'une machine avant son pr
↓
=
ochain bris
suit une distribution exponentielle de moyenne de 1 journée.
1Taux de bris d'une machine = 1 jour
1
↓
=
02
20
:
Hypothèses:
Les deux machines ne peuvent se briser au même moment: 0
Le réparateur ne répar
Taux de transition ( )
e qu'une seule machine
entre les
à la fois
états
: 0
ij
q
q
q
=
=
Temps de réparation suit une distribution exponentielle avec une moyenne de
0.5 journée
1 taux de réparation = 2 machines par jour
0.5⇒ =
Le temps d'utilisation d'une machine avant son prochain bris suit une distribution
exponentielle de moyenne de 1 journée
1 taux de bris = 1 jour
1⇒ =
( ) ( )Au moment où les deux machines fonctionnent, alors
taux de bris = taux de bris de machine 1 + taux de bris de machine 1 = 1 + 1 = 2
02
20
:
Hypothèses:
Les deux machines ne peuvent se briser au même moment: 0
Le réparateur ne répar
Taux de transition ( )
e qu'une seule machine
entre les
à la fois
états
: 0
ij
q
q
q
=
=
1Taux de réparation = 2 machines par jour
0.5=
1Taux de bris d'une machine = 1 jour
1=
Taux de bris si deux machines sont en marche = 2
0 1 2
01 2q = 12 1q =
21 2q =10 2q =
( ) ( )0 01 1 10 0 1
1 10 12 0 01 2 21 1 0 2 1 0 2
2 21 1 12 2 1
0 1 2
État 0: 2 2
État 1: 2 1 2 2 3 2 2
État 2: 2
1
q q
q q q q
q q
π π π π
π π π π π π π π π
π π π π
π π π
= ⇔ =
+ = + ⇔ + = + ⇔ = +
= ⇔ =
+ + +
0 1 2
01 2q = 12 1q =
21 2q =10 2q =
{ }0 0
0
ÉQUATIONS DE BALANCERappe :
0, ,
1
lM M
j ji i ij
i ii j i j
M
j
j
q q j Mπ π
π
= =≠ ≠
=
= ∈
=
∑ ∑
∑
… taux de départ de = taux d'arrivée à j j
0 1 2
01 2q = 12 1q =
21 2q =10 2q =
0 1 0 1
2 1 2 1 1 1 1 1 1
0 1 2 0 1 2
2 2
2 0.5 0.5 1 2.5 1 0.4
1 1
π π π π
π π π π π π π π π
π π π π π π
= =
= ⇔ = ⇔ + + = ⇔ = ⇔ = + + = + + =
( ) ( )0 1 2
Donc
, , = 0.4,0.4,0.2π π π
( ) ( )0 01 1 10 0 1
1 10 12 0 01 2 21 1 0 2 1 0 2
2 21 1 12 2 1
0 1 2
État 0: 2 2
État 1: 2 1 2 2 3 2 2
État 2: 2
1
q q
q q q q
q q
π π π π
π π π π π π π π π
π π π π
π π π
= ⇔ =
+ = + ⇔ + = + ⇔ = +
= ⇔ =
+ + +
0 1 2
01 2q = 12 1q =
21 2q =10 2q =
( ) ( )0 1 2
Donc
, , = 0.4,0.4,0.2π π π
( )( )( )
0
1
2
aucune machine brisée 0.4
une machine brisée 0.4
P
robabilités à
l
2 machines brisées 0.2
'équilibre
P
P
P
π
π
π
= =
= =
= =
0 1 2
(espérance mathématique)
Nombre moy
0 1 2 0 0.4 0
en de machines brisée
.4
0.8π π π⋅ + ⋅ + ⋅ = + + =
