Processus de markov et applications algorithmes, réseaux, génome et finance 43220

Extrait / Introduction

Extrait / Introduction :

Les briques de base de ce manuel sont le chapitre 1 sur les méthodes de Monte Carlo, le chapitre 2 sur les chaînes de Markov en temps discret à valeurs dans un ensemble ni ou dénombrable, et les chapitres 6 et 7 sur le processus de Poisson et les processus markoviens de sauts, qui sont des processus en temps continu, à nouveau à valeurs dans un ensemble ni ou dénombrable

Plan

Plan :

1 Monte Carlo 11 1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Théorèmes de convergence . . . . . . . . . . . . . . . . . . . . 13 1.3 Simulation de variables aléatoires . . . . . . . . . . . . . . . . 18 1.4 Méthodes de réduction de variance . . . . . . . . . . . . . . . 22 1.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2 Chaînes de Markov 33 2.1 Dénition et propriétés élémentaires. . . . . . . . . . . . . . . 34 2.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2.1 Marche aléatoire sur E = Zd . . . . . . . . . . . . . . . 37 2.2.2 Processus de GaltonWatson . . . . . . . . . . . . . . . 38 2.2.3 File d'attente en temps discret . . . . . . . . . . . . . . 38 2.3 Propriété de Markov forte . . . . . . . . . . . . . . . . . . . . 39 2.4 Etats récurrents et transitoires . . . . . . . . . . . . . . . . . . 41 2.5 Le cas récurrent irréductible . . . . . . . . . . . . . . . . . . . 44 2.6 Le cas apériodique . . . . . . . . . . . . . . . . . . . . . . . . 52 2.7 Chaîne de Markov réversible . . . . . . . . . . . . . . . . . . . 58 2.8 Statistique des chaînes de Markov . . . . . . . . . . . . . . . . 60 2.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.10 Problèmes corrigés . . . . . . . . . . . . . . . . . . . . . . . . 68 2.10.1 Enoncés . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.10.2 Corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3 Algorithmes stochastiques 85 3.1 Méthode MCCM . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.1.1 Un cadre d'application . . . . . . . . . . . . . . . . . . 88 3.1.2 Le modèle d'Ising . . . . . . . . . . . . . . . . . . . . . 90 3.1.3 Analyse bayésienne d'images . . . . . . . . . . . . . . . 92 3.1.4 Chaînes chauées . . . . . . . . . . . . . . . . . . . . . 93 3.2 Simulation de la probabilité invariante . . . . . . . . . . . . . 94 3.2.1 Simulation parfaite . . . . . . . . . . . . . . . . . . . . 95 3.2.2 Couplage depuis le passé . . . . . . . . . . . . . . . . . 99 3.3 Vitese de convergence . . . . . . . . . . . . . . . . . . . . . . . 101 3.4 Le recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4 Chaînes de Markov et génome 111 4.1 Comment lire l'ADN ? . . . . . . . . . . . . . . . . . . . . . . 111 4.1.1 Les ilôts cpg . . . . . . . . . . . . . . . . . . . . . . . . 112 4.1.2 Recherche de gènes . . . . . . . . . . . . . . . . . . . . 113 4.2 Le modèle i.i.d . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.3 Le modèle de Markov . . . . . . . . . . . . . . . . . . . . . . . 115 4.3.1 Application aux ilôts cpg . . . . . . . . . . . . . . . . . 115 4.3.2 Recherche de gènes . . . . . . . . . . . . . . . . . . . . 116 4.3.3 Statistique des chaînes de Markov Mk . . . . . . . . . 117 4.3.4 Chaîne de Markov phasée . . . . . . . . . . . . . . . . 118 4.3.5 Chaîne de Markov localement homogène . . . . . . . . 118 4.4 Chaîne de Markov cachée . . . . . . . . . . . . . . . . . . . . . 119 4.4.1 Calcul de la vraisemblance . . . . . . . . . . . . . . . . 121 4.4.2 L'algorithme de Viterbi . . . . . . . . . . . . . . . . . . 122 4.4.3 Estimation des paramètres . . . . . . . . . . . . . . . . 123 4.5 Modèle semimarkovien caché . . . . . . . . . . . . . . . . . . 129 4.5.1 Les limites du modèle de Markov caché . . . . . . . . . 129 4.5.2 Chaîne semimarkovienne . . . . . . . . . . . . . . . . 130 4.5.3 Le modèle semimarkovien caché . . . . . . . . . . . . 131 4.5.4 Viterbi semimarkovien . . . . . . . . . . . . . . . . . 132 4.5.5 Recherche de gènes . . . . . . . . . . . . . . . . . . . . 133 4.6 Alignement de deux séquences . . . . . . . . . . . . . . . . . . 136 4.6.1 Algorithme de NeedlemanWunsch . . . . . . . . . . . 137 4.6.2 Chaîne de Markov cachée . . . . . . . . . . . . . . . . 138 4.6.3 Loi a posteriori de l'alignement . . . . . . . . . . . . . 142 4.6.4 Probabilité a posteriori . . . . . . . . . . . . . . . . . . 144 4.7 Un algorithme d'alignement multiple . . . . . . . . . . . . . . 146 4.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 5 Contrôle et ltrage 149 5.1 Contrôle optimal déterministe . . . . . . . . . . . . . . . . . . 149 5.2 Contrôle des chaînes de Markov . . . . . . . . . . . . . . . . . 151 5.3 Contrôle optimal linéaire quadratique . . . . . . . . . . . . . . 152 5.4 Filtrage des chaînes de Markov . . . . . . . . . . . . . . . . . 154 5.5 Le ltre de KalmanBucy . . . . . . . . . . . . . . . . . . . . 156 5.5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . 156 5.5.2 Solution du problème . . . . . . . . . . . . . . . . . . . 158 5.6 Contrôle avec observation partielle . . . . . . . . . . . . . . . 161 5.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 6 Le processus de Poisson 165 6.1 Processus ponctuels et f.a. de comptage . . . . . . . . . . . . . 165 6.2 Le processus de Poisson . . . . . . . . . . . . . . . . . . . . . 166 6.3 Propriété de Markov . . . . . . . . . . . . . . . . . . . . . . . 170 6.4 Comportement asymptotique . . . . . . . . . . . . . . . . . . 174 6.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 7 Processus markoviens de saut 181 7.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.2 Générateur innitésimal . . . . . . . . . . . . . . . . . . . . . 186 7.3 Propriété de Markov forte . . . . . . . . . . . . . . . . . . . . 189 7.4 Chaîne de Markov incluse . . . . . . . . . . . . . . . . . . . . 192 7.5 Classication des états . . . . . . . . . . . . . . . . . . . . . . 195 7.6 Le cas irréductible récurrent . . . . . . . . . . . . . . . . . . . 197 7.7 Réversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 7.8 Phylogénie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 7.8.1 Modèles d'évolution . . . . . . . . . . . . . . . . . . . . 206 7.8.2 Vraisemblance en phylogénie . . . . . . . . . . . . . . . 212 7.8.3 L'approche bayésienne en phylogénie . . . . . . . . . . 216 7.9 Application aux EDP discrétisées . . . . . . . . . . . . . . . . 219 7.10 Le recuit simulé (suite) . . . . . . . . . . . . . . . . . . . . . . 221 7.11 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 7.12 Probèmes corrigés . . . . . . . . . . . . . . . . . . . . . . . . . 230 7.12.1 Enoncés . . . . . . . . . . . . . . . . . . . . . . . . . . 230 7.12.2 Corrigés . . . . . . . . . . . . . . . . . . . . . . . . . . 234 8 Files d'attente et réseaux 239 8.1 File d'attente M/M/1 . . . . . . . . . . . . . . . . . . . . . . . 240 8.2 File d'attente M/M/1/K . . . . . . . . . . . . . . . . . . . . . 242 8.3 File d'attente M/M/s . . . . . . . . . . . . . . . . . . . . . . . 243 8.4 File d'attente M/M/s/s . . . . . . . . . . . . . . . . . . . . . 246 8.5 Atelier de réparation . . . . . . . . . . . . . . . . . . . . . . . 246 8.6 Files d'attente en série . . . . . . . . . . . . . . . . . . . . . . 247 8.7 File d'attente M/G/1 . . . . . . . . . . . . . . . . . . . . . . 248 8.8 File d'attente M/G/1 . . . . . . . . . . . . . . . . . . . . . . . 249 8.8.1 Une chaîne incluse . . . . . . . . . . . . . . . . . . . . 249 8.8.2 Le cas récurrent positif . . . . . . . . . . . . . . . . . . 250 8.9 Réseau de Jackson ouvert . . . . . . . . . . . . . . . . . . . . 252 8.10 Réseau de Jackson fermé . . . . . . . . . . . . . . . . . . . . . 257 8.11 Réseau téléphonique . . . . . . . . . . . . . . . . . . . . . . . 259 8.12 Réseau de Kelly . . . . . . . . . . . . . . . . . . . . . . . . . . 263 8.12.1 Une seule le d'attente . . . . . . . . . . . . . . . . . . 263 8.12.2 Réseau multiclasse . . . . . . . . . . . . . . . . . . . . 267 8.13 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 9 Mathématiques nancières 271 9.1 Les concepts de fondamentaux . . . . . . . . . . . . . . . . . . 272 9.1.1 Option . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 9.1.2 Arbitrage . . . . . . . . . . . . . . . . . . . . . . . . . 273 9.1.3 Marchés viables et complets . . . . . . . . . . . . . . . 274 9.2 Options européennes dans le modèle discret . . . . . . . . . . 275 9.2.1 Le modèle . . . . . . . . . . . . . . . . . . . . . . . . . 275 9.2.2 Stratégie admissible . . . . . . . . . . . . . . . . . . . . 275 9.2.3 Martingales . . . . . . . . . . . . . . . . . . . . . . . . 277 9.2.4 Le marché est viable et complet . . . . . . . . . . . . . 278 9.2.5 Prix du call et du put . . . . . . . . . . . . . . . . . . 281 9.2.6 La formule de BlackScholes . . . . . . . . . . . . . . . 281 9.3 Le modèle et la formule de BlackScholes . . . . . . . . . . . . 284 9.3.1 Introduction au calcul stochastique . . . . . . . . . . . 284 9.3.2 Équations diérentielles stochastiques . . . . . . . . . . 292 9.3.3 Formule de FeynmanKac . . . . . . . . . . . . . . . . 294 9.3.4 L'EDP de BlackScholes . . . . . . . . . . . . . . . . . 295 9.3.5 La formule de BlackScholes (2) . . . . . . . . . . . . . 297 9.3.6 Généralisation du modèle de BlackScholes . . . . . . . 298 9.3.7 La formule de BlackScholes (3) . . . . . . . . . . . . . 299 9.3.8 Le théorème de Girsanov . . . . . . . . . . . . . . . . . 302 9.3.9 Propriété de Markov et EDP . . . . . . . . . . . . . . . 303 9.3.10 Option portant sur plusieurs sousjacent . . . . . . . . 305 9.3.11 Viabilité et Complétude . . . . . . . . . . . . . . . . . 308 9.3.12 Remarques sur le calcul eectif . . . . . . . . . . . . . 308 9.3.13 Volatilité implicite . . . . . . . . . . . . . . . . . . . . 310 9.4 Options américaines . . . . . . . . . . . . . . . . . . . . . . . 310 9.4.1 Enveloppe de Snell . . . . . . . . . . . . . . . . . . . . 312 9.4.2 Décomposition de Doob . . . . . . . . . . . . . . . . . 314 9.4.3 Enveloppe de Snell et chaînes de Markov . . . . . . . . 316 9.4.4 Retour aux options américaines . . . . . . . . . . . . . 316 9.4.5 Options américaines et options européennes . . . . . . 317 9.4.6 Options américaines et modèle markovien . . . . . . . 318 9.5 Options américaines . . . . . . . . . . . . . . . . . . . . . . . 318 9.6 Taux d'intérêt et obligations . . . . . . . . . . . . . . . . . . . 319 9.6.1 Courbe de taux en avenir certain . . . . . . . . . . . . 320 9.6.2 Taux et obligations . . . . . . . . . . . . . . . . . . . . 320 9.6.3 Option sur obligation . . . . . . . . . . . . . . . . . . . 323 9.6.4 Un modèle de taux d'intérêt . . . . . . . . . . . . . . . 324 9.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Bibliographie 329 Index 333

Signaler un abus