Raphael Lachieze Rey
51
pages
Français
Documents
2011
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
51
pages
Français
Documents
2011
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Supérieur
Chaînes de Markov Raphael Lachieze-Rey? 18 juillet 2011 Notes pour le BASI à l'Université de Luxembourg, semestre 6. Table des matières 1 Préliminaires 2 1.1 Probabilités conditionnelles . . . . . . . . . . . . . . . . . . . . . 2 1.2 Théorème de Fubini . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Chaînes de Markov homogènes 3 2.1 Exemples et définitions . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Loi des Xn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Temps d'absorption 9 3.1 Temps d'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Probabilités et temps d'absorptions . . . . . . . . . . . . . . . . . 11 4 Classification des états 16 4.1 Récurrence et transience . . . . . . . . . . . . . . . . . . . . . . . 17 5 Distributions invariantes 23 5.1 Convergence à l'équilibre .
Voir
Chaînes de Markov Raphael Lachieze-Rey? 18 juillet 2011 Notes pour le BASI à l'Université de Luxembourg, semestre 6. Table des matières 1 Préliminaires 2 1.1 Probabilités conditionnelles . . . . . . . . . . . . . . . . . . . . . 2 1.2 Théorème de Fubini . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Chaînes de Markov homogènes 3 2.1 Exemples et définitions . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Loi des Xn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Temps d'absorption 9 3.1 Temps d'arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Probabilités et temps d'absorptions . . . . . . . . . . . . . . . . . 11 4 Classification des états 16 4.1 Récurrence et transience . . . . . . . . . . . . . . . . . . . . . . . 17 5 Distributions invariantes 23 5.1 Convergence à l'équilibre .
- temps d'absorptions
- barreau avec probabilité
- variables indépendantes
- théorème de fubini
- matrice de transition
- espace probabilisé
- chaîne de markov
- transformation aléatoire
- chaîne de markov homogène
Chaînes de Markov Raphael Lachieze-Rey∗ 18 juillet 2011
Notes pour le BASI à l’Université de Luxembourg, semestre 6.
Table des matières 1 Préliminaires 2 1.1 Probabilités conditionnelles . . . . . . . . . . . . . . . . . . . . . 2 1.2 Théorème de Fubini . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Chaînes de Markov homogènes 3 2.1 Exemples et définitions . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Loi desXn 6. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 3 Temps d’absorption 9 3.1 Temps d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Probabilités et temps d’absorptions . . . . . . . . . . . . . . . . . 11 4 Classification des états 16 4.1 Récurrence et transience . . . . . . . . . . . . . . . . . . . . . . . 17 5 Distributions invariantes 23 5.1 Convergence à l’équilibre . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Théorème ergodique . . . . . . . . . . . . . . . . . . . . . . . . . 37 6 Activités 40 6.1 Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.2 Marche aléatoire sur un graphe. . . . . . . . . . . . . . . . . . . . 43 7 Sujet d’examen 48 7.1 Juin 2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
∗lr.raphael@gmail.com
1
1 Préliminaires 1.1 Probabilités conditionnelles On se place dans un espace probabilisé(Ω,A,P). On rappelle que siAetB sont deux évènements, et queBest de probabilité non-nulle, la probabilité de AsachantBest P(A|B) =PP((AA);P(BB)). Autre rappel : SiA, BetCsont des événements tels queBetCsoient non-négligeables, P(A, B|C) =P(A|B, C)P(B|C).(1) Exercice 1. – SiAetBsont indépendants,P(A|B) =P(A)(savoir siBs’est réalisé n’influence pas la probablitié deA). – Quelle est la probabilité qu’un dé tombe sur6sachant que son résultat est pair ? – Quelle est la probabilité que le résultat soit pair sachant qu’un dé tombe sur6? – Si j’enlève deux cartes au hasard d’un paquet de cartes, quelle est la pro-babilité que la seconde soit un trèfle sachant que la première était un valet de trèfle ? sachant que la première était un4? Sachant que la première était un coeur ? En ne sachant rien sur la première ? L’espérance conditionelle d’une variable discrèteXpar rapport à un événe-mentAest E(X|A) =E(X1X=x|A) =XE(1X=x|A) =XP(X=x|A). x x x 1.2 Théorème de Fubini Théorème 1(Fubini).Soit deux mesures σµ, ν-finies définies resp. sur des espace measurable(Ω,A),(Ω0,A0). 1. Alors pour toute fonction positive mesurablef(x, y)sur(X×Y,A ⊗ A0), on a ZΩ×Ω0f(x, y)(µ⊗ν) =ZΩZΩ0f(x, y)ν(dy)ν(dx) =ZΩ0ZΩf(x, y)µ(dy)ν(dx). (2) (Si vous ne savez pas ce qu’est la mesure produitµ⊗ν, cette formule peut tenir lieu de définition.) 2. La formule précédente est encore valable pour toute fonctionftelle que |f|soit intégrable par rapport àµ⊗ν.
2
Pour 2., vérifier l’intégrabilité de|f|revient à vérifier qu’un des trois termes de (2) soit fini. Dans le cours, on utilisera ce théorème avecµ=P,Ω0=Netν=Pn≥1δn est la mesure de comptage. On pourra alors intervertirPetEdans tout formule du type EXX(n) =ν(n)P(dω n≥1ZΩ×N)X(n, ω) pour des variables aléatoiresX(n), pourvu queE(Pn≥1|X(n)|)<∞ouP(E(|X(n)|)|)< ∞, ce qui sera toujours le cas. 2 Chaînes de Markov homogènes 2.1 Exemples et définitions Idée: Une chaîne de Markov est une suite d’événements aléatoires dans le temps oùconditionellement au présent, le futur ne dépend pas du passé, ou autrement dit le futur ne dépend du passé que par le présent. Exemple 1. – Les records du monde du 100m – La population mondiale – Le nombre de personnes dans une file d’attente – Le couple (position, vitesse) d’une voiture de course Exemple 2(Ce qui n’est pas une chaîne de Markov). – La position d’une voiture (le passé nous renseigne sur sa vitesse, et donc sur sa position future) – Un marcheur aléatoire qui ne revient jamais sur ses pas. Définition 1.Formellement, soitEun espace fini ou dénombrable. Ce sera l’espace d’états. SoitX={Xn;n≥0}une suite de variables aléatoires à va-leurs dansE. On dit queXest une chaîne de Markov si, pour toutx1, . . . , xn+1∈ E, on a P(Xn+1=xn+1|X1=x1, X2=x2, . . . , Xn=xn) =P(Xn+1=xn+1|Xn=xn) Le futur Le passé Le présent Cette propriété des chaînes de Markov est aussi connue commepropriété de Markov. Exercice 2.SoitRn, n≥0des variables indépendantes à valeurs dansE. Montrer queSn=Pnk=1RietPn=Qin=1Risont des chaînes de Markov. Une chaîne de Markov peut être vue comme unsystème dynamique, ce qui veut dire queXn+1=fn(Xn), oùfnest une “transformation aléatoire”. 3
Dans l’exemple précédent,fn(Xn)est la somme (ou le produit) deXnavec Rn+1. Si la transformation aléatoirefnne dépend pas den, i.e.Xn+1=f(Xn) pour toutnpour une certaine transformationf, on dit queXest unechaîne de Markov homogène. Cela veut dire que si à un certain instantn≥0la chaîne se trouve à l’état x(Xn=x), alors la propabilité qu’elle se trouve à l’étatyau tempsn+ 1est la même que si l’on était au temps initial. Définition 2.Une chaîne de Markov est homogène si pour toutn≥0,xety dansE P(Xn+1=y|Xn=x) =P(X1=y|X0=x). Dans ce cas, on pose Q(x, y) =P(X1=y|X0=x) y, x,∈E. Qest lamatrice de transitionde la chaîneX. Une chaîne de Markov homogène “saute” donc aléatoirement d’états en états, et la probabilité de chaque saut est donnée par la matriceQ. Exercice 3.Le nombre d’individus d’une population évolue de la manière sui-vante : A chaque instant, un individu nait avec la probabilitép∈(0,1), ou meurt avec la probabilitéq= 1−p. Ecrire la matrice de transition. Ecrire la chaîne de Markov en termes des variables introduites à l’exemple 2. Comment corriger la matrice de transition pour qu’il n’y ait pas un nombre négatif d’individus ? Exemple 3.Une grenouille monte sur une échelle. Chaque minute, elle peut monter d’un barreau avec probabilité1/2, ou descendre d’un barreau avec pro-babilité1/2. L’échelle a5barreaux. Si la grenouille arrive tout en haut, elle saute immédiatement en bas de l’échelle et recommence. On appelleXnla position de la grenouille sur l’échelle. L’espace d’états est doncE={0,1,2, . . . ,5}. Si a un instantnla grenouille est au niveau x∈ {1,2,3,4}de l’échelle, alors à l’instantn+ 1elle sera (arauubbaarreuruaaexx+−11bilitéaevpcorabitilévarpcebabo11//22,, ce qui se traduit par P(Xn+1=x+ 1|Xn=x) = 1/2 (=P(X1=x+ 1|X0=x)), P(Xn+1=x−1|Xn=x) = 1/2 (=P(X1=x−1|X0=x)
4
Comme les probabilités ne dépendent pas den, il semble que l’on tienne le bon bout pour avoir une chaîne de Markov. Si c’est le cas, on peut écrire une partie de la matrice de transition : ? ? ? ? ? 0 1/2 0 1/2 0 0 0 0 1/2 0 1/ 02 0 Q 1= 0 0/2 0 1/2 0 ???0100/102??/2? Si la grenouille se retrouve à l’état5, alors elle peut soit passer à l’état4, soit passer à l’état0. Il faut donc remplacer la dernière ligne de la matrice par (1/2,0,0,1/2,0), (encore une fois cela ne dépend pas de l’instantn). Si la grenouille est à l’état 0, elle ne peut que passer à l’état1. La première ligne de la matrice est donc (0,1,0,0,0). XnMarkov homogène, avec matrice de transitionest donc bien une chaîne de Q. Exercice 4.Introduisons un facteur de fatiguef∈(0,1), et imaginons qu’à chaque instant la grenouille reste à son état actuel avec probabilitéf.Xnest toujours une chaîne de Markov ? Si oui, quelle est sa matrice de transition ? Imaginons désormais que le facteur de fatiguef=fndépend du temps. Que cela change-t-il ? Si désormais le facteur de fatigue dépend de tout le chemin parcouru par la grenouille (nombre de barreaux montés et descendus), a-t-on toujours une chaîne de Markov ? Définition 3.On dit qu’une matriceQeststochastiquessi tous ses coeffi-cients sont≥0et si la somme de chaque ligne fait1:∀x∈E, XQ(x, y) = 1. y∈E On dit aussimatrice markovienne. Remarque 1.Les coefficients d’une matrice stochastique sont≤1. Proposition 1.SiQde transition d’une chaîne de Markov, alorsest la matrice elle est stochastique. Démonstration.Soitx∈E. Alors XQ(x, y) =XP(X1=y|X0=x) y∈E y =P(“Xnaille quelque part après être allé enx...00) = 1.
5
