Efektywność systemów

informatycznych

Wykład 2

TEMAT:Modele matematyczne SI i

analityczne metody wyznaczania

wartości wskaźników efektywności.

Modele strumieni zdarzeń

2

Rekurencyjne strumienie zdarzeń



Przyjmijmy, że interesuje nas występowanie w czasie

Przyjmijmy, że interesuje nas występowanie w czasie

określonych zdarzeń (awarii , napływania zgłoszeń do

określonych zdarzeń (awarii , napływania zgłoszeń do

SI, zgłoszeń do systemu obsługi)

SI, zgłoszeń do systemu obsługi)



Oznaczmy przez

Oznaczmy przez

t

t

i

i

, i=1, 2, ..

, i=1, 2, ..

chwile występowania

chwile występowania

rozpatrywanych zdarzeń. Wówczas ciąg

rozpatrywanych zdarzeń. Wówczas ciąg

nazywamy strumieniem zdarzeń.

nazywamy strumieniem zdarzeń.



Strumienie deterministyczne i stochastyczne.

Strumienie deterministyczne i stochastyczne.



Dalej rozpatrywane będą stochastyczne rekurencyjne

Dalej rozpatrywane będą stochastyczne rekurencyjne

strumienie zdarzeń.

strumienie zdarzeń.



Rozpatrzmy następujący ciąg zmiennych losowych:

Rozpatrzmy następujący ciąg zmiennych losowych:



Zmienne losowe

Zmienne losowe

T

T

i

i

oznaczają odstępy czasu między

oznaczają odstępy czasu między

kolejnymi zdarzeniami. W zależności od własności

kolejnymi zdarzeniami. W zależności od własności

ciągów

ciągów

(t

(t

i

i

), (T

), (T

i

i

)

)

mamy do czynienia z różnymi typami

mamy do czynienia z różnymi typami

strumieni zdarzeń.

strumieni zdarzeń.

 

1



i

i

t

0

..

,

2

,

1

0

,

1











t

i

t

t

T

i

i

i

3

Rekurencyjne strumienie zdarzeń -
2



Strumień

Strumień

(t

(t

i

i

),

),

dla którego ciąg

dla którego ciąg

(T

(T

i

i

)

)

jest ciągiem

jest ciągiem

łącznie niezależnych zmiennych losowych, nazywa

łącznie niezależnych zmiennych losowych, nazywa

się

się

strumieniem o ograniczonych następstwach.

strumieniem o ograniczonych następstwach.



Przyjmijmy dalej, że

Przyjmijmy dalej, że

F

F

i

i

,

,

i=1, 2, .. są dystrybuantami

i=1, 2, .. są dystrybuantami

rozkładu prawdopodobieństwa zmiennych losowych

rozkładu prawdopodobieństwa zmiennych losowych

T

T

i

i

i=1, 2, .., czyli:

i=1, 2, .., czyli:



Strumień o ograniczonych następstwach, dla

Strumień o ograniczonych następstwach, dla

którego:

którego:

gdzie:

gdzie:

F

F

jest pewna dystrybuantą, nazywamy

jest pewna dystrybuantą, nazywamy

opóźnionym strumieniem rekurencyjnym.

opóźnionym strumieniem rekurencyjnym.



Jeśli dodatkowo

Jeśli dodatkowo

to mamy do czynienia ze

to mamy do czynienia ze

strumieniem rekurencyjnym

strumieniem rekurencyjnym

..

,

2

,

1

},

{

)

(







i

t

T

P

t

F

i

i

F

...

3

2





F

F

,..

2

,

1

,

.

,

1







i

F

F

tzn

F

F

i

4

Rekurencyjne strumienie zdarzeń -
3



Jeśli natomiast:

Jeśli natomiast:

to

to

(t

(t

i

i

)

)

jest stacjonarnym strumieniem rekurencyjnym.

jest stacjonarnym strumieniem rekurencyjnym.



Ze strumieniem rekurencyjnym można związać

Ze strumieniem rekurencyjnym można związać

proces zliczający określono następująco:

proces zliczający określono następująco:

























0

0

0

1

)

