Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ECE2-B 2019-2020 TP8/9 : Chaînes de Markov Pré-requis : je vous invite à consul

ECE2-B 2019-2020 TP8/9 : Chaînes de Markov Pré-requis : je vous invite à consulter les chapitres de cours correspondants sur ma page (support informatique). Pour ce TP, on pourra en particulier se reporter à la section « Tracés d’histogrammes » du CH 8. I Dans votre dossier Info_2a, créer le dossier TP_8. I. Notion de chaîne de Markov : illustration sur un exemple I.1. Énoncé du problème Doudou le hamster passe son temps entre ses trois activités favorites : dormir, manger et faire de la roue. Au début de la journée, il mange, et à chaque heure, il change d’activité selon les critères suivants. 1) Si, à l’heure n, il est en train de manger, alors il va dormir l’heure suivante avec probabilité 0.7 et faire de l’exercice avec probabilité 0.3. 2) Si, à l’heure n, il est en train de dormir, alors il continue à dormir l’heure n + 1 avec probabilité 0.4, il va manger avec probabilité 0.3 et il va faire de l’exercice avec probabilité 0.3. 3) Si, à l’heure n, il est en train de faire de la roue, il va manger l’heure suivante avec probabilité 0.5 et il va dormir avec probabilité 0.5. On s’intéresse ici à l’évolution du comportement de Doudou. On souhaite notamment déterminer si l’une de ses activités prendra, à terme, le dessus sur les autres. I.2. Modélisation mathématique On modélise ce problème comme suit. • On commence par numéroter les activités par un entier entre 1 et 3. • On note Xn la v.a.r. égale à l’état du hamster à l’heure n. Ainsi, la suite de v.a.r. (Xn) représente l’évolution des activités du hamster. • Cette évolution peut être modélisée par le graphe suivant. D (2) M (1) R (3) 0.4 0.3 0.3 0.7 0.3 0.5 0.5 • On déﬁnit enﬁn la matrice de transition A associée au problème. Il s’agit de la matrice : A = (ai,j) où ai,j = P[Xn=j]([Xn+1 = i]) (ai,j représente la probabilité de passage de l’état j à l’état i) 1 ECE2-B 2019-2020 I.3. Étude de la matrice de transition I Déterminer la matrice de transition du problème précédent. Écrire l’appel permettant de la stocker dans une variable A. A = 0 @ 0 0.3 0.5 0.7 0.4 0.5 0.3 0.3 0 1 A En Scilab : A = [0, 0.3, 0.5 ; 0.7, 0.4, 0.5 ; 0.3, 0.3, 0] I Déterminer P[X0=j]([X1 = i]). À quel cœﬃcient de la matrice A cela correspond-il ? On a : P[X0=j]([X1 = i]) = P[Xn=j]([Xn+1 = i]) Ceci permet de démontrer que la matrice de transition est indépendante de n. Cette propriété est appelée homogénéité. I Soit (i0, . . . , in, in+1) 2 J1, 3Kn+2. Que vaut P[X0=i0]\...\[Xn=in]([Xn+1 = in+1]) ? On a : P[X0=i0]\...\[Xn=in]([Xn+1 = in+1]) = P[Xn=in]([Xn+1 = in+1]) Cette propriété est appelée propriété de Markov. On la retient souvent par la phrase : Le futur (la position Xn+1 à l’instant n + 1) ne dépend du passé (positions X0, . . . , Xn) que par le présent (la position Xn à l’instant n). Ces deux propriétés font de (Xn) une chaîne de Markov homogène. Remarque • Il est classique de faire l’étude d’une grandeur aléatoire qui varie dans le temps discret. Par exemple, on peut étudier : ⇥l’évolution du prix d’une action jour après jour, ⇥l’évolution du gain d’un joueur après chaque partie d’un jeu, ⇥le déplacement d’un mobile (d’une puce) sur les sommets d’un carré (ou sur un axe gradué), (c’était le cas du sujet EDHEC 2017) ⇥. . . Lorsque l’évolution se fait de sorte que l’état à un instant ne dépend que de l’état à l’instant précédent, on est dans le cadre de la chaîne de Markov. • Même si le mot chaîne de Markov n’apparaît que dans le programme d’informatique (et donc pas dans celui de maths), il est fréquent de voir ce type d’étude aux concours. Comme on va le voir, cela permet de faire un sujet qui mêle les résultats des chapitres Probabilités (FPT, sce) et algèbre linéaire (étude d’une matrice et des ses puissances). 2 ECE2-B 2019-2020 I.4. Matrice de transition et évolution de la loi de Xn Dans la suite, on considère le vecteur Un qui déﬁnit la loi de Xn : Un = 0 @ P([Xn = 1]) P([Xn = 2]) P([Xn = 3]) 1 A I Déterminer la probabilité P([Xn+1 = 1]) en fonction de P([Xn = 1]), P([Xn = 2]) et P([Xn = 3]) et des cœﬃcients de la matrice A. La famille ([Xn = 1] , [Xn = 2] , [Xn = 3]) est un système complet d’événements. Ainsi, d’après la formule des probabilités totales : P([Xn+1 = 1]) = 3 P k=1 P([Xn = k] \ [Xn+1 = 1]) = 3 P k=1 P([Xn = k]) ⇥P[Xn=k]([Xn+1 = 1]) = P([Xn = 1]) ⇥ P[Xn=1]([Xn+1 = 1]) + P([Xn = 2]) ⇥ P[Xn=2]([Xn+1 = 1]) + P([Xn = 3]) ⇥ P[Xn=3]([Xn+1 = 1]) = a1,1 ⇥P([Xn = 1]) + a1,2 ⇥P([Xn = 2]) + a1,3 ⇥P([Xn = 3]) I Déterminer de même P([Xn+1 = 2]) et P([Xn+1 = 3]). En déduire que pour tout n 2 N, Un+1 = A ⇥Un. Exprimer enﬁn Un en fonction de A et de U0. Que signiﬁe le choix U0 = 0 @ 1 0 0 1 A ? Comment obtient-on Un dans ce cas ? En procédant de la même manière, on obtient : • P([Xn+1 = 2]) = a2,1 ⇥P([Xn = 1]) + a2,2 ⇥P([Xn = 2]) + a2,3 ⇥P([Xn = 3]) • P([Xn+1 = 3]) = a3,1 ⇥P([Xn = 1]) + a3,2 ⇥P([Xn = 2]) + a3,3 ⇥P([Xn = 3]) On en déduit que : 8n 2 N, Un+1 = A ⇥Un. Par une récurrence immédiate, on obtient : 8n 2 N, Un = An ⇥U0. Si U0 = 0 @ 1 0 0 1 A, c’est que P([X0 = 1]) = 1. Ce choix signiﬁe donc que le hamster est initialement dans l’état 1. En appliquant la formule précédente, on obtient la valeur de Un correspondant à ce choix initial. D’après la formule, cette valeur de Un est le contenu de la première colonne de An. I Déterminer A5, A10 et A20. Que remarque-t-on ? On remarque que la suite des puissances itérées (An) semble converger vers une matrice proche de : 0 @ 0.27 0.27 0.27 0.5 0.5 0.5 0.23 0.23 0.23 1 A 3 ECE2-B 2019-2020 II. Simulation des trajectoires en Scilab II.1. Évolution de l’état du hamster partant d’un état x0 ﬁxé Dans ce qui suit, et sauf mention du contraire, on fait l’hypothèse que le hamster se trouve initialement dans l’état x0 = 2. Autrement dit : P([X0 = x0]) = 1. I Que vaut U0 dans ce cas ? Et U1 ? Dans ce cas, on a U0 = 0 @ 0 1 0 1 A et U1 = A ⇥U0 = 0 @ 0.3 0.4 0.3 1 A I Faire le lien entre U1 et A. En Scilab, quel appel sur A permet de récupérer U1 ? U1 est la deuxième colonne de A. On récupère cette colonne à l’aide de l’appel : A(:,2). I Rappeler l’ensemble image de X1. Décrire le comportement que doit avoir une fonction simulant X1. X1(⌦) = J1, 3K. Une fonction simulant X1 doit renvoyer : • 1 avec probabilité 0.3 (= A(1, 2)), • 2 avec probabilité 0.4 (= A(2, 2)), • 3 avec probabilité 0.3 (= A(3, 2)). I Écrire, à l’aide de la fonction rand, une fonction simuX1 (sans paramètre d’entrée et dont la sortie est stocké dans une variable x1) permettant de simuler la v.a.r. X1 dans le cas où x0 = 2. On testera la fonction une dizaine de fois et on commentera le résultat obtenu. 1 function x1 = simuX1() 2 r = rand() 3 if r < 0.3 then 4 x1 = 1 5 elseif r < 0.7 then 6 x1 = 2 7 else // r < 1 8 x1 = 3 9 end 10 endfunction • Lorsque l’on exécute une dizaine de fois la fonction simuX1, elle renvoie à peu près le même nombre de 1, de 2 et de 3. • En vertu de la LfGN, il faudrait exécuter un grand nombre de fois cette fonction pour vériﬁer si elle simule correctement la v.a.r. X1. Par exemple, si on exécute N = 10000 fois cette fonction, on obtiendra environ 3000 fois le nombre 1, 4000 fois le nombre 2 et 3000 fois le nombre 3. I Modiﬁer cette fonction aﬁn de l’adapter au cas où x0 est quelconque. 4 ECE2-B 2019-2020 On prendra la valeur x0 en paramètre ainsi que la matrice de transition A. 1 function x1 = simuX1(x0, A) 2 r = rand() 3 if r < A(1,x0) then 4 x1 = 1 5 elseif r < A(1,x0) + A(2,x0) then 6 x1 = 2 7 else // r < A(1,x0) + A(2,x0) + A(3,x0) 8 x1 = 3 9 end 10 endfunction On peut uploads/Religion/ chaines-markov.pdf