Graniczne własciwosci łańcuchów Markowa

background image

Toruń, 2003

Zbigniew S. Szewczak

Uniwersytet Mikołaja Kopernika

Wydział Matematyki i Informatyki

“Graniczne własności łańcuchów

Markowa”

background image

Co to jest łańcuch Markowa?

Każdy skończony, jednorodny łańcuch Markowa

jest równoważny modelowi urnowemu

background image

Model urnowy

Urna czarna, czerwona, niebieska

1

2

0

background image

Model urnowy - zasada 1

Kolor urny, z której losujemy, jest taki sam jak

ostatnio wylosowana kula

1

2

0

background image

Model urnowy - zasada 2

Zawsze zwracamy wylosowaną kulę do urny i

mieszamy kule

1

2

0

background image

Model urnowy - losowanie 0

Najpierw losujemy jedną kulę z urny czarnej

1

2

0

background image

Model urnowy - losowanie 0

Chowamy urnę czarną do szafy

1

2

0

background image

Model urnowy - losowanie 0

Ponieważ wylosowaliśmy kulę niebieską to

pierwsze losowanie będzie z urny niebieskiej

1

2

background image

Model urnowy - losowanie 1

W pierwszym losowaniu uzyskujemy kulę

czerwoną

1

2

0

background image

Model urnowy - losowanie 1

Ponieważ wylosowaliśmy kulę czerwoną to

następne losowanie będzie z urny czerwonej

1

2

background image

Model urnowy - losowanie 2

Zwracamy kulę czerwoną do urny niebieskiej

Losujemy z urny czerwonej kulę czerwoną

1

2

background image

Model urnowy - losowanie 3

Zwracamy kulę czerwoną do urny czerwonej

Losujemy z urny czerwonej kulę niebieską

1

2

background image

Model urnowy - losowanie 4

Zwracamy kulę niebieską do urny czerwonej

Losujemy z urny niebieskiej kulę niebieską

1

2

background image

Model urnowy - losowanie 5

Zwracamy kulę niebieską do urny niebieskiej

Losujemy z urny niebieskiej kulę czerwoną

itd...

1

2

background image

Model ze zwracaniem i wymianą

Jeśli wylosowana kula jest tego samego koloru co

poprzednio wylosowana kula to: losujemy dalej

Jeśli nie to: ujmujemy cztery kule wylosowanego

koloru i dodajemy cztery koloru przeciwnego

1

2

background image

Drzewo losowań

c

n

n

n

c

c

n

c

n

c

n

c

n

c

n

O

1
2

3

n

4

background image

Model urnowy - kolor (1)

Pierwszy przypadek nieciekawy

1

2

0

background image

Model urnowy - kolor (2)

Drugi przypadek nieciekawy

1

2

0

background image

Model urnowy - niezależny (1)

Składy urn są jednakowe = schemat Bernoulliego

1

2

0

background image

Model urnowy - niezależny (2)

Równie dobrze moglibyśmy losować jedynie z

urny czerwonej

1

2

0

background image

Jaka jest częstość względna?

Częstość względna występowania kul niebieskich

=(liczba wylosowanych kul niebieskich)/(liczba

losowań)

Jak zmienia się częstość względna

występowania kul niebieskich w przypadku, gdy

składy urn są jednakowe a liczba losowań się

zwiększa?

background image

Schemat Bernoulliego

Jakub Bernoulli I

ur. 27.12.1654, Bazylea

zm. 16.8.1705, Bazylea

Prawo wielkich liczb

dla schematu Bernoulliego

Szansa na to, że częstość

względna pojawienia się kul

niebieskich odchyli się od o

dowolnie małą liczbę dodatnią

zmierza do zera wraz ze

wzrostem liczby losowań.

(1713)

5

12

background image

Model urnowy

Składy urn są różne

1

2

0

background image

Jaka jest częstość względna?

Jaka jest częstość względna pojawienia się kuli

niebieskiej w przypadku, gdy składy urn nie są

jednakowe?

Na to pytanie prawo wielkich liczb Bernoulliego

nie daje odpowiedzi bowiem jest to binarny

łańcuch Markowa

background image

Łańcuch Markowa

Andriej A. Markow I

ur. 14.6.1856, Riazań

zm. 20.7.1922, Petersburg