(

)

(

1

(

)

(

1

(

1

)

(

u

tdF

du

u

F

du

u

F

t

F

t





}

:

max{

)

(

t

t

n

t

n









{0}

N



5

Rekurencyjne strumienie zdarzeń -
4



Mówimy, że dysponujemy pełnym opisem

Mówimy, że dysponujemy pełnym opisem

probabilistycznym strumienia

probabilistycznym strumienia

(t

(t

i

i

)

)

i=1,2,..

i=1,2,..

jeśli

jeśli

dysponujemy dystrybuantami

dysponujemy dystrybuantami

F

F

1

1

, F

, F

.

.



Podstawowe charakterystyki strumieni

Podstawowe charakterystyki strumieni

rekurencyjnych

rekurencyjnych

:

:



Rozkład czasu do wystąpienia r-tego zdarzenia,

Rozkład czasu do wystąpienia r-tego zdarzenia,



Rozkład chwilowy procesu zliczającego

Rozkład chwilowy procesu zliczającego

zdarzenia,

zdarzenia,



Oczekiwana liczba zdarzeń do chwili

Oczekiwana liczba zdarzeń do chwili

t

t

,

,



Operacje na strumieniach rekurencyjnych:

Operacje na strumieniach rekurencyjnych:



Sumowanie i rozrzedzanie strumieni

Sumowanie i rozrzedzanie strumieni



Niepojedynczy strumień zdarzeń.

Niepojedynczy strumień zdarzeń.

6

Rekurencyjne strumienie zdarzeń -
5

Rozkładu czasu do wystąpienia r-tego zdarzenia

Rozkładu czasu do wystąpienia r-tego zdarzenia



Ze związku

Ze związku

wynika, że:

wynika, że:



Rozkład sumy niezależnych zmiennych

Rozkład sumy niezależnych zmiennych

losowych

losowych

0

..

,

2

,

1

0

,

1











t

i

t

t

T

i

i

i

1

,

1









r

T

t

r

i

i

r























z

X

Y

z

Y

X

Z

Z

Y

X

x

dF

x

z

F

y

dF

y

z

F

z

Y

X

P

z

F

F

Z

Y

X

Z

F

Y

F

X

0

0

)

(

)

(

)

(

)

(

}

{

)

(

~

,

,

~

,

~

7

Rekurencyjne strumienie zdarzeń -
6



Jeśli istnieje

Jeśli istnieje

to

to



Zatem, jeśli przez

Zatem, jeśli przez

K

K

r

r

oznaczymy dystrybuantę

oznaczymy dystrybuantę

t

t

r

r

:

:

to otrzymujemy:

to otrzymujemy:

)

(

)

(

z

F

dz

d

z

f

Z

Z



dx

x

f

x

z

f

dy

y

f

y

z

f

z

f

z

X

Y

z

Y

X

Z













0

0

)

(

)

(

)

(

)

(

)

(

}

{

)

(

t

t

P

t

K

r

r



































r

i

i

r

r

r

r

i

t

i

r

t

T

P

t

F

t

F

F

u

dF

u

t

F

t

T

P

t

K

2

)

1

(

)

1

(

1

)

1

(

1

0

1

}

{

)

(

:

gdzie

)

(

*

)

(

)

(

}

{

)

(

8

Rekurencyjne strumienie zdarzeń -
7



Jeśli przyjmiemy oznaczenia:

Jeśli przyjmiemy oznaczenia:

To

To

oraz

oraz

))

(

(

)

(

)

(

))

(

(

)

(

)

(

)

(

0

0

*

t

K

L

t

dK

e

dt

t

k

e

t

k

L

s

k

t

K

dt

d

t

k

r

s

r

st

r

st

r

r

r

r























1

*

)

1

(

*

)

1

(

1

1

*

1

*

*

*

))

(

(

))

(

(

)

(

))

(

(

))

(

(

)

(

))

(

(

))

(

(

)

(

)

(

1

))

(

(

)

(























r

r

r

s

s

r

r

r

s

f

t

f

L

s

f

t

F

L

t

f

L

s

f

t

F

L

t

f

L

s

f

s

k

s

t

K

L

s

K





1

*

*

1

*

)

1

(

*

1

*

)

(

)

(

)

(

)

(

)

(













r

r

r

s

f

s

f

s

f

s

f

s

k

9

Rekurencyjne strumienie zdarzeń -
7



Dla strumienia rekurencyjnego:

Dla strumienia rekurencyjnego:



Dla strumienia stacjonarnego otrzymujemy:

Dla strumienia stacjonarnego otrzymujemy:

stąd:

stąd:









r

r

r

r

s

f

s

f

s

f

s

f

s

f

s

k

)

(

)

(

)

(

)

(

)

(

)

(

*

1

*

*

*

)

1

(

*

1

*















))

(

1

(

1

)

(

1

1

1

))

(

(

1

1

1

))

(

1

(

1

(

)

(

*

*

*

1

s

f

s

s

f

s

s

t

F

L

s

t

F

L

s

f









































1

*

*

*

)

(

))

(

1

(

1

)

(









r

r

s

f

s

f

s

s

k



10

Rekurencyjne strumienie zdarzeń -
8

Rozkład chwilowy procesu zliczającego

Rozkład chwilowy procesu zliczającego





(t)

(t)

określony jest następującym wektorem:

określony jest następującym wektorem:



Można pokazać, że:

Można pokazać, że:



Inna metoda wyznaczania

Inna metoda wyznaczania

P(t)

P(t)

polega na

polega na

wykorzystaniu funkcji tworzącej rozkładu

wykorzystaniu funkcji tworzącej rozkładu

chwilowego procesu

chwilowego procesu





(t):

(t):





,..

2

,

1

,

0

},

)

(

{

)

(

gdzie

)

(

)

(

,..

2

,

1

,

0











i

i

t

P

t

P

t

P

t

P

i

i

i



,...

2

,

1

,

0

),

(

)

(

)

(

1









n

t

K

t

K

t

P

n

n

n

dt

z

t

G

e

z

t

G

L

z

s

G

z

z

t

P

z

t

G

st

k

k

k

)

,

(

))

,

(

(

)

,

(

oraz

1

,

)

(

)

,

(

0

*

0























11

Rekurencyjne strumienie zdarzeń -
9



Dowodzi się zależności:

Dowodzi się zależności:



Dla strumienia rekurencyjnego:

Dla strumienia rekurencyjnego:



Dla strumienia stacjonarnego:

Dla strumienia stacjonarnego:

))

(

1

(

)

(

)

1

(

)

(

1

)

,

(

*

*

1

*

*

s

zf

s

s

f

z

s

zf

z

s

G











))

(

1

(

)

(

1

)

,

(

*

*

*

s

zf

s

s

f

z

s

G







))

(

1

(

)

(

1

)

1

(

)

(

1

)

,

(

*

*

*

*

s

zf

s

s

s

f

z

s

zf

z

s

G















12

Rekurencyjne strumienie zdarzeń -
10

Oczekiwana liczba zdarzeń do chwili t

Oczekiwana liczba zdarzeń do chwili t



W praktyce wykorzystuje się zależność:

W praktyce wykorzystuje się zależność:



Dla strumienia rekurencyjnego:

Dla strumienia rekurencyjnego:











1

)

(

)}

(

{

)

(

r

r

t

K

t

E

t

H



)

(

1

)

(

1

))

(

(

)

(

*

*

1

*

s

f

s

f

s

t

H

L

s

H







)

(

1

)

(

1

)

(

*

*

*

s

f

s

f

s

s

H





13

Rekurencyjne strumienie zdarzeń -
11



Dla stacjonarnego strumienia rekurencyjnego:

Dla stacjonarnego strumienia rekurencyjnego:







t

H(t)

zatem

1

1

)

(

1

))

(

1

(

1

1

)

(

2

*

*

*















s

s

f

s

f

s

s

s

H

14

Rekurencyjne strumienie zdarzeń -
12

Rozrzedzanie strumieni zdarzeń

Rozrzedzanie strumieni zdarzeń



Jeśli jest zadany pewien strumień zdarzeń, to

Jeśli jest zadany pewien strumień zdarzeń, to

przez jego „rozrzedzenie” można tworzyć inne

przez jego „rozrzedzenie” można tworzyć inne

strumienie. Operacja rozrzedzania polega na

strumienie. Operacja rozrzedzania polega na

zaliczaniu do nowego strumienia tylko

zaliczaniu do nowego strumienia tylko

niektórych zdarzeń ze strumienia pierwotnego.

niektórych zdarzeń ze strumienia pierwotnego.



Szczególnie interesująca jest operacja

Szczególnie interesująca jest operacja

rekurencyjnego rozrzedzania.

rekurencyjnego rozrzedzania.



Załóżmy, że z pierwotnego strumienia zdarzeń

Załóżmy, że z pierwotnego strumienia zdarzeń

odrzucamy pierwszych

odrzucamy pierwszych





1

1

zdarzeń, a następne

zdarzeń, a następne

zaliczamy do nowego strumienia. Potem znowu

zaliczamy do nowego strumienia. Potem znowu

odrzucamy

odrzucamy





2

2

zdarzeń a kolejne zaliczamy itd..

zdarzeń a kolejne zaliczamy itd..



Jeśli ciąg (

Jeśli ciąg (





i

i

)

)

i=1,2,..

i=1,2,..

jest ciągiem niezależnych

jest ciągiem niezależnych

zmiennych losowych o identycznym rozkładzie to

zmiennych losowych o identycznym rozkładzie to

mówimy o rekurencyjnej operacji rozrzedzania.

mówimy o rekurencyjnej operacji rozrzedzania.

15

Rekurencyjne strumienie zdarzeń -
13

Tw.2.1.

Tw.2.1.

Strumień otrzymany z opóźnionego strumienia

Strumień otrzymany z opóźnionego strumienia

rekurencyjnego za pomocą rekurencyjnej

rekurencyjnego za pomocą rekurencyjnej

operacji rozrzedzania jest również

operacji rozrzedzania jest również

opóźnionym strumieniem rekurencyjnym.

opóźnionym strumieniem rekurencyjnym.



Wyznaczymy rozkład zmiennej losowej

Wyznaczymy rozkład zmiennej losowej

oznaczającej odstępy czasu między kolejnymi

oznaczającej odstępy czasu między kolejnymi

zdarzeniami w strumieniu rozrzedzonym.

zdarzeniami w strumieniu rozrzedzonym.



Przyjmijmy następujące oznaczenia

Przyjmijmy następujące oznaczenia

dodatkowe:

dodatkowe:

,..

3

,

2

,

'



i

T

i

))

(

(

)

(

)),

(

(

)

(

},

{

)

(

},

{

)

(

1

1

'

1

1

'

t

B

L

s

t

B

L

s

t

T

P

t

B

t

T

P

t

B

s

s

















16

Rekurencyjne strumienie zdarzeń -
14



Można wykazać, że:

Można wykazać, że:

1

,

,...

1

,

0

},

{

oraz

1

,

}

{

)

(

:

gdzie

))

(

(

)

(

)

(

))

(

(

)

(

)

(

0

*

*

*

*

1

1





























i

k

k

P

a

z

z

a

z

E

z

G

s

f

G

s

f

s

s

f

G

s

f

s

i

D

k

k

k

k













17

Rekurencyjne strumienie zdarzeń -
15

Sumowanie strumieni zdarzeń

Sumowanie strumieni zdarzeń



Inna operacją wykonywaną na strumieniach

Inna operacją wykonywaną na strumieniach

zdarzeń jest sumowanie. Jeśli

zdarzeń jest sumowanie. Jeśli

rozpatrywalibyśmy n różnych strumieni

rozpatrywalibyśmy n różnych strumieni

zdarzeń, to strumieniem sumarycznym byłby

zdarzeń, to strumieniem sumarycznym byłby

strumień, do którego zaliczylibyśmy wszystkie

strumień, do którego zaliczylibyśmy wszystkie

zdarzenia ze strumieni sumowanych.

zdarzenia ze strumieni sumowanych.



Ogólnie suma strumieni rekurencyjnych nie

Ogólnie suma strumieni rekurencyjnych nie

jest strumieniem rekurencyjnym (wyjątkiem

jest strumieniem rekurencyjnym (wyjątkiem

są strumienie Poissona).

są strumienie Poissona).



Prawdziwa jest jedynie następująca własność:

Prawdziwa jest jedynie następująca własność:

Jeśli

Jeśli

)

,

(

~

)

(

),

(

)

(

,..,

1

),

,

(

~

)

(

1

z

t

G

t

t

t

n

i

z

t

G

t

n

i

i

i

i

















18

Rekurencyjne strumienie zdarzeń -
16



To zachodzi zależność:

To zachodzi zależność:







n

i

i

z

t

G

z

t

G

1

)

,

(

)

,

(

19

Rekurencyjne strumienie zdarzeń -
17

Strumienie niepojedyncze

Strumienie niepojedyncze



Rozpatrzmy strumień zdarzeń

Rozpatrzmy strumień zdarzeń

(t

(t

i

i

)

)

i=1,2,..

i=1,2,..

i

i

załóżmy, że w chwili wystąpienia zdarzenia

załóżmy, że w chwili wystąpienia zdarzenia

przybywa paczka zgłoszeń o liczności

przybywa paczka zgłoszeń o liczności





i.

i.

,

,



Zakładamy, że ciąg (

Zakładamy, że ciąg (





i

i

)

)

i=1,2,..

i=1,2,..

jest ciągiem

jest ciągiem

zmiennych losowych i.i.d. oraz

zmiennych losowych i.i.d. oraz

(t

(t

i

i

)

)

i=1,2,..

i=1,2,..

i

i

(

(





i

i

)

)

i=1,2

i=1,2

są stochastycznie niezależne,

są stochastycznie niezależne,



Przyjmijmy następujące oznaczenia:

Przyjmijmy następujące oznaczenia:



Jeśli strumień zdarzeń

Jeśli strumień zdarzeń

(t

(t

i

i

)

)

i=1,2,..

i=1,2,..

jest opóźnionym

jest opóźnionym

strumieniem rekurencyjnym to strumień

strumieniem rekurencyjnym to strumień

zgłoszeń nazywamy opóźnionym strumieniem

zgłoszeń nazywamy opóźnionym strumieniem

quasi-rekurencyjnym.

quasi-rekurencyjnym.

1

,

d

(z)

oraz

,..

2

,

1

,

0

}

{

0

k

k

,















z

z

k

d

k

P

k

k

i





20

Rekurencyjne strumienie zdarzeń -
18



Oznaczmy przez

Oznaczmy przez





*

*

(t)

(t)

proces zliczający

proces zliczający

zgłoszenia w przedziale czasu

zgłoszenia w przedziale czasu

(0, t)

(0, t)

. Proces

. Proces

ten można a formalnie określić następująco:

ten można a formalnie określić następująco:



Dalej, niech:

Dalej, niech:







)

(

0

)

(

*

t

i

i

t







0

},

)

(

{

)

(

,

)

(

)

,

(

)

,

(

))

,

(

(

)

,

(

)

(

)

,

(

0

},

)

(

{

)

(

0

0

*

0

*

*











































k

k

t

P

t

P

z

t

P

z

t

G

dt

z

t

G

e

s

z

t

G

L

z

s

g

z

t

P

z

t

G

k

k

t

P

t

P

k

k

k

k

st

s

k

k

k

k





21

Rekurencyjne strumienie zdarzeń -
19



Podstawowe własności procesu

Podstawowe własności procesu





*

*

(t) :

(t) :

)}

(

{

var

)

(

var

}}

{

(

)

(

var

)}

(

{

}

{

)}

(

{

3

))

(

,

(

)

,

(

2

))

(

,

(

))

(

)(

(

)

(

)

,

(

1

2

0

*

0

0

0

*

0

t

E

t

E

t

t

E

E

t

E

z

s

g

z

s

g

z

t

G

z

t

P

z

t

P

z

t

G

k

k

k

k

k

k























































