Chaîne de Markov : Qu’est-ce que c’est ? À quoi ça sert ?

On dit qu’un modèle possède la propriété de Markov si son état à un instant T dépend uniquement de son état à l’instant T-1. Si on peut observer les états dans lesquels se trouve le modèle à chaque instant, on parle de modèle de Markov observable. Sinon, on parle de modèle de Markov caché. Dans cet article, nous allons illustrer ces modèles pour comprendre leur fonctionnement et leur utilité.

Définition mathématique rigoureuse

Mathématiquement, une suite de variables aléatoires (X_n) à valeurs dans un espace d’états E est une chaîne de Markov si elle vérifie la propriété de Markov faible. Cette propriété s’exprime par la relation suivante :

Pour tout n ≥ 0 et tout ensemble mesurable A ⊂ E, P(X_n+1 ∈ A | X₀, …, X_n) = P(X_n+1 ∈ A | X_n). Dans un espace d’états discret, cela revient à dire que, pour i, j ∈ E, p_ij = P(X_n+1 = j | X_n = i) ne dépend pas de n. Une chaîne est entièrement spécifiée par une loi initiale μ₀ sur E et un noyau de transition P = (p_ij)_i,j∈E stochastique par lignes.

Quels sont les éléments clés d’une chaîne de Markov ?

• Espace d’états E : ensemble fini ou dénombrable des états possibles.
• Loi initiale μ₀ : distribution de X₀ sur E.
• Noyau ou matrice de transition P : coefficients p_ij = P(X₁ = j | X₀ = i), avec p_ij ≥ 0 et ∑_j p_ij = 1 pour tout i.
• Probabilités à n pas p_ij⁽ⁿ⁾ : P(X_n = j | X₀ = i), obtenues par composition des transitions.
• Trajectoires et filtration naturelle (𝔽_n) : information disponible jusqu’au temps n pour raisonner par conditionnement.
• États particuliers : absorbants, récurrents, transients, utiles pour décrire le comportement à long terme.

Temps discret, espace d’états fini vs dénombrable : quelles différences ?

Cadre	Points clés
E fini	Matrice P de taille |E| × |E|. Il existe toujours au moins une distribution stationnaire π avec πP = π. Unicité et convergence μ0Pn → π si la chaîne est irréductible et apériodique.
E dénombrable	P est un noyau sur E. L’existence d’une distribution stationnaire n’est pas garantie. Des conditions supplémentaires sont requises, par exemple récurrence positive pour admettre une π normalisable. Les phénomènes de transience et d’explosion de temps de retour peuvent apparaître.

Dans les deux cas, la construction du modèle en temps discret repose sur μ₀ et P, mais les résultats asymptotiques et la facilité de calcul diffèrent sensiblement selon que E est fini ou simplement dénombrable.

Représentation matricielle et équations de Chapman, Kolmogorov (discrètes)

En temps discret et espace d’états discret, la dynamique se réécrit élégamment en termes de matrices et de composition des transitions, ce qui formalise l’idée que plusieurs petits pas se composent en un grand pas.

1. Matrice de transition P = (p_ij) avec p_ij = P(X_n+1 = j | X_n = i).
2. Composition des transitions (Chapman, Kolmogorov) : pour tous n, m ≥ 0, p_ij^(n+m) = ∑_k∈E p_ik⁽ⁿ⁾ p_kj^(m), soit en matriciel P^n+m = PⁿP^m.
3. Loi au temps n : μ_n = μ₀Pⁿ et, en particulier, P(X_n = j) = ∑_i μ₀(i) p_ij⁽ⁿ⁾.
4. Itérations concrètes : p_ij⁽²⁾ = ∑_k p_ik p_kj, p_ij⁽³⁾ = ∑_k,ℓ p_ik p_kℓ p_ℓj, etc.

Propriété de Markov forte : pourquoi est‑elle cruciale ?

Un temps d’arrêt T est une variable aléatoire à valeurs dans ℕ ∪ {+∞} telle que {T ≤ n} ∈ 𝔽_n pour tout n. La propriété de Markov forte affirme que, conditionnellement à {T < +∞} et à l’information 𝔽_T, le processus redémarre depuis X_T avec le même noyau P. Formellement, pour toute fonction bornée f et tout k ≥ 0, E[f(X_T+k) | 𝔽_T] = E_XT[f(X_k)].

Exemple utile : pour l’instant d’atteinte T_a = inf{n ≥ 0 : X_n = a}, la chaîne après T_a se comporte comme une chaîne neuve partant de a. Cette propriété est centrale dans les preuves de formules de probabilités d’atteinte, de temps de retour, et dans les décompositions de trajectoires par blocs indépendants.

Bref historique et innovation conceptuelle

Au tournant du XX^e siècle, Andreï Markov a étendu la loi des grands nombres à des suites dépendantes en introduisant des processus où le futur ne dépend du passé qu’via l’état courant. Cette idée simple et puissante a fourni un cadre rigoureux pour modéliser des dépendances de courte portée.

Markov a illustré son approche par l’analyse de séquences de lettres, puis le concept s’est diffusé vers de nombreux domaines scientifiques et technologiques, de l’étude des chaînes de symboles et des marches aléatoires à des applications modernes comme l’analyse de l’ADN, la modélisation d’épidémies et l’ordonnancement de pages sur le web, au cœur de la Data & IA.

Modèle de Markov observable : comment le formaliser ?

On dit qu’un modèle possède la propriété de Markov si son état à un instant T dépend uniquement de son état à l’instant T-1. Si on peut observer les états dans lesquels se trouve le modèle à chaque instant, on parle de modèle de Markov observable. Concrètement, on décrit une chaîne par un espace d’états observable E, une distribution initiale μ₀ et une matrice de transition P dont les coefficients P_ij = P(X_t+1 = j | X_t = i) sont estimés à partir des données.

• Définir E (liste finie ou dénombrable d’états observables).
• Spécifier μ₀ (probabilités au temps 0) et estimer P à partir des fréquences de passages observées.
• Vérifier les propriétés clés de P avant toute prédiction longue durée.
• Prédire une loi à l’horizon n par μ_n = μ₀Pⁿ et, si besoin, des trajectoires par simulation.

Quelles sont les propriétés de la matrice de transition ?

• Structure stochastique : P est une matrice ligne-stochastique. Pour tout état i, P_ij ≥ 0 et ∑_j P_ij = 1.
• Positivité : on a toujours P_ij ≥ 0. Si, pour un certain entier k, toutes les cases de P^k sont strictement positives, on dit que P est primitive (cas très favorable pour la convergence).
• Irréductibilité : tous les états communiquent entre eux. Formulé en graphe, le graphe orienté de P est fortement connexe. Pratiquement, cela signifie qu’il existe une probabilité non nulle d’atteindre n’importe quel état à partir de n’importe quel autre en un nombre fini d’étapes.
• Apériodicité : chaque état a une période égale à 1. Autrement dit, le plus grand commun diviseur des temps de retour possibles vers un état est 1. Astuce pratique : si P est primitive, elle est nécessairement irréductible et apériodique.

Bonnes pratiques : commencer par contrôler la stochasticité des lignes, puis examiner la structure du graphe des transitions pour repérer d’éventuelles classes fermées, et enfin tester l’apériodicité (présence d’auto-boucles P_ii > 0 ou positivité d’une puissance P^k).

Comment calculer Pⁿ ? (diagonalisation, décomposition spectrale)

