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