Efektywność systemów
informatycznych
Wykład 3
TEMAT:Procesy Markowa klasy DC
Efektywność systemów
informatycznych
Wykład 3
TEMAT:Procesy Markowa klasy DC
2
Pojęcia podstawowe
Klasyfikacja procesów
Klasyfikacja procesów
stochastycznych
stochastycznych
gdzie:
gdzie:
- zbiór zdarzeń elementarnych;
- zbiór zdarzeń elementarnych;
T – zbiór wartości parametrów procesu (czas),
T – zbiór wartości parametrów procesu (czas),
X
X
– zbiór możliwych wartości procesu.
– zbiór możliwych wartości procesu.
Mówimy, że
Mówimy, że
X
X
i T są dyskretne jeśli są co
i T są dyskretne jeśli są co
najwyżej przeliczalne, tzn.:
najwyżej przeliczalne, tzn.:
Mówimy, że
Mówimy, że
X
X
i T są ciągłe jeśli:
i T są ciągłe jeśli:
X
T
:
,..}
2
,
1
,
0
{
T
lub
}
,..,
2
,
1
,
0
{
n
T
,..}
,
{
lub
}
,..,
,
{
1
0
1
0
x
x
x
x
x
n
X
X
1
]
,
[
,
R
b
a
T
X
3
Pojęcia podstawowe - 2
T
T
X
X
Dyskret
Dyskret
ny
ny
Ciągły
Ciągły
dyskret
dyskret
n
n
y
y
DD
DD
DC
DC
Ciągły
Ciągły
CD
CD
CC
CC
Ze względu na charakter zbiorów T i
Ze względu na charakter zbiorów T i
X
X
można
można
wyróżnić cztery klasy procesów.
wyróżnić cztery klasy procesów.
4
Pojęcia podstawowe - 3
Definicja 3.1.
Definicja 3.1.
(proces Markowa)
(proces Markowa)
Proces
Proces
t
t
nazywamy procesem Markowa, jeśli
nazywamy procesem Markowa, jeśli
spełnia następujący warunek:
spełnia następujący warunek:
Dla dowolnego n
Dla dowolnego n
1, dla dowolnych chwil
1, dla dowolnych chwil
t
t
1
1
<t
<t
2
2
<..<t
<..<t
n
n
<t
<t
n+1
n+1
ze zbioru T i dowolnych
ze zbioru T i dowolnych
x
x
1,
1,
x
x
2
2
,...,x
,...,x
n+1
n+1
X
X
takich, że:
takich, że:
Jeśli T={0, 1, ...} to mówimy o łańcuchu
Jeśli T={0, 1, ...} to mówimy o łańcuchu
Markowa.
Markowa.
Procesy Markowa są tzw. procesami
Procesy Markowa są tzw. procesami
ahistorycznymi.
ahistorycznymi.
}
|
{
}
,...,
|
{
1
1
1
1
1
1
n
t
n
t
t
n
t
n
t
x
x
P
x
x
x
P
n
n
n
n
0
}
,...,
{
1
1
x
x
P
t
n
t
n
5
Pojęcia podstawowe - 4
Definicja 3.2.
Definicja 3.2.
(jednorodny proces Markowa)
(jednorodny proces Markowa)
Proces Markowa
Proces Markowa
t
t
nazywamy jednorodnym, jeśli
nazywamy jednorodnym, jeśli
spełnia następujący warunek:
spełnia następujący warunek:
W dalszym ciągu rozpatrywane będą procesy
W dalszym ciągu rozpatrywane będą procesy
jednorodne.
jednorodne.
Wprowadźmy następujące oznaczenia:
Wprowadźmy następujące oznaczenia:
}
|
{
}
|
{
0
,
0
:
0
,
1
2
1
2
2
1
2
1
1
2
1
2
x
x
P
x
x
P
h
t
h
t
h
t
t
t
t
h
t
h
t
X
X
X
X
i
t
i
i
j
i
ij
t
t
ij
i
P
t
P
t
P
p
i
j
P
p
j
i
T
t
}
{
)
(
)
(
3
)
(
)
(
2
}
|
{
)
(
,
,
0
,
1
0
,
0
0
6
Własność jednorodnych procesów
Markowa
Funkcje
Funkcje
oznaczają prawdopodobieństwo
oznaczają prawdopodobieństwo
przejścia ze stanu
przejścia ze stanu
i
i
w chwili
w chwili
t
t
do stanu j w chwili
do stanu j w chwili
t+
t+
.
.
Macierz
Macierz
nazywa się macierzą
nazywa się macierzą
prawdopodobieństw przejść.
prawdopodobieństw przejść.
Wektor
Wektor
P(t)
P(t)
określa rozkład chwilowy procesu w
określa rozkład chwilowy procesu w
chwili
chwili
t
t
.
.
Z definicji procesu Markowa oraz określeń 1
Z definicji procesu Markowa oraz określeń 1
0
0
-3
-3
0
0
wynikają następujące własności procesu
wynikają następujące własności procesu
Markowa:
Markowa:
Spełnienie warunku (A) powoduje , że macierz
Spełnienie warunku (A) powoduje , że macierz
(
(
)
)
nazywamy macierzą stochastyczną
nazywamy macierzą stochastyczną
.
.
)
(
ij
p
)
(
1
)
(
1
)
(
0
,
0
,
,
)
(
X
j
X
X
ij
ij
p
i
p
j
i
A
7
Własności jednorodnych procesów
Markowa-2
Czyli
Czyli
(równanie Chapmana – Kołmogorowa).
(równanie Chapmana – Kołmogorowa).
)
(
)
(
)
(
0
,
)
(
t
t
t
B
)
(
)
(
)
(
,
0
,
,
,
kj
k
ik
ij
p
t
p
t
p
t
j
i
X
X
)
(
)
(
)
(
czyli
)
(
)
(
)
(
0
,
)
(
ij
i
j
p
t
P
t
P
X
j
t
P
t
P
t
C
8
Rozkład chwilowy procesu Markowa
dyskretnego w stanach
Własność 3.1
Własność 3.1
Do wyznaczenia rozkładu chwilowego procesu
Do wyznaczenia rozkładu chwilowego procesu
Markowa w dowolnej chwili wystarczy
Markowa w dowolnej chwili wystarczy
znajomość rozkładu początkowego
znajomość rozkładu początkowego
P(0)
P(0)
oraz
oraz
macierzy prawdopodobieństw przejść.
macierzy prawdopodobieństw przejść.
Rozkład początkowy określony jest następująco:
Rozkład początkowy określony jest następująco:
Własność 3.1 wynika z własności (C) macierzy
Własność 3.1 wynika z własności (C) macierzy
prawdopodobieństw przejść. Z (C) wiadomo,
prawdopodobieństw przejść. Z (C) wiadomo,
że:
że:
Przyjmując, że t=0 otrzymujemy:
Przyjmując, że t=0 otrzymujemy:
}
{
)
0
(
)
0
(
)
0
(
0
i
P
P
oraz
P
P
i
i
i
X
)
(
)
(
)
(
t
P
t
P
)
(
)
0
(
)
(
0
P
P
9
Wyznaczanie macierzy prawdopodobieństw
przejść
Wyznaczanie macierzy
Wyznaczanie macierzy
(
(
) dla procesów klasy
) dla procesów klasy
DD
DD
W przypadku procesów dyskretnych w czasie
W przypadku procesów dyskretnych w czasie
(łańcuchów) często zamiast o czasie, kolejnych
(łańcuchów) często zamiast o czasie, kolejnych
chwilach mówi się o krokach i oznacza je
chwilach mówi się o krokach i oznacza je
zamiast litery
zamiast litery
t
t
literami:
literami:
k, l, m, n.
k, l, m, n.
Z własności (B) macierzy
Z własności (B) macierzy
(
(
) łatwo wykazać,
) łatwo wykazać,
że:
że:
Zatem:
Zatem:
a własność (C) uzyskuje postać:
a własność (C) uzyskuje postać:
k
def
k
k
k
)
1
(
)
(
,...}
2
,
1
,
0
{
k
P
k
P
k
P
T
k
)
0
(
)
(
)
0
(
)
(
l
k
P
l
k
P
l
k
P
T
l
k
)
(
)
(
)
(
)
(
,
10
Wyznaczanie macierzy prawdopodobieństw
przejść
Wyznaczanie macierzy
Wyznaczanie macierzy
(
(
) dla procesów klasy DC
) dla procesów klasy DC
W przypadku procesów ciągłych w czasie
W przypadku procesów ciągłych w czasie
wykorzystuje się do wyznaczenia macierzy
wykorzystuje się do wyznaczenia macierzy
(
(
)
)
funkcję intensywności przejść.
funkcję intensywności przejść.
Przyjmijmy do dalszych rozważań, że macierz
Przyjmijmy do dalszych rozważań, że macierz
(
(
) spełnia oprócz własności (A)
) spełnia oprócz własności (A)
(C) jeszcze
(C) jeszcze
jedną, oznaczoną jako (D):
jedną, oznaczoną jako (D):
Procesy Markowa spełniający własność (D)
Procesy Markowa spełniający własność (D)
nazywany jest procesem standardowym.
nazywany jest procesem standardowym.
Własność (D) odpowiada stochastycznej
Własność (D) odpowiada stochastycznej
ciągłości procesów stochastycznych.
ciągłości procesów stochastycznych.
I
p
j
i
D
ij
ij
0
0
)
(
inaczej
)
(
,
)
(
X
I
I
oznacza
oznacza
macierz
macierz
jednostko
jednostko
wą
wą
11
Wyznaczanie macierzy prawdopodobieństw
przejść
Twierdzenie 3.1.
Twierdzenie 3.1.
Niech macierz
Niech macierz
(
(
) spełnia warunki (A)
) spełnia warunki (A)
(D).
(D).
Prawdziwe są wówczas następujące związki:
Prawdziwe są wówczas następujące związki:
Macierz
Macierz
nazywamy macierzą
nazywamy macierzą
intensywności przejść, a
intensywności przejść, a
ij
ij
intensywnością
intensywnością
przejścia ze stanu i do stany j, przy czym
przejścia ze stanu i do stany j, przy czym
ii
ii
= -
= -
i
i
i
i
j
j
ij
ii
i
ij
ij
i
p
i
p
j
i
j
i
X
X
X
X
)
3
)
(
1
lim
istnieje
)
2
)
(
lim
,
,
)
1
0
0
X
j
i
ij ,
12
Wyznaczanie macierzy prawdopodobieństw
przejść
Elementom macierzy
Elementom macierzy
można nadać następującą
można nadać następującą
interpretację probabilistyczną:
interpretację probabilistyczną:
Definicja 3.3
Definicja 3.3
Stan
Stan
i
i
X
X
taki, że
taki, że
nazywamy regularnym, jeśli:
nazywamy regularnym, jeśli:
Proces, w którym wszystkie stany są regularne,
Proces, w którym wszystkie stany są regularne,
nazywamy lokalnie regularnym.
nazywamy lokalnie regularnym.
0
)
(
gdzie
)
(
)
(
1
)
(
)
(
0
o
p
o
p
o
ii
i
ij
ij
X
j
i
ij ,
i
i
j
X
j
ij
i
13
Wyznaczanie macierzy prawdopodobieństw
przejść
Układy równań Kołmogorowa
Układy równań Kołmogorowa
Układy równań Kołmogorowa określają związki
Układy równań Kołmogorowa określają związki
między macierzami
między macierzami
i
i
. Związki te pozwalają
. Związki te pozwalają
wyznaczać
wyznaczać
przy znajomości
przy znajomości
.
.
Twierdzenie 3.2.
Twierdzenie 3.2.
Jeśli
Jeśli
(
(
) spełnia warunki (A)
) spełnia warunki (A)
(D) oraz proces jest
(D) oraz proces jest
lokalnie regularny to zachodzą następujące
lokalnie regularny to zachodzą następujące
równania:
równania:
Postać macierzowa tego układu:
Postać macierzowa tego układu:
.
)
0
(
,
,
0
),
(
)
(
ij
ij
k
kj
ik
ij
p
j
i
p
d
dp
X
X
I
d
d
)
0
(
)
(
)
(
Pierwotny układ
Pierwotny układ
równań
równań
Kołmogorowa
Kołmogorowa
14
Wyznaczanie macierzy prawdopodobieństw
przejść
Jeśli dodatkowo założymy, że:
Jeśli dodatkowo założymy, że:
to spełnione są również równania postaci:
to spełnione są również równania postaci:
czyli:
czyli:
Uwaga
Uwaga
1.Jeśli
1.Jeśli
to wszystkie stany są regularne
to wszystkie stany są regularne
2. Jeśli
2. Jeśli
X
X
jest skończony to
jest skończony to
.
)
0
(
,
,
0
,
)
(
)
(
ij
ij
k
kj
ik
ij
p
j
i
p
d
dp
X
X
I
d
d
)
0
(
)
(
)
(
Układ wtórny
Układ wtórny
równań
równań
Kołmogorowa
Kołmogorowa
i
i
X
sup
i
i
X
sup
i
i
X
sup
15
Wyznaczanie macierzy prawdopodobieństw
przejść
Załóżmy, ze dana jest macierz
Załóżmy, ze dana jest macierz
taka, że:
taka, że:
To zachodzą następujące twierdzenia:
To zachodzą następujące twierdzenia:
Twierdzenie 3.3.
Twierdzenie 3.3.
Jeśli macierz liczbowa
Jeśli macierz liczbowa
spełnia określone wyżej
spełnia określone wyżej
warunki 1)-4) to istnieje funkcja macierzowa
warunki 1)-4) to istnieje funkcja macierzowa
(
(
)
)
będąca jedynym rozwiązaniem układu równań
będąca jedynym rozwiązaniem układu równań
Kołmogorowa (pierwotnego i wtórnego). Funkcja ta
Kołmogorowa (pierwotnego i wtórnego). Funkcja ta
spełnia warunki (A)-(D) macierzy
spełnia warunki (A)-(D) macierzy
prawdopodobieństw przejść jednorodnego procesu
prawdopodobieństw przejść jednorodnego procesu
Markowa
Markowa
ii
i
j
ij
ij
ii
i
j
i
i
X
X
X
0
X
X
sup
)
4
0
)
3
,
)
2
0
)
1
X
j
i
ij ,
16
Wyznaczanie rozkładu chwilowego
Twierdzenie 3.4.
Twierdzenie 3.4.
Jeśli macierz
Jeśli macierz
spełnia określone wyżej warunki
spełnia określone wyżej warunki
1)-4) oraz stany procesu Markowa są parami
1)-4) oraz stany procesu Markowa są parami
tranzytywne to układ równań:
tranzytywne to układ równań:
przy zadanym
przy zadanym
P(0)
P(0)
posiada jednoznaczne
posiada jednoznaczne
rozwiązanie, będące rozkładem chwilowym
rozwiązanie, będące rozkładem chwilowym
procesu Markowa przy ustalonym
procesu Markowa przy ustalonym
t
t
.
.
X
X
j
t
P
t
P
t
P
t
P
kj
k
k
j
,
)
(
)
(
czyli
)
(
)
(
'
'
17
Rozkład graniczny jednorodnego PM
dyskretnego w stanach
Definicja 3.4
Definicja 3.4
(rozkład stacjonarny)
(rozkład stacjonarny)
Wektor
Wektor
nazywamy rozkładem
nazywamy rozkładem
stacjonarnym jeśli:
stacjonarnym jeśli:
X
i
i
)
(
)
(
)
(
1
)
(
0
)
(
t
T
t
t
p
j
T
t
c
b
i
a
ij
i
i
i
i
i
X
j
X
X
X
18
Rozkład graniczny jednorodnego PM
dyskretnego w stanach
- 2
Definicja 3.5
Definicja 3.5
(rozkład graniczny)
(rozkład graniczny)
Wektor
Wektor
nazywamy rozkładem
nazywamy rozkładem
granicznym jeśli:
granicznym jeśli:
X
i
i
j
j
j
j
X
X
X
t
j
ij
t
i
i
i
t
P
i
t
p
j
c
b
i
a
)
(
(c)
od
zalezy
nie
)
(
lim
)
(
1
)
(
0
)
(
19
Klasyfikacja stanów dyskretnego PM
Dwa stany
Dwa stany
„i, j”
„i, j”
nazywamy
nazywamy
tranzytywnymi
tranzytywnymi
(komunikującymi się) jeśli:
(komunikującymi się) jeśli:
Odpowiada to takiej sytuacji, że w grafie procesu
Odpowiada to takiej sytuacji, że w grafie procesu
istnieje droga z wierzchołka
istnieje droga z wierzchołka
i
i
do wierzchołka
do wierzchołka
j
j
oraz droga z
oraz droga z
j
j
do
do
i
i
.
.
Zbiór stanów
Zbiór stanów
S
S
X
X
nazywamy zbiorem
nazywamy zbiorem
zamkniętym jeżeli:
zamkniętym jeżeli:
Zbiór
Zbiór
S
S
nazywamy właściwym zbiorem
nazywamy właściwym zbiorem
zamkniętym, jeśli jest on zamknięty i wszystkie
zamkniętym, jeśli jest on zamknięty i wszystkie
pary jego elementów są tranzytywne.
pary jego elementów są tranzytywne.
0
)
(
0
)
(
0
,
ji
ij
p
t
p
t
S
\
X
S
S
S
:
0
)
(
0
gdzie
p
i
j
ij
20
Klasyfikacja stanów dyskretnego PM - 2
Stan
Stan
i
i
X
X
nazywamy cyklicznym stanem procesu
nazywamy cyklicznym stanem procesu
klasy DD, jeśli:
klasy DD, jeśli:
1
)
(
..}
,
3
,
2
{
1
k
ii
k
p
21
Warunki wystarczające istnienia rozkładu
granicznego
Twierdzenie 3.5
Twierdzenie 3.5
Jeśli
Jeśli
(skończony zbiór stanów) i w zbiorze
(skończony zbiór stanów) i w zbiorze
stanów procesu istnieje tylko jeden właściwy
stanów procesu istnieje tylko jeden właściwy
zbiór zamknięty (dla czasu dyskretnego stany
zbiór zamknięty (dla czasu dyskretnego stany
są dodatkowo acykliczne) to istnieją rozkłady
są dodatkowo acykliczne) to istnieją rozkłady
graniczny oraz stacjonarny i są one sobie
graniczny oraz stacjonarny i są one sobie
równe:
równe:
X
22
Warunki wystarczające istnienia rozkładu
granicznego -2
Twierdzenie 3.6
Twierdzenie 3.6
Jeśli istnieje rozkład stacjonarny
Jeśli istnieje rozkład stacjonarny
, to następujące
, to następujące
zdania są równoważne:
zdania są równoważne:
1
1
0
0
2
2
0
0
Wszystkie stany są parami tranzytywne (dla
Wszystkie stany są parami tranzytywne (dla
procesów klasy DD stany są dodatkowo
procesów klasy DD stany są dodatkowo
acykliczne).
acykliczne).
Uwaga
Uwaga
Jeśli rozkład stacjonarny nie istnieje i proces ma
Jeśli rozkład stacjonarny nie istnieje i proces ma
tylko jeden właściwy zbiór zamknięty stanów to:
tylko jeden właściwy zbiór zamknięty stanów to:
X
j
t
p
j
j
ij
t
,
0
)
(
lim
0
)
(
,
t
ij
t
p
j
i
X
23
Wyznaczania rozkładu stacjonarnego
Rozkład stacjonarny PM klasy DD wyznaczamy
Rozkład stacjonarny PM klasy DD wyznaczamy
jako rozwiązanie następującego układu równań:
jako rozwiązanie następującego układu równań:
Rozkład stacjonarny PM klasy DC wyznaczamy
Rozkład stacjonarny PM klasy DC wyznaczamy
jako rozwiązanie następującego układu równań:
jako rozwiązanie następującego układu równań:
X
X
i
i
i
i
I
1
0
)
(
1
X
i
i
1
0
24
Ergodyczność procesu Markowa
Twierdzenie 3.7
Twierdzenie 3.7
Jeśli jednorodny proces Markowa (dyskretny w
Jeśli jednorodny proces Markowa (dyskretny w
stanach):
stanach):
posiada rozkład stacjonarny
posiada rozkład stacjonarny
i jego stany są parami
i jego stany są parami
tranzytywne lub
tranzytywne lub
posiada rozkład graniczny
posiada rozkład graniczny
i jest procesem standardowym to zachodzą
i jest procesem standardowym to zachodzą
następujące własności:
następujące własności:
dla procesów klasy DD:
dla procesów klasy DD:
dla procesów klasy DC:
dla procesów klasy DC:
gdzie:
gdzie:
oraz
oraz
f
f
jest mierzalna.
jest mierzalna.
1
)
(
1
lim
1
n
k
k
n
f
f
n
P
1
)
(
1
lim
0
f
dy
f
t
P
t
y
t
X
i
i
i
f
f
R
R
f
)
(
,
:
1
1