1. David Blackwell tétele

SZAKDOLGOZAT

Rejtett Markov láncok entrópiája és önkonformis mértékek Torma Lídia Boglárka

Témavezet®k:

Simon Károly,

egyetemi tanár

Komjáthy Júlia,

tudományos munkatárs

BME Matematika Intézet,

Sztochasztika Tanszék

BME 2012

Tartalomjegyzék Köszönetnyilvánítás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

1.

1

David Blackwell tétele

. . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.

Eddigi eredmények

. . . . . . . . . . . . . . . . . . . . . . . .

1

1.2.

A f® eredmény . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2.

Bináris szimmetrikus csatornák

. . . . . . . . . . . . . . . . . . . . .

3

3.

Blackwell tételének bizonyítása

. . . . . . . . . . . . . . . . . . . . .

6

4.

John J. Birch tétele . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

4.1.

Entrópiaközelítések . . . . . . . . . . . . . . . . . . . . . . . .

9

4.2.

Röviden az entrópia tulajdonságairól

. . . . . . . . . . . . . .

10

4.3.

Folyamat entrópiájának közelít®függvényei . . . . . . . . . . .

11

4.4.

Feltételes entrópiák konvergenciasebessége

. . . . . . . . . . .

12

5.

Víctor Ruiz tétele . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6.

A Sierpi«ski háromszög . . . . . . . . . . . . . . . . . . . . . . . . . .

17

6.1.

Az állapotvalószín¶ségek meghatározása

. . . . . . . . . . . .

17

6.2.

Az entrópia kiszámítása

. . . . . . . . . . . . . . . . . . . . .

19

. . . . . . . . . . . . . . . . . . . . . . . . . . .

21

7.

A Sierpi«ski sz®nyeg 7.1.

Az állapotvalószín¶ségek meghatározása

. . . . . . . . . . . .

21

7.2.

Az entrópia kiszámítása

. . . . . . . . . . . . . . . . . . . . .

24

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

Összegzés

i

ii

Köszönetnyilvánítás Ezúton szeretném megköszönni témavezet®imnek, Simon Károlynak és Komjáthy Júliának, kitartó és lelkes munkájukat, de mindenekfelett a türelmet és bátorítást, amit t®lük kaptam. Köszönöm szépen barátaimnak, Áginak és Anikónak, hogy átsegítettek az eddigi hat féléven. Köszönöm Bettinek és Ákosnak, hogy mindig számíthattam rájuk. Nem utolsó sorban hálás vagyok szüleimnek, akik szeretete és támogatása nélkül most nem írhatnám ezeket a sorokat, továbbá n®véremnek, aki a nehéz id®kben is mindig mellettem állt. Köszönettel tartozom a tanáraimnak és iskoláimnak a megfelel® alapokért a további fejl®déshez.

1.

DAVID BLACKWELL TÉTELE

1

1. David Blackwell tétele 1.1. Eddigi eredmények A rejtett Markov-láncok

H

entrópiájának számolása nem

egyszer¶ feladat. Már az 1950-es években napvilágot láttak olyan eredmények, melyeknek a mai napig hasznát vesszük az információelméletben. David Blackwell munkássága folytán, 1957-ben publikált eredménye[1] jó alapot adott a kés®bbi számításoknak és alkalmazásoknak is. Legyen

{1, . . . , N }

(p1 , . . . , pN )

{Xi }∞ i=1

egy

állapotokkal,

stacionárius,

ergodikus,

M = ||m(i, j)||

véges

Markov-lánc,

állapotvalószín¶ség-mátrixszal, és

kezdeti eloszlásvektorral. Ekkor egy véges

következésének valószín¶sége

állapotú

i = (i1 , . . . , ik )

P(X1 = i1 , . . . , Xk = ik ).

Legyen

Zi

az

| qX =

sorozat be-

(X1 , . . . , Xi )

valószín¶ségi változók együttes eloszlása. Shannon munkája alapján McMillan megmutatta, hogy

{Zi } aszimptotikusan tart egy konstanshoz, az {Xi } folyamat H ≥ 0

entrópiájához, oly módon, hogy nyezi, hogy nagy

− k1 E| ln Zk | → H ,

amint

k → ∞.

Ez azt eredmé-

k esetén nagy valószín¶séggel a ténylegesen bekövetkez® X1 , . . . , Xk

sorozat valószín¶sége

eHk

lesz. Ezen felül

H = −E ln P(X1 |X0 , X−1 , . . . ). Tehát, ha

{Xi }

egy Markov-folyamat

m(i, j) = P(Xk+1 = j|Xk = i, Xk−1 , . . . ) H=−

X

πi = P(Xk = i)

(1)

stacionárius eloszlással, és

állapotvalószín¶ségekkel, akkor

πi m(i, j) ln m(i, j),

(2)

i,j

(l. [3]). Habár a Markov-láncok entrópiája az el®z® formula alapján könnyen számolható, ugyanez nem mondható el a rejtett Markov-láncokról. Ha

{1, . . . , M },

akkor

{Yi = Φ(Xi )}

egyszer¶ formula. Valójában

H

Φ : {1, . . . , N } 7→

entrópiájának számításához nincs (2)-hez hasonló,

az

M = ||m(i, j)|| mátrix és Φ bonyolult függvénye.

1.2. A f® eredmény 1. Tétel (Blackwell [1]).

Legyen

{Xi }∞ i=0

nárius, ergodikus Markov-folyamat,

egy

[N ]

állapottéren értelmezett, stacio-

M = ||m(i, j)||

állapotvalószín¶ség-mátrixszal.

2

Legyen

Φ : {1, . . . , N } 7→ {1, . . . , M }

entrópiája

H=−

Z X

olyan, hogy

Yi = Φ(Xi ).

Az

{Yi }

folyamat

ra (w) ln ra (w)dQ(w),

(3)

w = (w1 , . . . , wN ) ∈ W , avagy wi jelöli az i állapotban tartózkodás valószíN P P P n¶ségét. wi = 1, és ra (w) = wi m(i, j), avagy az a állapotba ugrás

ahol

i

i=1 j : Φ(j)=a

valószín¶sége, adott

w W

eloszlása a

w

valószín¶ségi vektor mellett.

W1 , . . . , W M

elemekb®l áll, hogy

halmazokon értelmezett

eloszlás, és

Φ(i) 6= a, és kielégíti a X Z Q(E) = ra (w)dQ(w)

wi = 0,

ha

a

egyenletet, ahol

Q

P wi m(i,j) i

ra (w)

, ha

olyan

w∈

(4)

fa−1 (E)

fa (w) : W 7→ Wa , fa (w) =

Wa

Φ(j) = a.

2.

BINÁRIS SZIMMETRIKUS CSATORNÁK

3

2. Bináris szimmetrikus csatornák Az el®z® tétel könnyebb megértéséhez egy konkrét példát mutatunk be.[2] A bemenet az

Xi

Markov lánc,

Π=

szal. A csatornában a jelre rakódott

PEi (1) = ε. folyamat, A kal és

Π00 Π01

! állapotvalószín¶ségi mátrix-

Π10 Π11 bináris zaj E = {Ei } úgy,

hogy

PEi (0) = 1 − ε,

A zajjal módosult kimenet a stacionárius, sztochasztikus

Yi = Xi ⊕ Ei . ⊕

{Zi = (Xi , Ei )}

a bináris összeadást jelenti.

folyamat szintén Markovi,

(0, 0)

(0, 0), (0, 1), (1, 0), (1, 1)

(0, 1)

(1, 0)

Y = {Yi } állapotok-

(1, 1)

(0, 0) Π00 (1 − ε) Π00 ε Π01 (1 − ε) Π01 ε

