Paramètres
Actions
Options d'Affichage
Éditeur de Matrice de Transition
Chaque ligne doit sommer à 1.0 (matrice stochastique)
Distribution de Probabilité
Convergence vers Distribution Stationnaire
Analyse Mathématique
Distribution Actuelle p_t
Distribution Stationnaire π
π satisfait π = πP
Valeurs Propres de P
λ₁ = 1 est garanti pour les matrices stochastiques
Propriétés de la Chaîne
Estimation du Temps de Mélange
Pas pour atteindre une distance ε = 0.01 de π
Distance de Variation Totale
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Qu'est-ce qu'une Chaîne de Markov?
Une chaîne de Markov est un processus stochastique avec la propriété sans mémoire: l'état futur dépend uniquement de l'état actuel, et non de la séquence d'événements qui l'a précédé.
Propriété de Markov
P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t)
Formule de Transition
p_{t+1} = p_t P
où p_t est le vecteur de distribution au temps t, et P est la matrice de transition
Concepts Clés
- Espace d'États S: L'ensemble de tous les états possibles
- Matrice de Transition P: P[i][j] = P(X_{t+1}=j | X_t=i)
- Matrice Stochastique: Chaque ligne somme à 1.0
- Probabilité de Chemin: Produit des probabilités de transition le long du chemin
Distribution Stationnaire π
Une distribution stationnaire π est une distribution de probabilité qui reste inchangée dans la chaîne de Markov: une fois que le système atteint π, il y reste pour toujours.
Équation Stationnaire
π = πP
ou équivalent: π(P - I) = 0
Interprétation de Vecteur Propre Gauche
π est le vecteur propre gauche de P correspondant à la valeur propre 1
πP = λπ where λ = 1
Existence et Unicité
- Existence: Toute chaîne de Markov finie a au moins une distribution stationnaire
- Unicité: Garantie pour les chaînes irréductibles (tous les états communiquent)
- Perron-Frobenius: Pour les chaînes régulières, π a toutes les entrées positives
Distance de Variation Totale
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Mesure à quel point la distribution actuelle est proche de la stationnaire
Propriétés de Convergence
Sous quelles conditions une chaîne de Markov converge-t-elle vers sa distribution stationnaire?
Types de Chaînes
- Régulière (Apériodique + Irréductible): Converge vers une π unique depuis toute distribution initiale
- Périodique: Les états cyclent selon un motif périodique
- Réductible: Contient des états absorbants ou plusieurs classes communicantes
Taux de Convergence
Déterminé par la deuxième plus grande valeur propre en magnitude (SLEM):
|p_t - π| ≈ C × |λ_2|^t
Écart spectral = 1 - |λ₂|, écart plus grand = convergence plus rapide
Temps de Mélange
Temps pour être à ε de la distribution stationnaire:
t_mix(ε) = log(ε) / log(|λ_2|)
Détection de Périodicité
Un état a une période d si tous les cycles depuis cet état ont des longueurs divisibles par d
- Apériodique: d = 1 (peut revenir à tout moment)
- Périodique: d > 1 (les cycles sont synchronisés)
Balance Détaillée (Chaînes Réversibles)
π(i)P(i,j) = π(j)P(j,i)
Une condition suffisante pour que π soit stationnaire
Applications Réelles
Algorithme PageRank
Le PageRank de Google modèle la navigation web comme une marche aléatoire. La distribution stationnaire donne l'importance de chaque page.
P = (1-d)M + d(1/n)J
M: matrice de liens, d: facteur d'amortissement, J: matrice de uns
Marches Aléatoires sur Graphes
Utilisé dans l'analyse de réseaux, systèmes de recommandation et échantillonnage de graphes. La distribution stationnaire est liée aux degrés des nœuds.
Méthodes d'Échantillonnage MCMC
Les méthodes de Monte Carlo par Chaîne de Markov génèrent des échantillons de distributions de probabilité complexes en construisant des chaînes avec la cible comme distribution stationnaire.
- Metropolis-Hastings algorithm
- Gibbs sampling
- Boltzmann machines
Modèles de Markov Cachés (HMM)
Utilisés en reconnaissance vocale, bioinformatique et finance. Les HMM ont une chaîne de Markov sous-jacente avec des états cachés.
Théorie des Files
Les processus de naissance-mort modélisent les files. La distribution stationnaire donne la probabilité à long terme d'avoir n clients dans le système.
Jeux de Société
Des jeux comme Monopoly et Serpents et Échelles peuvent être modélisés comme des chaînes de Markov pour calculer la durée attendue du jeu et les fréquences de visite.