Bartosz Naskręcki
A
ańcuchy Markowa
referat dla Koła Naukowego Matematyków, 31.05.2006.
1. Czym jest łańcuch?
Proces stochastyczny: funkcja, która przyporządkowuje zbiorowi indeksów
procesu (zazwyczaj jest to czas) wartości, które leżą w przestrzeni zdarzeń lo-
sowych.
A
ańcuchem nazywamy proces stochastyczny, który jest określony na dyskret-
nej przestrzeni stanów.
2. Procesy Markowa
Proces Markowa to ciąg zdarzeń, w którym prawdopodobieństwo każde-
go zdarzenia zależy jedynie od wyniku poprzedniego. W ujęciu matematycznym
procesy Markowa to takie procesy stochastyczne, które spełniają własność Mar-
kowa.
3. A
ańcuchy Markowa
A
ańcuchy Markowa to takie procesy Markowa, które zdefiniowane są na
dyskretnej przestrzeni stanów.
A
ańcuch Markowa jest ciągiem X1, X2, X3, ... zmiennych losowych. Dziedzinę
tych zmiennych nazywamy przestrzenią stanów, a realizacje Xn to stany w czasie
n. Jeśli rozkład warunkowy Xn+1 jest funkcją wyłącznie zmiennej Xn:
P (Xn|X0, X1, ..., Xn-1) = P (Xn|Xn-1)
4. Reprezentacja macierzowa
A
ańcuchy Markowa można opisywać językiem algebry liniowej.
Załóżmy, że rozpatrujemy łańcuch, w którym występuje n rozróżnialnych
stanów. Każdy z nich opisywany jest przez zmienną 0 xi 1, która wyraża
prawdopodobieństwo znalezienia się w stanie i.
Otrzymujemy wektor stanu:
x = (x1, . . . , xn)
Jest to wektor stochastyczny, czyli zachodzi warunek:
x1 + . . . + xn = 1
Ewolucję łańcucha opisuje zestaw liczb, które opisują prawdopodobieństwo
przejścia ze stanu i do stanu j:
0 qij 1
Liczby te tworzą macierz:
1
�ł łł
q11 q12 . . . q1n
�ł
q21 q22 . . . q2n śł
�ł śł
P = �ł śł
. . .
.
. . . .
�ł �ł
.
. . .
qn1 qn2 . . . qnn
Macierz ta jest macierzą stochastyczną, czyli:
"1 i n qi1 + . . . + qin = 1
Wektor stanu początkowego oznaczamy przez x(0).
Stan układu w chwili n+1 w zależności od stanu w chwili n opisuje równanie:
x(n+1) = x(n)P
Jako naturalny wniosek otrzymujemy:
n
x(n) = x(0)P
5. A
ańcuchy pochłaniające
Definicja 1. A
ańcuch Markowa nazywamy pochłaniającym (AMC), jeśli istnie-
je taki stan i, z którego nie można wyjść, czyli:
qii = 1 '" "i =j [qij = 0]
Stan taki nazywamy stanem pochłaniającym (ang. absorbing state).
Stan nie będacy stanem pochłaniającym nazywamy stanem przejściowym
(ang. transient state).
6. Postać kanoniczna łańcucha pochłaniającego

Q R
P =
0 I
 Q  macierz tranzytywna
 0  macierz zerowa
 I  macierz identycznościowa
 R  macierz przejścia do stanów pochłaniających
7. Podstawowe własności
Twierdzenie 1. Prawdopodobieństwo pochłonięcia w łańcuchu pochłaniającym
wynosi 1, inaczej:
Qn n" Om,m
-
Twierdzenie 2. W AMC macierz I - Q jest odwracalna, a jej odwrotnością
jest macierz:
N = I + Q + Q2 + . . . + Qn + . . .
ij-ta pozycja macierzy N jest oczekiwaną wartością liczby  odwiedzeń stanu
j przy założeniu, że proces zaczął się w stanie i.
2
Twierdzenie 3. Oczekiwana wartość ilości kroków zanim łańcuch zostanie po-
chłonięty wyraża się wzorem:
t = Nc
gdzie:
�ł łł �ł łł
t1 1
�ł śł �ł śł
. .
. .
t = , c = ,
�ł �ł �ł �ł
. .
tn 1
ti opisuje oczekiwaną ilość kroków przed pochłonięciem, jeśli łańcuch rozpo-
czął się w stanie i.
Twierdzenie 4. ij-ty element macierzy B = NR opisuje prawdopodobieństwo,
że zaczynając w stanie i łańcuch zostanie pochłonięty w stanie pochłaniającym
j.
8. A
ańcuchy regularne i ergodyczne
Definicja 2. A
ańcuch Markowa nazywamy ergodycznym, jeśli z dowolnego sta-
nu można przejść do dowolnego innego (niekoniecznie w jednym kroku).
Definicja 3. A
ańcuch Markowa nazywamy regularnym, jeśli:
(n) (n)
n
"n"N [P = [qij ] '" "i,j"{1,...,n} [qij > 0]]
9. Własności łańcuchów regularnych i ergodycznych
Twierdzenie 5. Dla macierzy przejścia P łańcucha regularnego istnieje ma-
cierz W stochastyczna, której kolumny są wektorami stałymi, a wiersze są takie
same:
n"
n
P - W
Ponadto wektor wierszowy w ma wszystkie wyrazy dodatnie.
Twierdzenie 6. Istnieje dokladnie jeden wektor stochastyczny w taki, że jeśli
P jest macierzą regularną, to:
w = wP
Ponadto wektor w jest wierszem macierzy W z poprzedniego twierdzenia.
Twierdzenie działa także dla ogólniejszych macierzy P łańcuchów ergodycz-
nych.
Twierdzenie 7. Dla danego wektora stanu początkowego v i macierzy P łań-
cucha regularnego zachodzi:
n
lim vP = w
n"
Wektor w jest wektorem wierszowym macierzy W .
10. Macierz fundamentalna
Dla macierzy ergodycznych (i jednocześnie regularnych) odpowiednikiem
macierzy fundamentalnej N jest macierz:
Z = (I - P + W )-1
3
11. Macierz M
M = [mij]
"i=j [mij = 0]
"i = j [mij = 0]

Liczba mij oznacza średni oczekiwany czas, po jakim zaczynając w stanie i
znajdziemy się po raz pierwszy w stanie j.
Dla wektora stanu stabilnego w możemy rozpatrzyć wektor złożony z od-
wrotności kolejnych elementów tego wektora:
w = (w1, w2, . . . , wn)
�!

1 1 1
r = , , . . . ,
w1 w2 wn
Elementy wektora r mają interpretację średniego czasu powrotu do stanu i.
Twierdzenie 8. Elementy macierzy M wyrażają się równością:
zjj - zij
mij =
wj
12. Prawo wielkich liczb dla macierzy ergodycznych
(n)
Niech Hj będzie stosunkiem ilości  odwiedzin stanu j do ilości kroków n.
Wówczas:

(n) n"
"e>0 P |Hj - wj| > e - 0
niezależnie od stanu początkowego i.
Literatura
 American Mathematical Society: Handbook of probability (rozdz. 11)
 Nicolson: Linear Algebra with Applications (rozdz. Matrix Algebra)
 Kostrikin: Wstęp do algebry, tom 2 (rozdział o macierzach nieujemnych)
4