4 Chaine Markov Continu

Embed Size (px)

Citation preview

  • 8/18/2019 4 Chaine Markov Continu

    1/26

     

    Modèles stochastiques

    Chaîne de Markov en temps continu

     

  • 8/18/2019 4 Chaine Markov Continu

    2/26

     

    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 ont de a!on continue plu

    t  =   K 

    t"t #u$% des moments discrets.

    ( ) ( ) { }

      1 mutuellement e&clusis' 0,1, ,

    $analyse débute au temps 0 et le temps s$écoule de a!on continue

    état du syst*me au temps ' 0,1, ,

    es points de chan+ement d$éta

    1. ormulati

    é

    t

    t s

    s

    at

    on

     M M 

     X t t X t M 

    +

    ( ) ( )   ( )

    {-1

    1 -

    1 -

    0

      , , sont des points aléatoires dans le temps

    (pas nécessairement entiers)'

      0t t  X    X  X 

    t t 

    t t t 

    K 1 44 2 4 43   1 4 4 4 4 2 4 4 4 4 3

  • 8/18/2019 4 Chaine Markov Continu

    3/26

     

    ( )

    /onsidérons trois points consécutis dans le temps où il y a eu chan+ement d$états'

      0 temps passé

      ( ) temps courant (actuel)

      ( 0) unités de temps dans le

    r r 

     s s r 

     s t t t 

    >

    + ≥

    ( ) ( ) { }

    ( ) ( ) ( )( )

     utur.upposons #ue et #ue , avec , 0, , .

    $évaluation de

     and 0, ,

    est acilité 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é deMar n pro

    kovcessus stochasti#ue en temps continu 2 0 a la

    si

     and

    , , 0, 2 0, ,

    Déiniti 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  

    + = = = = + = =

    ∀ ∈ ∀ ≥ > >K 

  • 8/18/2019 4 Chaine Markov Continu

    4/26

     

    ( ){ }

    ( ) ( ) ( )( )   ( ) ( )( )

    { }

     propriété de

    Mar 

    n pro

    kov

    cessus stochasti#ue en temps continu 2 0 a la

    si

     and

    , , 0, 2 0, ,

    Déiniti 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  

    + = = = = + = =

    ∀ ∈ ∀ ≥ > >K 

    ( ) ( )( )  probabilités de tranes probabilités sont dessimilaires % celles #ue nous avions e

    sit

    n temps discr 

    ion

    et.

     P X s t j X s i+ = =

    ( ) ( )( )   ( ) ( )( )

    es sont puis#u$elles sont indépen probabilit dantes deés de transition stat 'ionna

     

      0

    i e

    0

    s   s

     P X s t j X s i P X t j X i s+ = = = = = ∀ >

    ( ) ( ) ( )( )

    ( )

    3ar symétrie avec le cas discret

    0

    où dénot onction de probabilité de transition en temps ce la ontinu

    ij

    ij

     p t P X t j X i

     p t 

    = = =

    (e processus stochasti#ue est alors u chaîne de Markov en temps cone ntinu

  • 8/18/2019 4 Chaine Markov Continu

    5/26

     

    ( ) ( )( )   ( ) ( )( )

    es sont puis#u$elles sont indépen probabilit dantes deés de transition stat 'ionna

     

      0

    i e

    0

    s   s

     P X s t j X s i P X t j X i s+ = = = = = ∀ >

    ( ) ( ) ( )( )

    ( )

    3ar symétrie avec le cas discret

    0

    où dénot onction de probabilité de transition en temps ce la ontinu

    ij

    ij

     p t P X t j X i

     p t 

    = = =

    ( )0

    $hypoth*se suivante est aite'1 si

    lim0 siijt 

    i j p t 

    i j→

    == 

  • 8/18/2019 4 Chaine Markov Continu

    6/26

     

    -. 4ariables aléatoires importantes 

    Dans l$évolution du processus, dénotons

    variable aléatoire du temps passé dans l$état avant de se déplacer

    -.1 5emps

    vers un

    dans un état

    autre état

     

    iT i

    { }  0, ,i M ∀ ∈   K 

    ( )   [ ]

    upposons #ue le processus entre dans l$état au temps .

    3our toute durée 0,

    , .i

    i t s

    T t X t i t s s t  

    ′ =

    >

    ′ ′> ⇔ = ∀ ∈ +

    ( )   ( )

    a propriété de stationnarité des probabilités de transition entraîne #ue

    .i i i P T s t T s P T t > + > = >

  • 8/18/2019 4 Chaine Markov Continu

    7/26 

    ( )   [ ]

    upposons #ue le processus entre dans l$état au temps .

    3our toute durée 0,

    , .i

    i t s

    T t X t i t s s t  

    ′ =

    >

    ′ ′> ⇔ = ∀ ∈ +

    ( )   ( )

    a propriété de stationnarité des probabilités de transition entraîne #ue

    .i i i

     P T s t T s P T t > + > = >

    3ropriété particuli*re' la distribution du temps restant d$ici la prochaine sortiede par le processus est la m6me #uelle #ue soit le temps dé7a pass

    a variable

    é dans l$

     est sa

    é

    n

    ta

    s

    t .

    .

     

    mémoirei

    i i

     a seule distribution de variable aléatoire continue ay

    d

    a

    i

    nt

    st

     cet

    ribu

    te propr 

    tion e&p

    iété

    onent

    est

    ie

     

    la lle.

  • 8/18/2019 4 Chaine Markov Continu

    8/26 

    3ropriété particuli*re' la distribution du temps restant d$ici la prochaine sortie

    de par le processus est la m6me #uelle #ue soit le temps dé7a pass

    a variable

    é dans l$

     est sa

    é

    n

    ta

    s

    t .

    .

     

    mémoirei

    i i

     a seule distribution de variable aléatoire continue ay

    d

    a

    i

    nt

    st

     cet

    ribu

    te propr 

    tion e&p

    iété

    onent

    est

    ie

     

    la lle.

    ( )

    [ ]

    ' a poss*de un seul param*tre

    1 0,et sa moyenne (espéran

    distribu

    ce mathé

    ti

    mati#ue) est

    1  .

    on e8appe &ponentiellel  i

    i i

    q t 

    i

    i

    i

    T q

     P T t e t 

     E T q

    ≤ = − ∀ >

    =

    /e résultat nous permet de décrire une chaîne de Markov en temps continu

    d$une a!on é#uivalente comme suit'

  • 8/18/2019 4 Chaine Markov Continu

    9/26 

    11. (a variable aléatoire a une distribution e&ponentielle avec moyenne de

    -. 9uand le processus #uitte l$état , il passe % l$état avec une probabilité de

      satisaisant les conditions s

    i

    i

    ij

    T q

    i j

     p

    { }

    { }0

    uivantes'

      0 0, ,

    1 0, ,

    . (e 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

    =

    = ∀ ∈

    = ∀ ∈∑

    /e résultat nous permet de décrire une chaîne de Markov en temps continu

    d$une a!on é#uivalente comme suit'

  • 8/18/2019 4 Chaine Markov Continu

    10/26

     

    es 7ouent un r"le pour les chaînes de Markov en temps

    continu analo+ue au& probabili

    -.- :ntensité

    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, , 2

     où est la onction de la probabilité de transition en temps continu

    ii

    i iit 

    ij

    ij ij i ijt 

    ij

     p t d q p i M  

    dt t 

     p t d q p q p i j M i j

    dt t 

     p t 

    −= − = ∀ ∈

    = = = ∀ ∈ ≠

    ( ) ( ) ( )( )

    ( )

    ( )0

    onction de probabilité de transaction en temps

    3ar symétrie avec le cas discret

    0

    où dénote la

    $hypoth*se suivante est aite'1 si

    lim

    cont

    0 s

    i

    i

    nu

    ij

    ij

    ijt 

     p t P X t j X i

     p t 

    i j p t 

    i j→

    = = =

    == 

    et est décrit % l$item -. de la déinition é#uivalente de la chaîne de Markov

    en temps continu.

    ij p

    { }

    { }0

    -. 9uand le processus #uitte l$état , il passe % l$état avec une probabilité de

      satisaisant les conditions suivantes'

      0 0, ,

    1 0, ,

    ij

    ii

     M 

    ij

     j

    i j

     p

     p i M 

     p i M =

    = ∀ ∈

    = ∀ ∈∑

  • 8/18/2019 4 Chaine Markov Continu

    11/26

     

    et est décrit % l$item -. de la déinition é#uivalente de la chaîne de Markov

    en temps continu.

    ij p

    De plus, le est en ait le param*tre déinissant la distribution e&ponentielle

    de .i

    i

    q

    T  11. (a variable aléatoire a une distribution e&ponentielle avec moyenne dei

    i

    T q

    es 7ouent un r"le pour les chaînes de Markov en temps

    continu analo+ue au& probabili

    -.- :ntensité

    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, , 2

     où est la onction de la probabilité de transition en temps continu

    ii

    i iit 

    ij

    ij ij i ijt 

    ij

     p t d q p i M  

    dt t 

     p t d q p q p i j M i j

    dt t 

     p t 

    −= − = ∀ ∈

    = = = ∀ ∈ ≠

  • 8/18/2019 4 Chaine Markov Continu

    12/26

     

    [ ]

    [ ]

    ;n particulier'

    a)

    où moyenne du t

    1 tau& de transi

    emps passé % cha#

    tion % part

    ue visite dans l$état .

    ir dei

    i

    i E T 

    q i

    i

     E T =

     b)

    nombre moyen de ois #ue le processus passe de % par unité

    tau&

    de

    de transition d

      temps

    e

     

    ver 

     passé dans l$état

    sij

    i j

    q i j

    i

    =

    0

    :l s$ensuit #ue

    . M 

    i ij

     j j i

    q q=

    = ∑

  • 8/18/2019 4 Chaine Markov Continu

    13/26

     

    [ ]

    [ ]

    ;n particulier'

    a)

    où moyenne du t

    1 tau& de transi

    emps passé % cha#

    tion % part

    ue visite dans l$état .

    ir dei

    i

    i E T 

    q i

    i

     E T =

     b)

    nombre moyen de ois #ue le processus passe de % par unité

    tau&

    de

    de transition d

      temps

    e

     

    ver 

     passé dans l$état

    sij

    i j

    q i j

    i

    =

    3ar analo+ie avec , est le param*tre de la distribution e&ponentielle de lavariable aléatoire deinie comme suit'

    /ha#ue ois #ue 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∀ ∈ ≠K 

    es variables sont indépendantes, e&ponentielles avec param*tres dont les

    1moyennes .

    ij ij

    ij

    ij

    T q

     E T 

    q

      =

  • 8/18/2019 4 Chaine Markov Continu

    14/26

     

    3ar analo+ie avec , est le param*tre de la distribution e&ponentielle de la

    variable aléatoire deinie comme suit'

    /ha#ue ois #ue 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∀ ∈ ≠K 

    es variables sont indépendantes, e&ponentielles avec param*tres dont les

    1moyennes .

    ij ij

    ij

    ij

    T q

     E T  q   = ( )e temps passé dans l$état avant une transition i.e., est le minimum sur tous

    les des .i

    ij

    i T 

     j i T ≠

    9uand la transition se produit, la probabilité #u$elle soit vers l$état est  .ijij

    i

     jq

     pq

    =

  • 8/18/2019 4 Chaine Markov Continu

    15/26

     

    . 3robabilités % l$é#uilibre 

    ( ) ( ) ( )0

     olmo+oansition '

     

    o

    ,

    r v M 

    ij ik kj

     p t p s p t s i=

    = − ∀∑   { }0, 2 0 j M s t ∈ ≤ ≤K 

    ( ) ( )1 -

    1 -

    es états et si , ?0 tels #ue

     

    c

     

    ommuni#ue

     

    n

      0 et 0

    t

     ij ji

    i j t t  

     p t p t 

    > >

    5ous les états #ui communi#uent orment clune asse

    ( ) { }

    i tous les états orment une seule classe, alors la chaîne de Markov est

    (nous allons aire cette hypoth*se par la suite dans notre analyse)'  0irréductible

    02 , 0, , .

     

    ij p t t i j M > ∀ > ∈   K 

  • 8/18/2019 4 Chaine Markov Continu

    16/26

     

    ( )

    '  lim3robabilités %

    0, ,

    e&iste et est indépendante de l$état initial de la chaîn

    l$é#uilibre (probabilité stationnaire) de la chaîne de Ma

    e de Marko

    r ov

    v

    ij jt 

     p t j M π  →∞

    = =   K 

    ( ) { }

    i tous les états orment une seule classe, alors la chaîne de Markov est

    (nous allons aire cette hypoth*se par la suite dans notre analyse)'

      0

    irréductible

    02 , 0, , .

     

    ij p t t i j M > ∀ > ∈   K 

    ( )0

    es probabilités % l$é#uilibre satisont les relations suivantes  0, , 2 0

     M 

     j i ij

    i

     p t j M t π π  =

    = = ∀ ≥∑   K 

    { }0

    0

    M@: les suivantes donne un syst*me d$é#uations plus

    acile % résoudre pour identiier les '

     

    é#uations d$é#uilib

      0, ,

    re

    1

     j

     M 

     j j i ij

    ii j

     M 

     j

     j

    q q j M  

    π  

    π π  

    π  

    =≠

    =

    = ∈

    =

    lim 0nij j

    n p   π  

    →∞= >

    0

     M 

     j i ij

    i

     pπ π  =

    = ∑

  • 8/18/2019 4 Chaine Markov Continu

    17/26

     

    { }0

    0

    M@: les suivantes donne un syst*me d$é#uations plus

    acile % résoudre pour identiier les '

     

    é#uations d$é#uilib

      0, ,

    re

    1

     j

     M 

     j j i ij

    ii j

     M 

     j

     j

    q q j M  

    π  

    π π  

    π  

    =≠

    =

    = ∈

    =

    :nterprétation intuitive'

      puis#ue ' probabilité (% l$é#uilibre) #ue le processus soit dans l$état

    ' tau& au#uel le proc

      ' ta

    essus

    u& de

     part

    transition po

     de

    ur s

     j

     j

     j jq

     j

    q

     j

    π  

    π  

    ortir de l$état étant donné #ue le

     processus est dans l$état' tau& de passa+e de l$état % l$état

     puis#ue ' tau& de transition de l$état % l$état

    i ij

    ij

     j

     jq i j

    q i

    π  

    0

    ' tau& de pas

    étant donné #

    sa+e % l$état

    ue le

    #uel#ue soit l$état dans le#uel se trouve

    le process

      processus est dans l$éta

    s

    t

    u

     M 

    i ij

    ii j

    q j i

     j

    i

    π  

    =≠

    tau&

    Donc

     de

    il s$en

    départ d

    suit #ue

      tau& d  $ae r   rivée % j   j

  • 8/18/2019 4 Chaine Markov Continu

    18/26

     

    :nterprétation intuitive'

    ' tau& au#uel le processus part de

     puis#ue ' probabilité (% l$é#uilibre) #ue le processus soit dans l$état

    ' tau& de transition pour s

     j j

     j

     j

    q j

     j

    q

    π  

    π  

    ortir de l$état étant donné #ue le processus est dans l$état

    ' tau& de passa+e de l$état % l$état

     puis#ue ' tau& de transition de l$état % l$état

    i ij

    ij

     j j

    q i j

    q i

    π  

    0

    étant donné #ue le

     processus est dans l$état

    ' tau& de passa+e % l$état #uel#ue soit l$état dans le#uel se trouve

    le processus

     M 

    i ij

    ii j

     j

    i

    q iπ  =≠

    tau&

    Donc

     de

    il s$en

    départ d

    suit #ue

      e tau& d$ar   rivée  % j j

     

  • 8/18/2019 4 Chaine Markov Continu

    19/26

     

    A9@5:B

  • 8/18/2019 4 Chaine Markov Continu

    20/26

     

    ' Deu& machines identi#ues onctionnent de a!on continue % moins d$6tre

     brisés.

      n réparateur disponible au besoin pour réparer les machines.

    5emps de réparation suit une d

    ;&e

    is

    mple

    tribution e&ponentielle avec une moyenne de

    0. 7ournée.

    ne ois réparée, le temps d$utilisation d$une machine avant son prochain bris

    suit une distribution e&ponentielle de moyenne de 1 7ournée.

     

  • 8/18/2019 4 Chaine Markov Continu

    21/26

     

    ( )  nombre de machines en panne au temps . X t t ′ ′=

    ( ) { }Atats de ' 0,1,- X t ′

    ( ){ }

    e temps de réparation suivant une distribution e&ponentielle et le temps 7us#u$au

     prochain bris suivant é+alement une distribution e&ponentielle entraî

    2 0 est une chaîne de

    nent #

     Marko

    ue

    v en tem X t t ′ ′ ≥  ps continu

    5emps de réparation suit une distribution e&ponentielle avec une moyenne de

    0. 7ournée. 

    15au& de réparation - machines par 7our 

    0.

    ne ois réparée, le temps d$utilisation d$une machine avant son pr 

    =

    ochain brissuit une distribution e&ponentielle de moyenne de 1 7ournée.

    15au& de bris d$une machine 1 7our 

    1

    =

    '5au& de transition ( ) entre les étatsq

  • 8/18/2019 4 Chaine Markov Continu

    22/26

     

    0-

    -0

    '

    Eypoth*ses'

    es deu& machines ne peuvent se briser au m6me moment' 0

    e réparateur ne répar 

    5au& de transition ( )

    e #u$une seule machine

    entre les

    % la ois

    états

    ' 0

    ij

    q

    q

    q

    =

    =

    5emps de réparation suit une distribution e&ponentielle avec une moyenne de

    0. 7ournée

    1  tau& de réparation - machines par 7our 

    0.⇒ =

    e temps d$utilisation d$une machine avant son prochain bris suit une distribution

    e&ponentielle de moyenne de 1 7ournée

    1  tau& de bris 1 7our 

    1

    ⇒ =

    ( ) ( )

    @u moment où les deu& machines onctionnent, alors

    tau& de bris tau& de bris de machine 1 F tau& de bris de machine 1 1 F 1 -

  • 8/18/2019 4 Chaine Markov Continu

    23/26

     

    0-

    -0

    '

    Eypoth*ses'

    es deu& machines ne peuvent se briser au m6me moment' 0

    e réparateur ne répar 

    5au& de transition ( )

    e #u$une seule machine

    entre les

    % la ois

    états

    ' 0

    ij

    q

    q

    q

    =

    =

    15au& de réparation - machines par 7our 

    0. =

    15au& de bris d$une machine 1 7our 

    1=

    5au& de bris si deu& machines sont en marche -

    0 1 -

    01 -q   = 1- 1q   =

    -1 -q   =10 -q   =

  • 8/18/2019 4 Chaine Markov Continu

    24/26

     

    ( ) ( )

    0 01 1 10 0 1

    1 10 1- 0 01 - -1 1 0 - 1 0 -

    - -1 1 1- - 1

    0 1 -

    Atat 0' - -

    Atat 1' - 1 - - - -

    Atat -' -1

    q q

    q q q q

    q q

    π π π π    

    π π π π π π π π π  

    π π π π    

    π π π  

    = ⇔ =

    + = + ⇔ + = + ⇔ = +

    = ⇔ =+ + +

    0 1 -

    01 -q   = 1- 1q   =

    -1 -q   =10 -q   =

    { }0 0

    0

    A9@5:B

  • 8/18/2019 4 Chaine Markov Continu

    25/26

     

    0 1 -

    01 -q   = 1- 1q   =

    -1 -q   =10 -q   =

    0 1 0 1

    - 1 - 1 1 1 1 1 1

    0 1 - 0 1 -

    - -

    - 0. 0. 1 -. 1 0.G

    1 1

    π π π π    

    π π π π π π π π π    

    π π π π π π    

    = =

    = ⇔ = ⇔ + + = ⇔ = ⇔ = + + = + + =  

    ( ) ( )0 1 -

    Donc

      , , 0.G,0.G,0.-π π π  

    ( ) ( )

    0 01 1 10 0 1

    1 10 1- 0 01 - -1 1 0 - 1 0 -

    - -1 1 1- - 1

    0 1 -

    Atat 0' - -

    Atat 1' - 1 - - - -

    Atat -' -

    1

    q q

    q q q q

    q q

    π π π π    

    π π π π π π π π π  

    π π π π    

    π π π  

    = ⇔ =

    + = + ⇔ + = + ⇔ = +

    = ⇔ =

    + + +

  • 8/18/2019 4 Chaine Markov Continu

    26/26

    0 1 -

    01 -q   = 1- 1q   =

    -1 -q   =10 -q   =

    ( ) ( )0 1 -

    Donc

      , , 0.G,0.G,0.-π π π  

    ( )( )

    ( )

    0

    1

    -

      aucune machine brisée 0.G  une machine brisée 0.G

     

    3

     

    robabilités %

     

    l

      - machines brisées 0.-

    $é#uilibre

     P 

     P 

     P 

    π  

    π  

    π  

    = == =

    = =

    0 1 -

    (espérance mathémati#ue)