1. Diagonalisation (si P est diagonalisable) : trouver P = VΛV⁻¹, alors Pⁿ = VΛⁿV⁻¹. Pratique pour des matrices de petite à moyenne taille. On rappelle que 1 est toujours une valeur propre de P et que les autres ont un module au plus 1.
2. Décomposition de Jordan (si non diagonalisable) : P = VJV⁻¹, où J est en blocs de Jordan. On obtient Pⁿ par élévation de J à la puissance n, ce qui introduit des polynômes en n multipliés par λⁿ. Utile pour une analyse fine, moins pour le calcul massif.
3. Chaînes réversibles : si P est réversible pour une distribution π, poser D = diag(π) et S = D^1/2PD^−1/2 (symétrique). On diagonalise S = QΛQ^⊤, puis Pⁿ = D^−1/2QΛⁿQ^⊤D^1/2. Cette voie est stable numériquement et clarifie la décroissance spectrale.
4. Puissances rapides et méthodes itératives : pour prédire μ_n, il est souvent plus efficace de propager un vecteur que de former Pⁿ explicitement. Utiliser l’exponentiation binaire pour Pⁿ si nécessaire, ou itérer μ_t+1 = μ_tP jusqu’à t = n. Pour de très grands espaces d’états, exploiter la parcimonie de P et des tolérances d’arrêt.

Objectif : accéder rapidement à μ_n et à des quantités d’intérêt (probabilités de ruine, temps d’atteinte, distributions d’équilibre approchées) sans surcoût inutile.

Perron, Frobenius et spectre : quel lien avec l’équilibre ?

Si P est irréductible et apériodique sur un ensemble fini, le théorème de Perron, Frobenius garantit l’existence d’un vecteur propre à composantes strictement positives associé à la valeur propre dominante 1. Ce vecteur, normalisé pour sommer à 1, est l’unique distribution stationnaire π telle que πP = π.

Le spectre de P contrôle la convergence : toutes les autres valeurs propres satisfont |λ| < 1. On a alors, pour toute distribution initiale μ₀, la convergence μ₀Pⁿ → π quand n → ∞, et la vitesse est typiquement gouvernée par l’écart spectral 1 − |λ₂|. Dans le cas primitif, Pⁿ converge vers la matrice de rang 1 dont chaque ligne est π, ce qui formalise l’équilibre à long terme.

Classification des états dans une chaîne de Markov

Dans une chaîne de Markov discrète (X_n) à valeurs dans un espace d’états E, classer les états aide à prévoir les temps d’arrêt, en particulier les temps d’entrée dans un ensemble donné et les temps de retour. La taxonomie suivante, condensée, relie immédiatement chaque type d’état aux comportements de visites et aux temps associés.

États transitoires, récurrents et absorbants

Type d’état	Intuition	Critère simple	Conséquence sur temps d’arrêt
Transitoire	On peut quitter l’état et ne jamais y revenir.	Probabilité de retour strictement inférieure à 1.	Nombre moyen de visites fini, probabilité que le temps de retour soit infini > 0.
Récurrent	On revient presque sûrement dans l’état.	Probabilité de retour égale à 1.	Temps de retour fini avec probabilité 1. Positif récurrent si l’espérance du temps de retour est finie, sinon nul récurrent.
Absorbant	Une fois entré, on n’en sort plus.	Pii = 1.	Le temps d’absorption vers cet état est un temps d’arrêt central, calculable par équations de première étape ou matrice fondamentale lorsque des états transitoires précèdent l’absorption.

Remarque pratique : dans une classe de communication irréductible, tous les états partagent la même nature de récurrence et, si elle est positive récurrente, ils admettent une distribution stationnaire π avec E_i[T_i⁺] = 1 / π_i.

Qu’est‑ce que la périodicité et pourquoi compte‑t‑elle ?

La période d’un état i est le plus grand commun diviseur des entiers n ≥ 1 tels que Pⁿ(i,i) > 0. Tous les états d’une même classe partagent la même période. Une chaîne irréductible est dite apériodique si cette période vaut 1. La périodicité conditionne la convergence des lois : en temps discret, même avec une distribution stationnaire, la chaîne peut osciller si elle est périodique, alors qu’en présence d’aperiodicité la loi de X_n converge typiquement vers π.

Exemple court : avec deux états {0,1} et P(0→1)=1, P(1→0)=1, la période est 2. La probabilité d’être en 0 alterne entre 1 et 0, il n’y a pas de convergence par n croissant.

Temps d’arrêt et temps de retour / entrée : comment les calculer ?

On note τ_A le temps d’entrée dans un ensemble cible A, et T_i⁺ le temps de premier retour à i. Ces temps se traitent efficacement par équations de première étape, qui donnent des systèmes linéaires pour les espérances cherchées.

1. Définir la cible et les conditions aux bords : pour h(i)=E_i[τ_A], poser h(a)=0 pour tout a∈A.
2. Écrire les équations de première étape : pour i∉A, h(i)=1+∑_jP_ijh(j). Résoudre le système sur les états i∉A.
3. Temps de retour : pour r(i)=E_i[T_i⁺], on peut écrire r(i)=1+∑_jP_ijh_j→i où h_j→i est l’espérance de τ_{i} en partant de j. Dans une chaîne irréductible positive récurrente, r(i)=1 / π_i.
4. Cas absorbant pratique : si l’on ordonne la matrice de transition sous la forme blocs transitoires Q puis transitions vers l’absorption R, la matrice fondamentale N=(I−Q)⁻¹ donne le temps moyen avant absorption t=N 1 et les probabilités d’absorption B=N R.
5. Contrôler l’effet de la périodicité : pour des distributions à long terme, vérifier l’aperiodicité. À défaut, interpréter les oscillations plutôt que de chercher une limite simple.

En résumé, identifier la nature des états oriente directement le calcul et l’interprétation des temps d’entrée et de retour, et la périodicité explique pourquoi certaines chaînes convergent alors que d’autres oscillent.

Distribution stationnaire et convergence vers l’équilibre

Synthèse qualitative : une chaîne de Markov converge vers l’équilibre si, quelle que soit la condition initiale, sa loi au temps n se rapproche d’une même distribution limite. Cette notion répond à la question « converge‑t‑on vers un état statistique stable » et dépend surtout de propriétés structurelles comme l’irréductibilité et l’apériodicité.

Mesure quantitative : au‑delà de l’existence d’un équilibre, on s’intéresse au rythme de convergence. On évalue « à quelle vitesse » la loi au temps n se rapproche de l’équilibre à l’aide d’une distance (variation totale) et d’indicateurs comme le temps de mélange, le spectral gap, la conductance, des couplages ou une condition de Doeblin.

Qu’est-ce qu’une distribution stationnaire ?

Définition et invariance : une distribution π sur l’espace des états est stationnaire pour une chaîne de transition P si elle vérifie l’égalité d’invariance πP = π. Autrement dit, si X₀ suit π, alors X₁, X₂, etc., suivent encore π. La stationnarité signifie que π est un point fixe de l’opérateur de transition.

Interprétation : π décrit les fréquences de visite à long terme des états lorsque la chaîne a oublié son passé. Dans un espace fini, on peut voir π comme l’équilibre statistique vers lequel la loi de X_n tend lorsque les conditions assurant l’ergodicité sont réunies.

Existence/Unicité et théorème ergodique

