vjordan.info · Created Date: 10/30/2008 10:25:54 AM

1 / 11rapport de TP "Les chaînes de Markov" - septembre 2008

1. Exemples

a. La vie du hamster

Le hamster ne peut réaliser que 3 tâches : dormir, manger etjouer. La probabilité de changer de tâche ne dépend pas duparcours suivi mais uniquement de la tâche précédente. Cettemodélisation de la vie d'un hamster correspond bien à unechaine de Markov. Cette chaîne de Markov est homogène carla probabilité de passage entre les tâches ne dépend pas dutemps, c'est à dire du numéro n de l'itération, ici en minute.

2. La matrice de transition d'une chaîne de Markov

Ces chaînes de Markov de la vie d'un hamster et du jeu de balle peuvent être représentées par unematrice. Chaque ligne correspond à un état de départ et chaque colonne à un état d'arrivée.Ces matrices de transitions sont stocastiques. La somme des coefficients de chaque ligne est 1.

b. Al ice, Bob et Clara

Alice, Bob et Clara jouent au ballon. Chaque enfant passe la balle à unautre en suivant les probabilités du graphe. Cette situation correspondelle aussi à une chaîne de Markov homogène.Sur le graphe, chaque arc représente la probabilité qu'à chaqueenfant, si celui-ci à la balle, de l'envoyer à un autre enfant. Aucun arcne boucle sur un état, les enfants ne gardent donc pas la balle poureux.

Algori thm ique Numéri queRapport de TP "Les chaînes de Markov"

Ce TP présente les chaînes de Markov. Les exemples de la vie d'un Hamster et celui du jeu de balle

seront utilisés tout le long du rapport pour vérifier les fonctions developpées. La dernière partie est un

exemple complet de l'utilisation possible d'une chaîne de Markov sur le cursus du master.


Fonction vérification de matrice stochastique

Propriétés des matrices stochastiques

La plus grande valeur propre (en valeur absolue) des matrices stochastiques est 1. Le vecteur propreassocié à celle valeur est un vecteur composé de coefficients tous identiques.

Exemples

Matrice de transition de la chaîne de Markov du Hamster>>> E41matrix( [ [ 0. 9 , 0. 05, 0. 05] ,

[ 0. 7 , 0. , 0. 3 ] ,[ 0. 8 , 0. , 0. 2 ] ] )

>>> vp_appro_pi( E41, 0. 0000001, 1000, 2)( matrix( [ [ 0. 57735028] ,

[ 0. 57735026] ,[ 0. 57735027] ] ) , 1. 0000000085875869)

Matrice de transition de la chaîne de Markov d'Alice, Bob et Clara>>> E45matrix( [ [ 0. , 0. 33333333, 0. 66666667] ,

[ 0. 5 , 0. , 0. 5 ] ,[ 0. 25 , 0. 75 , 0. ] ] )

>>> vp_appro_pi( E45, 0. 0000001, 1000, 2)( matrix( [ [ 0. 57735018] ,

[ 0. 57734953] ,[ 0. 5773511 ] ] ) , 1. 000000058036677)

La puissance d'une matrice stochastique est aussi une matrice stochastique. Elle respecte donc lesmêmes propriétés.>>> vp_appro_pi( puissance_appro( E41, 3) , 0. 0000001, 1000, 2)( matrix( [ [ - 0. 57735027] ,

[ - 0. 57735027] ,[ - 0. 57735027] ] ) , ( 0. 99999999999998634) )


a. Où est la bal le et que fait le hamster. . .

. . . au bout de 3 étapes :

>>> E40[ 0, 1/3, 2/3][ 1/2, 0, 1/2][ 1/4, 3/4, 0]>>> puissance_exact( E40, 3)[ 7/24, 17/72, 17/36][ 17/48, 7/24, 17/48][ 17/96, 17/32, 7/24]

Probabilité que la balle passe d'Alice à Bob en3 lancés : 17/72 = 24%

>>> E41matrix( [ [ 0. 9 , 0. 05, 0. 05] ,

[ 0. 7 , 0. , 0. 3 ] ,[ 0. 8 , 0. , 0. 2 ] ] )