M = (0, 1) Π00 (1 − ε) Π00 ε Π01 (1 − ε) Π01 ε (1, 0) Π10 (1 − ε) Π10 ε Π11 (1 − ε) Π11 ε (1, 1) Π10 (1 − ε) Π10 ε Π11 (1 − ε) Π11 ε átmenetvalószín¶ség-mátrixszal. Ekkor legyen

Φ : {(0, 0), (0, 1), (1, 0), (1, 1)} 7→ {0, 1} Φ(0, 0) = Φ(1, 1) = 0

továbbá

és

úgy, hogy

Φ(0, 1) = Φ(1, 0) = 1,

Yi = Φ(Zi ).

Abban a speciális esetben, amikor Markov folyamat az



{1, 2, 3, 4}

p

Π =

1−p

1−p

!

p

, és

Z = {Zi }∞ i=−∞

állapottéren van értelmezve, az

p(1 − ε)

pε

(1 − p)(1 − ε) (1 − p)ε

  p(1 − ε) pε (1 − p)(1 − ε) (1 − p)ε M =  (1 − p)(1 − ε) (1 − p)ε p(1 − ε) pε  (1 − p)(1 − ε) (1 − p)ε p(1 − ε) pε átmenetvalószín¶ség-mátrix adódik. Továbbá

Φ : {1, 2, 3, 4} 7→ {1, 2}

úgy, hogy

Φ(1) = Φ(4) = 1 és legyen

{Yi := Φ(Zi )}∞ i=−∞ .

Most nézzük a

W ⊂ R4 -en ( W :=

és

Φ(2) = Φ(3) = 2,

lév® szimplexet, ahol

w ∈ R4 : wi ≥ 0,

4 X

) wi = 1 ,

i=1

W1 = {w ∈ W : w2 = w3 = 0}

és

     

4

W2 = {w ∈ W : w1 = w4 = 0}. Annak érdekében, hogy a megfelel® átmenetvalószín¶ség-mátrixokat megkapjuk,

M -nek

kinullázzuk azokat az

i.

oszlopait, ahol



Φ(i) 6= a,

ha

a = 1, 2:

0 0 (1 − p)ε



(1 − p)(1 − ε) 0



p(1 − ε)

  p(1 − ε) 0 0 (1 − p)ε M1 =   (1 − p)(1 − ε) 0 0 pε  (1 − p)(1 − ε) 0 0 pε 

0

pε

    

   0  pε (1 − p)(1 − ε) 0 . M2 =   0 (1 − p)ε p(1 − ε) 0    0 (1 − p)ε p(1 − ε) 0 Továbbá

∀w ∈ W -re

legyen

ra (w) := w| · Ma · 1 = ||w| · Ma ||1 (vagyis az

a-ba

kerülés valószín¶sége), és

fa : W 7→ Wa : fa (w) := w| · w

Tekintsük most az 1. ábrát. Vegyünk egy tett, zöld

W -n.

ros

P1

W1 , (e1 , e4 ) és

P2

pontot a négy vektor által kifeszí-

Ez a Markov-lánc kezdeti értéke, azaz a kezdeti eloszlás.

a transzponáltját jobbról az valószín¶ségét,

Ma . ra (w)

|

w · M -et. és a kék

M

mátrixszal beszorozva kapjuk a következ® állapot

Ennek a pontnak keressük a mer®leges vetületét a pi-

W2 , (e2 , e3 )

lesznek. Ezt a vetítést az

vektorok által kifeszített síkra.

M1

illetve az

érjük el. Figyeljük meg ugyanis, hogy az

M1

M2

és

e3

vektorok értéke

nulla. Hasonlóképpen az

0,

és az

M2 -nél

M1 -nek

csak az

Markov-folyamatból megkapjuk az Annak a valószín¶sége, hogy a

r1 (w),

ami megfelel a

deniált

(f1 , f2 )

P1

Y w

Ezek rendre

mátrixokkal való szorzásként

mátrixban pontosan azok az oszlopok

vannak kinullázva, amely vektort nullának tekintünk.

e2

Ennek

{e1 , e4 }-re

Az

vetítésnél az

pont a második és a harmadik oszlopa

e2

és

e3

értékeket tartjuk meg. Ezzel a

Z

rejtett Markov-folyamatot. utáni állapot éppen

pont és az origó távolságának.

W1 -ben

lesz, pontosan

Az ennek a segítségével

iterált függvényekhez tartozó valószín¶ségek

(r1 (w), r2 (w))

a

w

helyt®l függ® valószín¶ségek. Tehát ez egy iterált függvény rendszer (IFS), helyt®l függ® valószín¶ségekkel.

2.

BINÁRIS SZIMMETRIKUS CSATORNÁK

f1 (w)

e1

R4

W1 e4

P1

wT · M

W 0

e3

w∈W

W

2

r1 (w)

5

P2 r2 (w)

e2

f2 (w)

1. ábra. Az ábra a [2] cikkb®l származik, szerz®k engedélyével.

6

3. Blackwell tételének bizonyítása Bizonyítás. Most rekonstruáljuk az 1. tétel bizonyítását.[1] Legyen

n αn := (α1n , . . . , αN ) = P(Xn |Yn , Yn−1 , . . . )

feltételes eloszlás, vagyis

αin = P(Xn = i|Yn , Yn−1 , . . . ). Továbbá legyen

Q

deníció szerint az

α0

eloszlása.

A bizonyítás menete a következ®képpen alakul. A (3) egyenlet igazolásához be kell látnunk, hogy

E(ln P(Y1 |Y0 , Y−1 , . . . )|α0 = w) = ahonnan az (1) egyenletb®l következik, hogy ha teljesül, nevezetesen az (1)-et alkalmazva

Y -ra,

X

w

ra (w) ln ra (w),

(5)

a eloszlása

Q,

akkor a (3) egyenlet

kapjuk, hogy

H = −E(ln P(Y1 |Y0 , Y−1 , . . . )). Innen, és a teljes valószín¶ség tételéb®l azonnal adódik, hogy a (3)-as egyenlet bal oldala egyenl®

H -val.

A következ® célunk, hogy a (4)-es formulát igazoljuk, vagyis hogy

Q(E) =

X Z a

ra (w)dQ(w).

fa−1 (E)

Ehhez az els® lépés, hogy belátjuk a következ® lemmát. 1. Lemma.

{αn }

egy stacionárius Markov-folyamat,

P(αn+1 ∈ E|αn , αn−1 , . . . ) =

X a : fa

ra (αn )

(6)

(αn )∈E

valószín¶ségekkel. Hiszen ekkor

αn

eloszlása megegyezik

α0

eloszlásával, ami éppen

Q(w).

A

Q

szerint integrálva (6)-ot, pedig pont a (4) egyenlethez jutunk. Az (5) formula igazolásához szükségünk van az 1. lemma bizonyításában elért eredményekre, így azt csak a fejezet végén tudjuk megmutatni.

Az 1. lemma bizonyítása.

αn

stacionaritását a következ®képpen bizonyítjuk.

Meg kell mutatnunk, hogy Legyen

αin állapotok eloszlása nem változik az id® el®rehaladtával.

gi (Y0 , Y−1 , . . . ) az a függvény, amely leírja αi0

viselkedését,

Ψ egy tetsz®leges,

3.

BLACKWELL TÉTELÉNEK BIZONYÍTÁSA

(Yn , Yn−1 , . . . )-t®l Gn

7

függ®, korlátos valószín¶ségi változó, továbbá

egy szigma-algebra. Akkor

G(Yn , Yn−1 , . . . ) =

