L2Mass -
Option "Markov & Martingales" - 2013-14
10 semaines de cours-TD le vendredi 13h15-16h30 en salle M23 ; 1er cours le 7 février.
Présentation.
1ère interrogation le 21 mar (45mn)
Progression du cours :
1. (7fev) Rappel variable aléatoire (v.a.) comme source d'information, loi de X: Ω→E donnée par la suite (P(X=ei))i lorsque E est énuméré {e1,e2,...}. Loi jointe de X à valeurs ds E et de Y à valeurs ds F est la loi du couple (X,Y):Ω→E×F puis (X,Y,Z)≡((X,Y),Z) ; loi marginale de X connaissant la loi de (X,Y), exercices : lois possibles pour (X,Y) étant données les lois de X,Y: Ω→{1,2}, loi de (X,X), de (X,Y) lorsque X est indépendante de Y, de (X,X+Y) pour le lancé de deux dés.
Rq Composée de X:Ω→E avec f:E→R, espérance de f(X) ; v.a. Ω→R à densité et lois marginales.
Processus aléatoire discret : suite (Xn) de v.a. à valeurs ds E. La loi jointe de X0,...,Xn donne plus d'information que le cumul des lois des Xi (Cf statistiques issues du suivi des élèves pendant 5 ans par 5 professeurs différents ou par un seul professeur). Mémoire du processus.
Une première chaîne de Markov ("fortune du joueur") avec l'ex. 4 de cette feuille corrigé sur celle-ci.
2. (14fev) Continuation sur la "fortune du joueur", exemple introduit le 7 fev : Probabilité conditionnelle, loi conditionnelle, calcul par conditionnement de la loi μn=(P(Xn=k))0≤k≤6 de Xn connaissant μn-1, expression matricielle, expression de μn+k en fonction de μn : puissance k-ième de la matrice des probabilités de transition, conditionnement itéré, somme sur les chemins de longueur k dans le graphe associée à la chaîne de Markov.
"TD" : loi du temps N passé dans le jeu sachant X0=2 : P(N≤n)=P(Xn=0 ou Xn=6 | X0=2) ; le temps moyen passé dans le jeu est il fini ?
3. (21fev) Continuation sur la "fortune du joueur" : questions de convergence de μn, loi stationnaire, matrice régulière et théorème de Perron-Frobenius pour les chaînes de Markov. Exemple avec la matrice
, régularité de A d'après le graphe associé.TD Questions a,b de l'ex 3 de cette feuille. Calcul par conditionnement d'une espérance ("Nombre de poussins espérés")
4. (7mar) Idée de la preuve du théorème de Perron-Frobenius : f:Rn→Rn dont la restriction à Δn-1 est strictement contractante. Limite des suites (An) et (Bn) pour les matrices ci-dessous via le théorème (pour A) ou l'expression de la somme sur les chemin ω:l→k de longueur n de P(ω) ; calcul de ∩nfon(Δn-1) (intersection de parties convexes fermées bornées de Rn) pour f de matrice B
, 
("fortune du joueur"
simplifié)Calcul numérique de B256 avec Sagemath.
Lecture : le théorème de Perron-Frobenius sur Wikipedia (en)
5. (14mar) Critère de régularité d'une matrice stochastique par connexité du graphe et pgcd des longueurs des chemins d'un sommet à lui même. TD : les exercices sur les chaînes de Markov de cette page : feuille 3 ex1 (puissance d'une matrice écrite par blocs), ex 3,4
6. (21mar) Interrogation (1h50), corrigé notamment de l'ex.2 : limite de Qn.
Calcul du temps moyen passé dans le jeu "fortune du joueur" simplifié (matrice B de la séance 4), d'abord P(N=+∞)=0, expression de l'espérance E(N).
7. (4avr) Recherche des mesures stationnaires pour une matrice stochastique de rang 1 puis 2. Théorème d'existence sans hypothèse, d'unicité dans le cas irréductible avec preuve. Notion d'état transcient, d'état récurrent, relation entre état récurrent et détermination des mesures stationnaires.
8. (11avr) Convergence géométrique de la loi de (Xn) hors des états transitoires : réindexation des états du système, puissances d'une matrice sous-stochastique (mais reste le calcul délicat des probabilités asymptotiques P(Xn=i|X0=j) avec i récurrent, j transitoire). Comportement asymptotique de la loi de (Xn) conditionnée à une composante irréductible en étudiant (Xdn)n, d=pgcd{longueurs des boucles d'un état de la composante}.
9. (18avr - 10h15) Calcul de l'espérance du temps T de 1er retour à l'état 1 partant de 1 pour chacune des deux chaînes de Markov représentées ci-dessous.
Enoncé : Si l'état i est transitoire, E(T|X0=i)=+∞ ; si i est récurrent, E(T|X0=i)=1/μ(i) où μ est la mesure stationnaire portée par la composante irréductible de i.
10. (jeu 24avr, 9h) Esquisse de preuve du résultat E(Tii|X0=i)=1/μ(i). Temps moyen de transition entre deux états avec l'exemple ci-dessous :
11. (16 mai, 10h15) Autour du devoir.
12. (23 mai) Interrogation (2h) sujet + corrigé.
Corrigé de l'interrogation de mars 2014.
Liens : Option "Jeux et décision" en 2007-08
