Bartosz Naskręcki
Ł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ń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ńcuchy Markowa
Łańcuchy Markowa to takie procesy Markowa, które zdefiniowane są na
dyskretnej przestrzeni stanów.
Łańcuch Markowa jest ciągiem X
1
, X
2
, X
3
, ... zmiennych losowych. Dziedzinę
tych zmiennych nazywamy przestrzenią stanów, a realizacje X
n
to stany w czasie
n. Jeśli rozkład warunkowy X
n+1
jest funkcją wyłącznie zmiennej X
n
:
P (X
n
|X
0
, X
1
, ..., X
n−1
) = P (X
n
|X
n−1
)
4. Reprezentacja macierzowa
Ł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 ¬ x
i
¬ 1, która wyraża
prawdopodobieństwo znalezienia się w stanie i.
Otrzymujemy wektor stanu:
x = (x
1
, . . . , x
n
)
Jest to wektor stochastyczny, czyli zachodzi warunek:
x
1
+ . . . + x
n
= 1
Ewolucję łańcucha opisuje zestaw liczb, które opisują prawdopodobieństwo
przejścia ze stanu i do stanu j:
0 ¬ q
ij
¬ 1
Liczby te tworzą macierz:
1
P =
q
11
q
12
. . .
q
1n
q
21
q
22
. . .
q
2n
..
.
..
.
. .
.
..
.
q
n1
q
n2
. . .
q
nn
Macierz ta jest macierzą stochastyczną, czyli:
∀
1¬i¬n
q
i1
+ . . . + q
in
= 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:
x
(n)
= x
(0)
P
n
5. Łańcuchy pochłaniające
Definicja 1. Łańcuch Markowa nazywamy pochłaniającym (AMC), jeśli istnie-
je taki stan i, z którego nie można wyjść, czyli:
q
ii
= 1
∧
∀
i6=j
[q
ij
= 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
P =
Q
R
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:
Q
n n→∞
−→ O
m,m
Twierdzenie 2. W AMC macierz I − Q jest odwracalna, a jej odwrotnością
jest macierz:
N = I + Q + Q
2
+ . . . + Q
n
+ . . .
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 = N c
gdzie:
t =
t
1
..
.
t
n
,
c =
1
..
.
1
,
t
i
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 = N R opisuje prawdopodobieństwo,
że zaczynając w stanie i łańcuch zostanie pochłonięty w stanie pochłaniającym
j.
8. Łańcuchy regularne i ergodyczne
Definicja 2. Łańcuch Markowa nazywamy ergodycznym, jeśli z dowolnego sta-
nu można przejść do dowolnego innego (niekoniecznie w jednym kroku).
Definicja 3. Łańcuch Markowa nazywamy regularnym, jeśli:
∃
n∈N
[P
n
= [q
(n)
ij
]
∧
∀
i,j∈{1,...,n}
[q
(n)
ij
> 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:
P
n n→∞
−→ 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:
lim
n→∞
vP
n
= w
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 = [m
ij
]
∀
i=j
[m
ij
= 0]
∀i 6= j
[m
ij
6= 0]
Liczba m
ij
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 = (w
1
, w
2
, . . . , w
n
)
↓
r =
1
w
1
,
1
w
2
, . . . ,
1
w
n
Elementy wektora r mają interpretację średniego czasu powrotu do stanu i.
Twierdzenie 8. Elementy macierzy M wyrażają się równością:
m
ij
=
z
jj
− z
ij
w
j
12. Prawo wielkich liczb dla macierzy ergodycznych
Niech H
(n)
j
będzie stosunkiem ilości „odwiedzin” stanu j do ilości kroków n.
Wówczas:
∀
e>0
h
P
|H
(n)
j
− w
j
| > e
n→∞
−→ 0
i
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