Zbigniew S. Szewczak
Uniwersytet Mikołaja Kopernika
Wydział Matematyki i Informatyki
Graniczne własności łańcuchów
Markowa
Toruń, 2003
Co to jest łańcuch Markowa?
&Każdy skończony, jednorodny łańcuch Markowa
jest równoważny modelowi urnowemu
Model urnowy
&Urna czarna, czerwona, niebieska
2
1
0
Model urnowy - zasada 1
&Kolor urny, z której losujemy, jest taki sam jak
ostatnio wylosowana kula
2
1
0
Model urnowy - zasada 2
&Zawsze zwracamy wylosowaną kulę do urny i
mieszamy kule
2
1
0
Model urnowy - losowanie 0
&Najpierw losujemy jedną kulę z urny czarnej
2
1
0
Model urnowy - losowanie 0
&Chowamy urnę czarną do szafy
2
1
0
Model urnowy - losowanie 0
&Ponieważ wylosowaliśmy kulę niebieską to
pierwsze losowanie będzie z urny niebieskiej
2
1
Model urnowy - losowanie 1
&W pierwszym losowaniu uzyskujemy kulę
czerwoną
1
2
0
Model urnowy - losowanie 1
&Ponieważ wylosowaliśmy kulę czerwoną to
następne losowanie będzie z urny czerwonej
1
2
Model urnowy - losowanie 2
&Zwracamy kulę czerwoną do urny niebieskiej
&Losujemy z urny czerwonej kulę czerwoną
1
2
Model urnowy - losowanie 3
&Zwracamy kulę czerwoną do urny czerwonej
&Losujemy z urny czerwonej kulę niebieską
1
2
Model urnowy - losowanie 4
&Zwracamy kulę niebieską do urny czerwonej
&Losujemy z urny niebieskiej kulę niebieską
1
2
Model urnowy - losowanie 5
&Zwracamy kulę niebieską do urny niebieskiej
&Losujemy z urny niebieskiej kulę czerwoną
&itd...
1
2
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
2
1
Drzewo losowań
O
n
c
n
1
c
n c n
2
3
c n c n c n c n
4
n
Model urnowy - kolor (1)
&Pierwszy przypadek nieciekawy
2
1
0
Model urnowy - kolor (2)
&Drugi przypadek nieciekawy
2
1
0
Model urnowy - niezależny (1)
&Składy urn są jednakowe = schemat Bernoulliego
2
1
0
Model urnowy - niezależny (2)
&Równie dobrze moglibyśmy losować jedynie z
urny czerwonej
2
1
0
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?
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
5
niebieskich odchyli się od o
12
dowolnie małą liczbę dodatnią
zmierza do zera wraz ze
wzrostem liczby losowań.
(1713)
Model urnowy
&Składy urn są różne
2
1
0
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
Aańcuch Markowa
&Andriej A. Markow I
&ur. 14.6.1856, Riazań
&zm. 20.7.1922, Petersburg
&Prawo wielkich liczb
&dla łańcuchów Markowa
Szansa na to, że częstość
względna pojawienia się kul 4
niebieskich odchyli się od o
11
dowolnie małą liczbę dodatnią
zmierza do zera wraz ze
wzrostem liczby losowań.
(1906)
Model urnowy
&Cztery urny : ciekawe czy nieciekawe czy
ciekawe?
1 2
3 4
0
Model urnowy
&Pięć urn: ciekawe czy nieciekawe czy ciekawe?
4
1
2
16?
3 5
0
Twierdzenie Wielandta
&Jeśli losowując kulę dowolnego koloru z
2
.
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
Model urnowy
&Trzy urny dlatego, że trzy jest drugą liczbą
pierwszą
2
1
3
0
Model urnowy (c.d.)
&Z urny niebieskiej nie ma bezpośredniego
przejścia do urny zielonej
2
1
3
Tablica
& 3x3
k
u
4 4 4
5 7 0
4 6 2
Macierz
&u->i
&k->j
j
1 2 3
i
1 4 4 4
2 5 7 0
3 4 6 2
Macierz stochastyczna
j
1 2 3
i
4 4 4
1
12 12 12
5 7 0
2
12 12 12
4 6 2
3
12 12 12
&suma liczb w każdym wierszu wynosi 1
Graf stochastyczny
4
12
4 5 4 4
12 12 12 12
6
2
7 12
12
12
0
12
&suma strzałek wychodzących wynosi 1
Macierz przejścia
j
1 2 3
i
p p p
1
11 12 13
p p p
2
21 22 23
p p p
3
31 32 33
& liczby nieujemne
& suma liczb w każdym wierszu wynosi 1
Nieciekawy 1
j
1 2
i
1 0
1
0 1
2
&macierz jednostkowa
Nieciekawy 2
j
1 2
i
0 1
1
1 0
2
&transponowana macierz jednostkowa
Schemat Bernoulliego
j
1 2
i
7 5
1
12 12
7 5
2
12 12
&niezależny: takie same wiersze
Macierz przejścia - zadanie
j
1 2
i
1
? ?
2
? ?
&urna czerwona: 4 x i 8 x
&urna niebieska: 5 x i 7 x
Co dalej?
4
&Skąd te w prawie wielkich liczb Markowa?
11
&Jak szybko szansa na to, że częstość względna
4
występowania kul niebieskich odchyli się od o
11
więcej niż 0.001 zmierza do zera?
&Czy jest na to jakieś oszacowanie?
Rozkład stacjonarny
&Skład urn : 4 kule niebieskie, 7 kul czerwonych
2
1
0
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
Macierz stochastyczna
Definicja.
Tablice liczb postaci
taka, że oraz
nazywamy macierza stochastyczna
Graniczne własności binarnych łańcuchów Markowa p. 2/2
Macierz stochastyczna
Definicja.
Tablice liczb postaci
taka, że oraz
nazywamy macierza stochastyczna
Przykład.
gdzie
Graniczne własności binarnych łańcuchów Markowa p. 2/2
Prawdopodobieństwa przejścia
Definicja. Liczby nazywamy
prawdopodobieństwami przejścia za jeden krok i oznaczamy
.
Graniczne własności binarnych łańcuchów Markowa p. 3/2
Prawdopodobieństwa przejścia
Definicja. Liczby nazywamy
prawdopodobieństwami przejścia za jeden krok i oznaczamy
.
Definicja. Jeśli to liczby
nazywamy prawdopodobieństwami przejścia za kroków
Graniczne własności binarnych łańcuchów Markowa p. 3/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 4/2
Przykład dla
Prawdopodobieństwa przejścia za 2 kroki
Graniczne własności binarnych łańcuchów Markowa p. 4/2
Przykład dla i
Graniczne własności binarnych łańcuchów Markowa p. 5/2
Przykład dla i
Graniczne własności binarnych łańcuchów Markowa p. 5/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 6/2
Przykład dla
Prawdopodobieństwa przejścia za 3 kroki
Graniczne własności binarnych łańcuchów Markowa p. 6/2
Przykład dla i
Graniczne własności binarnych łańcuchów Markowa p. 7/2
Przykład dla i
Graniczne własności binarnych łańcuchów Markowa p. 7/2
Zadanie
Załóżmy, że Oznaczmy
Graniczne własności binarnych łańcuchów Markowa p. 8/2
Zadanie
Załóżmy, że Oznaczmy
Wykazać, że
Graniczne własności binarnych łańcuchów Markowa p. 8/2
Wskazówka
Mamy
Graniczne własności binarnych łańcuchów Markowa p. 9/2
Wskazówka
Mamy
Ponieważ to
Graniczne własności binarnych łańcuchów Markowa p. 9/2
Wskazówka
Mamy
Ponieważ to
Dodajemy do obu stron
Graniczne własności binarnych łańcuchów Markowa p. 9/2
Wskazówka
Mamy
Ponieważ to
Dodajemy do obu stron
Mnożymy wyrażenie w nawiasie
Graniczne własności binarnych łańcuchów Markowa p. 9/2
Wskazówka (c.d.)
Wynosimy poza nawias
Graniczne własności binarnych łańcuchów Markowa p. 10/2
Wskazówka (c.d.)
Wynosimy poza nawias
Ponieważ to
Graniczne własności binarnych łańcuchów Markowa p. 10/2
Wskazówka (c.d.)
Wynosimy poza nawias
Ponieważ to
Przenosimy na praw strone
a
Graniczne własności binarnych łańcuchów Markowa p. 10/2
Wskazówka (c.d.)
Wynosimy poza nawias
Ponieważ to
Przenosimy na praw strone
a
Zamieniamy na
Graniczne własności binarnych łańcuchów Markowa p. 10/2
Wskazówka (c.d.)
Wynosimy poza nawias
Graniczne własności binarnych łańcuchów Markowa p. 11/2
Wskazówka (c.d.)
Wynosimy poza nawias
Wynosimy poza nawias
Graniczne własności binarnych łańcuchów Markowa p. 11/2
Wskazówka (c.d.)
Wynosimy poza nawias
Wynosimy poza nawias
Ponieważ dzielimy obie strony przez
Graniczne własności binarnych łańcuchów Markowa p. 11/2
Wskazówka (c.d.)
Wynosimy poza nawias
Wynosimy poza nawias
Ponieważ dzielimy obie strony przez
Podstawiamy
Graniczne własności binarnych łańcuchów Markowa p. 11/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 12/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 12/2
Przykład dla (c.d.)
Graniczne własności binarnych łańcuchów Markowa p. 13/2
Przykład dla (c.d.)
Mamy wiec
Graniczne własności binarnych łańcuchów Markowa p. 13/2
Przykład dla (c.d.)
Graniczne własności binarnych łańcuchów Markowa p. 14/2
Przykład dla (c.d.)
Rozkład stacjonarny
Graniczne własności binarnych łańcuchów Markowa p. 14/2
Przykład dla (c.d.)
Rozkład stacjonarny
Zadanie
Graniczne własności binarnych łańcuchów Markowa p. 14/2
Prawdopodobieństwa za 2 kroki
Graniczne własności binarnych łańcuchów Markowa p. 15/2
Prawdopodobieństwa za 2 kroki
Jaki wzór?
Graniczne własności binarnych łańcuchów Markowa p. 15/2
Zadanie (c.d.)
Dla
Jeśli to
Graniczne własności binarnych łańcuchów Markowa p. 16/2
Zadanie (c.d.)
Dla
Jeśli to
Dla
Jeśli to
Graniczne własności binarnych łańcuchów Markowa p. 16/2
Twierdzenie spektralne
Twierdzenie
Jeśli to
Graniczne własności binarnych łańcuchów Markowa p. 17/2
Twierdzenie spektralne
Twierdzenie
Jeśli to
Zadanie. Udowodnić twierdzenie spektralne.
Graniczne własności binarnych łańcuchów Markowa p. 17/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 18/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 18/2
Twierdzenie ergodyczne
Twierdzenie
Jeśli
to i
Graniczne własności binarnych łańcuchów Markowa p. 19/2
Twierdzenie ergodyczne
Twierdzenie
Jeśli
to i
Zadanie. Udowodnić twierdzenie ergodyczne
Graniczne własności binarnych łańcuchów Markowa p. 19/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 20/2
Przykład dla
Graniczne własności binarnych łańcuchów Markowa p. 20/2
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
Gdzie można o tym poczytać?
William Feller
wstęp
do
rachunku
prawdopo-
dobień-
stwa
tom pierwszy
Gdzie można o tym poczytać?
Marek Fisz
Biblioteka
Matematyczna
TOM 18
RACHUNEK
PRAWDOPODO-
BIECSTWA
I STATYSTYKA
MATEMATYCZNA
WYDANIE CZWARTE
Państwowe
Wydawnictwo
Naukowe
Warszawa 1969
A gdzie jest o tym więcej?
William Feller
wstęp
do
rachunku
prawdopo-
dobień-
stwa
tom drugi
Gdzie się można tego nauczyć?
&http://www.mat.uni.torun.pl/
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'
Zbigniew S.
Szewczak
Podpis nie
zweryfikowany
Wyszukiwarka
Podobne podstrony:
Łancuchy Markowa p175 lancuchy markowa2Lancuchy Markowa 06 Naskrecki p4notatek pl sily wewnetrzne i odksztalcenia w stanie granicznymRóżne interpretacje tytułu powieści GranicaDereń jadalny, właściwyTKANKA LACZNA WLASCIWAwięcej podobnych podstron