Prawo wielkich liczb

dla łańcuchów Markowa

(1906)

Szansa na to, że częstość

względna pojawienia się kul

niebieskich odchyli się od o

dowolnie małą liczbę dodatnią

zmierza do zera wraz ze

wzrostem liczby losowań.

4

11

background image

Model urnowy

Cztery urny : ciekawe czy nieciekawe czy

ciekawe?

1

2

3

0

4

background image

Model urnowy

Pięć urn: ciekawe czy nieciekawe czy ciekawe?

1

2

3

0

4

5

16?

background image

Twierdzenie Wielandta

Jeśli losowując kulę dowolnego koloru z

dowolnej z N urn po N - 2 N + 2 krokach

możemy wylosować kulę dowolnego koloru to

taki łańcuch Markowa jest „ciekawy”.

„Ciekawy” bowiem zachodzi dla niego wiele praw

rachunku prawdopodobieństwa

2

.

background image

Model urnowy

Trzy urny dlatego, że trzy jest drugą liczbą

pierwszą

1

2

3

0

background image

Model urnowy (c.d.)

Z urny niebieskiej nie ma bezpośredniego

przejścia do urny zielonej

1

2

3

background image

Tablica

3x3

4

5
4

4

7
6

4

0
2

uk

background image

Macierz

u->i

k->j

4

5
4

4

7
6

4

0
2

2

1

3

1

2

3

i j

background image

Macierz stochastyczna

suma liczb w każdym wierszu wynosi 1

4

12

2

1

3

1

2

3

4

12

4

12

5

12

7

12

0

12

4

12

6

12

2

12

i

j

background image

Graf stochastyczny

suma „strzałek” wychodzących wynosi 1

4

12

5

12

4

12

4

12

6

12

4

12

0

12

2

12

7

12

background image

Macierz przejścia

liczby nieujemne

suma liczb w każdym wierszu wynosi 1

p

2

1

3

1

2

3

11

p

p

p

p

p

p

p

p

1

2

1

3

2

1

3

1

22

2

3

3

2

33

i

j

background image

Nieciekawy 1

macierz jednostkowa

1

2

1

1

2

0

0

1

i j

background image

Nieciekawy 2

transponowana macierz jednostkowa

0

2

1

1

2

1

1

0

j

i

background image

Schemat Bernoulliego

niezależny: takie same wiersze

2

1

1

2

7

12

5

12

7

12

5

12

j

i

background image

Macierz przejścia - zadanie

urna

czerwona

: 4 x i 8 x

urna

niebieska

: 5 x i 7 x

2

1

1

2

?

?

?

?

i j

background image

Co dalej?

Skąd te w prawie wielkich liczb Markowa?

Jak szybko szansa na to, że częstość względna

występowania kul niebieskich odchyli się od o

więcej niż 0.001 zmierza do zera?

Czy jest na to jakieś oszacowanie?

4

11

4

11

background image

Rozkład stacjonarny

Skład urn : 4 kule niebieskie, 7 kul czerwonych

1

2

0

background image

Własności graniczne

Twierdzenia graniczne dla łańcuchów Markowa

twierdzenie spektralne dla macierzy przejścia

twierdzenie ergodyczne dla macierzy przejścia

prawo wielkich liczb

teoria wielkich odchyleń

Twierdzenia graniczne można symulować

komputerowo

symulacja prawa wielkich liczb Markowa - Maple

background image

Macierz stochastyczna

Definicja.

Tablic¸e liczb





















postaci

tak¸a, ˙ze







oraz











nazywamy

macierz¸a stochastyczn¸a



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 2/20

background image

Macierz stochastyczna

Definicja.

Tablic¸e liczb





















postaci

tak¸a, ˙ze







oraz











nazywamy

macierz¸a stochastyczn¸a



Przykład.















gdzie

























Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 2/20

background image

Prawdopodobie ´nstwa przej´scia

Definicja.

Liczby





















nazywamy

prawdopodobie´nstwami przej´scia za jeden krok i oznaczamy









.

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 3/20

background image

Prawdopodobie ´nstwa przej´scia

Definicja.

Liczby





















nazywamy

prawdopodobie´nstwami przej´scia za jeden krok i oznaczamy









.

Definicja.

Je´sli





to liczby



























































































