>>> puissance_appro( E41, 3)matrix( [ [ 0. 8840, 0. 04425, 0. 0717] ,

[ 0. 8835, 0. 04350, 0. 0730] ,[ 0. 8840, 0. 04400, 0. 0720] ] )

Probabilité que le hamster dorme puis mangeau bout de 3 minutes : 4%


>>> puissance_exact( E40, 7)[ 1309/4608, 14657/41472, 7517/20736][ 7517/27648, 5117/13824, 3299/9216][ 14657/55296, 20171/55296, 5117/13824]

Probabilité que la balle passe de Bob à Claraen 7 lancés : 36%


[ 0. 8840, 0. 0442, 0. 0718] ,[ 0. 8840, 0. 0442, 0. 0718] ] )

Probabilité que la hamster mange puis joue aubout de 7 minutes : 7%


>>> ( puissance_exact( E40, 40) ) . evalf( )[ 0. 2727, 0. 3636, 0. 3636][ 0. 2727, 0. 3636, 0. 3636][ 0. 2727, 0. 3636, 0. 3636]

Probabilité que la balle passe de Clara à Aliceen 40 lancés : 27%


[ 0. 8840, 0. 0442, 0. 0718] ,[ 0. 8840, 0. 0442, 0. 0718] ] )

Probabilité que le hamster joue puis dorme aubout de 40 minutes : 88%

b. Générer des images de graphes à partir de la matrice de transition

La fonction ci-contre permet de générer unfichier utilisant la syntaxe 'dot' quireprésente la matrice de transition.

Exemple avecla matrice "Alice" :


c. Le modèle de diffusion d'Ehrenfest

La matrice de transition du modèle d'Ehrenfest permet de simuler un échange de boules entre deuxurnes. À chaque étapes on selectionne au hasard une boule dans l'urne A et on la met dans l'urne B.Comme pour les exemples précédents, ce processus est une chaîne de Markov homogène.La fonction suivante permet de générer la matrice de transition en fonction du nombre de boules total.

Exemple avec 4 boules :>>> gen_ehrenfest( 4)array( [ [ 0. , 1. , 0. , 0. , 0. ] ,

[ 0. 25, 0. , 0. 75, 0. , 0. ] ,[ 0. , 0. 5 , 0. , 0. 5 , 0. ] ,[ 0. , 0. , 0. 75, 0. , 0. 25] ,[ 0. , 0. , 0. , 1. , 0. ] ] )

La fonction ehrenfest prend en argument unvecteur ligne contenant les probabilitésd'avoir, au départ, chaque état de l'urne A (0,1, ... ou a boules).

Exemple :>>> X0 = matrix( ( 0, 0, 1, 0, 0) )>>> ehrenfest( X0, 1)[ [ 0. , 0. 5, 0. , 0. 5, 0. ] ]>>> ehrenfest( X0, 2)[ [ 0. 125, 0. , 0. 75 , 0. , 0. 125] ]>>> ehrenfest( X0, 3)[ [ 0. , 0. 5, 0. , 0. 5, 0. ] ]

Il y a forcement des 0 sur la diagonale car il y a toujours déplacementde boule.Les coins supérieur et inférieur sont à 0 car il est impossible dedéplacer plus d'une boule à la fois.À l'état 0 et 4, il n'y a plus qu'un choix possible avec la probabilité 1.Quand l'urne est vide, on ajoute forcement une boule et quand l'urneest pleine on en enlève forcement une.


Exemple :>>> E43[ 1, 0, 0, 0, 0][ 2/3, 0, 1/3, 0, 0][ 0, 1/2, 0, 1/6, 1/3][ 0, 0, 0, 1, 0][ 0, 1/2, 0, 0, 1/2]>>> mat2dot( E43, " exemple. dot" )>>> mat_equ2dot( E43, " exemple_equ. dot" )

4. Classification

a. Les classes d'équivalence

Les classes d'équivalence d'une chaîne de Markov représentent chaqune un ensemble d'états quicommuniquent entre eux. À partir de n'importe quel état d'un même classe, on peut atteindre lesautres états de la classe d'équivalence.La fonction python suivante permet de trouver les classes d'équivalence à partir de la matrice detransitions de la chaîne de Markov.

devient