E(Ψ(Yn , Yn−1 , . . . )P(Xn = i|Yn , Yn−1 , . . . )) = = E(Ψ(Yn , Yn−1 , . . . )P(Xn = i|Gn )) = = E(E(Ψ(Yn , Yn−1 , . . . )[1 1(Xn = i)|Gn ])) = = E(Ψ(Yn , Yn−1 , . . . )1 1(Xn = i)) = = E(Ψ(Y0 , Y−1 , . . . )1 1(X0 = i)) = = E(E(Ψ(Y0 , Y−1 , . . . )[1 1(X0 = i|G0 ])) = = E(Ψ(Y0 , Y−1 , . . . )P(X0 = i|G0 )) = = E(Ψ(Y0 , Y−1 , . . . )P(X0 = i|Y0 , Y−1 , . . . )) = = E(Ψ(Yn , Yn−1 , . . . )gi (Yn , Yn−1 , . . . )).

Tehát

P(Xn = i|Yn , Yn−1 , . . . ) = αin = gi (Yn , Yn−1 , . . . ),

eloszlása szintén

tehát

Q.

{αn }

stacionárius, és

Következ® lépés a (6) egyenlet igazolása.

P(Xn+1 = i|Yn , Yn−1 , . . . ) =

X

P(Xn+1 = i, Xn = j|Yn , Yn−1 , . . . ) =

(7)

j

=

X

=

X

j

j

P(Xn = j|Yn , Yn−1 , . . . ) · P(Xn+1 = i|Xn = j, Yn , Yn−1 , . . . ) = P(Xn = j|Yn , Yn−1 , . . . ) · m(j, i).

Az utolsó egyenl®ség a Markov tulajdonság miatt teljesül. Ha a (7) egyenletet minden olyan

P(Yn+1 = a|Yn , Yn−1 , . . . ) =

i-re

összeadjuk, hogy

X

Φ(i) = a

teljesül, akkor

P(Xn+1 = i|Yn , Yn−1 , . . . ) =

i : Φ(i)=a

=

X X i : Φ(i)=a

j

P(Xn = j|Yn , Yn−1 , . . . ) · m(j, i) = ra (αn ).

Ezt felhasználva

P(Xn+1 = i|Yn , Yn−1 , . . . ) = = P(Xn+1 = i|Yn+1 = a, Yn , Yn−1 , . . . ) · P(Yn+1 = a|Yn , Yn−1 , . . . ) =

= ra (αn )P(Xn+1 = i|Yn+1 , Yn , . . . )1 1(Yn+1 = a).

(8)

8

Ezt, és a (7) egyenletet összevetve kapjuk, hogy

X

ra (αn )P(Xn+1 = i|Yn+1 , Yn , . . . ) =

j

fa (w) =

P wi m(i,j) i

ra (w)

esetén

P(Xn = j|Yn , Yn−1 , . . . ) · m(j, i)

X P(Xn = j|Yn , Yn−1 , . . . ) · m(j, i) , n) r (α a j

P(Xn+1 = i|Yn+1 , Yn , . . . ) = tehát az

Yn+1 = a = Φ(i)

deníció alapján

αn+1 = fYn+1 (αn ). Mivel

fa (w) ∈ Wa ∀ w-re,

W1 , . . . , WM -re

így az

αn

(9)

valószín¶ségi változónak a

Q

eloszlása

koncentrálódik. A (9) egyenletb®l következik, hogy

P(αn+1 ∈ E|αn , αn−1 , . . . ) =

X

P(Yn+1 = a|αn , αn−1 , . . . ),

a : fa (αn )∈E

ahonnan a (8) egyenletet használva megkapjuk a (6) egyenletet, vagyis

P(αn+1 ∈ E|αn , αn−1 , . . . ) = =

X

P(Yn+1 = a|αn , αn−1 , . . . ) =

a : fa (αn )∈E

X

ra (αn ).

a : fa (αn )∈E

Innen már a fejezet elején elmondottakból következik a (4). Végül a (3) egyenletet kell belátnunk, vagyis az

Yn

folyamat entrópiáját kell

kiszámítanunk. A (8) egyenletb®l tudjuk, hogy

E(ln P(Y1 |Y0 , Y−1 , . . . )|α0 = w) =

P(Y1 = a|Y0 , Y−1 , . . . ) = ra (α0 ), X

P(Y1 = a|α0 ) ln ra (α0 ) =

a

Innen a (3) egyenlet  a fejezet elején kimondottak alapján 

X

tehát

ra (α0 ) ln ra (α0 ).

a

Q szerinti integrálással,

teljes valószín¶ség tételével, és az (1) egyenlet felhasználásával már következik.

4.

JOHN J. BIRCH TÉTELE

9

4. John J. Birch tétele 4.1. Entrópiaközelítések Ha

{Xn }

egy

{1, 2, . . . , N }

véges halmazon vett stacionárius, ergodikus Markov fo-

lyamat, akkor az entrópiája közvetlenül számolható. Azonban, ha a

Φ : {1, 2, . . . , N } 7→ {1, 2, . . . , M }, akkor nincs átfogó formula

{Yn = Φ(Xn )}

entrópiájának kiszámítására.

Ezt az

értéket azonban John J. Birch 1961-ben publikált eredménye szerint [5] közelíthetjük

¯ n = h(Yn |Yn−1 , . . . , Y1 ) G

feltételes entrópiákkal.

és

Gn = h(Yn |Yn−1 , . . . , Y1 , X0 )

Továbbá, ha az eredeti

{Xn }

monoton függvényekkel, a Markov folyamat átmenet

valószín¶ségei szigorúan pozitívak, vagyis minden állapotból minden állapot elérési valószín¶sége nagyobb, mint nulla, akkor

H

entrópiához:

függetlenek. Legyen

Q

a

¯ n − H ≤ Bρ 0≤G P(Y0 |X0 , X−1 , . . . )

n−1

és

¯n G

és

Gn

exponenciálisan konvergálnak a

0 ≤ H − Gn ≤ Bρn−1 , 0 < ρ < 1, ρ

valószín¶ségi változó eloszlása, azaz

X0

és

Φ

®sképein

egy eloszlás, ami pozitív súlyt ad.

A gyakorlati alkalmazásokhoz azonban szükségünk van az entrópia egy olyan közelítésére, amely gyorsan konvergál. Meg kell jegyezni,

hogy ha az

{Xn }

folyamat markovi,

akkor az entrópia

a (2) egyenletb®l közvetlenül számítható. Továbbá, ahogyan az 1 fejezetben láttuk, Blackwell megmutatta, hogyha

Φ

egy olyan leképezés, amely az állapotok csupán

egy osztályát ejti össze, akkor az entrópia kifejezhet® a konvergáló elemek összegével. (Például ha

Q

egy véges halmazra koncentrálódik, akkor a legkézenfekv®bb példa

az, amikor a Markov-folyamat legalább két állapotosztályát összeejtjük különálló állapotokká.) Megmutatjuk, hogy ha

{Xn }

egy stacionárius, ergodikus, véges állapotter¶

{Yn = Φ(Xn )}

Markov-folyamat, akkor az

folyamat entrópiája közelíthet® a

¯ n = h(Yn |Yn−1 , . . . , Y1 ) G és

Gn = h(Yn |Yn−1 , . . . , Y1 , X0 ) monoton függvényekkel. Továbbá, ha ennek az

{Xn }

Markov-folyamatnak szigorúan pozitív állapotva-

lószín¶ségei vannak, akkor ez a két approximáció exponenciálisan konvergál a

H

10

entrópiához, ahol a konvergencia az alábbi képlettel adott:

¯ n − H ≤ Bρn−1 0
B=

0 ≤ H − Gn ≤ Bρn−1 ,

és

N uma , és N um1 mini,j m(i,j)

 0 < ρ = 1 − min

i,j,k,n,o

N um1 N um2M



m(i, k)m(k, n) m(i, j)m(j, o

avagy a kétlépéses átmenetek mennyire térhetnek el. és a maximuma a

Φ

N um1

2 < 1,

és

N umM

a minimuma

által összehúzott állapotok számának.

4.2. Röviden az entrópia tulajdonságairól Legyen

Y

egy valószín¶ségi változó, véges

els® fejezetben láttuk, az

Y

(y1 , . . . , yk ) értékekkel. h(Y )

valószín¶ségi változónak a

Mint ahogy azt az

entrópiája a következ®

képlettel számítható:

h(Y ) = − A

(i)

(ii)

h

X

P(Y = yi ) ln P(Y = yi ).

i

függvény néhány tulajdonsága:

h(Y ) ≤ ln k

(egyenletes entrópia),

h(X, Y ) = h(Y ) + h(X|Y )

(Bayes), ahol

h(X|Y ) = −

ln P(X = xj |Y = yi ), (iii)

h(X|Y, Z) ≤ h(X|Y ) ≤ h(X),

(iv) minden,

Y

egyenl®ség akkor, ha

értékein értelmezett

összehúzzuk) és

Φ

függvényre

h(Z|Y ) ≤ h(Z|Φ(Y ))

P i,j

P(Y = ui , X = vj )

X, Y, Z

függetelnek,

h(Φ(Y )) ≤ h(Y )

(csökken, mert

(ha kevesebbet ismerünk).

A fenti mennyiségek mindegyike nemnegatív. Az elkövetkezend®kben feltesszük, hogy adott egy

m(i, j), i, j = 1, 2, . . . , N egy kezdeti stacionárius

Y1 , Y2 , . . .

folyamatra

elemekkel, egy

λ = (λ1 , . . . , λN )

Yk = Φ(Xk ),

ami

N × N -es M

Markov mátrix

Φ : {1, . . . , N } 7→ {1, . . . , M } eloszlás

függvény, és

{1, . . . , N }-en, (λ, M )

{1, . . . , M }-b®l

tesen ez egy stacionárius, ergodikus folyamat lesz.

eloszlással.

veszi az értékeit. Természe-

4.

JOHN J. BIRCH TÉTELE

11

4.3. Folyamat entrópiájának közelít®függvényei El®ször deniáljuk a következ®t:

h(Y1 , Y2 , . . . , Yn ) , n együttes entrópia n-ed része.

Hn (M, Φ, λ) = n

hosszú trajektória mentén az

M. McMillan megmutatta, hogy ha monoton csökkenve konvergál a

λ

a stacionárius eloszlás, akkor

H(M, Φ, λ)

konstanshoz, vagyis az

Hn (M, Φ, λ)

{Yn }

folyamat

entrópiájához. Megemlítjük a következ®, L. Breiman-tól származó eredményt:

2 ln(N ). n ¯ n = h(Yn |Yn−1 , . . . , Y1 ), ahol {Yn = Φ(Xn )} a folyamat. A (iii) tuLegyen G ¯1 ≥ G ¯ 2 ≥ . . . , és mivel G ¯ n ≥ 0, ezért lim G ¯n = H lajdonságból kapjuk, hogy G |H(M, Φ, λ) − Hn (M, Φ, λ)| ≤

n→∞

n P ¯i G

határérték létezik. Most, a stacionaritást felhasználva kor

¯ n = H(M, Φ, λ). lim G Legyen most

2. Lemma.

Gn

Gn = h(Yn |Yn−1 , . . . , Y1 , X0 ),

lim

1

n→∞ n+1

= H(M, Φ, λ).

Ek-

akkor:

monoton n®ve konvergál az entrópiához (H(M, Φ, λ)).

Bizonyítás. Hogy lássuk, hogy

Gn

monoton,

Gn = h(Yn |Yn−1 , . . . , Y1 , X0 , X−1 ) (X−1

nem számít, mert Markovi)

≤ h(Yn |Yn−1 , . . . , Y1 , Φ(X0 ), X−1 ) (a Gn ≤ h(Yn |Yn−1 , . . . , Y1 , Y0 , X−1 ) = Gn+1

(iv) miatt)

stacionaritás miatt.

Alkalmazva a (ii)-t,

¯ n − Gn = h(Yn |Yn−1 , . . . , Y1 ) − h(Yn |Yn−1 , . . . , Y1 , X0 ) G   P(X0 |Y1 , . . . Yn ) = E ln (≤ 0). P(X0 |Y1 , . . . , Yn−1 ) (Y1 , . . . , Yn ) = tn , X0 = i

Minden rögzített egybeesik valamelyik valamely

n-re

P(X0 = i|Y1 , . . . , Yn )

és valamely

esetén, az

P(X0 |Y1 , . . . Yn )

eseménnyel, ahol

(X1 , . . . , Xn )-re

i ∈ {1, . . . , N }.

változó Tehát,

|P(X0 |Y1 , . . . Yn ) − P(X0 |Y1 , . . . Yn−1 )| ≤ De

X i

|P(X0 = i|Y1 , . . . , Yn ) − P(X0 = i|Y1 , . . . , Yn−1 )|.

P(X0 = i|Y1 , . . . , Yn )

P(X0 |Y1 , . . . Yn ) konvergál. ¯ n ≥ Gn a (iii)-ból következik. ≥G

kezésképpen

¯ n−1 G

egy martingál, így majdnem mindenütt konvergál. Követ-

12

4.4. Feltételes entrópiák konvergenciasebessége

Most csak azokat az eseteket vizsgáljuk, mikor az gorúan pozitívak,

Legyen

m(i, j)

állapotvalószín¶ségek szi-

∀i, j -re.

X0 , X1 , . . .

egy véges állapotú Markov lánc,

gekkel. Deniáljunk egy

{Yn }

m(i, j)

folyamatot aszerint, hogy

(X -t minden pillanatban levetítem).

Most rögzített

átmenetvalószín¶sé-

Y = i <=> X ∈ Φ−1 (i)

Y1 = i1 , . . . , Yn−1 = in−1 -re,

legyen

fn (g, a) = P(Xn = a|X0 = g, X1 ∈ Φ−1 (i1 ), . . . , Xn−1 ∈ Φ−1 (in−1 )),

ami pont az a valószín¶ség, hogy Markov láncban, ahol a

k -adik

g -b®l n

lépés alatt

a-ba

értünk egy nem homogén

lépés állapotvalószín¶sége:

M (k) (j, l) = P(Xk = l|Xk−1 = j, Xk ∈ Φ−1 (ik ), . . . , Xn−1 ∈ Φ−1 (in−1 )) = (6= 0,

ha

l ∈ Φ−1 (ik ))

m(i, j)P(Xk ∈ Φ−1 (ik ), . . . , Xn−1 ∈ Φ−1 (in−1 )|Xk = l) =P , m(j, l0 )P(Xk ∈ Φ−1 (ik ), . . . , Xn−1 ∈ Φ−1 (in−1 )|Xk = l0 ) l0

k = 1, . . . , n − 1

és

M (n) (j, l) = m(j, l).

fn (g, a) =

X

Innen

M (1) (g, a1 )M (2) (a1 , a2 ) . . . M (n) (an−1 , a).

4.

JOHN J. BIRCH TÉTELE

13

n = 2-re:

A képlet helyessége

X

f2 (g, a) =

M (1) (g, a1 )M (2) (a1 , a) =

a1 ∈Φ−1 (i1 )

X m(g, a1 )P(X1 ∈ Φ−1 (i1 ), X2 ∈ Φ−1 (i2 )|X1 = a1 ) P ∗ = m(g, l0 )P(X1 ∈ Φ−1 (i1 ), X2 ∈ Φ−1 (i2 )|X1 = l0 ) a 1

l0

p(a1 , a)P(X2 ∈ Φ−1 (i2 )|X2 = a) ∗P = m(a1 , j 0 )P(X2 ∈ Φ−1 (i2 )|X2 = j 0 ) j0

X m(g, a1 )P(X1 ∈ Φ−1 (i1 ), X2 ∈ Φ−1 (i2 )|X1 = a1 ) P = ∗ m(a1 , j 0 )1 1(j 0 ∈ Φ−1 (i2 )) a 1

j0

∗P l0

P(X2 ∈ Φ−1 (i2 )|X2 = a)m(a1 , a) = m(g, l0 )1 1(l0 ∈ Φ−1 (i1 ))P(X2 ∈ Φ−1 (i2 )|X1 = l0 )

=P l0

∗

X

m(g, a1 )

a1

1 0

0

m(g, l )1 1(l ∈

Φ−1 (i1 ))P(X2

∈ Φ−1 (i2 )|X1 = l0 )

∗

P(X2 ∈ Φ−1 (i2 )|X1 = a1 )m(a1 , a)1 1(a ∈ Φ−1 (i2 )) P = m(a1 , j 0 ) j 0 ∈Φ−1 (i2 )

=P l0

1 0

0

m(g, l )1 1(l ∈ X

a1 ∈Φ−1 (i1 )

Φ−1 (i

m(l0 , x)

P

1 ))

∗

x∈Φ−1 (i2 )

m(g, a1 )m(a1 , a)1 1(a ∈ Φ−1 (i2 )) =

P(X2 = a, X0 = g, X1 ∈ Φ (i1 )) = P(X2 = a|X0 = g, X1 ∈ Φ−1 (i1 )). P(X0 = g, X1 ∈ Φ−1 (i1 )) −1

A következ® tételt Markov-láncokra fogjuk használni.

Legyen

2. Tétel.

1, 2, . . . , N ,

g

és

h

a Markov-lánc két állapota.

Ha

akkor

m(i, j) > 0 ∀i, j =

|fn (g, a) − fn (h, a)| ≤ ρn−1 , ahol

 ρ = 1 − min

i,j,l,m

avagy a

2

N um1 N um2M



m(i, l)m(l, n) m(i, j)m(j, m)

2 ,

hosszú utak valószín¶ségei mennyire térhetnek el.

Bizonyítás. Doeblin two-particle módszerét használtuk a bizonyításhoz.

||(P m (x, .) − π(.)|| ≤ (1 − )m ) ∀m ∈ N.

14

Ez alapján

|fn (g, Φ−1 (i)) − fn (h, Φ−1 (i))| P P ≤| fn (g, a) − fn (h, a)| a∈Φ−1 (i)

≤|

P a∈Φ−1 (i)

(10) (11)

a∈Φ−1 (i)

|fn (g, a) − fn (h, a)| = N umM ρn−1 .

(12)

Továbbá,

|P(Yn = i|X0 = g, Y1 , . . . , Yn−1 ) − P(Yn = i|Y1 , . . . ), Yn−1 )| ≤ N umM ρn−1 . Hogy ezt lássuk, megmutatjuk, hogy létezik egy

(Y1 , . . . , Yn−1 )-t®l

függ®

h,

hogy

P(Yn = i|Y1 , . . . , Yn−1 ) ≥ P(Yn = i|X0 = h, Y1 , . . . , Yn−1 ). Ez viszont következik P P P(Yn = i|Y1 , . . . , Yn−1 ) = P(Yn = i, X0 = h|Y1 , . . . , Yn−1 ) = P(Yn = i|X0 = h

h, Y1 , . . . , Yn−1 )P(Yn = i|Y1 , . . . , Yn−1 ) miatt van legalább egy

h,

amire

h, Y1 , . . . , Yn−1 ). 3. Tétel.