nazywamy prawdopodobie´nstwami przej´scia za



kroków

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 3/20

background image

Przykład dla



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 4/20

background image

Przykład dla



Prawdopodobie´nstwa przej´scia za 2 kroki

























Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 4/20

background image

Przykład dla



i













Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 5/20

background image

Przykład dla



i

































!





















"









!









"





!









!







"





"



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 5/20

background image

Przykład dla



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 6/20

background image

Przykład dla



Prawdopodobie´nstwa przej´scia za 3 kroki



#





$

%



$

%





#





$

%



$

%





#





$

%



$

%





#





$

%



$

%



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 6/20

background image

Przykład dla



i













Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 7/20

background image

Przykład dla



i















#

























!



















!







"





!





#























!

















"







"





"





#





!















"





!









!









!



"





"





!





#





!













"





!







!









"



"





"





"



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 7/20

background image

Zadanie

Załó˙zmy, ˙ze

&



'

Oznaczmy

(





)

)

*



+

*





Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 8/20

background image

Zadanie

Załó˙zmy, ˙ze

&



'

Oznaczmy

(





)

)

*



+

*





Wykaza´c, ˙ze



*

(

*



*

)

(

*



*

)

(

*



*

(

*

'

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 8/20

background image

Wskazówka

Mamy

)



)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 9/20

background image

Wskazówka

Mamy

)



)

Poniewa˙z





to

)

$

%





)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 9/20

background image

Wskazówka

Mamy

)



)

Poniewa˙z





to

)

$

%





)

Dodajemy

do obu stron

)

$

%





)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 9/20

background image

Wskazówka

Mamy

)



)

Poniewa˙z





to

)

$

%





)

Dodajemy

do obu stron

)

$

%





)

Mno˙zymy wyra˙zenie w nawiasie

)



)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 9/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias

$



)

%





)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 10/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias

$



)

%





)

Poniewa˙z



)



to



)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 10/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias

$



)

%





)

Poniewa˙z



)



to



)

Przenosimy

na praw¸a stron¸e



)

)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 10/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias

$



)

%





)

Poniewa˙z



)



to



)

Przenosimy

na praw¸a stron¸e



)

)

Zamieniamy

na



)

)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 10/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias



$

%



)

)

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 11/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias



$

%



)

)

Wynosimy

poza nawias



$

%



$



)

)

%



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 11/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias



$

%



)

)

Wynosimy

poza nawias



$

%



$



)

)

%



Poniewa˙z

&



dzielimy obie strony przez



$



)

)

%



Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 11/20

background image

Wskazówka (c.d.)

Wynosimy

poza nawias



$

%



)

)

Wynosimy

poza nawias



$

%



$



)

)

%



Poniewa˙z

&



dzielimy obie strony przez



$



)

)

%



Podstawiamy

,

-

.

,

.

-

/

,

-

.



*





)

)



(



,

.

-

,

.

-

/

,

-

.



*



*

(

*

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 11/20

background image

Przykład dla













Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 12/20

background image

Przykład dla













(





)

)





)



)

!









*













!







*







)

*







Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 12/20

background image

Przykład dla

(c.d.)













Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 13/20

background image

Przykład dla

(c.d.)













Mamy

(





*







*





wi¸ec



*

(

*



!























*

)

(

*







)

















*

)

(

*



!





)







!







!





*