Les graphes réduits des exemples précédents (hamster,Alice) ne comportent chacun qu'une seule classe puisquetous les états communiquent entre eux.

Pour Ehrenfest :>>> E = gen_ehrenfest( 4)>>> class_equ( E)[ [ 0, 1, 2, 3, 4] ]

Pour Alice, Bob et Clara :>>> E40[ 0, 1/3, 2/3][ 1/2, 0, 1/2][ 1/4, 3/4, 0]>>> class_equ( E40)[ [ 0, 1, 2] ]

b. Types de classes

Les classes d'équivalences peuvent être séparées en plusieurs catégories :– les classes transitoires sont celles dont on peut sortir.– les classes persistantes sont celles dont on ne peut pas sortir.– les classes absorbantes sont des classes persistantes composées d'un seul élément.Les chaînes de Markov peuvent être classées en fonction du type de classes d'équivalences qui lesconstituent :– les chaînes irréductibles sont celles composées d'une seule classe d'équivalence.– les chaînes absorbantes sont celles dont les classes persistantes sont toutes absorbantes.

Les exemples précédents (Ehrenfest, Jeu de balle et Hamster) sont tous des chaînes de Markovirréductibles, c'est à dire composées d'une seule classe persistante.

5. Comportement transitoire

La matrice de transitions de la chaîne de Markov permet avec, un vecteur représentant la distributionde probabilité initiale, de trouver la distribution à chaque itération.

Jeu de balle quand Bob àla balle au début :>>> E40[ 0, 1/3, 2/3][ 1/2, 0, 1/2][ 1/4, 3/4, 0]>>> V[ 0, 1, 0]>>> for i in range( 10) :. . . V = V*E40. . . print V. evalf( ). . .[ 0. 500, 0, 0. 500][ 0. 125, 0. 542, 0. 333][ 0. 354, 0. 292, 0. 354][ 0. 234, 0. 384, 0. 382][ 0. 287, 0. 364, 0. 348][ 0. 269, 0. 357, 0. 374][ 0. 272, 0. 370, 0. 358][ 0. 274, 0. 359, 0. 366][ 0. 271, 0. 366, 0. 362][ 0. 274, 0. 362, 0. 364]

Quand Clara à la balleau début :>>> V[ 0, 1, 0]>>> for i inrange( 10) :. . . V = V*E40. . . printV. evalf( ). . .[ 0. 250, 0. 750, 0][ 0. 375, 0. 083, 0. 541][ 0. 177, 0. 531, 0. 291][ 0. 338, 0. 277, 0. 383][ 0. 234, 0. 400, 0. 364][ 0. 291, 0. 351, 0. 356][ 0. 265, 0. 364, 0. 370][ 0. 274, 0. 365, 0. 359][ 0. 272, 0. 360, 0. 366][ 0. 272, 0. 365, 0. 362]

Modèle d'Ehrenfest avec 4 boules :>>> E = gen_ehrenfest( 4)>>> Vmatrix( [ [ 1, 0, 0, 0, 0] ] )>>> for i in range( 10) :. . . V = V*E. . . print V. . .>>> for i in range( 10) :. . . V = V*E. . . print V. . .[ 0. 25 0. 0. 75 0. 0. ][ 0. 0. 625 0. 0. 375 0. ][ 0. 156 0. 0. 75 0. 0. 094][ 0. 0. 531 0. 0. 469 0. ][ 0. 133 0. 0. 75 0. 0. 117][ 0. 0. 508 0. 0. 492 0. ][ 0. 127 0. 0. 75 0. 0. 123][ 0. 0. 502 0. 0. 498 0. ][ 0. 125 0. 0. 75 0. 0. 125][ 0. 0. 5 0. 0. 5 0. ]

À la première itération, la balle est envoyée à un desautres enfants avec la probabilité de l'arc du graphe.La distribution de probabilité semble converger dans lesdeux cas (quand Bob ou Clara possède la balle au départ).

Le modèle d'Ehrenfest est différent etne semble pas converger.


a. Les états récurrents

Un état récurrent est un état à partir duquel on est sûr de revenir. Les trois exemples précédents(Alice, Hamster et Ehrenfest) étant irréductibles, ils sont composés d'une seule classe, tous les étatssont donc récurrents.

