Chain e Markov

  • View
    215

  • Download
    0

Embed Size (px)

Text of Chain e Markov

  • 7/31/2019 Chain e Markov

    1/32

    Mthodes nonlinaires et stochastiques de la recherche

    oprationnelle

    Marco Dozzi

    2 aot 2004

  • 7/31/2019 Chain e Markov

    2/32

    2

  • 7/31/2019 Chain e Markov

    3/32

    Table des matires

    II Chanes de Markov et files dattente 5

    II.1 Rappel sur les probabilits conditionnelles et le modle dIsing . . . . . . . . 5II.2 Les chanes de Markov temps discret . . . . . . . . . . . . . . . . . . . . . 7

    II.2.1 Dfinition, probabilits de transition et loi stationnaire . . . . . . . . 8II.2.2 Exemples en gestion, conomie et imagerie . . . . . . . . . . . . . . . 12II.3 Les chanes de Markov temps continu . . . . . . . . . . . . . . . . . . . . . 15

    II.3.1 Intensits de transition et modles linaires . . . . . . . . . . . . . . 16II.3.2 Le processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 17II.3.3 La loi stationnaire dans le cas o lensemble des tats possibles est fini 19II.3.4 Un exemple en gestion . . . . . . . . . . . . . . . . . . . . . . . . . . 20II.3.5 Les files dattente M/M/s/R . . . . . . . . . . . . . . . . . . . . . . . 22

    II.4 Simulation de files dattente . . . . . . . . . . . . . . . . . . . . . . . . . . . 24II.4.1 Simulation dune variable alatoire de loi donne . . . . . . . . . . . 25II.4.2 Gnrateur de nombres pseudo-alatoires . . . . . . . . . . . . . . . 27

    II.4.3 Un exemple de gestion . . . . . . . . . . . . . . . . . . . . . . . . . . 31II.5 Remarques bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    3

  • 7/31/2019 Chain e Markov

    4/32

    4 TABLE DES MATIRES

  • 7/31/2019 Chain e Markov

    5/32

    Chapitre II

    Chanes de Markov et files dattente

    Dans ce chapitre des mthodes probabilistes et statistiques de la recherche opration-nelle sont traites. Il sagit, par exemple, danalyser lvolution temporelle du march dunproduit, ou de reconstituer une image ou danalyser une file dattente avec des arrives etdes dparts alatoires. Nous effectuons ces analyses dans le cadre des chanes de Markov entemps discret (section II.2) ou en temps continu (section II.3). Plus gnralement ce cadrepermet danalyser des systmes dont lvolution temporelle comporte des incertitudes dues des facteurs qui ne sont pas entirement sous contrle. Lanalyse se fait en termes devariables alatoires ou de vecteurs alatoires et de leur lois qui dcrivent le comportementfutur du systme en fonction des paramtres observs. Il est assez frquent que de telssystmes trouvent, aprs un certain temps, un tat dquilibre, appel tat stationnaire quireste valable jusqu ce que des facteurs extrieurs provoquent nouveau un dsquilibre.En section II.2 et II.3 nous donnons des formules explicites qui permettent de trouver ceslois stationnaires et qui sont applicables des systmes peu complexes. Pour des systmesplus complexes les analyses mathmatiquement rigoureuses sont souvent difficiles effec-tuer et dpassent le cadre de ce cours. Parfois on prfre simuler lvolution du systme surordinateur et obtenir des prvisions sur le comportement futur de cette faon. Pour cetteraison nous traitons en section II.4 la simulation de variables alatoires.

    Comme la notion de probabilit conditionnelle est fondamentale pour les chanes deMarkov, nous commenons ce chapitre par un rappel de ces notions.

    II.1 Rappel sur les probabilits conditionnelles et le modle

    dIsingDfinition. La probabilit conditionnelle de B donn A, note P(B|A), est donne par :

    P(B|A) = P(B A)P(A)

    si P(A) = 0.

    B est indpendant de A si P(B|A) = P(B).

    Exemple :A lensemble des fumeurs dune population note

    B lensemble des personnes souffrant dun cancer des poumons de P(B|A) est alors le risque de souffrir dun cancer des poumons si on considre uniquement lapopulation des fumeurs. Une question qui se pose souvent est alors si P(A|B) > P(B|Ac).

    5

  • 7/31/2019 Chain e Markov

    6/32

  • 7/31/2019 Chain e Markov

    7/32

    II.2. LES CHANES DE MARKOV TEMPS DISCRET 7

    H(c) = ij

    cicj,

    o i j signifie que i et j sont voisins (horizontalement ou verticalement). H(c) est lesurplus des voisins de coloration diffrente sur les voisins de coloration gale (contrastes).Souvent on considre H(c) = H(c) o est une constante donne. Il sagit dun casparticulier dun modle que E. Ising avait considr en magntisme, o est la tempratureinverse, et ci est la charge positive ou ngative dune particule. On va voir que ce modlesert, parmi dautres, la reconstitution dimages.Pour faire le lien avec les probabilits conditionnelles, nous considrons des configurationsalatoires, notes (Xi)iG, o les Xi sont des variables alatoires. Une loi de probabilitassocie H sur lensemble des configurations est donne par :

    (c) =1

    Z

    exp(

    ij

    cicj ), c = (ci)iG,

    o Z =

    c exp(

    ij cicj), la somme

    c stend sur lensemble des configurations pos-

    sibles de G. Cette somme est impraticable parce que le nombre de configurations possiblesest beaucoup trop grand en pratique : de lordre de (106)256, si la grille compte 106 points,chacun dentre eux tant color par un des 256 niveaux de gris disponibles. On prfre doncles probabilits conditionnelles qui sont plus simples calculer comme le montre le calculsuivant. Pour S = {1, +1} et pour i G fix on a :

    P(Xi = ci|Xj = cj pour tous j = i) = P(Xj = cj pour tous j = i et Xi = ci)

    P(Xj = cj pour tous j = i)= P(Xi = cj pour tous j = i et Xi = ci)

    P(Xj = cj pour tous j = i et Xi = 1) + P(Xj = cj pour tous j = i et Xi = +1)

    =[exp(ji cicj lj,l,j=i clcj )]/Z

    [exp(+

    ji cj lj,l,j=i clcj ) + exp(ji cj lj,l,j=i clcj )]/Z

    =exp(ciji cj )

    exp(

    ji cj ) + exp(ji cj) (II.1)

    Pour ci = 1 on a doncP(Xi = 1|Xj = cj pourtous j = i) = (1 + exp(2

    ji

    cj ))1.

    La loi conditionnelle de Xi donn Xj pour tous j G, j = i se calcule donc facilement partir des valeurs des points voisins de i seulement. Nous utiliserons ces probabilitsconditionnelles la section suivante.

    II.2 Les chanes de Markov temps discret

    Nous allons tudier lvolution temporelle dun systme, qui possde la proprt deMarkov. Le futur dun tel systme est dtermin par son tat prsent, et ne tient pascompte de son pass.

    Notons Xt ltat du systme linstant t. Nous modlisons Xt par une variable alatoireou un vecteur alatoire valeurs dans S, lensemble des tats possibles du systme quelque soit t.

  • 7/31/2019 Chain e Markov

    8/32

    8 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    Dans cette section t varie dans N ou dans un sous-ensemble fini de N. Pour des modlesen temps continu que lon tudiera la section suivante, t varie dans R ou dans un sous-ensemble de R. De faon gnrale on note (Xt, t I) une famille de variables alatoires.La proprit de Markov signifie alors que ltat futur Xt+u est indpendant du pass Xts,sachant le prsent Xt (t, s, u > 0).

    II.2.1 Dfinition, probabilits de transition et loi stationnaire

    Dfinition. Soit I N. (Xt, t I) est une chane de Markov1 ( temps discret) siP(Xt+1 = xj|Xt = xi, Xt1 = xt1,...,Xtn = xtn) = P(Xt+1 = xj|Xt = xi)

    pour tous n N tel que t + 1,t,t 1,...,t n I et tous xj , xi, xt1,..., xtn S.Exemple 1 : La souris markovienne et les quatre trous.

    2

    3

    1

    4

    12/

    12/

    12/

    12/

    12/12/

    12/

    12/

    I = N, S = {1, 2, 3, 4}La souris qui se trouve dans le trou i prsent,saute avec une probabilit 12 vers lun des trousi + 1 ou i 1 (mod 4). Son choix du prochaintrou ne tient donc pas compte du trou par lequelelle est arrive au trou i. De faon gnrale onnote

    tpij = P(Xt+1 = j|Xt = i)la probabilit de transition de i vers j (i,j S).Notons quil sagit de probabilits condition-nelles dfinies en section II.1.

    Dans cet exemple les probabilits de transition sont stationnaires au sens que tpij nedpend pas de t. On crit donc pij la place de tpij. On pose

    P := (pij; i, j S) =

    0 12 012

    12 0

    12 0

    0 12 012

    12 0

    12 0

    .

    P est la matrice de transition de la chane de Markov.On va voir maintenant que la loi initiale (cest--dire le vecteur des probabilits P(X0 =i), i S) et P dterminent la loi de Xn (cest--dire le vecteur des probabilits P(Xn =i), i S) pour tous n N. En effet, par la formule de la probabilit totale (voir sectionII.1), on a :

    P(X1 = j) =4

    i=1

    P(X0 = i)P(X1 = j|X0 = i) =4

    i=1

    P(X0 = i)pij j = 1, 2, 3, 4,

    ce qui signifie quon obtient la loi de X1 en multipliant la loi de X0 par P.

    On procde la dfinition des probabilits de transition dordre suprieur :

    1A.A. Markov, mathmaticien russe, 1856-1922

  • 7/31/2019 Chain e Markov

    9/32

    II.2. LES CHANES DE MARKOV TEMPS DISCRET 9

    Dfinition. Soit I N et (Xt; t I) une chane de Markov. Les probabilits de transition dordre nsont donnes par

    t

    p(m)ij = P(Xt+m = xj|Xt = xi) m N, t, t + m I.

    Les probabilits de transition dordre m sont stationnaires sit

    p(m)ij =p

    (m)ij pour tous xi, xj

    S (cest--dire ne dpendant pas de t).

    La prochaine proposition montre que les probabilits de transition dordre m pourm > 1 se calculent facilement partir de P.

    Proposition II.1. (galits de Chapman-Kolmogorov)Soit (Xt; t N) une chane de Markov dont les probabilits de transition dordre m sontstationnaires pour tous m N. Soit S = {x1, x2,...,xn} lensemble des tats possibles dela chane. Alors

    p(m)ij = P(Xt+m = xj|Xt = xi) =kS

    p(l)ikp(ml)kj

    pour tous l {1,...,m 1} et xi, xj S. Notons P(m) = (p(m)ij ; i, j S). Alors P(m) =P(l)P(ml) pour tous l {1