Elementy modelowania matematycznego

background image

1

Elementy modelowania

matematycznego

Jakub Wróblewski

jakubw@pjwstk.edu.pl

http://zajecia.jakubw.pl/

Łańcuchy Markowa.

ŁAŃCUCH MARKOWA

Przykład:
Rozważmy problem częstości występowania w języku
poszczególnych liter. Załóżmy, że interesuje nas nie tyle częstość
(prawdopodobieństwo) bezwzględne, co częstość uzależniona od
poprzedniej litery. Np. po literze ‘c’ częściej występuje ‘h’ niż ‘k’,
chociaż litera ‘k’ jest w języku polskim powszechniejsza.

Definicja:

Łańcuchem Markowa nazywamy ciąg zmiennych losowych X

n

o wartościach w pewnym zbiorze S taki, że dla każdego n:

czyli wartość zmiennej n zależy tylko od wartości dla n-1.

)

(

)

,

,

(

1

1

1

1

1

1

=

=

=

=

=

=

n

n

n

n

n

n

n

n

s

X

s

X

P

s

X

s

X

s

X

P

background image

2

MACIERZ PRZEJŚCIA

Z definicji łańcucha Markowa wynika, że prawdopodobieństwo
przejścia ze stanu i do j jest zawsze jednakowe. Oznaczmy je p

ij

.

Reprezentacja macierzowa przykładowego łańcucha Markowa:

Reprezentacja graficzna powyższego przykładu:

1





=





=

5

.

0

2

.

0

0

3

.

0

7

.

0

0

0

3

.

0

0

5

.

0

0

5

.

0

0

0

1

0

44

43

42

41

34

33

32

31

24

23

22

21

14

13

12

11

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

P

4

3

2

1

0.5

0.5

0.5

0.3

0.3

0.7

0.2

MACIERZ PRZEJŚCIA

Macierz przejścia może być użyta do policzenia, z jakimi
prawdopodobieństwami znajdziemy się w poszczególnych stanach
w kolejnym kroku. Np. jeśli w poprzednim przykładzie startujemy z
pozycji 1 lub 3 z jednakowym prawdopodobieństwem, to rozkład
prawdopodobieństwa w kolejnym kroku uzyskamy mnożąc wektor
prawdopodobieństw wyjściowych przez macierz przejścia:

Ogólnie, wektor (rozkład) prawdopodobieństw po k krokach
uzyskamy wymnażając wyjściowy rozkład przez P

k

.

(

)

(

)

35

.

0

,

0

,

5

.

0

,

15

.

0

5

.

0

2

.

0

0

3

.

0

7

.

0

0

0

3

.

0

0

5

.

0

0

5

.

0

0

0

1

0

0

,

5

.

0

,

0

,

5

.

0

0

1

=





=

=

P

p

p

background image

3

SYMULACJA ZJAWISK

Prawdopodobieństwa przejścia łańcucha Markowa można znaleźć
doświadczalnie, zliczając przypadki przejść między stanami.
Znaleziony łańcuch może być użyty do symulacji badanego zjawiska.

Przykład: Mamy zbiór N liter polskiego alfabetu. Przez p

ij

oznaczmy

prawdopodobieństwo, że po literze i następuje litera j. Możemy
znaleźć macierz P=(p

ij

) analizując dostatecznie duży zbiór tekstów.

Macierz P będzie miała różne wartości, w zależności od
analizowanego języka.

Symulacja powstawania słów: startujemy od losowej litery i,
następnie losujemy kolejną zgodnie z rozkładem (p

i1

, ... p

iN

).

Oznaczmy wylosowaną literę przez j. Potem losujemy kolejną z
rozkładem (p

j1

, ... p

jN

) itd. Utworzone w ten sposób słowo zwykle nic

nie znaczy, ale brzmi prawdopodobnie.

ROZKŁAD STACJONARNY

Rozkład prawdopodobieństwa π na zbiorze stanów łańcucha
Markowa, który nie zmienia się po wykonaniu jednego kroku,
nazywamy rozkładem stacjonarnym:

P

π

π

=

To, czy taki rozkład istnieje i jest jednoznacznie wyznaczony,
zależy m.in. od rodzaju stanów występujących w danym łańcuchu.

background image

4

KLASYFIKACJA STANÓW

Stan i jest osiągalny z j, jeśli istnieje
niezerowa ścieżka z j do i.

Zbiór stanów C jest zamknięty, jeśli
żaden stan spoza C nie jest
osiągalny ze stanu należącego do C.

Jednoelementowy zbiór zamknięty
nazywamy stanem pochłaniającym.

1

3

2

1

Przykład – zagadnienie ruiny gracza. Gracz ma kapitał początkowy N.
Z prawdopodobieństwem p wygrywa 1, z prawdop. 1-p przegrywa 1.
Jakie jest prawdopodobieństwo, że zbankrutuje (dojdzie do 0)?


Wyszukiwarka

Podobne podstrony:
MODELOWANIE MATEMATYCZNE
Elementy statystyki matematycznej wykorzystywane do opracowywania wielkości wyznaczanych, Geodezja i
BADANIA OPERACYJNE wykład1, WAT, semestr IV, Modelowanie Matematyczne
Gwiazdy i gwiazdeczki. Świadomość stałej liczby elementów w zbiorze.(1), matematyka
Modelowanie matematyczne problem 7(model)
2015 pytania na egzamin modelownie matematyczne
Elementarz modelowania powierzchniowego (cz I)
Cwiczenie6, Politechnika Wrocławska Energetyka, - MGR II semestr, Modelowanie matematyczne instalacj
Tematy na Modelowanie matematyczne w praktyce
Elementy Logiki Matematycznej Powtorzenie I Utrwalenie Materialu
Modelowanie matematyczne oceny 2
Elementy-logiki-matematycznej, WAT, semestr I, Analiza Matematyczna
Modelowanie matematyczne problem 2(model)
Modelowanie matematyczne problem 1(model)
MODELOWANIE MATEMATYCZNE BLOKU
02 Modelowanie matematyczne układów dynamicznych
Zadanie domowe, WAT, semestr IV, Modelowanie Matematyczne

więcej podobnych podstron