6. Comportement asymptotique

a. Distributions invariantes

Le nombre de distributions invariantes (linéairement indépendantes) est égal à la multiplicité de lavaleur propre 1 de la matrice de transitions de la chaîne de Markov.

Exemple du jeu de balle entre Alice, Bob et Clara

La multiplicité de la valeur propre 1 est 1. Il y a une distribution invariante.>>> solve( [ Eq( Rational( 1, 2) *y +Rational( 1, 4) *z, x) , Eq( Rational( 1, 3) *x + Rational( 3, 4) *z, y) ,Eq( x + y + z, 1) ] , [ x, y, z] ){x: 3/11, y: 4/11, z: 4/11}

Vérification (E40 est la matrice de transition de la chaîne de Markov)>>> V[ 3/11, 4/11, 4/11]>>> V*E40[ 3/11, 4/11, 4/11]

La distribution de probabilité du vecteur V est bien invariante puisque le vecteur ne change pas àl'itération suivante.

Exemple du hamster

La multiplicité est 1, la distribution invariante est :>>> solve( [ Eq( 0. 9*x + 0. 7*y + 0. 8*z, x) , Eq( 0. 05*x , y) , Eq( x + y + z , 1) ] , [ x, y, z] ){x: 0. 883977900552486, y: 0. 0441988950276243, z: 0. 0718232044198895}

Vérification (E41 est la matrice de transition)>>> Vmatrix( [ [ 0. 8839779006, 0. 044198895 , 0. 0718232044] ] )>>> V*E41matrix( [ [ 0. 8839779006, 0. 044198895 , 0. 0718232044] ] )

Exemple du modèle d'Ehrenfest (avec a = 4)

Dans cet exemple la multiplicité est 1.>>> solve( [ Eq( a + b + c + d + e, 1) , Eq( a + Rational( 1, 2) *c, b) , Eq( Rational( 3, 4) *b +Rational( 3, 4) *d, c) , Eq( Rational( 1, 2) *c + e, d) , Eq( Rational( 1, 4) *d, e) ] , [ a, b, c, d, e] ){e: 1/16, a: 1/16, b: 1/4, c: 3/8, d: 1/4}

Vérification>>> Vmatrix( [ [ 0. 0625, 0. 25 , 0. 375 , 0. 25 , 0. 0625] ] )>>> V * gen_ehrenfest( 4)matrix( [ [ 0. 0625, 0. 25 , 0. 375 , 0. 25 , 0. 0625] ] )


b. Distribution l imite

On peut déduire si la limite de la distribution existe et est independante de la ditribution initiale encalculant la limite de la suite de puissances de la matrice de transition de la chaîne de Markov.

Exemple du jeu de balle

>>> E45[ [ 0. , 0. 3333333333, 0. 6666666667] ,[ 0. 5 , 0. , 0. 5 ] ,[ 0. 25 , 0. 75 , 0. ] ]

>>> puissance_appro( E45, 100)[ [ 0. 2727272727, 0. 3636363636, 0. 3636363636] ,[ 0. 2727272727, 0. 3636363636, 0. 3636363636] ,[ 0. 2727272727, 0. 3636363636, 0. 3636363636] ]

La limite existe et cette limite correspond àune matrice P* dont toutes les lignes sontégales. La ditribution limite est independantede la ditribution initiale et est égale à uneligne de P*.Contrètement quelque soit l'enfant qui a laballe au départ, Alice aura un peu moinssouvent la balle que Bob et Clara.

Exemple du hamster

>>> E41[ [ 0. 9 , 0. 05, 0. 05] ,[ 0. 7 , 0. , 0. 3 ] ,[ 0. 8 , 0. , 0. 2 ] ]

>>> puissance_appro( E41, 100)[ [ 0. 8839779006, 0. 0441988950, 0. 0718232044] ,[ 0. 8839779006, 0. 0441988950, 0. 0718232044] ,[ 0. 8839779006, 0. 0441988950, 0. 0718232044] ]

Exemple du modèle d'Ehrenfest

