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