Legyen

{Xn }

h alapján, ugyanis ez egy súlyozott átlag, ami

P(Yn = i|X0 = h, Y1 , . . . , Yn−1 ) ≤ P(Yn = i|X0 =

egy stacionárius, ergodikus, véges állapotter¶ Markov-lánc,

szigorúan pozitív állapotvalószín¶ségekkel. Akkor az

{Yn = Φ(Xn )} folyamat entrópi-

¯ n = h(Yn |Yn−1 , . . . , Y1 ) és Gn = h(Yn |Yn−1 , . . . , Y1 , X0 )-al G N umM ¯ n − Gn ≤ Bρn−1 , 0 < ρ < 1, ahol B = 0≤G . ája

becsülhet®. Továbbá,

N um1 min m(i,j) i,j

Bizonyítás. Már csak az exponenciális csökkenést kell megmutatni. Korábban már láttuk, hogy

¯ n − Gn = E ln P(Yn |X0 , Y1 , . . . , Yn−1 ) . G P(Yn |Y1 , . . . , Yn−1 ) Most legyen

0<

1 r

:= N um1 min m(i, j) ≤ P(Xn |X1 , . . . , Xn−1 ), i,j

és az el®z®ek miatt

¯ n − Gn ≤ G ¯n → H ln(1 + rN umM ρn−1 ) ≤ rN umM ρn−1 = Bρn−1 , ha n elég nagy. S mivel G ¯ n − Bρn−1 ≤ monoton csökken®en, és Gn → H monoton növekedve, kapjuk, hogy G ¯ n ≤ Gn + Bρn−1 . Gn ≤ H ≤ G P(Xn |Y0 , X1 , . . . , Xn−1 ) − P(Xn |X1 , . . . , Xn−1 ) ≤ N umM ρn−1 .

Érdekesség, hogy az exponenciális csökkenés független a

Φ

Ekkor

függvényt®l.

5.

VÍCTOR RUIZ TÉTELE

15

5. Víctor Ruiz tétele

A következ® fejezetek Vícitor Ruiz [6] munkájára alapulnak, és arra irányulnak, hogy a rejtett Markov-láncok elméletének felhasználásával, egészen konkrétan az el®z® fejezetben látottakkal, exponenciális közelítést adjunk bizonyos önhasonló mértékek dimenziójára. Deniáljuk az

[N ]

állapottéren értelmezett

N × N -es,

sztochasztikus

Z1 = 1,

∃

Zn

Z1 , Z2 , . . . , Zn

mátrixokkal, és a

átmenetvalószín¶ség-mátrixszal. Ekkor

A

és

π

egy

{Vj }j∈N

N P

q | Zi1 1 = q |

i1 =1

Zi -k

stacionárius eloszlás, hogy

folyamatra igaz lesz, hogy

q | Zi1 Zi2 . . . Zik 1,

V1 , V2 , · · · = {Vj }j∈N

ahol

q

a kezdeti eloszlás

folyamatot az

Z = Z1 + Z2 + · · · +

tulajdonságaiból következik, hogy

πZ = π .

P(V1 = i1 , V2 = i2 , . . . , Vk = ik ) = N P P(V1 = i1 ) = vektor. k = 1 esetén i1 =1

X

Zi1 1 = q | 1 = 1. | {z } Z

Megmutatjuk,

hogy

az

így

deniált

folyamat

értelmezhet®

rejtett

Markov-láncként (HMC). Ehhez konstruáljunk egy HMC-t, ami pontosan a lálnunk kell egy

X1 , X2 , . . .

{Vj }j∈N

Markov-láncot, és egy olyan

Φ

folyamatot adja. Ta-

függvényt, hogy

Vi =

Φ(Xi ). X

állapottere legyen

úgy, hogy az

és deniáljuk

{1, 2, . . . , n}

↓

függvényt

állapotokat rendre

↓

n 1 2 állapotokba viszi. A HMC állapotait leíró mátrixokat



nN

z   0 ···   . . Mi =  .. ..   0 ··· 

alakban kapjuk,

Mn .

Φ : {N × N } 7→ {n × n}

1, . . . N , N + 1, . . . , 2N , . . . , (n − 1)N + 1, . . . , nN | {z } | {z } | {z } ↓

az

[nN ],

q |M = (q | Z1 , . . . , q | Zn )

}| Zi · · · . . .