>>> E = gen_ehrenfest( 4)>>> puissance_appro( E, 100)matrix( [ [ 0. 125, 0. , 0. 75 , 0. , 0. 125] ,

[ 0. , 0. 5 , 0. , 0. 5 , 0. ] ,[ 0. 125, 0. , 0. 75 , 0. , 0. 125] ,[ 0. , 0. 5 , 0. , 0. 5 , 0. ] ,[ 0. 125, 0. , 0. 75 , 0. , 0. 125] ] )

>>> puissance_appro( E, 101)matrix( [ [ 0. , 0. 5 , 0. , 0. 5 , 0. ] ,

[ 0. 125, 0. , 0. 75 , 0. , 0. 125] ,[ 0. , 0. 5 , 0. , 0. 5 , 0. ] ,[ 0. 125, 0. , 0. 75 , 0. , 0. 125] ,[ 0. , 0. 5 , 0. , 0. 5 , 0. ] ] )

[ . . . ]

La matrice de transition ne semble pasavoir de limite. Concrètement, on ne peutpas prédire les probabilités des états del'urne A sans connaître la distributioninitiale.

Dans l'exemple de la vie du hamster, ondéduit de la distribution limite qu'au bout d'uncertain temps, il dort 88% du temps (quelquesoit l'activité de départ).


7. Exemple complet : "Les études de master"

Les études de master durent 2 ans. Chaque année l'élève a trois continuations possibles :– il réussit et passe à l'étape suivante avec la probabilité 'p'.– il recommence l'étape avec la probabilité 'q'.– il est renvoyé définitivement avec la probabilité 'r'.

Si on considère que chaque année, les probabilités nedépendent pas des années précédentes, le cursus peut êtremodélisé par la chaîne de Markov ci-contre.

a. Probabi l i té d'obtenir son diplôme

La probabilité qu'un élève ait son diplôme est décomposable en plusieurs événements :– l'élève a son diplôme partant de M1– l'élève a son diplôme partant de M2À chaque étape p + q + r = 1.

Résolution avec un pivot de Gauss :Le système d'équation est d'abord mis sous la formed'une matrice.>>> p = Symbol( ' p' )>>> q = Symbol( ' q' )>>> r = Symbol( ' r' )>>> E50[ - 1 + q, p, 0][ 0, - 1 + q, - p]>>> gauss_j ordan( E50)[ 1, 0, 1/( 1 - q) **2*p**2][ 0, 1, p/( 1 - q) ]

Probabilité d'être renvoyé

Les probabilité d'être renvoyé sont déduites du fait qu'un élève est soit diplomé soit renvoyé.À chaque étape, la somme de ces 2 probabilités est égale à 1.


b. Durée moyenne des études

La fin des études concerne indifféremment la réussite ou l'échec. Les2 états absorbants D et R sont regroupés en un état F (pour fin desétudes).t1 est le temps moyen de séjour dans l'état M1 et t2 celui dans l'étatM2.

Résolution :>>> E51[ 1 - q, - p, 1][ 0, 1 - q, 1]>>> gauss_j ordan( E51)[ 1, 0, 1/( 1 - q) + p/( 1 - q) **2][ 0, 1, 1/( 1 - q) ]

c. Durée moyenne d'obtention du diplôme

Sachant qu'on est certain qu'un élève obtiendra son diplôme, la duréemoyenne des études se calcul de la même façon que précédement, lesprobabilités de passage, par-contre, ne sont plus les mêmes. Ellesdeviennent les probabilités "sachant que" le diplôme sera obtenu.

Résolution :>>> E52[ 1 - q, - 1 + q, 1][ 0, 1 - q, 1]>>> gauss_j ordan( E52)[ 1, 0, 2/( 1 - q) ][ 0, 1, 1/( 1 - q) ]


d. Durée moyenne avant renvoi

Avec la même méthode, en utilisant les probabilités sachant quel'élève sera renvoyé.

Résolution :>>> E53[ p + r, - p*( p + r) /( r + 2*p) , 1][ 0, p + r, 1]>>> gauss_j ordan( E53)[ 1, 0, 1/( p + r) + p/( ( p + r) *( r + 2*p) ) ][ 0, 1, 1/( p + r) ]

Documents

vjordan.info · Created Date: 10/30/2008 10:25:54 AM