Modèles stochastiques

Un serveur de calcul tombe parfois en panne, puis on le répare. Une API reçoit des requêtes à des instants imprévisibles et les traite une par une. Un visiteur passe d’une page à l’autre sur un site avant de s’abonner ou de partir. Aucun de ces systèmes n’est prévisible au coup par coup, et pourtant on peut répondre à des questions très précises à leur sujet : quelle est la proportion du temps pendant laquelle le serveur fonctionne ? Combien de temps une requête attend-elle en moyenne ? Quelle part des visiteurs finit par s’abonner ? Les modèles stochastiques donnent les outils pour poser ces questions proprement et y répondre par le calcul.

Ce cours s’appuie sur un seul objet, la chaîne de Markov : un système dont le futur ne dépend du passé qu’à travers son état présent. Vous l’étudierez d’abord en temps discret (on observe le système à chaque pas), puis en temps continu (les événements arrivent à n’importe quel instant), avant de l’appliquer aux files d’attente, qui servent à dimensionner des serveurs, des centres d’appels ou des tampons réseau.

Objectifs pédagogiques

À la fin de ce cours, vous serez capable de :

• Modéliser un système aléatoire par une chaîne de Markov : choisir les états, écrire la matrice de transition ou le générateur, dessiner le graphe.
• Calculer l’évolution des probabilités d’état au cours du temps (régime transitoire) avec $p(n) = p(0)P^n$ ou les équations de Kolmogorov.
• Classer les états d’une chaîne (classes, période, récurrence, transience) et en déduire son comportement à long terme.
• Déterminer une loi stationnaire, savoir quand elle est aussi la limite, et calculer des probabilités et des temps moyens d’absorption.
• Analyser un processus de Poisson et les files d’attente classiques (M/M/1, M/M/s, M/M/∞, M/M/s/s) avec la loi de Little et les formules d’Erlang.
• Simuler ces modèles en Python pour vérifier un calcul ou traiter un cas sans formule.

Prérequis

• Les bases des probabilités : probabilité conditionnelle, formule des probabilités totales, lois discrètes usuelles, espérance. Le cours de Probabilités de ce site couvre tout ce qu’il faut.
• Un peu d’algèbre linéaire : produit matriciel, systèmes linéaires, et la notion de valeur propre pour le chapitre 3.
• Pour la partie 2, les équations différentielles linéaires du premier ordre et la fonction exponentielle.
• La notion de graphe orienté et de composante fortement connexe aide beaucoup au chapitre 2 (voir le cours Graphes et algorithmes).
• Python, avec si possible une première pratique de NumPy.

Le plan du cours

Partie 1 · Chaînes de Markov à temps discret

1. Découvrez les chaînes de Markov : processus stochastique, propriété de Markov, matrice de transition, graphe, loi à l’instant $n$ et relation de Chapman-Kolmogorov.
2. Classez les états d’une chaîne : accessibilité, classes, irréductibilité, période, états récurrents et transitoires.
3. Trouvez la loi stationnaire : équation $\Pi P = \Pi$, théorème ergodique, vitesse de convergence, temps de retour et PageRank.
4. Calculez des probabilités d’absorption : ruine du joueur, conditionnement sur le premier pas, matrice fondamentale.

Partie 2 · Chaînes de Markov à temps continu

5. Passez au temps continu : loi exponentielle, générateur infinitésimal, équations de Kolmogorov et régime stationnaire.
6. Modélisez un processus de naissance et de mort : générateur tridiagonal, balance locale et formule générale du régime stationnaire.
7. Comptez les arrivées avec le processus de Poisson : loi de Poisson, temps inter-arrivées exponentiels, superposition et décomposition.

Partie 3 · Files d’attente

8. Analysez une file d’attente M/M/1 : notation de Kendall, disciplines de service, régime stationnaire, loi de Little et explosion des temps d’attente.
9. Dimensionnez un système à plusieurs serveurs : M/M/s et formule d’Erlang C, M/M/∞, système à perte M/M/s/s et formule d’Erlang B.

Chaque chapitre se termine par un résumé et des exercices corrigés, de difficulté croissante. Si vous vous intéressez à l’apprentissage par renforcement, le chapitre 4 prépare directement les processus de décision markoviens du cours d’Apprentissage par renforcement, et la partie 3 rejoint le cours d’Évaluation de performances.

D’où vient ce cours

Ce cours reprend l’enseignement de modèles stochastiques suivi en 4e année du cycle ingénieur de l’INSA Rennes, en spécialité informatique (premier semestre) : chaînes de Markov à temps discret et continu, processus de naissance et de mort, processus de Poisson et files d’attente isolées. Il s’appuie sur des notes de cours prises par des étudiants et sur les supports officiels des derniers chapitres.

Le texte, les exemples et les exercices ont été entièrement réécrits. Plusieurs notions standard, absentes des sources ou seulement esquissées, ont été ajoutées à partir d’ouvrages de référence sur les processus stochastiques et les files d’attente : le critère « une classe finie est récurrente si et seulement si elle est fermée », la formule des temps de retour ($\Pi_i = 1/\mu_i$), la vitesse de convergence liée à la seconde valeur propre, les probabilités et temps moyens d’absorption (matrice fondamentale), l’interprétation « temps de séjour exponentiel puis saut » des chaînes à temps continu, l’écriture $G(t) = e^{tA}$, la loi d’Erlang de l’instant de la $n$-ième arrivée, la loi de Little, les indicateurs de performance de la file M/M/1, la formule d’Erlang C, ainsi que les exemples de PageRank et les simulations en Python. Aucun de ces exemples ne provient d’un TP.