(

*













!







"



'

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 13/20

background image

Przykład dla

(c.d.)













Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 14/20

background image

Przykład dla

(c.d.)













Rozkład stacjonarny

*



*





!

















!





!







*

*



*





!















"











*

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 14/20

background image

Przykład dla

(c.d.)













Rozkład stacjonarny

*



*





!

















!





!







*

*



*





!















"











*

Zadanie

*









*











*



*









*











*

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 14/20

background image

Prawdopodobie ´nstwa za 2 kroki





























Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 15/20

background image

Prawdopodobie ´nstwa za 2 kroki





























Jaki

wzór?









$

*

(

*

%



$

*

(

*

%

$

*

)

(

*

%



$

*

)

(

*

%



*

*

(

*

*

(

*

*

(

*

*

*

*

)

(

*

*

)

(

*

*

(

*

*



*

*

*

*

(

*

*

(

*

*



$

*

*

%



*

$

(

*

(

*

%



*



*

$

(

$

*

*

%

%



*



*

(

*

'

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 15/20

background image

Zadanie (c.d.)

Dla

0

1

2

Je´sli

&



to







*

(

*

+







*

)

(

*







*

)

(

*

+







*

(

*

'

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 16/20

background image

Zadanie (c.d.)

Dla

0

1

2

Je´sli

&



to







*

(

*

+







*

)

(

*







*

)

(

*

+







*

(

*

'

Dla

0

1

3

Je´sli

&



to



#





*

(

#

*

+



#





*

)

(

#

*



#





*

)

(

#

*

+



#





*

(

#

*

'

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 16/20

background image

Twierdzenie spektralne

Twierdzenie

Je´sli

&



to









*

(



*

+









*

)

(



*









*

)

(



*

+









*

(



*

'

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 17/20

background image

Twierdzenie spektralne

Twierdzenie

Je´sli

&



to









*

(



*

+









*

)

(



*









*

)

(



*

+









*

(



*

'

Zadanie. Udowodni´c twierdzenie spektralne.

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 17/20

background image

Przykład dla













Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 18/20

background image

Przykład dla





















*

(



*



!

























*

)

(



*







)





















*

)

(



*



!





)









!













*

(



*















!





Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 18/20

background image

Twierdzenie ergodyczne

Twierdzenie

Je´sli

$

%

$

%

&



to

4

(

4



4



)

)

4

5



i







)

6



*

+







)

6



*







)

6



*

+







)

6



*

'

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 19/20

background image

Twierdzenie ergodyczne

Twierdzenie

Je´sli

$

%

$

%

&



to

4

(

4



4



)

)

4

5



i







)

6



*

+







)

6



*







)

6



*

+







)

6



*

'

Zadanie. Udowodni´c twierdzenie ergodyczne

Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 19/20

background image

Przykład dla













Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 20/20

background image

Przykład dla





















*

(



*



!

















6

!













*

)

(



*







)













6













*

)

(



*



!





)









!





6

!













*

(



*















!





6





Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 20/20

background image

Kto po Markowie?

S. N. Bernstein

G. D. Birkhoff

A. J. Chinczyn

J. Hadamard

A. N. Kołmogorow

W. I. Romanowski

B. W. Gniedenko

W. Doeblin

W. Feller

S. V. Nagaev

background image

Gdzie można o tym poczytać?

wstęp

do

rachunku

prawdopo-

dobień-

stwa

William Feller

tom pierwszy

background image

Gdzie można o tym poczytać?

Biblioteka

Matematyczna

TOM 18

Państwowe

Wydawnictwo

Naukowe

Warszawa 1969

Marek Fisz

RACHUNEK

PRAWDOPODO-

BIEŃSTWA

I

STATYSTYKA

MATEMATYCZNA

WYDANIE

CZWARTE

background image

A gdzie jest o tym więcej?

wstęp

do

rachunku

prawdopo-

dobień-

stwa

William Feller

tom drugi

background image

Gdzie się można tego nauczyć?

http

://www.mat.uni.torun.pl/

Zbigniew S.
Szewczak

Elektronicznie podpisany
przezZbigniew S.
Szewczak
DN: cn=Zbigniew S.
Szewczak, o=Nicholas
Copernicus University,
ou=Faculty of
Mathematics and
Computer Science, c=PL
Data:2003.11.29 16:30:46
+01'00'

Podpis nie
zweryfikowany


Document Outline


Wyszukiwarka

Podobne podstrony:
Tw o granicach wlaściwych funkcji
5 lancuchy markowa (2)
lancuchy markowa
Lancuchy Markowa 06 Naskrecki p4
Lasy Skierowane i Algorytmy Zwiazane z Lancuchami Markowa 97 Pokarowski PhD p147
lancuchy markowa
lancuchy markowa
5 lancuchy markowa2 (2)
Łancuchy Markowa p17
Prognozowanie na Podstawie Łancuchów Markowa p10x2 scan!!
5 lancuchy markowa
Prognozowanie na Podstawie Łancuchów Markowa p10x2 scan!!
D19241057 Rozporządzenie Rady Ministrów z dnia 29 grudnia 1924 r o rozszerzeniu granic gminy miejsk
Zarządzanie w Administracji Publicznej Rzeszów właściwe

więcej podobnych podstron