Remerciez-le!

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

Chaînes de Markov (et applications) Raphael Lachieze-Rey∗ 22 février 2021 M1 MM

Chaînes de Markov (et applications) Raphael Lachieze-Rey∗ 22 février 2021 M1 MM Paris Descartes, 2020 - 2021. Table des matières 0.1 Espérances et probas conditionnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.2 Familles sommables et théorème de Fubini . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.3 Formule des probabilités totales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1 Chaînes de Markov homogènes 3 1.1 Exemples et déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Loi des marginales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 TD : Chaînes de Markov homogènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Temps d’absorption 18 2.1 Temps d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Probabilités et temps d’absorptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 TD : Temps d’arrêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Classiﬁcation des états 25 3.1 Récurrence et transience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 TD : Classes d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 Distributions invariantes 31 4.1 Théorème ergodique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Existence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 TD : Mesures invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5 Convergence à l’équilibre 42 5.1 Périodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.3 Algorithme de Metropolis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 TD : Convergence et simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 TD : Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6 TP 1 - Moteur de recherche 56 6.1 Construction du “Web” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.2 Calcul de PageRank via les valeurs propres . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.3 Estimation du PageRank avec un surfeur aléatoire . . . . . . . . . . . . . . . . . . . . . 56 6.4 Interprétation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 ∗raphael.lachieze-rey@parisdescartes.fr 1 6.5 Construction du moteur de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.6 Raﬃnements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7 TP2 Simulation de polymères 58 7.1 Package geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.2 Evolution libre du polymère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.3 Test de polymères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 8 TP : Problème du voyageur de commerce 64 8.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 8.2 Algorithme d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 8.3 Etude de la convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 8.4 Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 CODE COULEUR En noir : l’essentiel En magenta : exemples, explications, exercices, commentaires, preuves,... Rappels 0.1 Espérances et probas conditionnelles On rappelle la formule de probabilités conditionnelles : P(A|B) = P(A ∩B)/P(B), pour P(B) ̸= 0. On note parfois PB(A) = P(A|B), rappelons que PB(·) est une mesure de probabilités à part entière. Le double conditionnement se traite ainsi : P(A ∩B ∩C) = P(A ∩B|C)P(C) = PC(A ∩B)P(C) = PC(A|B)PC(B)P(C) = P(A| B, C |{z} i.e.B∩C )P(B|C)P(C). Etant donné des variables aléatoires X et Y à valeurs réélles, E(X|Y ) = ϕ(Y ) est une variable aléatoire qui est entièrement uploads/Geographie/ markov.pdf