. . .

Zi · · ·

 {  0   .  .  .  0  

kezdeti eloszlással. Ekkor

M = M1 + · · · +

16

Nevezzük ezt a folyamatot

V˜ -nak.

Ekkor

V˜ = V ,

ugyanis

P(Y1 = i1 , Y2 = i2 , . . . , Yk = ik ) = q |M Mi1 Mi2 . . . Mik 1 = (q | Z1 Zi1 Zi2 . . . Zik , . . . , q | Zn Zi1 . . . Zik )1 = (q | Z1 , . . . , q | Zn ) · Zi1 Zi2 . . . Zik 1 = q | Z · Zi1 Zi2 . . . Zik 1 = q | Zi1 Zi2 . . . Zik 1 =

P(V1 = i1 , V2 = i2 , . . . , Vk = ik ). A kés®bbiekben ezt a megfeleltetést a Sierpi«ski háromszög, illetve a elforgatott Sierpi«ski sz®nyeg piaközelítéséhez használjuk.

[0, 1]

45◦ -kal

intervallumra vett pushdown mértékének entró-

6.

A SIERPI‹SKI HÁROMSZÖG

17

6. A Sierpi«ski háromszög

6.1. Az állapotvalószín¶ségek meghatározása Tekintsük az

( F=

x x S1 (x) = , S2 (x) = + 2 2 Λ

IFS-sel deniált

{ 13 , 13 , 13 } most a

[0, 1]

mérték

| 1 x , 0 , S3 (x) = + 2 2

Sierpinski-háromszöget

valószín¶ségvektorral. A

µ



Λ-n

Σ = {1, 2, 3}N

√ !| ) 1 3 , 4 4

állapottérrel, és

vett természetes mérték

intervallumon vett pushdown mértékét,

µ = pN . ν -t.

p =

Tekintsük

Ruiz megmu-

tatta, hogy ez a mérték egy diszkrét idej¶, nem-markovi, stacionárius és ergodikus sztochasztikus folyamat állapotaiként értelmezhet®, el®re meghatározott mátrixokkal.

Ahogyan azt az el®z®ekben láttuk, ez a folyamat egy rejtett Markov-láncot

határoz meg, melynek entrópiáját a

Gn

így elég jó pontossággal meghatározva

¯n G

és

monoton függvényekkel közelíthetjük,

dim ν -t.

Π∗

ν 0

1

A mátrixok meghatározásához tekintsük a Sierpinski-gasket-et, kissé másként. A 2. ábra szerint vágjuk függ®legesen félbe a háromszöget; a bal oldali háromszöget színezzük feketére, míg a jobb oldalit zöldre. Ezt követ®en, az els® iteráció elvégzése után a jobb oldali felet illesszük pontosan a bal oldal fölé. A keletkezett alakzatot

1 -nél függ®legesen újra félbevágva gyeljük meg, hogy az eredeti fekete- illetve zöld 4 1 háromszögekhez hasonló, akkora háromszögek keletkeztek. 3 Deniáljuk a

Z0

Z0

és

Z1

mátrixokat a fekete és zöld háromszögek száma szerint.

jelöli azt az esetet, amikor a bal,

Hogyan kapjuk a

Zi

Z1

pedig, amikor a jobb oszlopot tekintjük.

mátrix elemeit? Legyen

vagy a földszinten vagyunk, és

u = 1, 2

aszerint, hogy az emeleten,

v = 1, 2, hogy melyik típusú háromszögr®l beszélünk.

18

emelet

földszint

0

1 4

1

1 2

0

1 4

1

1 2

2. ábra. Sierpi«ski háromszögek, másként

Így a mátrixok

Zi (u, v)

elemei rendre

Z0 = Ugyanis (Z0 (1, 1)

gyeljük

= 1),

emelet (Z0 (2, 1)

és

0

=1

meg,

1 0

! , Z1 =

1 1 hogy

a

és

Z0 (2, 2) = 1)

= 0)

