Toruń, 2003
Zbigniew S. Szewczak
Uniwersytet Mikołaja Kopernika
Wydział Matematyki i Informatyki
“Graniczne własności łańcuchów
Markowa”
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
1
2
0
Model urnowy - zasada 1
☛
Kolor urny, z której losujemy, jest taki sam jak
ostatnio wylosowana kula
1
2
0
Model urnowy - zasada 2
☛
Zawsze zwracamy wylosowaną kulę do urny i
mieszamy kule
1
2
0
Model urnowy - losowanie 0
☛
Najpierw losujemy jedną kulę z urny czarnej
1
2
0
Model urnowy - losowanie 0
☛
Chowamy urnę czarną do szafy
1
2
0
Model urnowy - losowanie 0
☛
Ponieważ wylosowaliśmy kulę niebieską to
pierwsze losowanie będzie z urny niebieskiej
1
2
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
1
2
Drzewo losowań
c
n
n
n
c
c
n
c
n
c
n
c
n
c
n
O
1
2
3
n
4
Model urnowy - kolor (1)
☛
Pierwszy przypadek nieciekawy
1
2
0
Model urnowy - kolor (2)
☛
Drugi przypadek nieciekawy
1
2
0
Model urnowy - niezależny (1)
☛
Składy urn są jednakowe = schemat Bernoulliego
1
2
0
Model urnowy - niezależny (2)
☛
Równie dobrze moglibyśmy losować jedynie z
urny czerwonej
1
2
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
niebieskich odchyli się od o
dowolnie małą liczbę dodatnią
zmierza do zera wraz ze
wzrostem liczby losowań.
(1713)
5
12
Model urnowy
☛
Składy urn są różne
1
2
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
Ł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
Model urnowy
☛
Cztery urny : ciekawe czy nieciekawe czy
ciekawe?
1
2
3
0
4
Model urnowy
☛
Pięć urn: ciekawe czy nieciekawe czy ciekawe?
1
2
3
0
4
5
16?
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
.
Model urnowy
☛
Trzy urny dlatego, że trzy jest drugą liczbą
pierwszą
1
2
3
0
Model urnowy (c.d.)
☛
Z urny niebieskiej nie ma bezpośredniego
przejścia do urny zielonej
1
2
3
Tablica
☛
3x3
4
5
4
4
7
6
4
0
2
uk
Macierz
☛
u->i
☛
k->j
4
5
4
4
7
6
4
0
2
2
1
3
1
2
3
i j
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
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
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
Nieciekawy 1
☛
macierz jednostkowa
1
2
1
1
2
0
0
1
i j
Nieciekawy 2
☛
transponowana macierz jednostkowa
0
2
1
1
2
1
1
0
j
i
Schemat Bernoulliego
☛
niezależny: takie same wiersze
2
1
1
2
7
12
5
12
7
12
5
12
j
i
Macierz przejścia - zadanie
☛
urna
czerwona
: 4 x i 8 x
☛
urna
niebieska
: 5 x i 7 x
2
1
1
2
?
?
?
?
i j
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
Rozkład stacjonarny
☛
Skład urn : 4 kule niebieskie, 7 kul czerwonych
1
2
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.
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
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
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
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
Przykład dla
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 4/20
Przykład dla
Prawdopodobie´nstwa przej´scia za 2 kroki
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 4/20
Przykład dla
i
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 5/20
Przykład dla
i
!
"
!
"
!
!
"
"
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 5/20
Przykład dla
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 6/20
Przykład dla
Prawdopodobie´nstwa przej´scia za 3 kroki
#
$
%
$
%
#
$
%
$
%
#
$
%
$
%
#
$
%
$
%
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 6/20
Przykład dla
i
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 7/20
Przykład dla
i
#
!
!
"
!
#
!
"
"
"
#
!
"
!
!
!
"
"
!
#
!
"
!
!
"
"
"
"
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 7/20
Zadanie
Załó˙zmy, ˙ze
&
'
Oznaczmy
(
)
)
*
+
*
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 8/20
Zadanie
Załó˙zmy, ˙ze
&
'
Oznaczmy
(
)
)
*
+
*
*
(
*
*
)
(
*
*
)
(
*
*
(
*
'
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 8/20
Wskazówka
Mamy
)
)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 9/20
Wskazówka
Mamy
)
)
Poniewa˙z
to
)
$
%
)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 9/20
Wskazówka
Mamy
)
)
Poniewa˙z
to
)
$
%
)
Dodajemy
do obu stron
)
$
%
)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 9/20
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
Wskazówka (c.d.)
Wynosimy
poza nawias
$
)
%
)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 10/20
Wskazówka (c.d.)
Wynosimy
poza nawias
$
)
%
)
Poniewa˙z
)
to
)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 10/20
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
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
Wskazówka (c.d.)
Wynosimy
poza nawias
$
%
)
)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 11/20
Wskazówka (c.d.)
Wynosimy
poza nawias
$
%
)
)
Wynosimy
poza nawias
$
%
$
)
)
%
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 11/20
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
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
Przykład dla
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 12/20
Przykład dla
(
)
)
)
)
!
*
!
*
)
*
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 12/20
Przykład dla
(c.d.)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 13/20
Przykład dla
(c.d.)
Mamy
(
*
*
wi¸ec
*
(
*
!
*
)
(
*
)
*
)
(
*
!
)
!
!
*
(
*
!
"
'
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 13/20
Przykład dla
(c.d.)
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 14/20
Przykład dla
(c.d.)
Rozkład stacjonarny
*
*
!
!
!
*
*
*
!
"
*
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 14/20
Przykład dla
(c.d.)
Rozkład stacjonarny
*
*
!
!
!
*
*
*
!
"
*
Zadanie
*
*
*
*
*
*
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 14/20
Prawdopodobie ´nstwa za 2 kroki
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 15/20
Prawdopodobie ´nstwa za 2 kroki
wzór?
$
*
(
*
%
$
*
(
*
%
$
*
)
(
*
%
$
*
)
(
*
%
*
*
(
*
*
(
*
*
(
*
*
*
*
)
(
*
*
)
(
*
*
(
*
*
*
*
*
*
(
*
*
(
*
*
$
*
*
%
*
$
(
*
(
*
%
*
*
$
(
$
*
*
%
%
*
*
(
*
'
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 15/20
Zadanie (c.d.)
Dla
0
1
2
Je´sli
&
to
*
(
*
+
*
)
(
*
*
)
(
*
+
*
(
*
'
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 16/20
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
Twierdzenie spektralne
Twierdzenie
Je´sli
&
to
*
(
*
+
*
)
(
*
*
)
(
*
+
*
(
*
'
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 17/20
Twierdzenie spektralne
Twierdzenie
Je´sli
&
to
*
(
*
+
*
)
(
*
*
)
(
*
+
*
(
*
'
Zadanie. Udowodni´c twierdzenie spektralne.
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 17/20
Przykład dla
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 18/20
Przykład dla
*
(
*
!
*
)
(
*
)
*
)
(
*
!
)
!
*
(
*
!
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 18/20
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
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
Przykład dla
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 20/20
Przykład dla
*
(
*
!
6
!
*
)
(
*
)
6
*
)
(
*
!
)
!
6
!
*
(
*
!
6
Graniczne własno´sci binarnych ła´ncuch´ow Markowa – p. 20/20
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ć?
wstęp
do
rachunku
prawdopo-
dobień-
stwa
William Feller
tom pierwszy
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
A gdzie jest o tym więcej?
wstęp
do
rachunku
prawdopo-
dobień-
stwa
William Feller
tom drugi
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
- urnc.pdf
- Zbigniew S. Szewczak Uniwersytet Miko³aja KopernikaWydzia³ Matematyki i Informatyki
- Co to jest ³añcuch Markowa?
- Model urnowy
- Model urnowy - zasada 1
- Model urnowy - zasada 2
- Model urnowy - losowanie 0
- Model urnowy - losowanie 0
- Model urnowy - losowanie 0
- Model urnowy - losowanie 1
- Model urnowy - losowanie 1
- Model urnowy - losowanie 2
- Model urnowy - losowanie 3
- Model urnowy - losowanie 4
- Model urnowy - losowanie 5
- Model ze zwracaniem i wymian¹
- Drzewo losowañ
- Model urnowy - kolor (1)
- Model urnowy - kolor (2)
- Model urnowy - niezale¿ny (1)
- Model urnowy - niezale¿ny (2)
- Jaka jest czêstoœæ wzglêdna?
- Schemat Bernoulliego
- Model urnowy
- Jaka jest czêstoœæ wzglêdna?
- £añcuch Markowa
- Model urnowy
- Model urnowy
- Twierdzenie Wielandta
- Model urnowy
- Model urnowy (c.d.)
- Tablica
- Macierz
- Macierz stochastyczna
- Graf stochastyczny
- Macierz przejœcia
- Nieciekawy 1
- Nieciekawy 2
- Schemat Bernoulliego
- Macierz przejœcia - zadanie
- Co dalej?
- Rozk³ad stacjonarny
- W³asnoœci graniczne
- Kto po Markowie?
- Gdzie mo¿na o tym poczytaæ?
- Gdzie mo¿na o tym poczytaæ?
- A gdzie jest o tym wiêcej?
- Gdzie siê mo¿na tego nauczyæ?
- limc.pdf
- Macierz stochastyczna
- Prawdopodobie'nstwa przej'scia
- Przykl ad dla $n=2$
- Przykl ad dla $n=2$ i ${ ed {f P}}$
- Przykl ad dla $n=3$
- Przykl ad dla $n=3$ i ${ ed {f P}}$
- Zadanie
- Wskaz'owka
- Wskaz'owka (c.d.)
- Wskaz'owka (c.d.)
- Przykl ad dla ${ ed {f P}}$
- Przykl ad dla ${ ed {f P}}$ (c.d.)
- Przykl ad dla ${ ed {f P}}$ (c.d.)
- Prawdopodobie'nstwa za 2 kroki
- Zadanie (c.d.)
- Twierdzenie spektralne
- Przykl ad dla ${ ed {f P}}$
- Twierdzenie ergodyczne
- Przykl ad dla ${ ed {f P}}$
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