• Conditions structurelles (cas fini) : si la chaîne est irréductible (tout état est accessible depuis tout autre) et apériodique (le plus grand commun diviseur des longueurs de retours possibles vaut 1), alors :
  • il existe une distribution stationnaire unique π,
  • pour tout état initial x, la loi Pⁿ(x,·) converge vers π.

  Quelle convergence et à quel rythme ? (variation totale, temps de mélange)

  Distance de variation totale : pour deux lois μ et ν sur un espace fini, d_TV(μ,ν) = 1/2 ∑_x |μ(x) − ν(x)|. On mesure ainsi l’écart entre la loi au temps n, Pⁿ(x,·), et l’équilibre π.

  Temps de mélange : pour ε ∈ (0,1), le temps de mélange est t_mix(ε) = min{ n ≥ 0 : sup_x d_TV(Pⁿ(x,·), π) ≤ ε }. Il quantifie le nombre d’itérations nécessaires pour que la chaîne soit ε‑proche de l’équilibre, quel que soit le départ.

  • Qualitatif : irréductible + apériodique implique d_TV(Pⁿ(x,·), π) → 0.
  • Quantitatif : on parle de convergence géométrique si d_TV ≤ C(x)ρⁿ avec ρ < 1, de convergence polynomiale si d_TV ≤ C(x)n^−α. En pratique, on rend souvent la chaîne paresseuse (ajout d’une probabilité de rester en place) pour briser la périodicité et faciliter les bornes.

  Spectral gap, conductance, coupling et Doeblin : que mesurent‑ils ?

  Ces outils donnent des bornes explicites sur d_TV et t_mix(ε). Ils quantifient la capacité de la chaîne à « se mélanger » en contrôlant la corrélation entre états successifs ou la probabilité de traverser des goulots d’étranglement.

  Outil	Ce que cela mesure	Conséquence typique sur la vitesse
  Spectral gap 1 − λ2 (réversible)	Écart entre 1 et la seconde valeur propre de P	Si 1 − λ2 = γ > 0, alors dTV(Pn(x,·), π) ≤ C(x) e−γn
  Conductance Φ	Goulots d’étranglement entre parties de l’espace	Inégalités de type Cheeger : γ ≳ Φ2, donc mélange en O(Φ−2 log(1/ε))
  Coupling	Temps pour que deux copies se rencontrent	dTV(Pn(x,·), Pn(y,·)) ≤ ℙ(Tcouple > n), d’où des bornes directes sur tmix(ε)
  Condition de Doeblin	Minorisation uniforme P(x,·) ≥ αν(·)	Donne une contraction uniforme: dTV(Pn(x,·), π) ≤ (1 − α)n

  Existe‑t‑il un CLT pour chaînes de Markov ?

  Énoncé : sous des conditions de mélange suffisantes (par exemple chaîne finie irréductible et apériodique), pour toute fonction f telle que 𝔼_π[f] = 0 et 𝔼_π[f²] < ∞, on a un théorème central limite pour la somme additive S_n = ∑_k=1ⁿ f(X_k) :

  S_n/√n ⇒ 𝒩(0, σ_f²)
  avec variance asymptotique σ_f² = Var_π(f(X₀)) + 2 ∑_k≥1 Cov_π(f(X₀), f(X_k)).
  Découvrir notre formation en Data

  Exemple : sur une chaîne binaire irréductible et apériodique, prenez f = 𝟙{état = 1} − π(1). Alors S_n/√n converge en loi vers une normale centrée, avec σ_f² calculable à partir de la probabilité de rester dans le même état et des autocovariances géométriques.

  Réversibilité et detailed balance : à quoi ça sert ?

  Une chaîne de Markov est un processus où l’état à l’instant T dépend uniquement de l’état à l’instant T‑1. Dans ce cadre, la réversibilité et la condition d’équilibre détaillé (detailed balance) sont des outils très pratiques pour identifier la loi stationnaire π et pour analyser la vitesse de convergence vers cette loi.

  Qu’est‑ce que la detailed balance ?

  Définition: une chaîne de Markov de matrice de transition P est dite réversible par rapport à une distribution π si, pour tous états i et j, on a l’égalité locale des flux probabilistes suivante: π(i) P(i, j) = π(j) P(j, i). Cette condition est appelée équilibre détaillé. Elle implique que π est stationnaire, car en sommant sur j on obtient π(j) = ∑_i π(i) P(i, j), soit πP = π.

  Interprétation probabiliste: si l’on démarre la chaîne sous π, le flux moyen de probabilité de i vers j est exactement compensé par le flux de j vers i. Vu à l’endroit ou à l’envers, le processus a la même loi, ce qui facilite grandement les calculs et les preuves.

  Conséquences pratiques : calcul de π et exemples

  • Calcul local de π: plutôt que de résoudre tout le système πP = π, l’équilibre détaillé fournit des égalités pair à pair. Il suffit souvent de chaîner ces relations puis de normaliser.
  • Exemple 2 états: si P = [[1 − a, a], [b, 1 − b]] avec a, b dans (0, 1), l’équilibre détaillé donne π(1) a = π(2) b. Avec π(1) + π(2) = 1, on obtient directement π = ( b/(a + b), a/(a + b) ).
  • Marche aléatoire sur un graphe non orienté: si les arêtes sont symétriques, P(i, j) est proportionnelle au poids w_ij = w_ji. Alors π(i) est proportionnelle au degré pondéré d(i) = ∑_j w_ij. Autrement dit, π met plus de masse sur les sommets très connectés.
  • Chaînes naissance‑mort: avec probabilités de montée p_i et de descente q_i, l’équilibre détaillé donne la récurrence π_i+1 = π_i p_i / q_i+1, puis normalisation ∑_i π_i = 1.
  • Métropolis‑Hastings: en MCMC, on choisit une proposition q(x, y) et on accepte y avec α(x, y) = min{1, [π*(y) q(y, x)] / [π*(x) q(x, y)]}, où π* est la densité cible connue à une constante près. Cette construction satisfait l’équilibre détaillé donc a π pour loi stationnaire.

  Cas concret: pour une marche sur un graphe simple non orienté, on peut lire π en un coup d’œil: π(i) = degré(i) divisé par la somme des degrés. Cela évite tout calcul spectral et donne immédiatement la stationnarité.

  Pourquoi la réversibilité importe‑t‑elle (et ses limites) ?

  Importance: la réversibilité rend l’opérateur de transition auto‑adjoint dans L²(π), ce qui simplifie l’étude du spectre, du gap spectral et des inégalités fonctionnelles, donc l’analyse de la convergence. En pratique, c’est la raison pour laquelle beaucoup d’algorithmes MCMC standards, comme Métropolis‑Hastings ou Gibbs, sont conçus pour être réversibles.

  Se renseigner sur notre formation

  Limites: la detailed balance est suffisante pour obtenir la stationnarité, mais pas nécessaire. Des chaînes non réversibles peuvent mélanger plus vite dans certains contextes. On peut donc parfois préférer des schémas non réversibles, par exemple en ajoutant une inertie directionnelle ou en brisant la symétrie des flux, au prix d’analyses plus techniques.

  Chaînes de naissance et mort (birth, death) : pourquoi sont‑elles centrales ?

  Une chaîne de naissance et mort est une chaîne de Markov sur des entiers ordonnés, où l’on ne peut passer d’un état i qu’à i+1 (naissance) ou à i-1 (mort). Cette structure simple modélise naturellement les arrivées et départs d’une file d’attente, les pannes et réparations d’un système, ou la taille d’une population. Elle est très utilisée car elle est soluble par des relations de récurrence et des équations de bilan, ce qui donne des formules explicites et des algorithmes linéaires en taille d’état.

  En pratique, ces chaînes sont un socle de la théorie des files d’attente (par exemple le modèle M/M/1), de la fiabilité et du dimensionnement de ressources. Elles offrent un bon compromis entre réalisme et calculs maîtrisables, tout en restant dans le cadre markovien où l’état futur dépend uniquement de l’état présent.

  Pourquoi ces chaînes sont‑elles spéciales ?

  • Transitions locales uniquement : depuis i, les seules transitions possibles sont vers i+1 et i-1 avec des paramètres de naissance λ_i et de mort μ_i.
  • Matrice de transition ou générateur tridiagonale : seuls les éléments sur la sous‑, la sur‑diagonale et la diagonale sont non nuls, ce qui facilite bilans et résolutions récursives.
  • Trajectoires à pas ±1 : les chemins sont monotones pas à pas, ce qui permet des couplages monotones, des bornes et des calculs de temps de passage efficaces.
  • Interprétation immédiate en file d’attente et fiabilité : naissances = arrivées ou réparations, morts = départs ou pannes.
  • Souvent réversibles avec des lois stationnaires obtenues par produits de rapports, menant à des formules fermées et à une analyse rapide.

  Cette tridiagonalité est la raison de leur puissance : elle transforme des problèmes stochastiques globaux en équations locales sur deux voisins, que l’on peut propager sur tout l’espace d’états.

  Comment trouver la loi stationnaire ? (M/M/1)

  1. Écrire les équations de bilan détaillé. Pour un M/M/1 avec taux d’arrivée λ et de service μ, pour tout n ≥ 0 on a π_n λ = π_n+1 μ, donc π_n+1 = (λ/μ) π_n.
  2. Former le produit de rapports : π_n = π₀ ∏_k=1ⁿ (λ_k-1/μ_k). Dans M/M/1, λ_k=λ et μ_k=μ pour k≥1, d’où π_n = π₀ ρⁿ avec ρ = λ/μ.
  3. Normaliser : la somme des probabilités doit valoir 1. On obtient ρ < 1, π₀ = 1 − ρ et, pour tout n≥0, π_n = (1 − ρ) ρⁿ.
  4. Exemple concret : si λ = 2 h⁻¹ et μ = 3 h⁻¹, alors ρ = 2/3, π_n = (1/3) (2/3)ⁿ. L’espérance du nombre de clients vaut L = ρ/(1−ρ) = 2.

  Si ρ ≥ 1, la chaîne ne possède pas de loi stationnaire normalisable, ce qui traduit une file instable où la population tend à croître sans borne.

  Comment calculer les temps d’absorption ?

  On s’intéresse au temps moyen pour atteindre un ensemble absorbant A, par exemple l’état 0 ou {0, N}. Les chaînes de naissance et mort se prêtent bien aux équations de première étape, qui ne font intervenir que les voisins immédiats.

  1. Poser les quantités d’intérêt : pour chaque état transitoire i, noter m_i = E_i[T_A] et imposer les conditions aux bords m_a = 0 pour tout a ∈ A.
  2. Écrire l’équation de première étape. En temps continu avec taux λ_i et μ_i :
     • Forme probabiliste : m_i = 1/(λ_i+μ_i) + (λ_i/(λ_i+μ_i)) m_i+1 + (μ_i/(λ_i+μ_i)) m_i-1.
     • Forme générateur : −1 = λ_i(m_i+1 − m_i) + μ_i(m_i-1 − m_i).
  3. Résoudre la récurrence tridiagonale sur l’intervalle d’états concerné, avec les conditions aux bords. On peut procéder par propagation avant‑arrière ou utiliser des coefficients potentiels s_k = (λ₀⋯λ_k−1)/(μ₁⋯μ_k) pour obtenir des formules fermées.
  4. Interpréter : dans une file M/M/1 tronquée à {0,…,N} avec absorption en 0 ou N, ces équations donnent directement le temps moyen jusqu’à déplétion ou saturation, calculable en temps linéaire en N.

  Ces équations locales sont la signature des chaînes de naissance et mort : elles réduisent des temps de passage complexes à la résolution d’un système tridiagonal simple.

  Extension aux chaînes de Markov à temps continu : quand et pourquoi ?

  Rappel utile, un modèle est dit markovien lorsque l’état présent suffit à résumer le passé pour prédire l’avenir. En pratique, nombre de phénomènes évoluent en temps continu, avec des transitions qui surviennent à des instants aléatoires plutôt qu’à dates discrètes. Les chaînes de Markov à temps continu modélisent précisément ces systèmes, par exemple des files d’attente, des populations qui naissent et meurent, ou des systèmes de fiabilité.

  Le cœur du formalisme continu repose sur un opérateur linéaire appelé générateur infinitésimal, qui encode les taux instantanés de saut entre états. Couplé aux équations de Kolmogorov, il permet de décrire la dynamique complète des probabilités de transition et d’accéder aux distributions transitoires et stationnaires.

  Qu’est‑ce que le générateur infinitésimal ?

  Considérons une chaîne de Markov à temps continu sur un espace d’états dénombrable E, de matrice des probabilités de transition P(t) = [p_ij(t)]. Son générateur infinitésimal est la matrice Q = [q_ij] définie, pour i ≠ j, par des taux q_ij ≥ 0 décrivant la vitesse instantanée de passage de i vers j, et par des diagonales q_ii = −∑_j≠i q_ij. Les lignes de Q somment à zéro, ce qui garantit la conservation de la masse de probabilité.

  Lien avec la dynamique, la famille (P(t))_t≥0 forme un semi-groupe vérifiant P(0) = I et P(t + s) = P(t)P(s). Elle est reliée au générateur par l’exponentielle de matrices, P(t) = exp(tQ) = ∑_n≥0 (tⁿ/n!) Qⁿ, qui est la solution unique des équations différentielles ci‑dessous avec condition initiale P(0) = I.

  Équations de Kolmogorov forward/backward

  • Équations de Kolmogorov forward pour P(t) = [p_ij(t)] : d/dt p_ij(t) = ∑_k∈E p_ik(t) q_kj, soit en forme matricielle P′(t) = P(t)Q avec P(0) = I.
  • Équations de Kolmogorov backward : d/dt p_ij(t) = ∑_k∈E q_ik p_kj(t), soit QP(t) = P′(t) avec P(0) = I.

  Ces équations maîtresses décrivent l’évolution temporelle des probabilités de transition et fournissent la base du calcul transitoire, de l’approximation numérique et de nombreuses mesures de performance. Elles sont cohérentes entre elles car la solution commune est précisément P(t) = exp(tQ).

  Découvrir le métier de Data Scientist

  Exemple concret : M/M/1 et stationnarité

  Cas canonique de file d’attente, le processus M/M/1 a pour états E = {0, 1, 2, …} représentant le nombre de clients dans le système. Les arrivées suivent un processus de Poisson de taux λ, les services sont exponentiels de taux μ, un seul serveur. Le générateur Q est tridiagonal avec q_n,n+1 = λ pour tout n ≥ 0, q_n,n−1 = μ pour n ≥ 1, q_nn = −(λ + μ) pour n ≥ 1, et q₀₀ = −λ.

  Critère de stabilité, si ρ = λ/μ < 1, il existe une distribution stationnaire géométrique π telle que π_n = (1 − ρ) ρⁿ pour n ≥ 0. Dans ce régime, le nombre moyen de clients vaut E[N] = ρ/(1 − ρ), et les autres indicateurs usuels (temps moyen dans le système, longueur moyenne de file) s’en déduisent. Si ρ ≥ 1, il n’y a pas de stationnarité, la file diverge en moyenne. Les distributions transitoires à temps fini s’obtiennent via P(t) = exp(tQ) ou par des méthodes numériques dédiées.

  Méthodes de Monte-Carlo par chaînes de Markov (MCMC)

  Idée générale. Les méthodes MCMC servent à échantillonner une loi complexe en construisant une chaîne de Markov qui l’explore. On dit qu’un modèle possède la propriété de Markov si son état à un instant T dépend uniquement de son état à l’instant T-1. Ici, on fabrique une telle chaîne dont la distribution cible π est invariante par la transition. En laissant tourner la chaîne assez longtemps, les fréquences empiriques approchent les probabilités de π et permettent de calculer des espérances par moyennes d’échantillons corrélés.

  En pratique. On se contente souvent d’évaluer la densité de π à une constante près (par exemple une postérieure bayésienne non normalisée). Les algorithmes MCMC proposent des déplacements dans l’espace des paramètres et acceptent ou rejettent ces propositions de sorte que π reste stationnaire. La clé du succès tient à un bon diagnostic de convergence et à un réglage soigné du schéma de proposition.

  Quel est le principe du MCMC ?

  Invariance. Une chaîne de Markov de noyau de transition P admet π pour distribution invariante si πP = π. Autrement dit, si Xt suit π, alors Xt+1 suit aussi π après une étape de la chaîne. Les algorithmes MCMC construisent P pour garantir cette invariance, souvent via la condition de balance détaillée π(x)P(x, y) = π(y)P(y, x).

  Ergodicité. Si la chaîne est irréductible, apériodique et récurrente positive, elle est ergodique. Cela implique que, quel que soit le point de départ, la loi de Xt converge vers π quand t augmente, et que les moyennes de Monte-Carlo corrélées 1/T ∑t f(Xt) convergent vers Eπ[f]. En MCMC, on exploite cette ergodicité pour estimer des quantités d’intérêt même quand l’échantillonnage indépendant direct est impossible.

  Metropolis-Hastings et Gibbs : quand les utiliser ?

  Algorithme	Principe	Atouts	Limites	Quand le privilégier
  Metropolis-Hastings	Proposer y ∼ q(y|x), accepter avec probabilité α(x, y) = min{1, π(y)q(x|y) / [π(x)q(y|x)]}	Polyvalent, fonctionne avec π non normalisée, simple à implémenter	Nécessite un bon choix de q et d’échelle, autocorrélation possible si réglage inadéquat	Cibles continues ou mixtes, modèles en boîte noire où seules les densités non normalisées sont accessibles
  Gibbs	Échantillonnage séquentiel depuis les conditionnelles complètes p(θi|θ-i)	Taux d’acceptation de 1, souvent facile en modèles conjugués, pas de réglage d’échelle	Nécessite des conditionnelles simulables, peut mélanger lentement si fortes corrélations	Modèles hiérarchiques avec conditionnelles connues, structures conjuguées, mises à jour par blocs

  Comparaison. Metropolis-Hastings est un couteau suisse qui exige de calibrer une distribution de proposition. Gibbs est idéal quand les conditionnelles complètes sont disponibles ou faciles à simuler, éventuellement par blocs pour réduire les corrélations. Des schémas hybrides combinent les deux, par exemple Gibbs avec étapes Metropolis-Hastings imbriquées pour les composantes sans conditionnelle fermée.

  Se former à la Data et à l’IA

  Diagnostics et tuning : burn-in, ESS, autocorrélation, taux d’acceptation

  • Burn-in ou échauffement: ignorer les premières itérations avant la stationnarité. Règle pratique, ajuster après inspection des traces, souvent quelques centaines à quelques milliers d’itérations selon le modèle.
  • Ess Effective Sample Size (ESS): mesure la taille d’échantillon indépendant équivalente. Viser un ESS suffisant par paramètre, par exemple plusieurs centaines pour des résumés stables. Améliorer ESS en réduisant l’autocorrélation par un meilleur réglage ou une reparamétrisation.
  • Autocorrélation: examiner ACF et temps d’intégrée. Une décroissance lente signale un mélange insuffisant. Augmenter l’échelle des déplacements n’est pas toujours bénéfique, privilégier des propositions informées ou des mises à jour par blocs.
  • Taux d’acceptation: pour un random-walk Metropolis, viser souvent une fourchette autour de 20 % à 40 % en dimension modérée. Des taux trop faibles indiquent des pas trop grands, des taux trop élevés indiquent des pas trop petits et donc une forte autocorrélation.
  • Plusieurs chaînes et R̂: lancer plusieurs chaînes depuis des points dispersés. Un R chapeau proche de 1 et des traces qui se mélangent bien sont des signaux positifs.
  • Thinning: rarement nécessaire. Préférer augmenter la durée de la chaîne et améliorer le mélange plutôt que d’écrémer.
  • Reparamétrisation: transformer des paramètres contraints (log, logit) et centrer-réduire ou non centrer les effets hiérarchiques pour accélérer le mélange.
  • Contrôles de stabilité: comparer résumés entre segments tardifs de la chaîne, vérifier la sensibilité à l’initialisation et au pas de proposition.

  Comment simuler et implémenter efficacement ?

  1. Initialisation: choisir des points de départ plausibles. Utiliser des estimations rapides (MAP approximatif, moindres carrés) ou des tirages larges mais compatibles avec les contraintes.
  2. Choix du schéma: Gibbs si les conditionnelles sont disponibles, Metropolis-Hastings sinon, éventuellement par blocs ou avec propositions adaptatives pendant l’échauffement.
  3. Échelle et propositions: pour un random-walk, ajuster l’écart type pour atteindre la cible d’acceptation. En forte corrélation, utiliser des propositions anisotropes ou informées par une matrice de covariance estimée.
  4. Transformations: travailler sur des espaces non contraints via des transformations bijectives et corriger par le jacobien si nécessaire.
  5. Vectorisation et calculs stables: opérer sur les log-densités, éviter les underflows, mettre en cache les termes invariants.
  6. Parallélisation: lancer plusieurs chaînes en parallèle pour diagnostics et ESS total, paralléliser l’évaluation de la vraisemblance quand c’est possible.
  7. Traçage et sauvegarde: enregistrer traces, acceptations, ACF, et des résumés périodiques. Surveiller en direct pour ajuster l’échauffement.
  8. Pièges courants: chaîne piégée dans un mode, proposition trop locale, paramètres mal échelonnés, contraintes non respectées, sur-thinning. Répondre par reparamétrisation, propositions plus globales, recuit si nécessaire, et contrôles de validité.

  Rappel fondamental sur la propriété de Markov. Mathématiquement, une suite de variables aléatoires (Xn) à valeurs dans un espace d’états E est une chaîne de Markov si, pour chaque n, la loi de Xn+1 ne dépend que de Xn. C’est précisément cette propriété qui permet d’itérer efficacement les algorithmes MCMC tout en garantissant l’invariance de la cible.

  Modèles de Markov cachés (HMM) : comment ça marche ?

  On dit qu’un modèle possède la propriété de Markov si son état à un instant T dépend uniquement de son état à l’instant T-1. Si on peut observer les états dans lesquels se trouve le modèle à chaque instant, on parle de modèle de Markov observable. Sinon, on parle de modèle de Markov caché. Les HMM modélisent donc une dynamique d’états non observables, tout en expliquant une suite d’observations visibles générées par ces états. Cette idée simple permet d’analyser des séquences où la cause est cachée et seul l’effet est mesuré.

  En pratique, un HMM repose sur trois briques: une chaîne d’états cachés, un mécanisme de génération des observations et un petit nombre de matrices de probabilités. Les tâches usuelles consistent à évaluer la vraisemblance d’une séquence, à décoder la suite d’états la plus probable et à apprendre les paramètres du modèle à partir de données.

  Se former à la Data Science

  Structure mathématique d’un HMM

  Un HMM décrit deux processus: une suite d’états cachés X_1:T prenant des valeurs dans un ensemble fini S, et une suite d’observations O_1:T. Le modèle est paramétré par λ = (A, B, π), sous hypothèse de Markov d’ordre 1 pour les états et d’indépendance conditionnelle des observations sachant l’état courant.

  • États cachés: ensemble fini S = {s₁, …, s_N}.
  • Observations: symboles discrets {v₁, …, v_M} ou variables continues (densités d’émission).
  • Matrice de transition A, avec A_ij = P(X_t = s_j | X_t-1 = s_i).
  • Émissions B: pour le cas discret, B_j(k) = P(O_t = v_k | X_t = s_j); pour le cas continu, une densité p(O_t | X_t = s_j).
  • Distribution initiale π, avec π_i = P(X₁ = s_i).

  Quels sont les trois problèmes fondamentaux ?

  1. Évaluation: calculer P(O_1:T | λ), la vraisemblance d’une séquence d’observations donnée le modèle.
  2. Décodage: trouver la suite d’états cachés la plus probable X̂_1:T compte tenu des observations et du modèle.
  3. Apprentissage: estimer les paramètres λ = (A, B, π) à partir de données, avec ou sans étiquettes d’états.

  Résoudre ces problèmes permet de noter la qualité d’ajustement d’un HMM à des données, d’expliquer une séquence par des états latents plausibles et d’entraîner automatiquement le modèle quand les paramètres sont inconnus.

  Algorithmes clés : forward-backward, Viterbi, Baum-Welch (EM)

  • Forward-backward: dynamique probabiliste avant et arrière pour calculer efficacement P(O_1:T | λ) et les postérieurs sur les états P(X_t | O_1:T, λ). Complexité typique O(N²T), avec normalisations ou calculs en log pour la stabilité numérique.
  • Viterbi: programmation dynamique qui maximise la probabilité du chemin d’états, en stockant les meilleurs prédécesseurs et en reconstituant la trajectoire optimale à la fin.
  • Baum-Welch: algorithme EM pour l’apprentissage non supervisé. Étape E: utiliser forward-backward pour obtenir les comptages attendus de transitions et d’émissions. Étape M: mettre à jour A, B, π par normalisation de ces comptages, jusqu’à convergence de la vraisemblance.

  En pratique, bien initialiser les paramètres (par exemple via k-means sur les observations, heuristiques métier ou multiples redémarrages) aide à éviter des optima locaux. Régulariser les probabilités, choisir des émissions adaptées (discrètes, gaussiennes, mélanges) et contrôler la taille N rendent l’entraînement plus robuste.

  Comment appliquer un HMM en pratique ? (exemples)

  Exemples typiques: en reconnaissance de la parole, les états peuvent représenter des unités phonétiques et les observations des vecteurs acoustiques; en étiquetage morpho-syntaxique, les états correspondent aux catégories grammaticales et les observations aux mots de la phrase.

  • Quand choisir un HMM: dépendance de court terme plausible, processus latent discret, besoin d’un modèle probabiliste interprétable.
  • Type d’émission: symboles discrets si vocabulaire limité, distributions continues ou mélanges gaussiens si les observations sont numériques.
  • Taille du modèle: sélectionner N selon la granularité souhaitée puis valider par vraisemblance sur jeu de validation et critères d’information (AIC, BIC).
  • Données disponibles: apprentissage supervisé si les états sont annotés, EM sinon; veiller à la quantité et à la qualité des séquences.
  • Alternatives: si les hypothèses de Markov et d’indépendance conditionnelle sont trop restrictives, envisager des CRF pour l’étiquetage discriminant ou des réseaux récurrents pour des dépendances plus longues.

  Chaînes de Markov dans l’écosystème de la data science moderne

  On dit qu’un modèle possède la propriété de Markov si son état à un instant T dépend uniquement de son état à l’instant T‑1. Quand les états sont observables, on parle de chaîne observable, sinon de modèle de Markov caché. Dans la data science, ces modèles servent à décrire des séquences, à prévoir l’étape suivante et à détecter des changements de comportement.

  • NLP et traitement de texte: modélisation de suites de mots avec n‑grammes, étiquetage grammatical, segmentation et alignement via modèles cachés.
  • Recommandation: prédiction du prochain clic ou de la prochaine catégorie consultée en fonction du parcours utilisateur.
  • IoT et maintenance: enchaînement d’états discrets ou de régimes cachés pour détecter des pannes et anticiper les dérives.
  • Cybersécurité et fraude: score d’anomalie sur des séquences d’événements et détection de changements de régime.
  Formation Data Scientist certifiante

  Où interviennent les chaînes de Markov en NLP ?

  • N‑grammes: un modèle de trigrammes estime P(mot_t | mot_t‑2, mot_t‑1) comme une chaîne d’ordre fini. Utile pour l’autocomplétion, la correction et la modélisation de langue de base.
  • Tagging (étiquetage morpho‑syntaxique): modèles de Markov cachés avec états cachés = étiquettes (NOM, VERB, ADJ), observations = mots. Décodage typique par Viterbi.
  • Segmentation: séparation de mots en langues sans espaces, segmentation syllabique ou en sous‑mots, alignement mot‑phonème avec HMM.
  • Détection de langue et normalisation: enchaînements de caractères n‑grammes pour estimer la vraisemblance d’un texte.

  Exemple bref: dans la séquence « il fait très », un modèle de trigrammes donnera une probabilité plus élevée à « chaud » qu’à « parapluie », car les transitions observées dans le corpus favorisent « très → chaud ».

  Peut‑on modéliser des recommandations avec Markov ?

  Oui. On peut représenter un parcours utilisateur comme une suite d’états (page, catégorie produit, étape d’entonnoir). La matrice de transition capture la probabilité de passer d’un état à un autre. On prédit ainsi la prochaine action, on calcule des chemins probables vers la conversion et on simule l’impact d’un changement d’interface.

  • Définir les états: catégories produit, niveaux d’engagement, étapes tunnel (visite, ajout panier, paiement).
  • Estimer les transitions: à partir de sessions, avec pondération temporelle pour refléter des goûts récents.
  • Personnaliser: chaînes par segment ou par utilisateur, ou modèles d’ordre variable pour tenir compte d’un peu plus d’historique.
  • Next‑best‑action: recommander la catégorie la plus probable ou l’offre qui mène au chemin avec la meilleure valeur attendue.
  • Mesure: comparer taux de conversion simulés, temps d’absorption vers un état cible, ou divergence entre matrices avant et après un test A/B.

  Comment modéliser des séries IoT ?

  Les capteurs produisent des séquences corrélées dans le temps. On peut discrétiser les mesures en états (bas, normal, élevé) et construire une chaîne observable, ou bien introduire des régimes cachés avec un HMM: états cachés = modes de fonctionnement (sain, déréglé, défaillance imminente), observations = mesures continues modélisées par des lois appropriées.

  Exemple: pour un moteur, on suit vibration et température. Un HMM à trois régimes apprend que le régime « déréglé » augmente la probabilité de passer à « défaillance imminente ». En ligne, le filtrage met à jour les probabilités de régime; si la probabilité du régime critique dépasse un seuil, une alerte maintenance est déclenchée, ce qui réduit les faux positifs par rapport à un simple seuil fixe.

  Cybersécurité et détection de fraudes : quels cas typiques ?

  Les séquences d’événements (logins, appels API, transactions) se prêtent bien aux chaînes de Markov. On apprend un modèle sur du comportement non frauduleux, puis on signale les séquences dont la probabilité est anormalement faible ou dont le régime latent bascule vers un état « compromis ».

  • Fraude carte et e‑commerce: enchaînement inhabituel de montants, pays, canaux, ou terminaux.
  • Account takeover: transitions rares entre étapes d’authentification, empreintes d’appareils et localisations.
  • Réseaux et endpoints: succession de ports, protocoles ou commandes système signalant une exfiltration de données.
  • APIs et microservices: pattern d’appels qui diverge du graphe de transitions attendu après déploiement.
  • Mise en production: score d’anomalie via log‑vraisemblance, détection de changement de régime, seuils calibrés pour contrôler le taux de faux positifs.

  Applications concrètes des chaînes de Markov

  On dit qu’un modèle possède la propriété de Markov si son état à un instant T dépend uniquement de son état à l’instant T-1. Cette idée simple se retrouve dans de nombreux domaines appliqués, en dehors de la seule data science, par exemple dans le classement du Web, la finance et l’assurance, la bioinformatique, ou encore les files d’attente et la fiabilité industrielle.

  Découvrir le métier de Data Scientist

  Pourquoi PageRank est‑il une chaîne de Markov ?

  PageRank modélise le comportement d’un surfeur aléatoire qui se trouve sur une page et qui, à l’étape suivante, suit au hasard l’un des liens sortants de cette page. L’état du système est donc la page courante, et la probabilité de passer à la page suivante ne dépend que de cette page en cours, ce qui en fait une chaîne de Markov sur l’ensemble des pages. Pour éviter les impasses et garantir l’ergodicité, le surfeur “téléporte” avec une probabilité 1 − α vers n’importe quelle page (par exemple α autour de 0,85), ce qui ajoute une petite probabilité de transition vers tous les états et assure l’existence d’une distribution stationnaire unique.

  Exemple bref : si une page A pointe vers B et C, alors la probabilité de passer de A à B ou C est 1/2 chacune, puis, avec téléportation, on mélange ces probabilités avec la distribution uniforme sur toutes les pages du site. La distribution stationnaire de cette chaîne fournit le score PageRank, interprété comme le temps long passé sur chaque page par le surfeur.

  Finance et assurance : quels modèles Markoviens ?

  • Matrices de transition de crédit : modéliser la migration des notations (AAA, AA, A, BBB, …, défaut) d’une période à l’autre, estimer les probabilités de défaut à horizon 1, 3 ou 5 ans, simuler des trajectoires de portefeuille.
  • Tarification et gestion du risque de crédit : valoriser des obligations d’entreprises ou des dérivés de crédit en combinant taux sans risque et chaîne de Markov des notations, calculer pertes attendues et inattendues.
  • Bonus‑malus en assurance auto : transitions annuelles entre classes de coefficient selon le sinistre observé, optimisation des primes et de l’équilibre technique.
  • Modèles multi‑états en assurance vie et prévoyance : transitions vivant, invalide, décédé, ou autonome, dépendant, décédé, pour tarifier rentes et contrats dépendance.
  • Régimes de marché : chaînes cachées pour représenter alternance de phases calmes et volatiles, aide à l’allocation et au pilotage du risque.

  En pratique, un analyste construit une matrice de transition annuelle à partir d’historiques de notations, l’élève à la puissance n pour obtenir les transitions à n ans, puis en déduit les probabilités cumulées de défaut et les provisions attendues d’un portefeuille de prêts. En assurance vie, les tables de passage entre états servent directement au calcul des primes et des réserves.

  Bioinformatique et génétique

  • Alignement et annotation de séquences : les modèles de Markov cachés (HMM) décrivent les régions codantes et non codantes, détectent exons et introns.
  • Motifs et familles de protéines : profils HMM pour repérer des motifs conservés et classer des séquences dans des familles.
  • Processus évolutifs : modèles de substitution nucléotidique ou protéique (par exemple Jukes‑Cantor, Kimura) pour estimer distances évolutives et reconstruire des phylogénies.

  Exemple bref : un HMM entraîné sur des gènes connus d’une bactérie peut parcourir un nouveau génome et produire, état par état, la probabilité d’être en région codante, ce qui guide l’annotation automatique et l’extraction des cadres de lecture.

  Théorie des files d’attente et fiabilité industrielle

  Les files d’attente classiques s’appuient sur des processus naissance‑mort markoviens : arrivées de clients de type Poisson, durées de service exponentielles. Les modèles M/M/1, M/M/c ou M/M/∞ fournissent des métriques clés comme le temps d’attente moyen, la longueur moyenne de file, le taux d’occupation, utiles pour dimensionner centres d’appels, serveurs et ateliers. En fiabilité, des chaînes à deux états fonctionnement, panne permettent de calculer disponibilité et temps moyen de bon fonctionnement, avec extensions à plusieurs composants et maintenance préventive.

  Cas concret : pour un centre de contacts estimant 60 appels par heure et 6 conseillers servis à 12 appels par heure chacun, un modèle M/M/6 permet d’évaluer la probabilité d’attente, d’ajuster le nombre d’agents et de respecter un objectif de délai moyen de réponse.

  Exercices pratiques pour maîtriser les chaînes de Markov

  On dit qu’un modèle possède la propriété de Markov si son état à un instant T dépend uniquement de son état à l’instant T-1. Les exercices suivants reprennent des classiques et ajoutent la ruine du joueur pour travailler les hitting times, la réversibilité, la convergence et les aspects spectraux.

  Se former à la Data et à l’IA

  Exercice : urne d’Ehrenfest

  Modèle. On répartit N particules entre deux urnes A et B. À chaque pas, on choisit uniformément une particule et on la déplace dans l’autre urne. La chaîne s’écrit sur X_n, le nombre de particules dans A au temps n. Les probabilités de transition sont P(k → k+1) = (N − k)/N et P(k → k−1) = k/N pour k ∈ {0,…,N}.

  • Réversibilité. Montrer que la loi stationnaire π(k) = 2^−N C(N,k) vérifie l’équilibre détaillé π(k) P(k → k+1) = π(k+1) P(k+1 → k).
  • Convergence. Partant de X₀ = k₀, vérifier numériquement que la loi de X_n converge vers π, par exemple via la distance en variation totale.
  • Exploration. Étudier l’influence de N sur la vitesse de convergence et observer le rôle de la symétrie autour de N/2.

  Exercice : marche aléatoire sur un graphe

  Modèle. Soit G un graphe non orienté, connexe, sans boucle multiple. La marche simple part d’un sommet i et, à chaque pas, se déplace vers un voisin j choisi uniformément. La matrice de transition est P(i,j) = 1/deg(i) si {i,j} est une arête, sinon 0.

  Données et preuves utiles.

  • Distribution stationnaire. Prouver la réversibilité avec π(i) proportionnelle au degré: π(i) = deg(i)/(2m), où m est le nombre d’arêtes.
  • Périodicité. Définir la période d’un sommet comme le plus grand commun diviseur des temps de retour possibles. Montrer qu’un graphe biparti induit une période 2 et qu’une marche paresseuse (ajout d’une probabilité α de rester sur place) rend la chaîne apériodique.
  • Propriétés spectrales. Étudier le spectre de P: 1 = λ₁ ≥ λ₂ ≥ … ≥ λ_n ≥ −1. Relier l’écart spectral 1 − λ₂ à la vitesse de mélange. Cas réguliers: si G est d-régulier, alors π est uniforme.
  • Travaux dirigés. Calculer π, la période et λ₂ pour le cycle C_n et pour le graphe complet K_n. Comparer les vitesses de convergence avec et sans marche paresseuse.

  Exercice : ruine du joueur (hitting times)

  1. Cadre. Capital entre 0 et N. À chaque coup, +1 avec probabilité p, −1 avec probabilité q = 1 − p. Les états 0 et N sont absorbants.
  2. Probabilité de ruine ou de gain. Poser h_i = P_i(atteindre N avant 0). Équations de première étape: h₀ = 0, h_N = 1, et pour 1 ≤ i ≤ N−1, h_i = p h_i+1 + q h_i−1. Solution: si p = q = 1/2, h_i = i/N. Si p ≠ q, h_i = [1 − (q/p)ⁱ] / [1 − (q/p)^N].
  3. Durée attendue jusqu’à l’absorption. Poser t_i = E_i[T], T étant le premier instant d’absorption. Équations: t₀ = 0, t_N = 0, et pour 1 ≤ i ≤ N−1, t_i = 1 + p t_i+1 + q t_i−1. Solutions classiques: si p = q = 1/2, t_i = i(N − i). Si p ≠ q, t_i = [i/(q − p)] − [N/(q − p)] · [1 − (q/p)ⁱ] / [1 − (q/p)^N].
  4. Pratique. Vérifier numériquement ces formules par simulation pour différents N et biais p. Observer l’asymétrie des hitting times lorsque p s’éloigne de 1/2.

  Exercice : temps d’absorption

  1. Identifier une chaîne absorbante. Réordonner les états pour écrire la matrice de transition sous forme canonique P = [ Q R ; 0 I ], avec Q pour les états transitoires et I pour les états absorbants.
  2. Calculs clés. La matrice fondamentale est N = (I − Q)⁻¹. Le vecteur des temps moyens d’absorption est t = N 1, où 1 est le vecteur de uns. Les probabilités d’absorption dans chaque état absorbant sont données par B = N R.
  3. Application guidée. Construire Q et R pour une petite chaîne avec deux états transitoires et un état absorbant. Calculer N, puis t et B. Interpréter: t mesure le nombre moyen de visites transitoires avant absorption, B la répartition des issues possibles.
  4. Aller plus loin. Comparer avec la ruine du joueur en identifiant Q, R et en retrouvant t_i et h_i via la méthode matricielle.

  Aspects numériques et simulation : par où commencer ?

  En pratique, la propriété de Markov rappelée plus haut implique que la simulation ne dépend que de l’état courant et de la matrice de transition. Voici une feuille de route concrète pour passer de la théorie au code, assurer la reproductibilité et éviter les pièges numériques les plus courants.

  Se former à la Data Science

  Comment simuler une chaîne ? (pseudo‑code/Python)

  1. Définir l’espace des états E et la matrice de transition P de taille |E| × |E|, avec des lignes stochastiques (chaque ligne somme à 1, valeurs dans [0,1]).
  2. Choisir une loi initiale π₀ sur E, ou un état initial x₀ tiré selon π₀.
  3. Pour t de 1 à T, échantillonner X_t depuis la ligne de P correspondant à X_t−1, puis stocker la trajectoire.
  4. Option utile pour la reproductibilité : fixer une graine aléatoire, enregistrer les versions des bibliothèques et, si besoin, répéter N trajectoires indépendantes pour estimer des moyennes.
  5. Contrôles rapides : vérifier que les fréquences empiriques restent cohérentes, et que les lignes de P sont toujours stochastiques après toute transformation.

  Calcul de Pⁿ/exponentiation : quelles méthodes pratiques ?

  • Puissances répétées par dichotomie (exponentiation rapide) : pour obtenir Pⁿ, factoriser n en base 2 et multiplier seulement les puissances nécessaires. Complexité en O(log n) multiplications de matrices. Adapté aux matrices denses de taille petite à moyenne.
  • Application à un vecteur sans former Pⁿ : pour π₀Pⁿ ou Pⁿv, appliquer P de façon répétée avec dichotomie sur des vecteurs. Évite les coûts mémoire et peut rester creux si P est clairsemée.
  • Diagonalisation quand c’est possible : si P = VDV⁻¹ avec D diagonale, alors Pⁿ = VDⁿV⁻¹. Utile pour analyser la convergence et accélérer certains calculs, mais sensible aux matrices mal conditionnées et aux valeurs propres complexes. À réserver aux tailles modestes.
  • Méthodes de Krylov (Arnoldi, Lanczos) : efficaces pour calculer Pⁿv ou u^⊤Pⁿ sans former Pⁿ, surtout en grand dimension et en creux, via des opérateurs linéaires. Donnent aussi accès aux valeurs propres dominantes.
  • Grand n et comportement asymptotique : pour des chaînes ergodiques, π₀Pⁿ converge vers la loi stationnaire π. Plutôt que de calculer Pⁿ, on peut estimer π par itérations π_k+1 = π_kP jusqu’à convergence, ou par vecteur propre associé à la valeur propre 1.
  • Matrices creuses : éviter la densification involontaire pendant les multiplications. Privilégier les formats creux et les produits matrice‑vecteur successifs.

  Quelles bibliothèques utiliser (Python/R/Julia) ?

  • Python :
    • NumPy et SciPy : produits matrice‑vecteur, valeurs propres, formats clairsemés et opérateurs linéaires.
    • NetworkX : construction de matrices de transition à partir de graphes, mesures sur les chaînes issues de graphes.
    • hmmlearn et pomegranate : modèles de Markov cachés et chaînes enrichies.
    • PyMC ou Stan via cmdstanpy : inférence bayésienne de chaînes et HMM, estimation de paramètres et incertitude.
    • Numba/JAX : accélération des boucles de simulation et différentiation automatique si nécessaire.
    • markovchain et Matrix : manipulation de chaînes finies, puissances, formats creux.
    • depmixS4 et msm : HMM et modèles multi‑états en temps discret ou continu.
    • rstan ou cmdstanr : modélisation bayésienne de chaînes et HMM.
    • igraph : graphes et transitions induites.
    • Distributions.jl et SparseArrays : tirages efficaces et calculs en creux.
    • MarkovChains.jl : utilitaires pour chaînes finies.
    • HiddenMarkovModels.jl et HMMBase.jl : HMM en Julia.
    • Graphs.jl : graphes et matrices d’adjacence pour construire P.

    Stabilité numérique : quels pièges éviter ?

    • Vérification de stochasticité : après chaque opération, s’assurer que chaque ligne de P est dans [0,1] et somme à 1 à une tolérance près, puis renormaliser si nécessaire.
    • Underflow en produits de probabilités : dans les algorithmes avant‑arrière des HMM, travailler en log‑probabilités et utiliser log‑sum‑exp ou introduire des facteurs d’échelle à chaque pas.
    • Overflow et perte de précision : éviter de former explicitement Pⁿ pour de grands n, préférer les itérations sur vecteurs. Utiliser float64 et surveiller le conditionnement lors des diagonalisation et inversions.
    • Densification des matrices creuses : les multiplications denses détruisent l’épargne mémoire et temps de calcul. Rester en formats creux et privilégier les produits matrice‑vecteur.
    • Contrôles d’intégrité : clipper les valeurs négatives dues aux erreurs d’arrondi, réimposer des sommes de lignes unitaires, poser des assertions dans les boucles de simulation.
    • Reproductibilité : fixer la graine aléatoire, consigner les versions logicielles, et si des résultats strictement déterministes sont requis, limiter le parallélisme qui peut réordonner les réductions numériques.

    Pour aller plus loin : références essentielles

    Une curation courte et à jour pour approfondir les chaînes de Markov, leurs variantes cachées et leurs applications, avec l’accent sur des classiques solides et des ressources pratiques.

    Formation Data Scientist certifiante

    Ouvrages de référence fondamentaux

    • J. R. Norris, Markov Chains (Cambridge University Press, 1998).
    • D. A. Levin, Y. Peres, E. L. Wilmer, Markov Chains and Mixing Times, 2e éd. (American Mathematical Society, 2017).
    • S. P. Meyn, R. L. Tweedie, Markov Chains and Stochastic Stability, 2e éd. (Cambridge University Press, 2009).
    • J. G. Kemeny, J. L. Snell, Finite Markov Chains (Springer, éd. classique).
    • D. Aldous, J. A. Fill, Reversible Markov Chains and Random Walks on Graphs (manuscrit en libre accès).

    Spécialisation par domaines d’application

    • Files d’attente et réseaux : F. P. Kelly, Reversibility and Stochastic Networks ; S. Asmussen, Applied Probability and Queues.
    • Finance et séries temporelles : J. D. Hamilton, Time Series Analysis (régimes de Markov) ; R. J. Elliott, L. Aggoun, J. B. Moore, Hidden Markov Models: Estimation and Control.
    • Bioinformatique : R. Durbin, S. Eddy, A. Krogh, G. Mitchison, Biological Sequence Analysis (HMM pour ADN/ protéines).

    Articles fondateurs historiques

    • A. A. Markov, 1906 : extension de la loi des grands nombres à des variables dépendantes.
    • A. A. Markov, 1913 : analyse statistique des lettres de Eugène Onéguine pour illustrer les chaînes.
    • S. Chapman, 1928, et A. N. Kolmogorov, 1931 : équations de Chapman‑Kolmogorov et formalisme des processus de Markov en temps continu.
    • J. L. Doob, 1953 : structuration moderne des processus stochastiques et des martingales.

    Ces jalons donnent le contexte historique et théorique qui sous‑tend les développements modernes, des marches aléatoires aux modèles cachés en pratique.

    Ressources pédagogiques complémentaires

    • P.-L. Méliot, Notes de cours agrégation : Chaînes de Markov (Université Paris‑Saclay).
    • P. Delmas, Modèles stochastiques (CERMICS, École des Ponts).
    • Bibmath : entrée Chaîne de Markov pour un rappel clair et progressif.
    • APMEP : introduction lycée, utile pour une première prise en main.
    • Supports en ligne complémentaires : LaBRI, processus stochastiques ; Université Lyon 1, polycopiés sur Claroline.

    Ressources numériques modernes

    • Bibliothèques Python : hmmlearn et pomegranate pour HMM et modèles graphiques ; NetworkX pour marches aléatoires sur graphes.
    • R : package markovchain pour chaînes finies ; package HMM pour modèles cachés.
    • Notebooks : tutoriels HMM et chaînes de Markov sur Jupyter, avec jeux de données jouets pour la convergence, le calcul des distributions stationnaires et le filtrage de type forward‑backward.
    • Datasets : corpus textuels libres (Gutenberg) pour modéliser des séquences symboliques ; bases protéiques comme Pfam pour expérimenter l’apprentissage de profils HMM.
    Maîtriser les modèles de Markov