.

0 1

földszint

darab zöld (Z0 (1, 2)

!

1 1

bal

1

darab

fekete

háromszöget tartartalmaz, míg az

mindkét típusból

1-et 1-et.

oszlopa mindkét típusból tartalmaz egyet-egyet (Z1 (1, 1) emeleten pedig csak

1

oszlopa

darab zöld háromszög van (Z1 (2, 1)

A földszint jobb

= 1

és

Z1 (1, 2) = 1),

= 0,

és

Z1 (2, 2) = 1).

az

Attól függ®en, hogy jobbra, vagy balra lépünk, a megfelel® mátrixok szorzódnak. Egy

1 méret¶ intervallum mátrixa 2n

Zi2 ,...,in .

Azonban hogyan kapjuk meg az elemeit?

A mátrix elemeit a következ®képp deniálhatjuk:

Zi2 ,...,in (u, v) = #{j n : Vjn ⊂ proj−1 x (I(u−1),i2 ,...,in )}, azaz

v = 1

(n − 1)-edik

esetén az

I(u−1),i2 ,...,in

intervallum fölötti fekete,

szinten lév® háromszögek száma.

Ii1 ...in

v = 2

jelölés esetén

esetén a zöld

i1

mindig az

6.

A SIERPI‹SKI HÁROMSZÖG

19

eredeti háromszögre vonatkozik, azaz megmondja, hogy a félbevágott háromszögben a földszinten, vagy az emeleten vagyunk. A deníció

n = 3-ra:

Zi2 i3 (u, v) = #{j2 ∈ {0, 1}2 : Vj2 ∈ proj−1 x {I(u−1)i2 i3 }}. 1. Állítás.

Zi2 ,...,in+1 (u, v) =

X

Zi1 ,...,in (u, t)Zin (t, v)

t∈{1,2}

ahol

u, v ∈ {1, 2}.

Bizonyítás. A

Zi2 ,...,in ,in+1 (u, v),

visszavezethet® az amikor

i2 = 1

és

vagyis az

(n − 1)-edik

szintre.

i3 = 0. Zi2 ,i3 (1, 1)

n-edik Például

szinten lév® háromszögek száma

n = 2-re

nézzük azt az esetet,

jelenti azoknak a második szint¶, fekete (bal-

oldali) háromszögeknek a számát, amelyek az

I010

intervallum fölött megmaradtak.

I01

intervallum feletti háromszögeket megszámol-

juk, és felnagyítva tovább bontjuk.

Ezek mindegyike úgy fog viselkedni, mint a

Ezeket úgy kapjuk meg, hogy az

földszinti, nagy, fekete, illetve az emeleti, nagy, zöld háromszög.

Z1 (1, 1) = Z1 (1, 2) = 1.

Egy újabb iteráció elvégzése után

háromszögb®l a bal oszlopban

Z1 (1, 1) · Z0 (1, 1) = 1

Deníció szerint

Z1 (1, 1)

darab fekete

darab fekete háromszög lesz.

Ugyanis felnagyítva a fekete háromszögeket, azok ugyanúgy viselkednek, mint a kiindulási fekete háromszög, amelynek egy iteráció után a bal oszlopban gyereke lesz.

Hasonlóan az el®z® gondolatmenethez,

Z1 (1, 2) · Z0 (2, 1) = 1 összesen

Z1 (1, 2)

kis fekete háromszöget képez az

I010

Z10 (1, 1) = Z1 (1, 1) · Z0 (1, 1) + Z1 (1, 2) · Z0 (2, 1) = 2

Z0 (1, 1)

db zöld háromszög

intervallum fölé.

Ez

kis fekete háromszög.

Ezt az elvet használva az állítás indukcióval adódik.

Fontos megjegyezni, hogy itt az önhasonlóságot er®teljesen kihasználtuk, hiszen minden lépést a kezdeti formákra vezettünk vissza. Ha például adódnának, akkor feljebb

3

3

3 × 3-as

mátrixok

különböz® alakzatunk lenne, és a továbbiakban ezekb®l is leg-

féle, ezekhez hasonló alakzatokat lehetne levezetni.

6.2. Az entrópia kiszámítása Most, hogy a

V (q, Z0 , Z1 )

ν

mérték állapotvalószín¶ségeit ismerjük, gyeljük meg, hogy a

folyamat egy rejtett Markov-láncként viselkedik, tehát az entrópiáját

ilyen módon közelítve is meghatározhatjuk. Vegyük

észre

azt

Zi 1 = 1 (i ∈ {0, 1}),

is,

hogy

a

Z0

és

Z1

mátrixok

ergodikusak,

és

tehát sztochasztikusak is. Ruiz el®z® fejezetben bemutatott

módszere szerint ekkor a folyamat entrópiáját egy rejtett markov-lánc entrópiájaként

20

kezelhetjük. Birch munkája alapján tudjuk, hogy létezik exponenciális közelítése a

¯ n = h(Vn |Vn−1 , . . . , V1 ) és Gn = h(Vn |Vn−1 , . . . , V1 , X0 ) feltételes entrópiákkal, ahol G ¯ n az entrópia fels® korlátját. Tudjuk, hogy Gn jelöli az alsó, míg G ¯ n = h(Vn |Vn−1 , . . . , V1 ) = h(Vn , Vn−1 , . . . , V1 ) − h(Vn−1 , . . . , V1 ). G Hasonlóképpen,

Gn = h(Vn |Vn−1 , . . . , V1 , X0 ) = h(Vn , Vn−1 , . . . , V1 , X0 ) − h(Vn−1 , . . . , V1 , X0 ). Az alsó közelítést könnyen számolhatjuk, így például

1

1

1

XXX ¯3 = 1 G P(V1 = i, V2 = j, V3 = k) ln P(V1 = i, V2 = j, V3 = k) − ln 2 i=0 j=0 k=0 1

1

1 XX P(V1 = i, V2 = j) ln P(V1 = i, V2 = j) = − ln 2 i=0 j=0 1

=

1

1

1 XXX | q Zj Zk 1 ln qi| Zj Zk 1 − ln 2 i=0 j=0 k=0 i 1

1

1 XX | − qi Zj 1 ln qi| Zj 1. ln 2 i=0 j=0 Wolfram Mathematica programmal számolva

¯ 11 = 0.98876588 G

elég jó közelítés

lesz.

Gn

számításához be kell vezetünk egy plusz feltételt, az eredeti Markov-láncot.

Tegyük fel, hogy ez elemei, és

X , és V = Φ(X), ahol X

Φ(1) = Φ(2) = 0,

és

lehetséges értékei az

Φ(3) = Φ(4) = 1.

{1, 2, 3, 4} halmaz

P(X0 = i0 , V1 = i1 , . . . , Vn = in ) = q | Zi∗0 Zi1 ,...,in 1, ahol

Zi∗ (i ∈ {1, 2, 3, 4})

mátrixokat úgy kapjuk, hogy a

ZΦ(i)

mátrix els®, illetve

második oszlopát változatlanul hagyjuk, a többit kinullázzuk. Ekkor

Z1∗ =

1 0

!

1 0

, Z2∗ =

0 0 0 1

! , Z3∗ =

1 0 0 0

! , és

0 1

Z4∗ =

!

0 1

mátrixok adódnak.

G11 = 0.98876557,

ami az els®

6

tizedesjegyik

Ezzel tulajdonképpen le is ellen®riztük Ruiz eredményét, az els®

6

tizedesjegyig.

Ezekkel a mátrixokkal számolva megegyezik

¯ 11 -gyel. G

7.

A SIERPI‹SKI SZŽNYEG

21

7. A Sierpi«ski sz®nyeg Ebben a fejezetben Ruiz [6] technikáját terjesztem ki a Sierpi«ski sz®nyeg

45◦ -os

vetületének esetére.

7.1. Az állapotvalószín¶ségek meghatározása Ruiz eredménye nem csupán a Sierpi«ski háromszög esetében használható. Vegyük például a természetes mértéket(az egyenletes eloszlás mértékét) a

[0, 1]

Sierpinski sz®nyegen, s ezt vertikálisan vetítsük le a

45◦ -kal elforgatott

intervallumra.

(A Sier-

pi«ski sz®nyeg pontos denícióját megtalálhatjuk [4] el®adásjegyzetben.) önhasonló

1 x 3

ν

mérték lesz, a

[0, 1]

F = {S1 (x) =

intervallumon vett

+ 61 , S3 (x) = 13 x + 26 , S4 (x) = 31 x + 36 , S5 (x) = 13 x + 46 }

valószín¶ségekkel. leképezése

Π∗ ,

azaz

IFS-sel,

A Sierpinski sz®nyegen vett természetes

µ

p=

mérték

Ez egy

1 x, S2 (x) = 3 ( 18 , 28 , 28 , 28 , 81 )

[0, 1]-re

való

ν = Π∗ µ.

Π∗

ν 0 A

Zi

1

mátrixok meghatározásához bontsuk fel a sz®nyeget a következ®képpen:

Az els® iteráció el®tt és

I1

0.5-nél

függ®legesen kettévágjuk a négyzetet, amely ezáltal

bal- illetve jobboldali háromszögekre esik szét.

Ezután végezzük el az els®

iterációt, majd a 3. ábrán látható módon, függ®leges egyenesekkel daraboljuk fel részre. Ezen részeknek az intervallumra es® vetületei Észrevehet®, hogy ekkor a négyzet derékszög¶ háromszögre esik szét.

8−8

I0

I00 , . . . , I12

6

lesznek.

jobb- illetve bal oldali, egyenl® szárú,

Ezek hasonlóak az els® vágás után keletkezett

háromszögekkel. Vizsgáljuk meg külön-külön az egyes szeleteket. Vegyünk fel egy intervallumon.

t ∈ I1

Ha

t ∈ I0 ,

t pontot a [0, 1]

akkor a bal oldali háromszöget kell vizsgálnunk, míg

esetén a jobb oldalit. A két intervallulmba esés valószín¶sége azonos,

1 . Így 2

22

a kezdeti eloszlás vektorok

e|0 = 12 (1, 0)

és

e|1 = 21 (0, 1).

Amennyiben a keletkezett

háromszögek számát szeretnénk megkapni, nem kell lenormálnunk a vektorokat,

e∗| 0 = (1, 0)-t

és

e∗| 1 = (0, 1)-et.

Két fajta háromszög lévén hiszen a háromszögeket

3

részre osztottuk fel. Legyenek ezek a mátrixok rendre

1 0

Z0∗ =

2 × 2-es mátrixokat kell konstruálni, számszerint 3-at,

!

2 2

, Z1∗ =

Számoljuk meg ugyanis, hogy az sz®nyeg hány darab maz.

0-ás

I00

1

és

1 2

fölött

1

1-es db

0

!

2 2

Z2∗ =

.

0 1

intervallumok fölött a Sierpinski-

(jobboldali) típusú háromszöget tartalés

nézzük, akkor látjuk, hogy mindkét típusból eloszlással, jobbról a

!

I00 , I01 , . . . , I1,2

(baloldali) ill.

Azt látjuk, hogy az

2 1

2

0

db

1-es

típusú van.

db van. Így

Z0∗ -ot

Ha az

I10 -át

balról a kezdeti

vektorral szorozva kapjuk az adott rész háromszögeinek a

számát. A

Z1∗

mátrixot beszorozva bal ol-

e∗0

dalról az

kezdeti eloszlásvektorral, a

mátrix els® sorából képzett vektort kapjuk vissza. Ekkor a bal oldali háromszög második oszlopát kell vizsgálnunk, azaz a mátrix els® sorának meg kell mutat-

I01

nia, hogy az

0-ás,

rab

és

1

intervallum fölött

darab

1-es

2

típusú három-

∗ szög van. Az e1 vektorral szorozva ot, az

I11

da-

I00 I01 I02 I10 I11 I12

Z1∗ -

I0

intervallum fölötti háromszö-

3. ábra.

gek eloszlását kell visszakapnunk, vagyis a mátrix

2.

sorában

(1, 2) kell,

I1

hogy áll-

∗ jon. Hasonlóan, a Z3 mátrix els® sorának mutatnia kell, hogy és

2

I02

jobboldali háromszög van, a második sornak pedig, hogy

fölött

I12

2

baloldali,

fölött csak egy

jobboldali háromszög található. Minden

t

pontnak így megfeleltethetünk egy

0

vagy

1-el

kezd®d®,

rozatot. Nézzünk egy példát. Legyen t1 kódjának els®

4 jegye 0201.

{0, 1, 2}N

Ekkor az

e∗i

so-

vektorok

∗ és a Zj mátrixok segítségével ki tudjuk fejezni azoknak a harmadik szinten lév® háromszögeknek a számát, amelyekbe a

t

ponton keresztül a sz®nyegre bocsátott

függ®leges egyenes belemetsz:

∗ ∗ ∗ #{háromszögek} = e∗| 0 Z2 Z0 Z1 1 = (16, 14)1 = 30.

Azaz

30

db, harmadik szin-

ten lév® kis háromszögbe metsz bele. A számítást vissza tudjuk ellen®rizni a 4. ábra

7.

A SIERPI‹SKI SZŽNYEG

23

I0201

I020

I02

I0 4. ábra.

24

alapján úgy, hogy a piros sávba es® háromszögeket összeszámoljuk. Ezzel egyúttal kapjuk, ha torok

e0

és

Zi∗ e1 ,

t I0102 intervallumban való tartózkodásának valószín¶ségét is meg-

mátrixokat normáljuk. Azt már tudjuk, hogy a kezdeti eloszlásvekösszegük az

Z = Z0 + Z1 + Z2 ,

és

1 (1, 1)| vektor. 2

e| Z1 = 1

Így annak a valószín¶sége, hogy

Z0∗ + Z1∗ + Z2∗ =

kell, hogy adódjon. Így

t

5 3

éppen az

I0201

!

3 5 Zi = 81 Zi∗ , i = 0, 1, 2

intervallumban lesz,

P(t ∈ I0201 ) = e|0 Z2 Z0 Z1 1. Ezzel a módszerrel most már minden állapotvalószín¶séget könnyedén tudunk számolni.

7.2. Az entrópia kiszámítása Ruiz

módszerét

(i ∈ {0, 1, 2})

itt

is

alkalmazhatjuk,

hiszen

könnyedén

mátrixok ergodikusak és sztochasztikusak.

látni,

hogy

a

Zi

A Birch által bemuta-

tott entrópiaközelítést alkalmazva például

1

2

2

XXX ¯3 = 1 G P(V1 = i, V2 = j, V3 = k) ln P(V1 = i, V2 = j, V3 = k) − ln 3 i=0 j=0 k=0 1

2

1 XX − P(V1 = i, V2 = j) ln P(V1 = i, V2 = j) = ln 3 i=0 j=0 1

=

2

2

1 XXX | q Zj Zk 1 ln qi| Zj Zk 1 − ln 3 i=0 j=0 k=0 i 1

2

1 XX | − qi Zj 1 ln qi| Zj 1. ln 3 i=0 j=0 Szintén Wolfram Mathematica-val számolva

¯ 11 = 0.993636141947118494 G

adó-

dik. Az alsó közelítés számolásához a Sierpinski háromszögnél már látott módszert

Zi , ! i = 0, 1, 2 0 0

kell alkalmaznunk. E szerint deniáljunk hat mátrixot a úgy, hogy azokat az

A =

1 0 0 0

! ,

illetve

B =

0 1

mátrixokból

mátrixokkal jobbról

megszorozzuk, azaz az els®, illetve második oszlopának elemeit nullákra cseréljük. Így a

7.

A SIERPI‹SKI SZŽNYEG

Z0A = Z0 A = Z1A = Z1 A = Z2A = Z2 A =

1 0

1 8

! Z0B = Z0 B =

2 0 2 0

1 8

1 8

1 8

! Z1B = Z1 B =

1 0 2 0

25

1 8

! Z2B = Z2 B =

0 0

1 8

0 0

!

0 2 0 1

!

0 2 0 2

!

0 1

mátrixok adódnak. Tehát az entrópia alsó közelítése a következ®képpen adódik:

1

2

2

1 XXX G3 = P(V1 = i, V2 = j, X0 = k) ln P(V1 = i, V2 = j, X0 = k) − ln 3 i=0 j=0 k=0 1

−

2

1 XX P(V1 = i, X0 = j) ln P(V1 = i, X0 = j) = ln 3 i=0 j=0 1

2

2

1 XXX | = qi Zj ZXk 1 ln qi| Zj ZXk 1 − ln 3 i=0 j=0 k=0 1

2

1 XX | − q ZX 1 ln qi| ZXj 1, ln 3 i=0 j=0 i j ahol

ZXi = Z0A , Z0B , Z1A , Z1B , Z2A , Z2B .

Wolfram Mathematica programmal számolva Összehasonlítva az eredményt megkaptuk a

ν

¯ 9 -cel, G

mérték entrópiáját.

G9 = 0.993636140531086233.

azt kapjuk, hogy

8

tizedesjegy pontossággal

26

Összegzés Az informatikában fontos szerepe van az úgynevezett rejtett Markov-láncok (HMC) elméletének.

Jó példa erre a bináris szimmetrikus csatornák esete, ahol ezzel a

módszerrel modellezzük a folyamatot. Azonban a rejtett Markov-láncok entrópiája nem határozható meg valamely egyszer¶ formula segítségével. David Blackwell 1957-ben mutatott egy lehetséges módszert ennek számolására, azonban a gyakorlatban való alkalmazása még mindig nem célravezet®. Vannak azonban olyan közelít® eljárások, melyekkel egy ilyen folyamat entrópiáját exponenciálisan tudjuk közelíteni.

Ilyen közelít® eljárást dolgozott ki

1961-ben John J. Birch is. Víctor Ruiznak az volt az észrevétele, hogy bizonyos önhasonló mértékeket, mint rejtett Markov-láncokat tekintheti, és a fent említett technika alkalmazásával nagyon jó becslést tudunk adni ezen mértékek Hausdor-dimenziójára.

Ruiz ezt az

elméletet a Sierpi«ski háromszög úgynevezett természetes mértékének az

x

tengely-

re vetítésével el®álló önhasonló mérték Hausdor-dimenziójának meghatározására alkalmazta. A dolgozatom önálló eredményeként ezzel a fenti technikával igazolom, hogy a Sierpi«ski sz®nyeg dimenziója

8

45◦ -os szöggel vett vetületeként el®álló önhasonló mérték Hausdor-

tizedesjegy pontossággal

H = 0.993636140.

Ruiz eredményét kevesen ismerték fel, így az ötlete számos, eddig kiaknázatlan lehet®séget rejt magában.

Irodalomjegyzék [1] David Blackwell, The entropy of functions of nite-state Markov chains.

Trans.

First Prague Conf. Information Theory, Statistical Decision Functions, Random Processes, (1957), 13-20. [2] B. Balázs, M. Pollicott, K. Simon, Probability measures for projective transformations: the Blackwell measure. Preprint 2012. [3] Simon Károly,

Dynamical systems course,

dynsyst/index.html,

http://www.math.bme.hu/~simonk/

Budapesti M¶szaki és Gazdaságtudományi Egyetem,

2012. [4] Simon Károly,

Geometriai mértékelmélet és Fraktálok kurzus,

math.bme.hu/~simonk/vf/lecture_1.pdf,

http://www.

Budapesti M¶szaki és Gazdaságtu-

dományi Egyetem, 2012. [5] John J. Birch, Approximations for the Entropy for Functions of Markov Chains.

Ann. Math. Statist. Vol. 33, (1962), 930-938. [6] Víctor Ruiz, A compact framework for hidden Markov chains with applications to fractal geometry.

J. Appl. Probab. Volume 45, Number 3 (2008), 630-639.

27