Markov Chain
Jak działa
Łańcuch Markowa definiuje się przez: (1) przestrzeń stanów S, (2) rozkład początkowy μ₀, (3) macierz przejść P (lub generator Q dla CTMC). Ewolucja: rozkład w kroku n to μ_n = μ₀ · Pⁿ. Stany klasyfikuje się jako: rekurencyjne (powracające) vs. tranzyentne, periodyczne vs. aperiodyczne, komunikujące się (te same klasy ekwiwalencji). Centralne twierdzenia: (a) twierdzenie o zbieżności — łańcuch ergodyczny zbiega do unikalnej dystrybucji stacjonarnej π = πP, (b) twierdzenie ergodyczne — średnia czasowa funkcji f(X_n) zbiega do średniej przestrzennej E_π[f]. Algorytmy: obliczanie π przez rozwiązanie równania liniowego, potęgowanie macierzy, iteracja von Mises. W praktyce algorytmicznej (MCMC) konstruuje się łańcuchy Markowa o zadanej dystrybucji stacjonarnej (np. Metropolis-Hastings, Gibbs sampling) — próbkowanie z rozkładu trudnego do bezpośredniego losowania.
Rozwiązany problem
Jak modelować i analizować systemy stochastyczne ewoluujące w czasie tak, aby możliwe było obliczenie długoterminowych własności (rozkład stacjonarny, czas powrotu, klasy stanów) bez konieczności śledzenia pełnej historii.
Komponenty
Zbiór wszystkich możliwych stanów łańcucha. Może być skończony, przeliczalny (DTMC) lub ciągły.
P_ij = P(X_{n+1}=j | X_n=i). Stochastyczna macierz (wiersze sumują się do 1). Definiuje pełną dynamikę łańcucha.
Rozkład prawdopodobieństwa stanu w chwili 0. Często wybierany jako rozkład deterministyczny (X₀ = s₀ z prawdopodobieństwem 1).
Oficjalna
Dystrybucja π spełniająca π = πP. Dla łańcucha ergodycznego: unikalna i jest granicą rozkładu μ_n niezależnie od μ₀.
Implementacja
Modelowanie systemu jako łańcuch Markowa, gdy stan nie zawiera wystarczającej informacji do predykcji przyszłości — prowadzi do błędnych wniosków o dystrybucji stacjonarnej i czasach przejść.
Łańcuch może potrzebować bardzo długiego czasu do zbieżności do dystrybucji stacjonarnej (slow mixing) — szczególnie w wysokowymiarowych przestrzeniach z wąskimi korytarzami.
Łańcuch może nie posiadać unikalnej dystrybucji stacjonarnej (przywiedlność, periodyczność) — wtedy klasyczne twierdzenia o zbieżności nie obowiązują.
Dla bardzo dużych |S| (np. modele językowe na poziomie słów) macierz P jest niemożliwa do jawnego przechowywania. Naiwne potęgowanie traci precyzję numeryczną.
Ewolucja
Andriej Markow rozszerza prawo wielkich liczb na zmienne losowe zależne — pierwsza formalna definicja łańcucha Markowa.
Pierwsze zastosowanie łańcuchów do tekstu naturalnego — analiza statystyczna sekwencji samogłosek/spółgłosek w poemacie Puszkina. Prekursor n-gramowych modeli językowych.
Metropolis et al. publikują pierwszy algorytm MCMC — używają łańcucha Markowa do próbkowania z rozkładu Boltzmanna w fizyce statystycznej.
Bellman rozszerza łańcuchy Markowa o akcje i nagrody — definiuje MDP, fundament Reinforcement Learning.
W. K. Hastings publikuje uogólnienie — Metropolis-Hastings staje się głównym algorytmem MCMC w statystyce bayesowskiej.
Lawrence Rabiner publikuje fundamentalny tutorial o HMM — łańcuchy Markowa stają się dominującym modelem rozpoznawania mowy aż do ery deep learning.
PageRank definiuje ranking stron jako stacjonarną dystrybucję łańcucha Markowa "random surfer" — fundament rewolucji wyszukiwarek.
Sohl-Dickstein et al. używają forward Markov chain do stopniowego szumienia danych — fundament współczesnych modeli dyfuzji (DDPM, Stable Diffusion).
Hiperparametry (konfigurowalne osie)
Liczba lub wymiarowość stanów. Wpływa na rozmiar macierzy P (|S|×|S|) i koszt obliczeń stacjonarnych.
Dyskretna (DTMC, sekwencja kroków) vs. ciągła (CTMC, generator Q i prawdopodobieństwa eksponencjalne).
Liczba poprzednich stanów wpływających na rozkład następnego. Standardowy łańcuch ma rząd 1; n-gramy w NLP to łańcuchy wyższego rzędu.
Złożoność obliczeniowa
Złożoność czasowa: O(|S|³) — obliczenie π przez rozwiązanie układu liniowego. Złożoność przestrzenna: O(|S|²).
Paradygmat wykonania
Łańcuch Markowa to formalny model matematyczny — sposób wykonania zależy od konkretnego algorytmu (forward simulation, Metropolis-Hastings, Gibbs sampling, eigen-decomposition).
Równoległość
Pojedynczy łańcuch jest wewnętrznie sekwencyjny. Można paralelizować wiele niezależnych łańcuchów (parallel tempering, multiple-chain MCMC). Operacje macierzowe (potęgowanie P) są w pełni paralelizowalne.
Wymagania sprzętowe
Symulacja sekwencyjna łańcucha Markowa jest typowo CPU-bound. Wektoryzacja AVX przyspiesza próbkowanie z dyskretnych rozkładów.
Operacje macierzowe (potęgowanie P, eigen-decomposition) i równoległe próbkowanie wielu łańcuchów (parallel tempering, batch MCMC) są bardzo dobrze przyspieszane na GPU.
Łańcuch Markowa to formalny model matematyczny — nie ma preferencji sprzętowych jako takich. Wybór hardware'u zależy od konkretnej implementacji.