Chain e Markov

Embed Size (px)

Citation preview

  • 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,...,m 1}. En particulier P(m) = Pm.Preuve. Elle se fait laide de la proprit de Markov et le calcul des probabilits condi-tionnelles. Nous donnons le calcul explicite pour m = 2 et l = 1.

    p(2)ij = P(Xt+2 = xj|Xt = xi) =

    kS

    P(Xt+2 = xj, Xt+1 = xk|Xt = xi)

    =

    xkS

    P(Xt+2 = xj, Xt+1 = xk, Xt = Xi)

    P(Xt = xi) P(Xt+1 = xk, Xt = xi)

    P(Xt+1 = xk, Xt = xi)

    =

    xkS

    P(Xt+2 = xj|Xt+1 = xk, Xt = xi)P(Xt+1 = xk|Xt = xi)

    =

    xkS

    pkjpik = (P P)ij = (P2)ij (i, j S)

    Donc P(2) = (p(2)ij ; i, j S) = P2. De mme faon on dmontre que

    p(3)ij = P(Xt+3 = xj|Xt = xi) =

    xkSpikp

    2kj = (P P

    2)ij = (P3)ij.

    Donc P(3) = P3. De faon gnrale on a

    P(m) = P(1)P(m1) = P(1)P(1)P(m2) = Pm

    .

    Exemple 1 (suite). Par la Proposition II.1 et en effectuant le calcul du produit de matriceson obtient :

    P(2) = P P =

    12 0

    12 0

    012 0

    121

    2 012 0

    0 12 012

    , P(3) = P P(2) = P, P(4) = P P(3) = P2

  • 7/31/2019 Chain e Markov

    10/32

    10 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    On en dduit que P(2m+1) = P et P(2m) = P2. Ceci dtermine le comportement de P(m)

    pour m . Dans ce cas la suite (P(m))mN ne converge donc pas. Lexemple suivantmontre que la suite (P(m))mN converge dans certains cas.

    Exemple 2. La souris markovienne et les 3 trous.

    23

    1

    12/

    12/

    12/

    12/

    12/

    12/

    I = N, S = {1, 2, 3},

    P =

    0 12 121

    2 012

    12

    12 0

    , P(2) = P2 =

    12 14 141

    412

    14

    14

    14

    12

    .

    On remarque quaucun lment de P(2) est ga zro, contrairement lExemple 1o il y avait des zros dans P(m) pour tous m N. Nous allons maintenant tudier lecomportement de (P(m))mN pour lExemple 2. Supposons dabord que la loi de X0 estdonne par

    P(X0 = 1) = P(X0 = 2) = P(X0 = 3) =1

    3Par la formule de probabilit totale on obtient pour j=1,2,3 :

    P(X1 = j) =3

    i=1

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

    3

    i=1

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

    3

    i=1

    pij =1

    3

    En remplaant X0 par X1 et X1 par X2 on obtient de mme faon : P(X2 = j) = 13(j=1,2,3). On en dduit du calcul ci-dessus que :

    a) P(Xn = j) = 13 pour tous n N, cest dire que Xn suit la loi uniforme surS = {1, 2, 3} pour tous n N.

    b) Notons = (1, 2, 3) = (13 ,13 ,

    13). Alors = P, cest dire que est invariant

    par multiplication droite par P.

    Le Thorme II.2 ci-dessous nous dit que P() = limn P(n) existe dans ce cas etque les lignes de P() sont gales :

    P() =

    13 13 131

    313

    13

    13

    13

    13

    Ceci veut dire que intervient aussi en tant que limite, quand n , des probabilits detransition. En plus, cette limite ne dpend pas de la loi initiale. En effet, par la formule dela probabilit totale, P(Xn = j) =

    3i=1 P(X0 = i)P(Xn = j| X0 = i) pour tous n N,

    quelle que soit la loi initiale P(X0 = i) i = 1, 2, 3. Donc

    limnP(Xn = j) =3

    i=1

    P(X0 = i) limn

    P(Xn = j| X0 = i) =3

    i=1

    P(X0 = i)pnij

    = j3i=1

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

  • 7/31/2019 Chain e Markov

    11/32

    II.2. LES CHANES DE MARKOV TEMPS DISCRET 11

    quelle que soit la loi initiale P(X0 = i), i = 1, 2, 3. On dit que = (1, 2, 3) est une loistationnaire.Pour la souris de lExemple 2 cela veut dire que quelque soit sa position linstant zro,

    la probabilit quelle se trouve dans le trou i aprs un grand nombre de sauts va convergervers 13 pour i = 1, 2, 3. La loi de sa position aprs un grand nombre de sauts va doncconverger vers la loi uniforme sur S = {1, 2, 3}.

    Sous quelles conditions la loi stationnaire existe-t-elle en gnral ?

    La dfinition qui suit donne des conditions suffisantes pour lexistence dune loi sta-tionnaire.

    Dfinition. Soit (Xn, n N) une chane de Markov dont les probabilits de transitionsont stationnaires. Soit S =

    {x1, x2,...,xq

    }.

    a) xj S est rcurent positif si xj est visit une infinit de fois, cest--dire quil existeun nombre infini de valeurs n telles que Xn = xj. On suppose en plus que le tempsmoyen entre deux visites est fini, ce qui est toujours le cas si S est fini, mais pasncessairement si S est infini.(Xn; n N) est rcurrent positif si tous les lments de S sont rcurrents positifs.

    b) (Xn; n N) est apriodique si p(m)ii > 0 pour tous m N suffisamment grand, etpour tous xi S.

    Remarque. Les chanes de Exemples 1 et 2 sont rcurrentes positives. En fait, la proba-bilit quun site ne sera plus jamais visit aprs un certain temps est gal zro. Notonsaussi que la probabilit quun certain site est visit une infinit de fois est soit zro soit un

    (preuve admise).La chane de lExemple 1 nest pas apriodique : en fait p(2m+1)ii = 0 pour tous m N ettous i S = {1, 2, 3, 4} (voir les zros dans les matrices de transition P et P2). La chanede lExemple 2 est apriodique : p(m)ii > 0 pour tous m N et tous i S = {1, 2, 3}.Thorme II.2. Soit (Xn, n N) une chane de Markov apriodique et rcurrente posi-tive, valeurs dans S={x1, x2,...,xq}. La loi deXn, ainsi que les probabilits de transitions

    p(m)ij (xi, xj S) convergent alors, quand n et m , vers une loi stationnaire

    = (j , j = 1, 2,...,q). Cette loi stationnaire ne dpend pas de la loi initiale (cest direde la loi de X0). Elle est dtermine de faon unique par le systme dquations linaires

    = P,qj=1

    j = 1, j 0 (j = 1,...,q)

    Remarque. a) Une autre condition suffisante pour lexistence de probabilits station-naires est la suivante :(C) il existe m N tel que tous les lments de P(m) sont positifs, cest--dire que

    p(m)ij > 0 pour tous xi, xj S.

    La condition (C) implique en fait que la chane est rcurrente positive et apriodique.b) On peut aussi dmontrer que la moyenne du nombre des visites en xj S jusquau

    temps n, donn par1

    n

    ni=0

    1xj (Xi),

    converge en probabilit, quand n , vers j pour tous xj S.

  • 7/31/2019 Chain e Markov

    12/32

    12 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    Pour une preuve du Thorme I.2 nous rfrons aux ouvrages suivants : A.A. Borovkov. Probability theory. Gordon and Breach, 1998 W. Feller. An introduction to probability theory and its applications. Vol. 1. Wiley,

    1970 V.G. Kulkarni. Modeling and analysis of stochastic systems. Chapman and Hall, 1995

    II.2.2 Exemples en gestion, conomie et imagerie

    Nous terminons cette section par quelques exemples de lois stationnaires.

    1) Considrons un march o n produits A1, A2,...,An sont en comptition les uns contreles autres. Supposons que les clients dcident de rester fidles leur produit ou de changerde produit en tenant compte de la satisfaction ou de linsatisfaction avec le produit utilis prsent sans tenir compte des produits utiliss antrieurement (mme comportement que

    la souris markovienne). Lvolution du comportement des clients (dune semaine lautrepar exemple) est alors donn par la matrice de transition P. Notons que dans ce cas leslments de la diagonale ne sont pas ncessairement = 0.P(m) dcrit le march aprs m semaines, et la loi stationnaire, si elle existe, donne ltatdquilibre du march, duquel il va sapprocher de plus en plus.Nous rfrons aux exercices en TD pour dautres exemples dapplication en gestion.

    2) La marche alatoire avec rflexion aux bords. Considrons la marche alatoire symtriquesur S = {N, N + 1,..., 1, 0, 1,...,N 1, N} qui consiste faire, chaque instant, unpas en arrire ou en avant avec la probabilit 14 ou de rester sur place avec la probabilit

    12 .

    Aux bords, la marche repart avec probabilit 14 et reste sur place avec probabilit34 . Pour

    N = 5 par exemple, on a le graphe des probabilits ci-dessous.

    -5 -4 -3 -2 -1 0 1 2 3 4 5

    3/4

    1/4 1/21/4 1/4

    La matrice de transition est de dimension 2N + 1 et donne par

    P = (pij; i, j S) =

    34

    14 0 ... 0 0 0

    14

    12

    14 ... 0 0 0

    ... ... ... ... ... ... ...0 0 0 ... 1412

    14

    0 0 0 ... 0 1434

    .

    Pour toute loi initiale (par exemple dpart du point 0), on peut calculer la loi de Xn laide de la formule de probabilit totale

    P(Xn = j) =N

    i=N

    P(X0 = i)p(n)ij (n N)

    La loi stationnaire est la loi uniforme sur S, i = 12N+1 pour tous i S. Elle se calcule laide du Thorme II.2. La figure ci-dessous (G. Winkler : Image analysis, RandomFields and Markov Chain Monte Carlo Methods, Springer 2003) illustre cette convergence.Le point de dpart est 0 (P(X0=0)=1) et N = 20. Le graphique en haut est un suivi de

  • 7/31/2019 Chain e Markov

    13/32

    II.2. LES CHANES DE MARKOV TEMPS DISCRET 13

    trajectoires dun grand nombre de ralisations (Xn ; n=0,1,...,600). Les histogrammes pourles instants n=0, 100 et 600 montrent bien la convergence vers la loi uniforme.

    Un cadre concret pour ce type de chane de Markov est lvolution du cours dchangeentre deux monnaies. Le bord infrieur et le bord suprieur sont les points dinterventionsde lautorit montaire pour stabiliser le cours dchange.

    Histogrammes : rpartitions des trajectoires de la chane aux instants n=0, 100 et 600

    3) Le modle dIsing. Ici S est lensemble des configurations des points dune grille G. Lesprobabilits de transition dune configuration vers lautre sont plus complexes dans cetexemple et se calculent partir des probabilits conditionnelles calcules en section II.1.Plus prcisment notons p{i} la probabilit de transition de la configuration du i-me pointde G. Pour deux configurations ct = (clt)lG et ct+1 = (c

    lt+1)lG, p{i} est donne par

    p{i}(ct, ct+1) = P(Xit+1 = c

    it+1| Xjt = cjt pour tous j = i).

    Cette probabilit se calcule laide de la formule II.1 . La matrice de transition duneconfiguration (de tous les points de G) vers une autre est alors donne par

    P = (p(ct, ct+1), ct, ct+1 S) o p(ct, ct+1) =iG

    p{i}(ct, ct+1).

    Notons que P est une matrice nn, sil y a n configurations possibles de G. Pour obtenir laprobabilit de transition dune configuration ct vers une configuration ct+1 il faut calculerllment de P qui se trouve sur la ligne qui correspond ct et dans la colonne qui correspond ct+1. On peut dmontrer que la matrice de transition dordre m est gale Pm, et quela loi stationnaire pour le modle de Ising ((c), c S) est donne par

    (c) =1

    Zexp(

    ij

    cicj ) o Z =

    c

    exp(ij

    cicj),

  • 7/31/2019 Chain e Markov

    14/32

    14 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    la somme

    c tant sur toutes les configurations possibles de G. A noter quil sagit de laloi introduite en section II.1.Il se peut que la convergence vers la loi staionnaire est assez lente comme le montre la

    Figure 1 ci dessous. Lchelle sur laxe vertical est la frquence relative de points voisinsayant la mme configuration, laxe horizontal est le temps. A gauche se trouve limagede dpart avec un trs grand nombre de voisins de configurations diffrentes. Lapplicationrptitive de P est cens nettoyer limage, cest--dire de sapercevoir quil ny a pas dob-

    jets rels, mais seulement des bruits (noise en anglais) quil faut supprimer. Ceci revient diminuer le nombre de voisins avec configurations diffrentes. Au cas o l image comportedes objets rels qui sont bruits, il faut choisir un algorithme qui supprime ces bruits sansfaire disparatre limage de ces objets rels. La suite de la Figure 1 montre ltat de ce

    nettoyage aprs 150, 300 et 8000 applications (sweeps en anglais) de P. Lefficacit dunettoyage dpend fortement de la valeur de . Pour la Figure 1=0.8, pour la Figure 2=0.43 et pour la Figure 3 =1.0. Les carrs des Figures 2 et 3 montrent ltat du net-

    toyage aprs 0, 1, 3,10, 30, 100, 1000 et 3000 applications de P. A noter la diffrence entreles rsultats du nettoyage. Les figures sont reproduites de : G. Winkler, Image Analysis,Random Fields and Markov Chain Monte Carlo Methods. Springer 2003. Nous remercionslauteur pour la permission de reproduire ces figures dans ce polycopi et rfrons sonouvrage pour un traitement dtaill de la reconstitution dimages.

    Figure 1. = 0.8, n = 0, 150, 300, 8000

  • 7/31/2019 Chain e Markov

    15/32

    II.3. LES CHANES DE MARKOV TEMPS CONTINU 15

    (a) (b) (c) (d)

    (e) (f) (g) (h)

    Figure 2. = 0.43 n = 0, 1, 3, 10, 30, 100, 1000, 3000

    (a) (b) (c) (d)

    (e) (f) (g) (h)

    Figure 3. = 1.0 n = 0, 1, 3, 10, 30, 100, 1000, 3000

    II.3 Les chanes de Markov temps continu

    Dans beaucoup des cas on souhaite disposer de manire continue lvolution temporelledun systme. On prfre alors considrer le temps comme tant une variable continue,

    prenant ses valeurs dans un intervalle I R+ et des chanes de Markov indexs par lespoints de I : (Xt; t I). Des exemples typiques sont le nombre dappels arrivant un

    service de renseignements tlphonique en priode [t, t + h], le nombre de tches arrivant

  • 7/31/2019 Chain e Markov

    16/32

    16 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    la partie centrale dun ordinateur ou encore le nombre de machines qui tombent en panneet qui doivent tre rpares en [t, t + h]. Ces exemples rentrent dans le cadre du schma

    clients/serveur : les clients sont les personnes qui appellent, les tches qui arrivent ou

    les machines tombes en panne ; les serveurs sont le service de renseignements, lordinateurou le centre de rparation des machines. Du ct pratique on sintresse, entre autres, la longueur de la file dattente qui se forme devant les guichets, aux dures dattente des

    clients ou au degr doccupation des serveurs.

    II.3.1 Intensits de transition et modles linaires

    Soit I R+ la priode dobservation, et soit S lensemble des tats possibles de lachane (S = {xl; l J}, J N, fini ou non). Dans les exemples prcdents les tats sonttypiquement le nombre de clients prsents (servis ou non) ou le nombre de clients enattente dtre servis. Notons Xt (t I) ltat de la chane linstant t, et notons

    pij(h) = P(Xt+h = xj| Xt = xi) (xi, xj S, t, t + h I, h > 0)les probabilits de transition, supposes stationnaires dans cette section, cest--dire que

    pij(h) ne dpend pas de t. Ces probabilits de transition sont des fonctions de h, doncdes expressions plus complexes quen section II.2. Nous allons dmontrer que les lois desXt (t I) sont dtermines uniquement par la loi initiale et les drives en h = 0 desprobabilits de transition. Ces drives remplacent donc les probabilits de transition deschanes temps discret dans le calcul des lois de Xt et de la loi stationnaire, si elle existe.Notons que :

    ddh

    pij(0) = limh0

    1

    h(pij(h) pij(0)) =

    limh0

    1hpij(h) si i = j,

    limh01h (pii(h)

    1) si i = j.

    (II.2)

    De faon quivalente on peut crire :

    pij(h) = pij(0) + hd

    dhpij(0) + (h) quand h 0.

    Ici (h) est une fonction de h, inconnue en gnral, tel que limh01h (h) = 0. Notons aussi

    que

    jS pij(h) = 1, et donc

    jSd

    dhpij(h) = 0 pour tous i S. Les drives sinter-prtent comme les intensits dun saut de xi vers xj dans une priode (infinitsimalement)courte. Nous traitons dans cette section le cas o seules les intensits dun saut vers un desvoisins dans S sont positives. Dans le cadre du schma clients/serveur ceci signifie quilest peu probable que deux ou plusieurs clients arrivent en mme temps : soit que la chanereste en ltat i, soit quelle passe ltat (i + 1) (un client est arriv), soit quelle passe

    ltat (i 1) (un client est servi et part).Dfinition. Une chane de Markov (Xt; t I) valeur dans S N est linaire (ou unprocessus de naissance et de mort) si, pour tous i, j S et t, t + h I

    pij(h) = P(Xt+h = j| Xt = i) =

    ih + (h) si j = i + 1ih + (h) si j = i 11 (i + i)h + (h) si i = j(h) si |i j| 2

    quand h 0. Daprs (II.2), i = ddhpi,i+1(0) et i = ddhpi,i1(0). i (resp. i) sont lesintensits (ou taux) de naissance (resp. de mort) ltat i S. Leurs valeurs sont sup-poses donnes ou estimables partir de lobservation de la chane. Pour S =

    N

    on a lareprsentation graphique suivante :

  • 7/31/2019 Chain e Markov

    17/32

    II.3. LES CHANES DE MARKOV TEMPS CONTINU 17

    0 1 2 30 1 2

    1

    2

    3

    2 2 33

    01 1

    n n, 0

    II.3.2 Le processus de Poisson

    (Denis Poisson, mathmaticien franais, 1781-1840)

    Considrons la chane de Markov linaire avec S = N, i = > 0 et i = 0 pour tousi N. Supposons que X0 = 0. Les probabilits de transition sont donnes par :

    pii(h) = (1 )h + (h), pi,i+1(h) = h + (h) quand h 0.Quelle est la loi de Xt, pour t > 0 ? Posons pi(t) = P(Xt = i) (i S). Nous dterminonsles valeurs de pi(t) rcursivement, en commenant par i = 0, et nous allons voir que les Xtsuivent la loi de Poisson avec paramtre t, cest--dire que pi(t) =

    (t)i

    i! et (t 0, i N).

    i = 0 :

    p0(t + h) = P(Xt+h = 0) = P(Xt+h = 0| Xt = 0)P(Xt = 0)= p00(h)p0(t) = (1 h + (h))p0(t) pour h 0.

    Donc p0(t + h) p0(t) = (h + (h))p0(t) pour h 0.

    Donc ddtp0(t) = limh01h (p0(t + h) p0(t)) = p0(t), p0(0) = 1.

    Do ddtp0(t) = p0(t), p0(0) = 1.

    La solution de cette quation diffrentielle est donne par p0(t) = et. Il sagit bien de laprobabilit en i = 0 de la loi de Poisson de paramtre t.

    Cas gnral : On procde par induction. On suppose que pi1(t) =(t)i1

    (i1)!et, et on

    souhaite dmontrer que la formule reste valable si i

    1 est remplac par i.

    pi(t + h) = P(Xt+h = i) = P(Xt+h = i, Xt = i) + P(Xt+h = i, Xt = i 1)= P(Xt+h = i| Xt = i)P(Xt = i) + P(Xt+h = i| Xt = i 1)P(Xt1 = i 1)= pii(h)pi(t) +pi1,i(h)pi1(t)

    = (1 h + (h)) pi(t) + (h + (h)) pi1(t) quand h 0.

    Doncddt

    pi(t) = pi(t) + pi1(t) = pi(t) + ( i1

    (i 1)!et), pi(0) = 0.

    On vrifie facilement que pi(t) =(t)i

    i! et

    est solution de cette quation diffrentielle.

  • 7/31/2019 Chain e Markov

    18/32

    18 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    Les trajectoires (temporelles) de ce processus sont donc des fonctions en escalier, avec desmarches (arrive de clients) des instants alatoires, nots T1, T2,... On pose T0 = 0. Ona donc

    Xt n Tn t pour n N, t 0.

    0

    1

    2

    3

    4

    5

    Xt

    T1

    T2

    T3

    T4

    t

    Le thorme suivant rsume le rsultat obtenu ci-dessus, et donne les proprits les plusimportantes du processus de Poisson.

    Thorme II.3. Les caractrisations suivantes sont quivalentes pour le processus de Pois-son (Xt; t 0) dintensit > 0 issu de zro.

    a) (Xt; t 0) est une chane de Markov linaire valeur dans N et dintensit i =

    > 0 et i = 0 (i N).b) pour touss, t 0, s < t et tous i N on a :

    P(Xt Xs = i) = P(Xts = i) = [(t s)]i

    i!e(ts), (II.3)

    et les accroissements sur des intervalles disjoints sont indpendants, cest--dire que,pour tous n N et tous 0 t0 < t1 < t2 < ... < tn,

    Xt1 Xt0 , Xt2 Xt1,...,Xtn Xtn1, (II.4)

    sont des variables alatoires indpendantes.

    Remarque. La premire galit en (II.3) dit que la loi des accroissements Xt Xs nedpend que de la longueur t s de lintervalle [s, t], mais pas de sa position. On ditque les accroissements sont stationnaires et par (II.4), indpendants. Une autre propritimportante du processus de Poisson est le fait que les temps dattente entre deux sautsUi = Ti Ti1 (i N) sont des variables alatoires indpendantes et que Ui suit la loiexponentielle de paramtre ; cest--dire que la fonction de rpartition des Ui est donnepar P(Ui x) = 1 exp(x)1R+(x).

    La proprit de Markov du processus de Poisson se traduit donc par labsence dunemmoire pour les temps dattente entre deux sauts. On a en fait

    P(Un > x + y| Un > x) = P(Un > x + y)P(Un > x)

    =e(x+y)

    ex= ey = P(Un > y).

  • 7/31/2019 Chain e Markov

    19/32

    II.3. LES CHANES DE MARKOV TEMPS CONTINU 19

    Cest--dire que la probabilit dattendre au moins x+ y units de temps jusquau prochainsaut ne dpend pas du fait que cette attente dure dj x units de temps. Elle est simplementgale la probabilit (inconditionnelle) que lattente dure au moins y units du temps aprs

    x.Notons que EUn = 1 , et que V ar U n =

    12

    , tandis que EXt = V ar Xt = t.

    Remarque. La dmonstration complte de lquivalence de a) et b) du Thorme prc-dent et de la loi exponentielle de Ui exige une analyse plus fine du processus de Poissonqui nest pas le but de ce cours.

    II.3.3 La loi stationnaire dans le cas o lensemble des tats possibles

    est fini

    Nous tudions maintenant le cas o S = {1, 2, . . ,n}. Soit (Xt; t 0) une chane deMarkov linaire et valeurs dans S. Sa fonction de transition ( valeur matrices) est donnepar P(t) = (pij(t), i , j S), o pij(t) = P(Xs+t = j| Xs = i) et t varie dans R+. Lesgalits de Chapman-Kolmogorov (Proposition II.1) restent valables en temps continu etse lisent de faon suivante :

    P(t + s) = P(t)P(s) pour tous t,s > 0.

    Elles nont cependant pas la mme importance quen temps discret, o lgalit P(n) = Pn

    permet le calcul direct de la loi de Xn. En temps continu, le calcul de P(t), de la loi Xtet de la loi stationnaire est plus compliqu en gnral. Il faut procder de mme faon quepour le processus de Poisson et rsoudre des systmes dquations diffrentielles pas trssimples en gnral. Nous nous contentons ici de poser ce systme dquations diffrentielles

    et den dduire une formule explicite pour la loi stationnaire qui sera la formule de basepour les files dattente. Le graphe des intensits de transition facilite la comprhension deces quations diffrentielles.

    0 1 2 n0 1

    1

    2

    2 2

    0

    1 1

    n-1

    n-1

    n-1

    n

    n-1

    n

    En appliquant lingalit de Chapman-Kolmogorov on dduit du graphe ci-dessus :

    pj(t + h) = P(Xt+h = j) =iS

    P(Xt = i)P(Xt+h = j| Xt = i) =iS

    pij(h)pi(t)

    = pj(t)(1 jh jh + (h)) +pj1(t)(j1h + (h))+pj+1(t)(j+1h + (h)) + (h) quand h 0

    Donc

    d

    dtpj(t) = lim

    h0

    1

    h(pj(t + h) pj(t))

    =

    (j + j)pj (t) + j1pj1(t) + j+1pj+1(t) 1 j n

    1

    En tenant compte des particularits aux tats 0 et n on obtient le systme dquationsdiffrentielles suivant :

  • 7/31/2019 Chain e Markov

    20/32

    20 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    Proposition II.4. Soit (Xt; t 0) une chane de Markov linaire valeurs dans S ={0, 1, . . ,n}. La loi de Xt pour tous t > 0 est alors donne par la loi X0 (pj(0) = P(X0 =

    j), j S) et la solution du systme suivant dquations diffrentielles :

    ddtpj (t) = (j + j )pj(t) + j1pj1(t) + j+1pj+1(t) 1 j n 1,ddtp0(t) = 0p0(t) + 1p1(t),ddtpn(t) = npn(t) + n1pn1(t).

    (II.5)

    La loi stationnaire de (Xt, t 0) se dduit facilement de la proposition prcdente.

    Thorme II.5. Soit (Xt; t 0) une chane de Markov linaire valeurs dans S ={0, 1, 2, . . ,n}. Supposons que i > 0 pour i = 0, 1, 2,...,n 1 et i > 0 pour i = 1, 2,...,n.La loi stationnaire (cest--dire la loi associe aux valeurs supposes donnes de i et iet valable pour tous t 0) est donne par

    pl = P(Xt = l) =lj=1

    j1jn

    i=0 ij=1

    j1j

    (l S, t I). (II.6)

    Remarque. a) Dans le dnominateur de la formule ci-dessus on obtient pour i = 0 leproduit 0j=1... Il faut le poser gal 1.b) Lexemple du processus de Poisson montre que la loi stationnaire nexiste pas toujourssi S est infini. Les files dattente que lon va traiter ci-dessous montrent cependant quelleexiste sous certaines conditions mme si S est infini.

    Preuve du Thorme II.5 : Sous le rgime stationnaire les probabilits pij(t) (j S, t

    I) ne dpendent pas de t. Le systme dquations diffrentielles de la Proposition

    II.4 devient donc un systme dquations pour les inconnues pj, j S. Il se lit :0p0 = 1p1

    (j + j)pj = j1pj1 + j+1pj+1 (1 j n 1)n1pn1 = npn

    Comme ce systme est linaire, on peut le rsoudre facilement de la faon suivante :

    p1 =01

    p0, p2 =1

    2[(1 + 1)p1 0p0] = 01

    12p0,...

    pn

    = n

    j=1

    j

    jp0

    .

    Commen

    j=0pj = 1, on obtient p0(n

    i=0 ij=1

    j1j

    ) = 1, et donc p0 = (n

    i=0 ij=1

    j1j

    )1.Il sensuit que p1,..pn se calculent daprs la formule du Thorme.

    II.3.4 Un exemple en gestion

    Considrons n machines de mme type. PosonsXi la dure alatoire de fonctionnement de la machine i entre deux tombes en pannesuccessives,Y la dure alatoire de rparation dune machine.

    Comme les machines sont du mme type, on peut supposer que les variables alatoiresXi suivent la mme loi. Supposons aussi que les variables alatoires Xi et Y sont indpen-dantes, que Xi suit la loi exponentielle de paramtre > 0 et que Y suit la loi exponentielle

  • 7/31/2019 Chain e Markov

    21/32

    II.3. LES CHANES DE MARKOV TEMPS CONTINU 21

    de paramtre > 02. Les machines qui tombent en panne sont rpares lune aprs lautre.Notons Zt le nombre de machines en panne linstant t. On sintresse la loi stationnairede Zt, cest--dire aux probabilits pl = P(Zt = l) pour l = 1,...,n. Pour calculer cette loi

    on modlise (Zt, t 0) comme une chane de Markov linaire, les naissances tant lesmachines qui tombent en panne, les morts tant les machines qui sont remises en serviceaprs rparation. Sous les hypothses faites sur Xi et Y on voit facilement que (Zt; t 0)est effectivement une chane de Markov. Il faut calculer les taux de naissances et les tauxde morts, et appliquer le Thorme II.5. Posons S = {0, 1, 2, . . ,n}. Pour calculer j onpose

    j =d

    dhpj,j1(0) = lim

    h0

    1

    hpj,j1(h) = lim

    h0

    1

    hP(Zt+h = j 1| Zt = j).

    Pour h trs petit il faut donc calculer la probabilit quune machine sort de rparation en]t,t + h]. Supposons qu linstant t la rparation dure dj t units de temps. On a alors

    P(Zt+h = j 1| Zt = j) = P(Y t + h| Y > t) =P(t < Y t + h)

    P(Y > t)

    =et

    e(t+h)et

    = 1 eh.

    Donc j = limh0 1h (1 eh) = pour j = 1, 2, . . ,n. Remarquons que, daprs le Tho-rme II.3, le nombre de machines rpares est un processus de Poisson avec intensit gale .Calcul de j (j = 0, 1,...,n 1) :

    j =d

    dhpj,j+1(0) = lim

    h0

    1

    hP(Zt+h = j + 1| Zt = j)

    Pour h trs petit il faut donc calculer la probabilit quune machine tombe en panne en]t,t + h]. Numrotons de 1 n j les machines en service linstant t.P(Zt+h = j + 1|Zt = j) = P( l {1,...,n j} tel que Xl ]t tl, t + h tl]| Xl > t tl)

    (tl est linstant de la remise en service actuelle de la machine l)

    = 1 P(Xl > t + h tl pour tous l {1, . . ,n j}| Xl > t tl)= 1 njl=1 P(Xl > t + h tl| Xl > t tl) = 1 njl=1 P(Xl > h)

    daprs la remarque qui suit le Thorme II.3. Donc

    j = limh0

    1

    h(1

    nj

    l=1

    P(Xl > h)) = limh0

    1

    h(1

    e(nj)h) = (n

    j).

    Le graphe des taux de naissances et de morts pour (Zt; t 0) est donc le suivant :

    0 1 2

    j n

    n (n-1) (n-2) (n-j)

    n (n-1) (n-2) (n-j)

    2Ces dernires hypothses peuvent bien sr ne pas tre satisfaites dans un cas concret. Elles figurent icipour que les calculs qui suivent restent simples.

  • 7/31/2019 Chain e Markov

    22/32

    22 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    En appliquant le Thorme II.5, on obtient la loi stationnaire de Z :

    pl = P(Zt = l) = lj=1

    (n j + 1)

    /(n

    i=0

    ij=1(n j + 1)

    )

    = (

    )l

    1

    (n l)! /(n

    i=0

    (

    )i

    1

    (n j)! ) l {0, 1,...,n}.

    II.3.5 Les files dattente M/M/s/R

    Les files dattente sont des cas particuliers des chanes de Markov linaires. On les notedhabitude par M/M/s/R, o

    M/M signifie que les arrives se font selon un processus de Poisson dintensit donne(note > 0). Par la remarque qui suit le Thorme II.3 les temps dattente entredeux arrives successives sont indpendants et suivent la loi exponentielle de para-mtre .Le deuxime M signifie que les dures de services suivent la loi exponentielle dunparamtre donn (not > 0), et que ces dures de services sont indpendantes. Lenombre de services effectus au cours de la priode ]t, t+h] suit donc la loi de Poissondintensit s, o

    s est le nombre de serveurs,R est le nombre maximal de clients dans le systme (en train dtre servi ou en attente

    dun service). Remarquons que R .

    Exemple : Une banque avec s guichets, o la porte dentre ne souvre plus ds quil y aR clients lintrieur de la banque. Remarquons que le nombre de guichets ouverts peutvarier selon lintensit des arrives des clients.

    On sintresse en gnral aux nombres de clients en file dattente en fonction du taux desarrives, du nombre de serveurs et de la dure de service. On sintresse aussi la duredattente et la dure totale de prsence dun client dans le systme. Nous allons rpondreaux questions laide dune chane de Markov linaire de taux constant, not , des arri-ves des clients et de taux de dpart des clients servis, not , dpendant uniquement de s.Remarquons que dautres modles sans la restriction que les taux darrives et de dpartssont constants peuvent tre dduits du Thorme II.5, mais les formules rpondant auxquestions ci-dessus sont alors plus compliques ou inconnues. Dans certains cas, il faut se

    contenter dapproximations.Notations :S = {0, 1,...,R}Xt S (t 0) nombre de clients prsents dans le systme linstant t en file dattente ouen train dtre servis

    pl = P(Xt = l), l S loi stationnaire de (Xt; t 0) si elle existe

    NS = EXt =lS

    pll

    NW = E(Xt s)+ = lS

    pl(l s)+

    Nombre moyen de clients pr-sents dans le systme (NS) oudans la file dattente (NW)

    TS (resp. TW) dure moyenne quun client passe dans le systme (resp. dans la file dattente)

  • 7/31/2019 Chain e Markov

    23/32

    II.3. LES CHANES DE MARKOV TEMPS CONTINU 23

    Les quantits NS, NW, TS et TW sont calcules sous la loi stationnaire.

    a) La file dattente M/M/1/R (R

    )

    Le graphe des taux des arrives et des dparts est le suivant :

    0 1 2

    R

    R-1

    Si R = + la loi stationnaire existe si et seulement si < .Les formules ci-dessous pour pl sont une consquence du Thorme II.5, appliqu n = Ret j = , j = .Si R = + les formules suivantes sont valables :

    pl = l(1 ) , l N, = / < 1

    NS =

    1 =

    , NW = NS =2

    ( )

    TS =1

    NS =1

    , TW =1

    NW =

    ( )

    Si R < + les formules suivantes sont valables :

    pl =l(1)1R+1

    , l {0, 1,...,R}, = /, =

    NS =[1(R+1)R+RR+1]

    (1R+1)(1), = , NW = NS (1 p0)

    TS =NS

    (1pR), TW =

    NW(1pR)

    Remarquons que pl = 1R+1 (l = 0, 1, . . ,R) si = et R < . Il sagit donc de laloi uniforme sur S. Les formules pour TS et TW sont connues sous le nom de formules deLittle. Pour une dmonstration de ces formules, nous rfrons au livre de K. Borovkov :Elements of stochastic modelling. World Scientific 2003.

    b) La file dattente M/M/s/R (R )

    Icij = (j = 0, 1,...,R 1)

    j = j si 1 j s

    s si j s (j = 1, 2,...,R)

    Le graphe des taux des arrives et des dparts est le suivant :

  • 7/31/2019 Chain e Markov

    24/32

    24 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    0 1 2 R

    R-1

    sss

    2

    S-1 S

    -(s-1)

    (s-1)

    -s -s -s

    2

    Si R = + la loi stationnaire existe si et seulement si < s. P(Xt s) est laprobabilit que tous les serveurs sont occups. Les formules ci-dessous pour pl sont uneconsquence du Thorme II.5. Pour s = 1 on retrouve les formules de la partie a).

    Si R = + les formules suivantes sont valables :

    pl =

    lp0l! si l s 1

    , l N, = / < slp0

    slss!si l s

    p0 = [s1i=0

    i

    i!+

    s

    (1 /s)s! ]1, P(Xt s) =

    sp0(1 /s)s!

    NW =

    s(1 /s) P(Xt s), Ns = NW + , TW =NW

    , TS =

    NS

    Si R < + les formules suivantes sont valables :

    pl =

    lp0

    l! si l s 1lp0

    slss!si s l R

    p0 = [s1i=0

    i

    i!+

    s

    s!

    Rsi=0

    i

    si]1

    NW =sp0

    (1 /s)2s!

    s[1 (

    s)Rs+1 (R s + 1)(

    s)Rs(1

    s)]

    NS = NW +s1

    i=0

    ipi + s(1 s1

    i=0

    pi), TW =NW

    (1

    pR)

    , TS =NS

    (1

    pR)

    II.4 Simulation de files dattente

    Souvent les systmes tudier sont trop complexes pour une analyse laide des for-mules proposes en section II.2 et II.3. Il existe des formules plus ou moins explicites pourcertains cas plus gnraux, et des travaux de recherche motivs par les applications r-centes, par exemple en rseaux de tlcommunication, ont t effectus. Dans dautres cason est amen effectuer des simulations sur ordinateur pour apprendre davantage surlvolution temporelle dun systme.

    Exemple : Bilan conomique dune compagnie daviation.Considrons une compagnie arienne qui dispose de 10 avions. Supposons quil en faut 8pour assurer lensemble des vols quotidiens sous sa responsabilit. Les avions sont soit en

  • 7/31/2019 Chain e Markov

    25/32

    II.4. SIMULATION DE FILES DATTENTE 25

    tat de service (not N), soit en attente dtre rpars (A), soit en rparation (R), soit entat dattente pour mise en service (S). Supposons aussi quil y a trois postes de rparation disposition. On peut alors dcrire le flux des avions dun tat vers le suivant par le schma

    suivant :

    S

    N

    A

    R

    Les surfaces hachures correspondent ltat initial du systme : 6 avions en service, 1avion en attente, 3 en rparation.Supposons que les dures entre 2 instants successifs quun avion tombe en panne sont desvariables alatoires indpendantes qui suivent une loi exponentielle de paramtre > 0(hypothse vrifier statistiquement partir dobservations, avec lestimation de ). Sup-posons aussi que les dures entre deux instants successifs quun avion sort de rparationsont, elles aussi, indpendantes et de loi exponentielle de paramtre > 0 (hypothse vrifier galement, avec estimation de ).

    Il y a donc deux files dattente, une pour les postes de rparation (il sagit dune M/M/3/10),et lautre les mises en service (il sagit dune M/M/8/10). Les arrives aux deux files dat-tente se font selon des processus de Poisson de paramtres resp. . Mais les deux processusne sont pas indpendants, parce que les dparts de lune des files dattente sont les arrives lautre file dattente. Les formules de la section II.3.5 ne sont donc pas applicables.Le but dans cet exemple est de faire des prvisions sur le bilan conomique de la socitdaviation. Il faut donc des informations sur lvolution probable des tats des avions pen-dant une certaine priode. Dans cet exemple, il convient de simuler la loi de (St, Nt, At, Rt)quand le temps t parcourt la dure [0,T]. Il faut donc simuler des ralisations de variablesalatoires exponentielles de paramtres et qui interviennent dans les deux files dat-tente. Ce sera fait dans les deux sous-sections qui suivent et on poursuivra ltude de la

    compagnie daviation dans le dernier paragraphe.

    II.4.1 Simulation dune variable alatoire de loi donne

    Thorme II.6. Soit X une variable alatoire de fonction de rpartition F continue don-ne. Alors Y = F(X) suit la loi uniforme sur [0,1].

    Preuve. Notons FY la fonction de rpartition de Y. Alors, pour y [0, 1],FY(y) = P(Y y) = P(F(X) y) = P(X F

    1

    (y)) = F(F1

    (y)) = y,et FY = 0 si y < 0 et FY = 1 si y > 1. Remarquons que F1 est dfinie telle queF1(y) = inf{x : F(x) = y}.

  • 7/31/2019 Chain e Markov

    26/32

    26 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    1

    0

    y

    x

    F(x)

    x=F (y)-1

    Remarque. Lexemple suivant montre comment le Thorme permet de simuler de va-riables alatoires de loi F partir de ralisations indpendantes de loi uniforme sur [0,1].On verra dans la sous-section suivante comment on peut obtenir ces derniers en simulantdes chiffres pseudo-alatoires.

    Exemple : Simulation de ralisations de variables alatoires de loi exponentielle de para-mtre donn.Choisissons = 3/heure la frquence des arrives dans une file dattente.La fonction de rpartition de cette loi est donne par

    y = F(x) = (1 ex) 1R+(x)

    Donc

    x = 1

    ln(1 y) = 13

    ln(1 y) [heures] = 20 ln(1 y) [minutes].

    Comme Y et 1 Y ont mme loi, on peut remplacer x par x = 20ln(y) [minutes]. Parle Thorme I.6 x est une ralisation de la loi F donne si y est une ralisation de la loiuniforme sur [0, 1].Supposons donns les chiffres alatoires suivants :

    57494 72484 22676

    Ils donnent lieu aux ralisations suivantes de la loi uniforme sur [0,1] :y1 = 0,57494 y2 = 0,72484 y3 = 0,22676On en dduit les valeurs suivantes de x :

    x1 = 11,0698 x2 = 6,4361 x

    3 = 29,6773

    Les valeurs x1, x2 et x3 sont donc des ralisations de la loi exponentielle de paramtre

    = 3/heure = 20/minute. Avec ces simulations on peut effectuer des valuations statis-tiques comme sil sagissait dobservations relles.

    La simulation de ralisations de variables alatoires de loi discrte est diffrente et illustrepar lexemple suivant. Considrons la loi F donne ci-dessous : elle ralise 4 valeurs avecles probabilits p1,p2,p3,p4 (

    4i=1pi = 1). Supposons donnes les ralisations y1,y2 de loi

    uniforme sur [0,1]. On en dduit les ralisations x1 = F1

    (y1) et x2 = F1

    (y2) de F suivantle graphique ci-dessous :

  • 7/31/2019 Chain e Markov

    27/32

    II.4. SIMULATION DE FILES DATTENTE 27

    F(x)

    x = F (y )1 1

    -1 x = F (y )2 2

    -1

    y1

    O

    P1

    P2

    P3

    P4

    1

    y2

    Remarquons que lon a F(F1(y)) = y en gnral au cas o F est discrte.

    II.4.2 Gnrateur de nombres pseudo-alatoires

    Si on a besoin dun grand nombre de ralisations de variables alatoires de la loi uniformesur [0,1] il faut les gnrer laide dun algorithme convenable. Ceci est prcis dans ladfinition suivante.

    Dfinition. Un gnrateur de nombres pseudo-alatoire (GNPA) est un algorithme quignre des suites de chiffres y1, y2,...,yn, quel que soit n N, tel que le comportement sta-tistique de ces suites est celui dune suite Y1, Y2,...,Yn de variables alatoires indpendantesde loi uniforme sur [0,1].

    Dfinition. Soient a,b,n N et n premier. Un GNPA congruentiel linaire est donn parla valeur initiale, note y0, et par la formule rcursive pour yi

    yi = (ayi1 + b) (mod n) i = 1, 2,...

    Remarque. On a videmment yi 0, 1, 2,...,n 1. Pour obtenir des ralisations ind-pendantes dune variable de loi uniforme sur [0,1], il suffit de fixer la prcision r souhaite,de choisir r chiffres conscutives de yi et de les identifier aux r premires dcimales dunnombre de [0,1].

    Le choix de a, b et n est crucial pour la qualit dun GNPA, comme le montrent les exemplessuivants :

    Exemple 1 : a=13, n=7, b=0. Soit y0=29. On obtienty1= 377 (mod 7) = 6, y2 = 78 (mod 7) = 1, y3 = 13 (mod 7) = 6.On obtient donc y2i1=6, y2i=1, i=1,2,... On a donc gnr la suite 296161616 qui nestcertainement pas une bonne suite de chiffres pseudo-alatoires.

    Exemple 2 : a=3, n=100, b=0. Soit y0=13.La suite de nombres gnrs par ce GNPA est priodique de priode 20, cest--dire queyi = yi(mod 20). Les 20 premiers nombres gnrs par cet algorithme sont les suivants :39 17 51 53 59 77 31 93 79 37 11 33 99 97 91 73 19 57 71 13En rptant cette suite de nombres on obtient une suite qui nest videmment pas utilisable

    pour crer des ralisations indpendantes de loi uniforme sur [0,1] parce que la priode estbeaucoup trop courte. Ceci est illustr par le fait que lensemble des couples ( y2i1/100,y2i/100) (n N) reprsentent 10 points seulement situs sur 3 droites dans [0,1]2.

  • 7/31/2019 Chain e Markov

    28/32

  • 7/31/2019 Chain e Markov

    29/32

    II.4. SIMULATION DE FILES DATTENTE 29

    format(20,20) ;fd1=mopen("fichier.data","w") ;a=216+3;n=231-1;b0=a;for i = 1 :100

    b1=pmodulo(b0*a,n) ;mfprintf (fd1,%5.3f %5.3f\n,b0/n,b1/n);b0=b1;

    endmclose(fd1) ;

    Pour visualiser ces rsultats, une possibilit : xgraphxgraph -x Y2-1 -y Y2 -bb -nl -M fichier.dataxgraph -x Y2-1 -y Y2 -bb fichier.data

    Il faut cependant dire que, quelle que soit la valeur de a, n et b, les points (y2i1/n,y2i/n)sont toujours situs sur un nombre fini de droites dans [0,1] 2. Plus gnralement les points(Yi/n,Yi+1/n,...,Yi+p1/n), i N seront toujours situs sur un nombre fini dhyperplansde dimension p 1 dans [0,1]p. Cependant ce nombre est trs lev pour les bons GNPA.Mais il est major par (p!n)1/p. Pour lexemple 3 et p = 2 on obtient

    2n = 65535 droites.

    Nous terminons cette sous-section par des tests statistiques pour la loi uniforme sur [0,1]et pour lindpendance des nombres pseudo-alatoires.

    a)Test de validit dajustement

    Il permet de tester la rpartition uniforme des nombres pseudo-alatoires sur [0,1]. Onaligne les chiffres cj {0, 1,..., 9} gnrs par les yi, i = 1,...,nSoit Xl le nombre de chiffres gaux l (l=0,1,...,9)Hypothse H0 : X = (X0, X1,...,X9) suit la loi multinomiale de paramtres (n, 110 ,

    110 , ...,

    110)

    Variable de test : 2 =9

    l=0

    (Xl n10

    )2/n

    10=

    10

    n

    9l=0

    (Xl n10

    )2

    Notons que n =9

    l=0

    Xl.

    Il faut rejeter H0 si 2 > 2(9)1, o 2(9) est la loi de Khi-deux avec 9 degrs de libert,

    est la probabilit dune erreur de 1re espce et 2(9) est lextrmit gauche de lintervallequi porte la probabilit (hachure dans la figure ci-dessous).

    2

    (9)21

    (9)2Fonction de densite de

    0

  • 7/31/2019 Chain e Markov

    30/32

    30 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    b) Test dindpendance des observationsSoit c1, c2,...,cn, la suite dfinie en partie a).Hypothse H0 : C1, C2,...,Cn, sont des variables alatoires indpendantes uniformment

    rparties sur {0,1,...,9}Variable de test : On calcule le nombre rn de soussuites croissantes ou dcroissantes dec1, c2,...,cn.Exemple numrique :

    39786 47879 45786 97125 83237n = 25 r25 = 15

    0.0000

    1.0000

    2.0000

    3.0000

    4.0000

    5.0000

    6.0000

    7.0000

    8.0000

    9.0000

    5.0000 10.0000 15.0000 20.0000 25.0000

    Sous H0 on a ERn = 13(2n 1) et V ar Rn = 190(16n 29). En plusZn := (Rn ERn)/

    V ar Rn suit, asymptotiquement, quand n , la loi normale

    centre rduite, note N(0, 1).Il faut rejeter H0, si |zn| > z1/2, o est la probabilit dune erreur de 1re espce etz1/2 est lextrmit gauche de lintervalle qui porte la probabilit /2 (hachure dans lafigure ci-dessous).

    Fonction densit de N(0, 1)

    /2/2

    -z1/2

    z1/2

    z

  • 7/31/2019 Chain e Markov

    31/32

  • 7/31/2019 Chain e Markov

    32/32

    32 CHAPITRE II. CHANES DE MARKOV ET FILES DATTENTE

    t1.0000

    2.0000

    3.0000

    4.0000

    5.0000

    6.0000

    7.0000

    8.0000

    0.0000 5.0000 10.0000 15.0000 20.0000 25.0000

    Nt

    Rt

    II.5 Remarques bibliographiques

    Dans la plupart les livres de probabilits et processus stochastiques on trouve des cha-pitres sur les chanes de Markov. Parmi les livres qui sadressent plus particulirement aux

    informaticiens et aux ingnieurs, on peut citer : K. Borovkov. Elements of stochastic modelling. World Scientiofic 2003. P. Brmaud. Markov chains. Springer Verlag 1998. N. Bouleau. Processus stochastiques et applications. Hermann 2000. S. M. Ross. Probability models for computer science. Academic Press 2002.

    Pour un trait plus avanc des files dattente on peut citer :P. Robert. Rseaux et files dattente : mthodes probabilistes. Springer Verlag 2000.

    Nombreux sont les ouvrages rcents sur lanalyse des images et sur les rseaux stochastiques.Nous citons :

    G. Winkler. Image analysis, random fields and Markov chains Monte Carlo methods.

    Springer Verlag 2003. H. Chen, D.D. Yao. Fundamentals of queuing networks. Springer Verlag 2001. R. Serfozo. Introduction to stochastic networks. Springer Verlag 1999.