Chaînes de Markov Théorie, algorithmes et applications Coll. Méthodes stochastiques appliquées

Les chaînes de Markov sont des modèles probabilistes utilisés dans des domaines variés comme la logistique, l'informatique, la fiabilité, les télécommunications, ou encore la biologie et la physique-chimie. On les retrouve également dans la finance, l’économie et les sciences sociales.

Cet ouvrage présente une étude approfondie des chaînes de Markov à temps discret et à temps continu avec des applications détaillées aux processus de naissance et mort et aux files d'attente. Ces applications sont illustrées par des algorithmes généraux de calcul de probabilités d'état et de distribution de temps de passage. Le développement de ces algorithmes repose sur l'utilisation de la technique d'uniformisation des chaînes de Markov qui est présentée de manière théorique et intuitive.

Ce livre s'adresse aux ingénieurs et chercheurs ayant besoin de modèles probabilistes pour évaluer et prédire le comportement des systèmes qu'ils étudient ou qu'ils développent. Il est aussi très bien adapté pour un cours de master.

Avant-propos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Chapitre 1. Chaînes de Markov à temps discret . . . . . . . . . . . . . . . . 13

1.1. Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2. Propriété de Markov forte . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.3. États récurrents et transitoires . . . . . . . . . . . . . . . . . . . . . . . 19

1.4. Classification des états . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.5. Visites à un état . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.6. Décomposition de l’espace d’états . . . . . . . . . . . . . . . . . . . . . 29

1.7. Chaînes de Markov irréductibles et récurrentes . . . . . . . . . . . . . . 34

1.8. Chaînes de Markov apériodiques . . . . . . . . . . . . . . . . . . . . . . 41

1.9. Convergence vers l’équilibre . . . . . . . . . . . . . . . . . . . . . . . . 45

1.10. Théorème ergodique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

1.11. Premier temps de passage et nombre de visites . . . . . . . . . . . . . 61

Chapitre 2. Chaînes de Markov à temps continu . . . . . . . . . . . . . . . . 93

2.1. Définitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

2.2. Fonctions de transition et générateur infinitésimal . . . . . . . . . . . . 97

2.3. Équation backward de Kolmogorov . . . . . . . . . . . . . . . . . . . . 111

2.4. Équation forward de Kolmogorov . . . . . . . . . . . . . . . . . . . . . 117

2.5. Existence et unicité des solutions . . . . . . . . . . . . . . . . . . . . . . 129

2.6. États récurrents et transitoires . . . . . . . . . . . . . . . . . . . . . . . 131

2.7. Classification des états . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

2.8. Explosion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

2.9. Chaînes de Markov irréductibles et récurrentes . . . . . . . . . . . . . . 149

2.10. Convergence vers l’équilibre . . . . . . . . . . . . . . . . . . . . . . . . 163

2.11. Théorème ergodique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

2.12.Premiers temps de passage . . . . . . . . . . . . . . . . . . . . . . . . . 172

2.12.1. Premier temps de passage à un état . . . . . . . . . . . . . . . . . 172

2.12.2. Premier temps de passage à un sous-ensemble d’états . . . . . . 176

2.13.Chaînes de Markov absorbantes . . . . . . . . . . . . . . . . . . . . . . 183

2.14.Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

Chapitre 3. Processus de naissance et de mort . . . . . . . . . . . . . . . . . 191

3.1. Processus de naissance et de mort discret . . . . . . . . . . . . . . . . . 191

3.2. Processus de naissance et de mort discret absorbant . . . . . . . . . . . 200

3.3. Processus de naissance et de mort discret périodique . . . . . . . . . . 207

3.4. Processus de naissance pure continu . . . . . . . . . . . . . . . . . . . . 208

3.5. Processus de naissance et de mort continu . . . . . . . . . . . . . . . . 212

3.6. Processus de naissance et de mort continu absorbant . . . . . . . . . . . 226

3.7. Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

Chapitre 4. Uniformisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

4.1. Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

4.2. Espaces et algèbres de Banach . . . . . . . . . . . . . . . . . . . . . . . 235

4.3. Matrices et vecteurs infinis . . . . . . . . . . . . . . . . . . . . . . . . . 241

4.4. Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

4.5. Chaînes de Markov uniformisables . . . . . . . . . . . . . . . . . . . . 261

4.6. Premier temps de passage à un sous-ensemble d’états . . . . . . . . . . 271

4.7. Chaînes de Markov finies . . . . . . . . . . . . . . . . . . . . . . . . . . 273

4.8. Régime transitoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

4.9. Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

Chapitre 5. Files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

5.1. La file M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

5.2. La file M/M/c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

5.3. La file M/M/∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

5.4. Distributions de type phase . . . . . . . . . . . . . . . . . . . . . . . . . 318

5.5. Processus d’arrivées markoviens . . . . . . . . . . . . . . . . . . . . . . 322

5.6. Processus d’arrivées markoviens par groupes . . . . . . . . . . . . . . . 338

5.7. Chaînes de Markov structurées par blocs . . . . . . . . . . . . . . . . . 347

5.8. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

5.9. Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 374

Annexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387

Bruno Sericola est directeur de recherche au centre Inria Rennes - Bretagne Atlantique. Ses travaux portent sur les modèles probabilistes pour l'évaluation des performances et de la sûreté de fonctionnement des systèmes informatiques et des réseaux de communications.

Retrouvez les autres ouvrages de la collection Méthodes stochastiques appliquées.