Optimális stratégiák magas tranzakciós költség esetén és a szerencsejátékokban

Optimális stratégiák magas tranzakciós költség esetén és a szerencsejátékokban Szakdolgozat Készítette:

Halász Sándor

Matematika B.Sc., Matematikai elemz® szakirány

Témavezet®:

Csiszár Vill®, adjunktus

Valószín¶ségelméleti és Statisztika Tanszék

Eötvös Loránd Tudományegyetem Természettudományi Kar 2010

Tartalomjegyzék

1. Bevezetés

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

1.1. A dolgozat felépítése . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Dinamikus programozás 2.1. 2.2. 2.3. 2.4.

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

Binomiális együtthatók számítása A hátizsák probléma . . . . . . . Optimális parkolás . . . . . . . . A legszebb kiválasztása . . . . . .

. . . .

. . . .

. . . .

. . . .

3. A magas tranzakciós költség problémája 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7.

Modell . . . . . . . . . . . . . . Bellman egyenlet . . . . . . . . A h=1 eset . . . . . . . . . . . A h>1 eset . . . . . . . . . . . Kontrakció . . . . . . . . . . . . Triviális eset . . . . . . . . . . . Kétérték¶ nempozitív cash-ow

. . . . . . .

. . . . . . .

4. Szerencsejátékok optimális stratégiái 4.1. 4.2. 4.3. 4.4.

. . . . . . .

. . . . . . .

. . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

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

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

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

Tönkremenetel egyszer¶ játékban . . . . . Kedvez®tlen helyzetben merész a jó játékos Óvatos stratégia kedvez® helyzetben . . . . Fogadások több lehet®ségre . . . . . . . .

5. Összefoglalás

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

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

i

1

2

2

3 3 6 8

10

10 11 12 14 15 19 19

20

21 22 27 27

30

Ábrák jegyzéke

1. 2. 3. 4. 5.

A hátizsák probléma súly/érték tábázata . . . . . . . . . . . . . . . 4 Optimális parkolás Vk , k függvényei . . . . . . . . . . . . . . . . . . 7 [q −1 E(V0 (z + X)) − b(z − ζ)] függvény Q=10, q=1.1, ζ = 1 esetén, X egyenletes eloszlású a [−1, 1] intervallumon . . . . . . . . . . . . 13 A Vh függvények elrendez®dése különböz® h értékekre . . . . . . . . 17 Optimális stratégia vr (x) függvénye . . . . . . . . . . . . . . . . . . 23

ii

1 1. Bevezetés

Tranzakciós költségekkel napjainkban bármelyik banknál találkozunk. Jellemz®en zetnünk kell, ha készpénzt szeretnénk felvenni, ugyanakkor természetesen a bankban tárolt pénzünk után kamatot zet nekünk a bank. Megtakarításainkat mindenképp forgatnunk kell, ha protot szeretnénk elérni. Hogy ezt mi módon tehetjük, arra nem térnék ki, hiszen az a sejtés, hogy lehet®ségeink tárháza tart a végtelenhez. Dolgozatomban két esettel fogok foglalkozni, a már említett banki lekötés mellett a szerencsejátékokkal. A bankban elhelyezett, és a szerencsejátékra fordított pénz tekinthet® egyfajta befektetésnek, éppen ezért semmiképp sem gondolhatunk veszteségminimalizálásra. A befektetés egyértelm¶ célja a protmaximalizálás. Mindkét lehet®ség érdekes, tanulságos, és a vizsgálatukban hatalmas segítséget nyújt a matematika. Meggyelhet® a banki reklámokban, hogy a biztonság mellett a kamat mértékét emelik ki, és többnyire ez a két szempont a legfontosabb, amikor megválasztjuk a számlánkat. Érdemes meggondolni azonban, hogy magas tranzakciós költség mellett a kamatunk akár teljesen elvész, s®t, az is el®fordulhat hogy a költségek címén levont pénz meghaladja a kamatra kizetett összeget, és így rosszabbul járunk, mintha a "párnánk alá tettük volna a pénzünket". A szerencsejátékok esetében szintén kockázatot vállalunk, azonban mégsem hasonlítható egy bankbetéthez, a szerencsejáték ugyanis nem adhat biztonságot, ugyanakkor lényegesen nagyobb prot érhet® el vele (természetesen óriási kockázat mellett). Éppen emiatt a bátorság könnyen válhat botorsággá, és ezt elkerülend®, mindenképp szükséges egy alapos matematikai vizsgálat, miel®tt a befektetés ezen formáját választjuk. Dolgozatom célja, hogy választ adjak arra a kérdésre, hogy adott feltételek mellett mekkora protot érhetünk el maximum, és hogy ezt a protot hogyan tudjuk elérni.

2

2. DINAMIKUS PROGRAMOZÁS

1.1. A dolgozat felépítése Dolgozatomban valóságon alapuló modelleket fogok vizsgálni, és ennek alapján fogom maximalizálni a pénzeszközöket. A 2. fejezetben a szükséges ismereteket írom le a dinamikus programozásról. Ez a témakör a dolgozat szempontjából kiemelten fontos, éppen ezért szemléltetem is néhány egyszer¶ példával. A fejezetet a |4| és a |3| források különböz® alfejezetei alapján készítettem. A 3. fejezetben egy modellt építek, és ennek segítségével keresek optimális megoldást arra, hogy hogyan tudjuk a protunkat maximalizálni magas tranzakciós költség mellett. A felmerül® fogalmakat az adott alpontok elején deniálom, továbbá a könnyebb megértés érdekében bizonyos részeknél egyszer¶ magyarázatot is adok, hogy 1-1 lépés mit is jelent a gyakorlatban. A fejezetet az |1| kézirat alapján készítettem. Az 4. fejezetben betekintünk a szerencsejátékok világába, és optimális stratégiákat keresünk különböz® helyzetekre. A fejezetet a |3| jegyzet hasonló fejezetei alapján készítettem. 2. Dinamikus programozás

A dinamikus programozás módszerét gyakran használjuk valamilyen numerikus paraméterekt®l függ® érték optimumának a meghatározására. Az a lényege, hogy az optimális megoldást arra alkalmas kisebb részfeladatok optimális megoldásából próbáljuk el®állítani. A dinamikus programozást használó algoritmusok vezérlési szerkezete gyakran emlékeztet egy táblázat szisztematikus (pl. sorról sorra haladó) kitöltésére. A táblázat kitöltését általában egy rekurzív összefüggés teszi lehet®vé, ami alapján a bejárási sorrend szerint korábbi elemekb®l meghatározhatók a kés®bbiek. A kapott módszer költségét többnyire a kitöltend® táblázat mérete határozza meg. A rekurzív összefüggés megtalálásában sokszor a segítségünkre van az optimalitás elve. A dinamikus programozásnak vannak er®teljes alkalmazásai a könny¶ és nehéz problémák körében egyaránt. M¶ködését néhány példán keresztül szeretném

2.1. Binomiális együtthatók számítása

3

bemutatni.

2.1. Binomiális együtthatók számítása ( )

Tegyük fel, hogy az nk binomiális együttható értékére vagyunk kíváncsiak. Lehetséges utat jelent a jól ismert ) ( ) ( ) ( n n−1 n−1 = + k k−1 k

(1)

azonosság használata. Ennek segítségével a kisebb n értékekt®l a nagyobbak felé ( ) haladva adódnak a binomiális együtthatók: ha az összes n−1 értéket ismerjük (0 ≤ j (n ) ≤ j ≤ n − 1), akkor az k alakú együtthatók egy-egy összeadással megkaphatók. ( ) ( ) Az elindulás lehet®ségét az m0 = m = 1 értékek biztosítják. Tulajdonképpen m a nevezetes Pascal-háromszög (vagyis egy háromszög alakú táblázat) kitöltésér®l van szó. Az algoritmus csak összeadásokat használ, ezért gyakorlati szempontból is érdekes lehet olyan aritmetikai környezetben, ahol az összeadás sokkal gyorsabb, mint a szorzás. A dinamikus programozás alulról építkez®, a kisebb esetekt®l a nagyobbak felé men® stratégiája gyakran hatékonyabb alternatívát kínál, a rekurzív eljárások felülr®l lefelé haladó felfogásával szemben. A binomiális együtthatók számítása jól mutatja ezt. A (1) összefüggés alapján megírt rekurzív eljárás hátránya, hogy többször ( ) is kiszámítja ugyanazokat a (közbüls®) binomiális együtthatókat. Például az nk ( ) számításakor az n−2 együtthatót kétszer is kiszámoljuk. A dinamikus programok−2 zás gondolatát követ® módszer kiküszöböli ezeket az ismétl®déseket.

2.2. A hátizsák probléma Ez egy klasszikus példafeladat. Tekintsünk egy betör®t, aki egy ®rizetlenül hagyott házban válogat a "kincsek" között. A lehet® legnagyobb értéket szeretné

4


1. ábra. A hátizsák probléma súly/érték tábázata magával vinni, de a hátizsákja csak meghatározott súlyt bír el. Legyen minden tárgynak egy adott si súlya, és vi értéke. Adottak az s1 , ..., sm súlyok, a b súlykorlát, a v1 , ..., vm értékek és a k értékkorlát. A kérdés, hogy van-e olyan I ⊆ {1, ..., m} részhalmaz, melyre teljesül, hogy ∑ ∑ i∈I si ≤ b és i∈I vi ≥ k . Feltesszük még, hogy a szerepl® mennyiségek mind pozitív egészek. A feladatról tudjuk, hogy NP-teljes. Itt most egy dinamikus programozást használó megoldást ismertetünk. Szeretnénk a feladatot visszavezetni kisebb hasonló problémákra. Ilyenkor gyakran segít, ha a feladatban megadott bizonyos paramétereket változónak tekintjük, és egy

2.2. A hátizsák probléma

5

értelmes tartományban "futni hagyjuk". A mi esetünkben az m és a b lesznek a paraméterek. Pontosabban fogalmazva legyen v(i, a) a maximális elérhet® érték az s1 , ..., si súlyokkal, v1 , ..., vi értékekkel és a súlykorláttal megadott feladatra (mivel a maximális értéket keressük, nincs szükség értékkorlátokra). Ekkor v(0, a) = = v(i, 0) = 0 tetsz®leges a és i számokra, és célunk a v(m, b) mennyiség meghatározása, illetve annak eldöntése, hogy fennáll-e a v(m, b) ≥ k egyenl®tlenség. A feladat úgy is felfogható, hogy meg akarjuk határozni az m + 1 sorból, és b + 1 oszlopból álló [v(a, i)] táblázat (m, b) pozíciójú elemét. A táblázat 0 index¶ sorában, illetve oszlopában az értékek ismertek. Az érdekesebb helyeken lev® számok meghatározásában segít a következ® egyszer¶ összefüggés: v(i, a) = max{v(i − 1, a); vi + v(i − 1, a − si )}.

Indoklásul megjegyezzük, hogy a jobb oldalon az els® mennyiség az i-edik súlyt nem tartalmazó választások optimális értéke, a második pedig az i-edik súlyt tartalmazó választások optimális értéke (mindkét esetben a súlykorlát mellett). Itt is érvényesül az optimalitás elve: ha a v(i, a) értéket adó kitöltésben az si súly szerepel, akkor a zsákban lev® többi (az s1 , s2 , ..., si−1 közül kikerül®) súlynak optimális kitöltést kell adnia az a − si súlykorláttal. Az összefüggés alapján a táblázat kitölthet® úgy, hogy vesszük rendre az 1, 2, ..., m index¶ sorokat, ezeken belül pedig az a indexet növelve haladunk. A táblázatnak mb eleme van. A módszer nem polinomiális idej¶, mert b mérete ⌈log2 (b + 1)⌉, az input hossza pedig

L=

m ∑

(⌈log2 (si + 1)⌉ + ⌈log2 (vi + 1)⌉) + ⌈log2 (k + 1)⌉ + ⌈log2 (b + 1)⌉.

i=1

Másfel®l a táblázat mérete is legalább mb, ami L-hez képest exponenciálisan nagy is lehet. Ha viszont b nem túl nagy a többi input paraméterhez képest, akkor a módszer akár polinom idej¶ is lehet. Ezt most pontosabban is megfogalmazzuk.

6


Deníció: A b egész unáris ábrázolása: 0b := 0...0(összesen b darab 0 egymás után.) Deníció: Egy feladat egy egész input paramétere apró, ha unárisan számítjuk bele az input hosszába.

Ha a b paraméter apró, akkor az input méretéhez való hozzájárulása |b| és nem ⌈log2 (b + 1)⌉, mint a bináris megoldás esetén. A b-t akkor érdemes aprónak tekinteni, amikor az unáris ábrázolása az inputban nem növelné meg az input méretének nagyságrendjét. Ez teljesül, ha |b| felülr®l becsülhet® az input más összetev®i méretének egy polinomjával. Például a Hátizsák feladatnál ha b ≤ m5 , akkor b-t szemlélhetjük úgy, mint egy apró paramétert. Ez természetesen nem jelenti azt, hogy b-t unárisan kell ábrázolnunk az inputban. Arról van csupán szó, hogy a költségszámításnál az unáris hosszát vesszük gyelembe.

Következmény: A Hátizsák probléma apró súlykorlát esetén megoldható polinom id®ben.

Igazolásul elég annyi, hogy ekkor L ≥ b, tehát a futási id® az input hosszának polinomjával becsülhet®: O(L2 ).

2.3. Optimális parkolás A bolt a kezd®pontban van, és a hozzá vezet® út k = 1, 2, ..., N helyein lehet parkolni. A parkolóhelyek egymástól függetlenül, 0 < p < 1 valószín¶séggel szabadok, q = 1 − p a foglaltság esélye. Ha a Vásárló beáll a k-ik üres helyre, akkor (mondjuk a cipekedés miatt) k lesz a költsége, tehát a bolthoz minél közelebb

2.3. Optimális parkolás

7

2. ábra. Optimális parkolás Vk , k függvényei szeretne leállni. Ha viszont annyira el®remegy hogy már nem talál helyet, akkor C ≫ 1 pénzt zet (mondjuk azért, mert ebben az esetben kénytelen behajtani egy zet®s parkolóházba). Az persze nem tudható hogy a j < k helyek között van-e üres. Mindegyik szabad parkolónál döntenie kell: beáll vagy tovább megy, várni vagy visszafordulni nem lehet. Jelölje Vk annak optimális várható veszteségét, aki a k-ik parkolónál van, persze V0 = C . Ezt a sorozatot kell meghatározni: ha a k-ik hely szabad, de Vk−1 < k , akkor érdemes tovább menni. A dinamikus programmozás alapelve szerint

8


Vk = p min (k, Vk−1 ) + qVk−1 ,

(2)

mert ha a k-ik hely foglalt, akkor tovább kell menni, egyébként döntési helyzet van. Világos hogy V1 = p + qC , de az iteráció ezután elbonyolódik. Könny¶ észrevenni hogy Vk ≤ Vk−1 mindig igaz, és ha Vk−1 ≤ k akkor Vk = = Vk−1 < k + 1 , tehát Vk+1 = Vk = Vk−1 , és így tovább. Másrészt, Vk < Vk−1 feltétele Vk−1 > min (k, Vk−1 ), vagyis Vk−1 > k . Ez indokolja a Vek = pk + q Vek−1 sorozat vizsgálatát a Ve0 = C kezdeti feltétel mellett (ez tulajdonképpen a (2), csak épp a min(k, Vk ) helyén k áll, így egyszer¶bb). Ez nem nehéz, néhány iteráció után felismerhet® hogy Vek = k + C − a + aq k alakú, amit a rekurzióba visszahelyettesítve 1 1 Vek = k + 1 − + (q + pC)q k p p

(3)

adódik. Másrészt Vek ≤ Vek−1 ha k ≤ Vek−1 , tehát az is látható, hogy Vk = Vek feltétele éppen Vek−1 ≥ k, és a (3) egyenletb®l k kritikus értéke a (q + pC)q k−1 = 1 egyenlet k∗ := 1 + log(q + pC)/ log(1/q) megoldása. Ez persze nem biztos hogy egész, el®tte Vk = Vek , utána Vk már nem változik. Szemléletesen ez azt jelenti, hogy amíg k > Vk (vagyis amíg messze vagyok a bolttól), addig mindenképpen továbbmegyek. Amint Vk > k (vagyis kell®en közel értem), beállok az els® szabad helyre.

2.4. A legszebb kiválasztása Egyesével vonul el el®ttünk n hölgy, és a legszebbet úgy kellene megtalálni hogy némi szemlél®dés után az éppen el®ttünk állóról kijelentjük: az. Azt is mondhatjuk hogy n különböz® szám van a kalapban, és nem tudjuk hogy a legnagyobb mekkora. Visszatevés nélkül húzzuk ki ®ket, tehát minden sorozat egyformán 1/n! ∗ := max ξk : k ≤ m. Azt az s valószin¶ség¶. Legyen ξk a k-ik húzás eredménye, ξm ∗ = ξs∗ és ξt∗ > ξs∗ id®pontot kell meghatározni, ameddig szemlél®dünk, vagyis ξt−1 bekövetkeztekor ξt mellett döntünk. Feladatunk a siker

9

2.4. A legszebb kiválasztása

p(s) =

n ∑

∗ P [ξs∗ = ξt−1 < ξt = ξn∗ ]

(4)

t=s+1

valószín¶ségének maximalizálása. Ha t > s és ξt = ξn∗ , akkor P [ξs∗

=

∗ ξt−1

< ξt =

ξn∗ ]

( ) 1 n−1 = s(t − 2)! (n − t)! = n! t − 1

(n − 1)! s(t − 2)! (n − t)! s = n! (t − 1)! (n − t)! n(t − 1) ∑n adódik, tehát p(s) = (s/n) t=s+1 (t − 1)−1 akkor maximális ha s = s(n) az a ∑ ∑ −1 −1 szám, melynél n−1 ≤ 1 ≤ n−1 t=s+1 t t=s t . Stratégiánk tehát a következ®: az így meghatározott s = s(n) id®pontig szemlél®dünk, majd a soron következ®, aktuális legszebbnél igent mondunk. Látható, hogy s(n) ≈ n/e , és a siker valószin¶sége körülbelül 1/e. =

Egy példa segítségével szemléltetem az algoritmust. Legyen 10 szám a kalapban, és a következ® sorrendben húzzuk ki: 3, 7, 1, 2, 5, 4, 10, 8, 6, 9, és legyen s = 4. 3, 7, 1, 2, 5, 4, 10, 8, 6, 9 | {z } s

Az els® 4 számot megnéztük, és kiválasztottuk a maximumot, vagyis ξs∗ = 7. Ezek után húzzuk sorra a számokat, és az els® olyat kiválasztjuk, amelyik nagyobb, mint ξs∗ , ez pedig a t. lesz, jelen példában a 10. Látható, hogy ha az utolsó három szám között lenne a 10-nél nagyobb, akkor is a 10-re esett volna a választás, éppen ezért nagyon fontos az s-t jól megválasztani (ha túl kicsi, könnyen lehet hogy nem a maximumot választjuk, ha viszont túl nagy, lehet hogy bele kerül a legnagyobb szám, könnyen meggondolható, hogy ilyenkor a sorrendben utoljára kihúzott számmal kell megelégednünk).

10

3. A MAGAS TRANZAKCIÓS KÖLTSÉG PROBLÉMÁJA

3. A magas tranzakciós költség problémá ja

Ebben a fejezetben egy modellt fogunk vizsgálni. Adott egy bank, ahol a lekötéseink kamatoznak, a pénzfelvétel pedig komoly tranzakciós költséggel jár (és szükségünk van készpénzre is). Az a célunk, hogy vagyonunkat maximalizáljuk, és optimális sratégiát fogunk keresni arra az esetre, ha a tranzakciós költség lényegesen magasabb, mint a kamat.

3.1. Modell Adott egy Xi iid cash-ow, ennyi készpénzt kapunk az i. napon (i = 0). Vagyonunkat kétféle eszközben tartjuk, készpénzben (zi ), illetve bankban (wi ). Jelöljük yi -vel azt az összeget, amennyit a bankból kiveszünk az i. napon, ezt mi választjuk. A bankban lév® vagyon minden lépésben kamatozik, azaz x q-szorosára n®. A bankból való pénzkivét esetén tranzakciós költséget kell zetni, azaz a kivett összeg Q -szorosa vonódik le az egyenlegünkb®l. Formálisan: z0 = w0 = 0, zi = zi−1 + Xi + yi , i ≥ 1 wi = qwi−1 − b(yi ), i ≥ 1

ahol { b(y) =

y ha y < 0 Qy ha y ≥ 0

valamint megköveteljük, hogy zi ≥0 minden i-re (ez a feltétel nemcsak a valóságszer¶séghez kell, meggondolható, hogy ellenkez® esetben legfeljebb egyszer, az utolsó lépésben vennénk ki pénzt). A bankban hitelünk is lehet (negatív pénzünk), ez ugyanúgy kamatozik, mint a betétünk. A probléma akkor érdekes, ha 1 < q <

11

3.2. Bellman egyenlet

teljesül, éppen ezért ezt mindig feltesszük. Bevezetjük továbbá a ζi = zi−1 + Xi jelölést, amely az i. napon a készpénzünk, miután a cash-ow beérkezett, de miel®tt a bankba mennénk. Célunk olyan {yi } (adaptált) stratégia keresése, mely maximalizálja a E(zt + wt ) várható értékét, ahol t egy meghatározott id®horizont. Q

3.2. Bellman egyenlet Az alábbiakban a Bellman-elv szerint fogunk gondolkodni, melynek lényege, hogy egy optimális stratégiának minden része is optimális. Jelölje vh (ζ, w) a h nap múlva elérhet® vagyon maximális várható értékét, amennyiben a mai napon ζ készpénzünk van, a bankban pedig w összeg (és a mai cash-ow már beérkezett, de a bankban még nem voltunk). Vegyük észre, hogy érvényes a vh (ζ, w) = vh (ζ,0) + q h w

összefüggés. A h = 0 esetet könnyen elintézhetjük: { v0 (ζ,0) = −b(−ζ) =

ζ ha ζ ≥ 0 Qζ ha ζ < 0

hiszen még ezen a napon is ki kell venni a bankból, ha negatív a készpénzünk. A Bellman-egyenlet pedig:

vh (ζ,0) = max E[vh−1 (ζ + X + y, −qb(y))] = max E[vh−1 (ζ + X + y,0) − q h b(y)]. y:ζ+y≥0

y:ζ+y≥0

Bevezetve a Vh (ζ) = vh (ζ,0)/q h jelölést, és a z = ζ + y változót, kapjuk:

12


Vh (ζ) = max E[q −1 Vh−1 (z+X)−b(z−ζ)] = max[q −1 E(Vh−1 (z+X))−b(z−ζ)]. (5) z≥0

z≥0

(Szemléletesen, Vh azt mutatja meg, hogy ha ζ készpénzünk van, és a bankban 0, akkor h nap múlva mennyi az elérhet® diszkontált vagyon maximális várható értéke.) Természetesen a maximum értéke mellett az optimális stratégia is érdekel minket: legyen sh (ζ) = z az a függvény, amely ζ -hoz hozzárendeli (5) egyenletben maximumot szolgáltató (remélhet®leg egyértelm¶en létez®) z -t. Az a sejtésünk, hogy minden h-ra létezik ch konstans, melyre    0 ha ζ ≤ 0 sh (ζ) = ζ ha 0 ≤ ζ ≤ ch   ch ha ζ ≥ ch

(6)

Ez szemléletesen azt jelenti, hogy ez a ch konstans az, amit tartalékolnunk kell ahhoz, hogy nagy valószín¶séggel elkerüljük a pénzkivétet. Ha 0 készpénzünk volt, és ζ ≤ 0, akkor ζ -t veszünk ki a bankból, és továbbra is 0 marad a készpénzünk. Ha 0 ≤ ζ ≤ ch , akkor nem teszünk be pénzt a bankba, így ζ készpénzünk lesz. Ha viszont ζ ≥ ch , akkor csak ch -t tartalékolunk, és ζ − ch -t teszünk a bankba.

3.3. A h=1 eset Számítsuk ki a V1 (ζ) és s1 (ζ) függvényeket! Látni fogjuk, hogy s1 (ζ) valóban (6) alakú. Természetesen a h = 1 eset nem túl izgalmas, de legalább számolható. Jelölje X eloszlásfüggvényét F (x). (2) szerint: V1 (ζ) = max[q −1 E(V0 (z + X)) − b(z − ζ)]. z≥0

ahol V0 (ζ) = −b(−ζ). Mivel V0 konkáv, ugyanez igaz az u(z) = q −1 EV0 (z + X)

13

3.3. A h=1 eset

3. ábra. [q −1 E(V0 (z + X)) − b(z − ζ)] függvény Q=10, q=1.1, ζ = 1 esetén, X egyenletes eloszlású a [−1, 1] intervallumon függvényre is, azaz u bal (jobb) oldali deriváltja monoton csökken, és lim u′ (z) = Q/q > 1,

z→−∞

és lim u′ (z) = 1/q < 1,

z→∞

ahol u′ jelölje az egyértelm¶ség kedvéért a baloldali deriváltat. Mindebb®l adódik, hogy s1 (ζ) valóban (6) alakú, és c1 = sup{c : u′ (c) ≥ 1}, amennyiben ez pozitív,

14


egyébként pedig c1 = 0. Mivel u′ (z) = 1 + (Q − 1)F (−z + 0), kapjuk, hogy c1 = max(−F − (

q−1 ), 0), Q−1

ahol F − az F általánosított inverze. A maximum értéke pedig V1 (ζ) = u(s1 (ζ)) − − b(s1 (ζ) − ζ), behelyettesítve kapjuk:   ha ζ ≤ 0  u(0) + Qζ V1 (ζ) = u(ζ) ha 0 ≤ ζ ≤ c1   u(c1 ) − c1 + ζ ha ζ ≥ c1 V1 (ζ) is monoton növekv®, konkáv függvény. Kérdés, hogy lehet-e innen tovább számolni explicit módon, vagy legalább kvantitatívan. Láthattuk, hogy h = 1 esetén c1 kiszámítható explicit módon, h > 1 esetben azonban nem. Viszont azt meg

tudjuk mutatni, hogy az optimális stratégia (6) alakú.

3.4. A h>1 eset Megmutatjuk, hogy sh (ζ) mindig (6) alakú. Indukcióval tegyük ugyanis fel, hogy h-ig már tudjuk sh (ζ) alakját, valamint azt, hogy Vh (ζ) monoton növ®, konkáv függvény, mely a ζ ≤ 0 félegyenesen lineáris Q meredekséggel, a ζ ≥ ch félegyenesen szintén lineáris 1 meredekséggel. Az el®z® szakasz szerint h = 0,1-re ezeket már mind tudjuk. A (5) Bellman egyenlet szerint Vh+1 (ζ) = max(uh+1 (z) − b(z − ζ)), z≥0

ahol uh+1 (z) = q −1 EVh (z + X). Az indukciós feltevés szerint uh+1 (z) monoton növ®, konkáv függvény, és lim u′h+1 (z) = Q/q > 1,

z→−∞

15

3.5. Kontrakció

és lim u′h+1 (z) = 1/q < 1

z→∞

(ahol u′h jelölje az egyértelm¶ség kedvéért a baloldali deriváltat). Mindebb®l adódik, hogy sh+1 (ζ) valóban (6) alakú, és ch+1 = sup{c : u′h+1 (c) ≥ 1}, amennyiben ez pozitív, egyébként pedig ch+1 = 0. (Amennyiben u′h+1 = 1 egy pozitív hosszúságú intervallumon teljesül, akkor ch+1 más is lehetne.) A maximum értéke pedig Vh+1 (ζ) = u(sh+1 (ζ)) − b(sh+1 (ζ) − ζ), behelyettesítve kapjuk:   ha ζ ≤ 0  uh+1 (0) + Qζ Vh+1 (ζ) = uh+1 (ζ) ha 0 ≤ ζ ≤ ch+1   uh+1 (ch+1 ) − ch+1 + ζ ha ζ ≥ ch+1

azaz Vh+1 (ζ)-ra teljesülnek az indukció folytatásához szükséges feltételek. Megmutatjuk azt is, hogy a stratégiákat deniáló ch konstansok monoton n®nek (vagyis minél több nap van még hátra, annál több pénzt kell tartalékolni). ′ Tegyük fel indukcióval, hogy ch ≥ ch−1 és Vh′ ≥ Vh−1 már ismert (h = 1-re ezeket tudjuk). Ezért ′ u′h+1 (z) = q −1 EVh′ (z + X) ≥ q −1 EVh−1 (z + X) = u′h (z)

Ebb®l már következik, hogy ch+1 ≥ ch és z > 0-ra ′ Vh+1 (z) = max{u′h+1 (z), 1} ≥ max{u′h (z), 1} = Vh′ (z).

3.5. Kontrakció Deníció: Legyen X egy tetsz®leges nem üres halmaz, ϱ : X ×X → R. Tegyük

fel, hogy érvényesek a következ® tulajdonságok:

16


1 : ϱ(x, y) ≥ 0, emellett ϱ(x, y) = 0 ⇔ x = y 2 : ϱ(x, y) = ϱ(y, x) 3 : ϱ(x, y) ≤ ϱ(x, z) + ϱ(z, y)

Az ilyen tulajdonságú függvényt metrikának, az (X, ϱ) párt metrikus térnek nevezzük. Azokat a metrikus tereket, amelyekben minden Cauchy-sorozat konvergens, teljes metrikus térnek, más néven Banach-térnek nevezzük. Deníció: f : X → X kontrakció, ha ∃ q ∈ [0,1), amelyre ϱ(f (x1 ), f (x2 )) ≤ ≤ qϱ(x1 , x2 ) ∀x1 , x2 ∈ X . Tétel: Legyenek •X Banach-tér •f : X → X egy kontrakció, D(f ) = X.

Ekkor 1: f -nek ∃ xpontja 2: egyetlen xpontja van (x∗ ) 3: az x(n) := f (x(n−1) ) n = 1, 2, ..., x(0) tetsz®leges iteráció konvergens, és limn→∞ x(n) = x∗ 4: érvényes a ϱ(x∗ , x(m) ) ≤ Aϱ(x(1) , x(0) )q m becslés, ahol A egy konstans.

Vezessük be a Vh′ (z) = gh (z) jelölést (z ≥ 0). Láthattuk, hogy ezekre a függvényekre gh+1 = T gh . Itt T = max(S, 1), ahol S, T : G → G operátorok. Itt G a g : R+ → [0, Q] balról folytonos, monoton függvények szuprémum normával ellátott Banach-tere. Konkrétan

1 Q (Sg)(z) = F (−z + 0) + q q S , és így T is kontrakció, mivel

∫

∞

g(z + x)F (dx) −z+0

z>0

17

3.5. Kontrakció

4. ábra. A Vh függvények elrendez®dése különböz® h értékekre

1 sup |(Sg)(z)−(Sh)(z)| = sup | q z>0 z>0

∫

∞ −z+0

(g(z+x)−h(z+x))F (dx)| ≤

1 sup |g(z)−h(z)| q z>0

Emiatt egyértelm¶en létezik g∞ , melyre T g∞ = g∞ , és gh → g∞ . Továbbá ch → c∞ , ahol c∞ = sup{z : g∞ (z) ≥ 1}. Kés®bb belátjuk, hogy c∞ < ∞. Vizsgáljuk meg Vh konvergenciáját!

18


{ Vh (ζ) =

∫ζ Vh (0) + 0 Vh′ (z)dz ha ζ > 0 Vh (0) + Qζ ha ζ ≤ 0

Ha tehát valamilyen h-ra Vh+1 (0) ≥ Vh (0), akkor Vh+1 (ζ) ≥ Vh (ζ) minden ζ -ra, amint azt a 4. ábra mutatja (a deriváltak monotonitása miatt). Ez a tulajdonság pedig örökl®dik, azaz Vn+1 (ζ) ≥ Vn (ζ) minden n ≥ h-ra és minden ζ -ra. Tehát a Vh (0) sorozat két monoton szakaszból állhat, egy csökken®b®l, majd egy növekv®b®l, de a kett® közül bármelyik hiányozhat is. Azonban mindenképp létezik a V∞ (0) = limh→∞ Vh (0) véges határérték. A végesség onnan adódik, hogy ha X sztochasztikusan kisebb, mint Y , akkor könnyen láthatóan VhX ≤ VhY minden h-ra (nyilván, hiszen ha várhatóan kevesebb pénzt kapunk, várhatóan kevesebbet is fogunk megtakarítani). Így Vh− ≤ Vh ≤ Vh+

minden h-ra, ahol Vh− (Vh+ ) az X negatív (pozitív) részéb®l számolódik. Ha pedig a cash-ow mindig kiadás (vagy bevétel), akkor explicit ki lehet számolni Vh (0)-t. Kaptuk tehát, hogy Vh konvergál, mégpedig { V∞ (ζ) =

∫ζ V∞ (0) + 0 g∞ (z)dz ha ζ > 0 V∞ (0) + Qζ ha ζ ≤ 0

Ez a V∞ függvény xpontja a Vh -ból Vh+1 -et el®állító operátornak, azaz V∞ (0) = = q −1 EV∞ (X). Ebb®l [ ∫ 0 ] ∫ ∞ 1 V∞ (0) = Q xdF (x) + g∞ (x)(1 − F (x))dx q−1 −∞ 0

Ez szemléletesen arról szól, hogy ha h elég nagy (vagyis sok id®m van még hátra), akkor a h, és a h + k (k > 0) nap múlva elérhet® összeg jelenértéke közel lesz egymáshoz (nyilván, hiszen mind a kett® V∞ jelenértékéhez konvergál).

19

3.6. Triviális eset

3.6. Triviális eset q−1 Nézzük meg röviden azt a triviális esetet, amikor F (0) < Q−1 . Láttuk, hogy ekkor c1 = 0, és indukcióval megmutatható, hogy ch = 0 minden h-ra is teljesül. q−1 (Ha F (0) = Q−1 , akkor c1 esetleg nem egyértelm¶, a korábbi deníciónk szerint pozitív is lehet, de ebben az esetben is választhatjuk 0-nak, azaz a továbbiak erre az esetre is vonatkoznak.) Azaz, amikor elég kicsi annak a valószín¶sége, hogy holnap kiadásunk lesz, akkor soha nem tartalékolunk pénzt. Továbbá kapjuk, hogy

Vh (ζ) = V0 (ζ) + u1 (0)

h−1 ∑

q −i

i=0

Ha ugyanis ezt h-ra már tudjuk (ahol h = 1-gyel elkezdhetjük az indukciót), akkor uh+1 (z) = q −1 EVh (z + X) = u1 (0)

h−1 ∑

q −i+1 + q −1 EV0 (z + X)

i=0

Innen látszik egyrészt, hogy ch+1 = 0. Másrészt Vh+1 (ζ) = uh+1 (0) + V0 (ζ), ahol ∑ uh+1 (0) = u1 (0) hi=0 q −i , mivel q −1 EV0 (X) = u1 (0). Visszahelyettesítve megkapjuk, hogy Vh (ζ) = V0 (ζ) + EV0 (X)

1 − q −h q−1

ahol V0 (ζ) = −b(−ζ).

3.7. Kétérték¶ nempozitív cash-ow Vajon tovább tudunk-e explicit számolni egy egyszer¶ konkrét esetben? Tegyük fel, hogy X eloszlása P (X = 0) = 1 − ϵ, P(X = −1) = ϵ

20

4. SZERENCSEJÁTÉKOK OPTIMÁLIS STRATÉGIÁI

Természetesen a negatív érték −1 helyett tetsz®leges −A lehet. Az el®z® szakasz q−1 triviális esetét zárjuk ki, azaz legyen ϵ > Q−1 . Ebben az esetben ki tudjuk számolni a g∞ függvényt. Induljunk ki a g0 (z) ≡ 1 függvényb®l. Vegyük észre, hogy minden h, k ≥ 0-ra gh konstans lesz a (k, k + 1) intervallumban, azaz g∞ is konstans lesz ezekben az intervallumokban. Jelölje Gk a g∞ értékét a (k − 1, k) intervallumban! Foglalkozzunk el®ször a (0,1) intervallummal! Itt qgh+1 (z) = ϵQ + (1 − ϵ)gh (z). Azaz a qG1 = ϵQ + (1 − ϵ)G1 xpontegyenletb®l G1 = Q/d, ahol d = q−1+ϵ . Ez ϵ q−1 pontosan akkor lesz 1-nél nagyobb, ha ϵ > Q−1 . Rátérve az (1,2) intervallumra, a xpontegyenlet: qG2 = ϵG1 + (1 − ϵ)G2 , ebb®l pedig G2 = Q/d2 . Ez akkor lesz q−1 1-nél nagyobb, ha ϵ > Q1/2 . Ezt iterálva végül kapjuk, hogy Gk = max(Q/dk , 1), −1 és c∞ az az egész szám, melyre q−1 q−1 < ϵ ≤ 1/(c∞ +1) −1 Q −1

Q1/c∞

Vegyük észre, hogy c∞ → △ − 1, ha ϵ → 1, ahol △ a legkisebb egész szám, melyre q △ ≥ Q. Szemléletesen c∞ azt mutatja meg, hogy ha ∞ napunk van még hátra, akkor mennyi készpénzt kell tartalékolnunk. Ez kiszámolható Q, q , és ϵ értékekb®l. Fontos megjegyezni, hogy általános nempozitív cash-ow esetén is kiszámítható, hogy mennyi kezd®t®kével kell rendelkeznünk ahhoz, hogy hosszú távon a diszkontált vagyonunk várható értéke 0 legyen az optimális stratégia mellett, ett®l azonban (a téma mélysége miatt) jelen dolgozatban eltekintek.

4. Szerencsejátékok optimális stratégiái

Különféle szerencsejátékok tanulmányozása jó alkalmat ad az optimális stratégia fogalmának illusztrálására, hiszen el®fordulhat, hogy els®re talán hasonló helyzetekben más-más módon tudjuk maximalizálni a pénzünket. A stratégia akkor opti-

21

4.1. Tönkremenetel egyszer¶ játékban

mális, ha az elérhet® maximum a nyereményünk.

4.1. Tönkremenetel egyszer¶ játékban Deníció: A Markov-lánc egy olyan diszkrét sztochasztikus folyamatot jelent,

amely Markov-tulajdonságú. Markov-tulajdonságúnak lenni röviden annyit jelent, hogy adott jelenbeli állapot mellett, a rendszer jöv®beni állapota nem függ a múltbeliekt®l. Másképpen megfogalmazva, ez azt is jelenti, hogy a jelen leírása teljesen magába foglalja az összes olyan információt, ami befolyásolhatja a jöv®beli helyzetét a folyamatnak. A rendszer korábbi állapotai a kés®bbi állapotokra csak a jelen állapoton keresztül gyakorolhatnak befolyást. Az asszimetrikus bolyong ás olyan Markov-lánc, melynek állapottere X = Z, és p(x, x+1) = p, p(x, x−1) = 1−p a megengedett átmenetek valószín¶sége, ahol 0 < < p < 1. Adott 0 ≤ x ≤ r természetes számokkal jelölje ur (x) annak valószin¶ségét, hogy az x helyr®l induló bolyongás el®bb éri el a 0 mint az r szintet, vagyis a játékos tönkremegy miel®tt a remélt r nyereséghez hozzájutna. Persze ur (0) = 1, ur (r) = 0, és a teljes valószin¶ség tétele miatt ur (x) = pur (x + 1) + (1 − p)ur (x − 1) ha 0 < x < r.

(7)

Az adott peremfeltétellel ez az egyenlet egyértelm¶en oldható meg, például ur (x) = 1 − x/r ha p = 1/2 , és ur (x) = α(eβx − γ) az általános megoldás (ezt a megoldást valahonnan "megsejtettük", de utólag igazolható, hogy tényleg ez a megoldás), ahol peβ + (1 − p)e−β = 1 , vagyis eβ = (1 − p)/p, továbbá γ = eβr és α(1 − eβr ) = 1 , ahonnan ur (x) =

eβx − eβr 1 − eβr

ahol β = log

1−p p

(8)

22


A p → 1/2 határátmenet után persze lineáris prolt kapunk, de ennél érdekesebb a p = 1/2 − ϵ/2 és r = 1/ϵ "gyengén asszimmetrikus" határátmenet, amikoris (7) mint az 12 ∂x2 u − ∂x u = 0; u(0) = 1, u(1) = 0 elliptikus peremérték feladat numerikus megoldásának algoritmusa jelenik meg. Legyen u˜r (x) = ur (rx), 0 ≤ x ≤ 1, u(x) = limr→∞ u˜r (x). 1 1 ϵ Ha ϵ = és p = − , akkor (7) átírva: r

2

2

(1 ϵ ) ϵ) ur (r(x + ϵ)) + + ur (r(x − ϵ)) = 2 2 2 2 (1 ϵ ) (1 ϵ ) = − u˜r (x + ϵ) + + u˜r (x − ϵ) 2 2 2 2 ezt átrendezve, és ϵ2 -tel osztva: u˜r (x) = ur (rx) =

(1

−

1 ( u˜r (x + ϵ) − 2˜ ur (x) + u˜r (x − ϵ) ) u˜r (x + ϵ) − u˜r (x − ϵ) − =0 2 ϵ2 2ϵ

Ennek megoldása tényleg u(x) = lim u1/ϵ (x/ϵ) = ϵ→0

e2 − e2x e2 − 1

(9)

mivel (1/ϵ)β → 2 amint ϵ → 0. Szép esetekben jó sejtés lehet, hogy ha egy közelít® képlet tart egy dierenciálegyenlethez, akkor a közelít® képlet megoldásának (jelen esetben ur (x)) is tartania kell a dierenciálegyenlet megoldásához (jelen esetben u(x)).

4.2. Kedvez®tlen helyzetben merész a jó játékos A szerencsejátékos pénze n játszma után: ζn := x +

n−1 ∑

γ(ζt )σt ,

(10)

t=0

ahol x ∈ N a játékos induló t®kéje, σt független ±1 sorozat, a nyerés valószín¶sége P [σt = 1] = p < 1/2, végül γ : N → N a játékos stratégiája: γ(y) az a tét,

4.2. Kedvez®tlen helyzetben merész a jó játékos

23

5. ábra. Optimális stratégia vr (x) függvénye amit y t®ke birtokosaként kockáztat. Olyan bolyongásról van szó, ahol az ugrás nagyságát a játékos határozza meg, a cél az el®re kit¶zött r > x összeg megszerzése. Feltesszük, hogy γ, r ∈ N és 0 < γ(x) ≤ γ˜ (x) := min{x, r − x}, ur,γ (x) a cél elérésének valószín¶sége γ stratégia esetén. Csak véges sok megengedett stratégia van, a feladat az u∗r (x) := maxγ ur,γ (x) optimum megvalósítása. Jelölje τ azt a véletlen id®pontot, amikor a játszma véget ér: ζτ = 0 ha tönkremegy, ζτ = r ha sikeres. Mivel

24


rur,γ (x) = Eζτ = x + (2p − 1)E

τ −1 ∑

γ(ζt ),

(11)

t=0

akkor lesz a stratégiánk optimális (azaz akkor lesz ur,γ (x) maximális), ha az ∑ −1 átlagos pénzforgalom, E τt=0 γ(ζt ), minimális (nyilván, hiszen x x, (2p − 1) pedig negatív). A nagy számok törvénye szerint ez egyáltalán nem meglep®, az igazságtalan játékot olyan gyorsan be kell fejezni, ahogy csak lehet. Ha r páros és x = r/2, akkor nyilván a merész játék optimális, tehát u∗r (r/2) = ur,˜γ (r/2) = p. Általában is igaz, hogy 1 ≤ x < r esetén u∗r (x) = max{pu∗r (x + k) + (1 − p)u∗r (x − k) : 1 ≤ k ≤ γ˜r (x)} k

(12)

ami az optimális kontroll elméletének Bellman féle alapelve: optimális stratégia minden lépése (szakasza) is az. El®ször azt mutatjuk meg, hogy az u∗r (0) = 0 és u∗r (r) = 1 peremfeltétel mellett (12) egyértelm¶en oldható meg. Állítás: Tegyük fel, hogy uˆr is megoldás, és legyen vr (x) := u∗r (x) − uˆr (x) ; persze vr (0) = vr (r) = 0. Mivel a két maximum helye különbözhet, maxk bk − − maxk ak ≤ maxk (bk − ak ), tehát vr (x) ≤ max{pvr (x + k) + (1 − p)vr (x − k) : 1 ≤ k ≤ γ˜r (x)}. k

A két oldal egyenl®, ha vr (x) = v¯r := maxy vr (y), ha tehát 0 < x < r maximumhely, akkor van 1 ≤ k ≤ γ˜ (x) úgy, hogy vr (x − k) = vr (x) = vr (x + k). Ugyanezt az x − k és x + k helyekr®l is elmondhatjuk, és véges sok lépés után bizonyítandó v¯r = vr (0) = 0 vagy v¯r = vr (r) = 0 egyenl®séget kapjuk.

Szemléletesen itt arról van szó, hogy ami a (12)-t kielégíti, az az optimális stratégia. Persze el®fordulhat, hogy több stratégia is kielégíti, de ebben az esetben ugyanazok lesznek a nyerési esélyek, így mindegyik ilyen stratégia optimális. Legyen u˜r (x) a merész játékos sikerének valószín¶sége, ezt az

25

4.2. Kedvez®tlen helyzetben merész a jó játékos

{ u˜r (x) =

p˜ ur (2x) ha x ≤ r/2 p + (1 − p)˜ ur (2x − r) ha x ≥ r/2

(13)

rekurzió deniálja. Az r = 2d egyszer¶sít® feltevés mellett, indukcióval bizonyítjuk, hogy u˜r megoldja a (12) Bellman egyenletet. Ehhez azt kell belátni, hogy u˜r (x) ≥ p˜ ur (x + k) + (1 − p)˜ ur (x − k)

ha 1 ≤ k ≤ γ˜r (x);

(14)

(13) szerint az egyenl®ség biztosan teljesül ha k = γ˜r (x). Tegyük fel hogy (14) igaz, az u˜2r (2x) = u˜r (x) azonosság miatt csak az x páratlan értékeivel van gond. Az indukció végrehajtásakor négy esetet kell szétválasztani. Ha x + k ≤ r akkor u˜2r (x) = p˜u2r (2x), míg u˜2r (x + k) = p˜u2r (2x + 2k) és u˜2r (x − k) = p˜ u2r (2x − 2r), de az indukciós feltevés és u˜2r (2x) = u˜r (x) miatt u˜2r (x) = p˜ u2r (2x) = p˜ ur (x) ≥ p2 u˜r (x + k) + p(1 − p)˜ ur (x − k) = p2 u˜2r (2x+2k)+p(1−p)˜ u2r (2x−2k) = p˜ u2r (x+k)+(1−p)˜ u2r (x−2)

ha 1 ≤ k ≤ γ˜r (x)

amit bizonyítani kellett. Ha x − k ≥ r akkor u˜2r számolása (13) második sora alapján történik. Az indukciós lépés egyébként ugyanaz, mint fent; (14) a 2x − 2r helyen alkalmazandó. Az r ≤ 2x ≤ 3r sávban az indukció kulcsa az önmagában is tanulságos { u˜2r (x) =

p2 + (1 − p)˜ u2r (2x − r) ha r ≤ 2x ≤ 2r (1 − p)p + p˜ u2r (2x − r) ha 2r ≤ 2x ≤ 3r

újabb azonosság, ami az els® esetben

u˜2r (x) = p˜ u2r (2x) = p2 + p(1 − p)˜ u2r (4x − 2r) = p2 + (1 − p)˜ u2r (2x − r)

miatt, a második esetben pedig

26


u˜2r (x) = p + (1 − p)˜ u2r (2x − 2r) = p + (1 − p)p˜ u2r (4x − 4r)

és u˜2r (2x − r) = p + (1 − p)˜ u2r (4x − 4r)

miatt igaz. A fennmaradó esetekben x + k ≥ r és x − k ≤ r, tehát r ≤ 2x ≤ 3r. Ha most r ≤ 2x ≤ 2r akkor az induktív feltevés szerint

u˜2r (x) = p2 +(1−p)˜ u2r (2x−r) ≥ p2 +p(1−p)˜ u2r (2x+2k −2r)+(1−p)2 u˜2r (2x−2k)

viszont u˜2r (x + k) = p + (1 − p)˜u2r (2x + 2k − 2r) és u˜2r (x − k) = p˜u2r (2x − 2k), amib®l p < 1 − p miatt állításunk következik. Ugyanígy ha 2r ≤ 2x ≤ 3r, akkor

u˜2r (x) = (1−p)p+p˜ u2r (2x−r) ≥ (1−p)p+p2 u˜2r (2x+2k−2r)+p(1−p)˜ u2r (2x−2k)

Megint u˜2r (x + k) = p + (1 − p)˜u2r (2x + 2k + 2r) és u˜2r (x − k) = p˜u2r (2x − 2k) felhasználásával hajtjuk végre az indukció utolsó lépését. Tehát a merész stratégia igazságtalan (p < 1/2) helyzetben optimális, legalábbis akkor, ha r = 2d . Szemléletesen az a lényeg, hogy ha igazságtalan a játék, akkor minél több lépést teszek, annál nagyobb a cs®d esélye, így kevés lépésre törekszem. Ezt úgy tudom elérni, ha nagyokat lépek, vagyis minden lépésben megduplázom a tétet, egészen addig, amíg már nincs szükségem arra, hogy az egész tétemet megnyerjem (például ha 8 forintot akarok nyerni, és már van 6 forintom, akkor nem kockáztatok, csak 2 forintot). Err®l szól a γ˜ , a teljes pénzemnél többet nem tehetek fel, a hiányzó összegnél pedig nyilván nem fogok többet feltenni.

4.3. Óvatos stratégia kedvez® helyzetben

27

4.3. Óvatos stratégia kedvez® helyzetben Azt a szituációt vizsgáljuk, amikor a játékos t®kéjének c ∈ [0,1] hányadát kockáztatja minden játszmában, de most a játék el®nyös. Feltehetjük, hogy a kezd®t®ke ζ0 = 1, ekkor n játszma után ζn =

n−1 ∏

(1 + σt+1 c)

(15)

t=0

a pénze, ahol σt független ±1 sorozat, P [σt = 1] = p > 1/2.Eζn = (1 + (2p − − 1)c)n akkor maximális, ha c = 1 (vagyis ha mindig felteszem az összes pénzem, hiszen p most kedvez®), de ez a stratégia igen kockázatos, mert ilyenkor P [ζ > 0] = = pn (nyilván, hiszen kedvez® p mellett is el®fordulhat hogy veszítünk, és akkor azonnal tönkremennénk, tehát ezt a stratégiát mégsem fogjuk választani). Viszont 1 E log ζn = p log(1 + c) + (1 − p) log(1 − c) = max! (16) n ha c = 2p − 1, és a t®ke növekedésének exponenciális sebessége éppen log 2 − − h(p) ≥ 0, ahol h(p) az entrópia (ez azt mutatja meg, hogy mennyire bizonytalan a játék kimenetele). A log 2 − h(p) csak akkor 0, ha p = 1/2. Ha p < 1/2 akkor a

számolás, és a hosszú távú játék értelmetlen. Látható, hogy ez a példa folytonos (az el®z® egészeken "ugrált"). Ennek a stratégiának az a lényege, hogy akár nyerünk, akár veszítünk, a t®kének mindig egy c-ed részét kockáztatjuk. Ha p > 1/2, akkor ez a stratégia kedvezni fog nekünk.

4.4. Fogadások több lehet®ségre Sok ló közül a pályán az i nev¶ pi > 0 valószín¶séggel nyer, p1 + p2 + ... + pr = = 1. Ha a játékos az i nev¶ lóra Si összeget tesz, és az nyer, akkor nyereménye ci Si lesz; a ci > 1 szorzókat az iroda határozza meg. Ha csak a befutóra akarunk fogadni, akkor stratégiánk a következ® lehet: aktuális S = S(t) pénzünkb®l csak βS összeget kockáztatunk, és ezt az r lehet®ség között az αi ≥ 0 arányok szerint ∑ osztjuk meg, vagyis βαi S az i-ik tét. Persze 0 ≤ β ≤ 1, αi = 1, és a t + 1-ik

28


futam után a pénzünk S(t + 1) = S(t)(1 − β + β

r ∑

αi ci σi (t + 1)),

(17)

i=1

ahol σi (t) = 1 ha i nyer, egyébként σi = 0. Feltesszük, hogy P [σi (t) = 1] = pi ∀t, és a σ(t) := (σ1 (t), σ2 (t), ..., σr (t)) sorozat teljesen független. Ilyenkor változatlan, determinisztikus stratégiával játszunk, tehát E(S(t + 1)|σ(1), σ(2), ..., σ(t)) = S(t)

r ∑

pi (1 − β + βαi ci ),

i=1

ami adott β mellett akkor maximális, ha pi ci < v ∗ := max{pk ck } esetén αi = 0. A maximum értéke, S(t)(1 − β + βv ∗ ) akkor a legnagyobb, ha β = 0 vagy β = 1, aszerint hogy v ∗ < 1 vagy v ∗ > 1. A v ∗ = 1 eset indierens, persze senki sem lesz hajlandó fogadni, ha tudja hogy v ∗ ≤ 1 (hiszen ekkor hosszabb távon mindenképp csökkenni fog a pénze). Ugyanúgy, mint az el®z® példánál, ha β = 1 akkor ez a stratégia hosszú távú játékra biztosan nem alkalmas, mert ha a favorit nem jön be, akkor mindenünket elveszítjük. Kérdés hogy az óvatosabb β < 1 választás mellett ez a merész stratégia lehet-e hosszú távon is eredményes. Deníció: A Largange-multiplikátorok módszeré nek lényege, hogy egy adott széls®érték feladatot egy adott mellékfeltétellel szeretnénk megoldani. Jelen esetben f (α) = 0 a mellékfeltétel. Ennek λ-szorosát hozzáadjuk a függvényhez, és akkor lesz "használható" az eredmény, ha teljesül a mellékfeltétel. Fix stratégia mellett a t®ke exponenciális növekedésének rátája J(α, β) =

r ∑

pi log(1 − β + βαi ci ),

(18)

i=1

ennek keressük a maximumát, amit két lépésben találunk meg. Rögzített β > > 0 mellett J az α konkáv függvénye. A Lagrange multuplikátorok módszerét alkalmazva az optimum α∗ helyen:

29

4.4. Fogadások több lehet®ségre

r ∑

pi log(1 − β + βαi ci ) = max

i=1 r ∑

r ∑ pi log(1 − β + βαi ci ) − λ( αi − 1)

i=1

i=1

1 ∂ = −λ + pi βci ∂αi 1 − β + βαi ci λ = pi

1 1 λ βci ⇒ = ⇒ 1 − β + βαi ci 1 − β + βαi ci pi βci pi βci pi βci ⇒ βαi ci = −1+β λ λ pi βci − λ + λβ αi = λβci

⇒ (1 − β + βαi ci ) =

r ∑ i=1

αi =

r ∑ λβ − λ + pi ci β

λβci

i=1

1−

r ∑ β−1 i=1

βci

=

=

r ∑ β−1 i=1

+

i=1

λ

=1

r r ∑ 1∑ pi , ahol pi = 1 λ i=1 i=1

∑1 1 β−1∑ 1 = , legyen Γ = β i=1 ci λ c i=1 i r

1−

βci

r ∑ pi

1−

r

β−1 1 β − (β − 1)Γ 1 Γ= ⇒ = β λ β λ

λ=

β β = β − (β − 1)Γ β(1 − Γ) + Γ

∑1 p βc − λ + λβ βpi ci β λ= = , Γ := , αi∗ = i i ∗ 1 − β + βαi ci Γ + β(1 − Γ) c λβci i=1 i r

∑

(19)

egyenleteket kapjuk, a második egyenl®ség a αi = 1 mellékfeltétel következménye. Természetesen az αi∗ ≥ 0, vagyis a β + pi ci ≥ 1 feltételeknek is teljesülni kell: β ≥

30

5. ÖSSZEFOGLALÁS

≥ 1 − v∗ , ahol v∗ := min{pi ci }. Ebben a tartományban βpi ci ∑ J(α , β) = pi log = pi log(pi ci (Γ + β(1 − Γ))), (20) λ i=1 i=1 ∑ ∑ ∑ legyen qi := (λ/β)(1 − β + βαi ci )/ci . Mivel qi = 1, pi log qi ≤ pi log pi , mert pi log(qi /pi ) ≤ qi −pi , tehát J(α, β) ≤ J(α∗ , β), és (19) az egyenl®ség feltétele. Az is látható, hogy J(α∗ , β) a β szigorúan növ®, illetve fogyó függvénye aszerint, hogy Γ < 1 vagy Γ > 1. Ha Γ > 1 akkor β = β ∗ := 1 − v∗ az optimális választás, de csak akkor érdemes játszani, ha J ∗ > 0. A Γ < 1 esetben az optimális ráta a β = β ∗ := 1 és αi = αi∗ := pi választással érhet® el, értéke pedig J ∗ := ∑ = J(α∗ , β ∗ ) = pi log(pi ci) > 0. A Γ = 1 eset β ≥ 1 − v∗ szempontjából indierens, pi log(pi ci ) ≥ pi − 1/ci miatt most is igaz, hogy J(α∗, 1) ≥ 0. Ez az egyszer¶ ∗

r ∑

r

példa jól mutatja, hogy hosszú futamid®nél több lábon kell állni, vagyis mindegyik nyerési lehet®ségnek érdemes sanszot adni. Meglep® hogy az optimális stratégia nem függ a ci szorzóktól, és a pi ci < 1 eseteket is meg kell játszani. Optimális stratégia készítéséhez ismerni kell(ene) a pi sanszokat. Ha az iroda mohó, például ci < 1 is el®fordul, akkor elérheti, hogy a nyereség optimális rátája J ∗ < 0 legyen, ami a fogadókat hosszú távon biztosan elkedvetleníti, tehát a mohóság visszaüt. Valódi pénzügyi - matematikai feladat a ci szorzók optimális megválasztása. Ha J ∗ túlzottan negatív, akkor a haszonkulcs magas ugyan, de kicsi lesz a forgalom, és így a nyereség is; ci := 1/pi korrektnek t¶nik (vagyis a szorzó pontosan a nyerés valószín¶ségének a reciproka), mert ekkor J ∗ = 0. Persze J ∗ > 0 még nem teszi az irodát veszteségessé, a fogadók többsége nyilván nem ért a lóhoz, csak szórakozni akar. 5. Összefoglalás

Dolgozatomban a valóságon alapuló modelleket vizsgáltam, és a protmaximalizálás lehet®ségeit mutattam be. Természetesen a modell mindig egyszer¶bb, mint maga a jelenség, mégis a kapott eredmények, algoritmusok irányt mutathatnak.

31 A 3. fejezetben tárgyaltak valójában nem csak a banki lekötések esetén alkalmazhatóak. A klasszikus készletgazdálkodási problémák elemzése is hasonló elveken alapul (s®t, ha még messzebbr®l szemléljük, még több alkalmazási területet fedezhetünk fel). A 4. fejezetben tárgyalt szerencsejátékok is egyre elterjedtebbé válnak, f®ként az online játékok az interneten, így érdemes, és napjainkban id®szer¶ is ennek a jelenségnek a matematikai hátterét vizsgálni.

32

5. ÖSSZEFOGLALÁS

Köszönetnyilvánítás

Hálás köszönettel tartozom mindazoknak, akik segítettek abban, hogy ez a dolgozat létrejöhessen. Külön köszönet Csiszár Vill® tanárn®nek, aki id®t, és energiát nem sajnáva segített mind a témaválasztásban, mind a dolgozat megírásában. Készségesen elmagyarázta a nehezebben érthet® részeket, észrevételeivel és hasznos tanácsaival pedig a dolgozatban tárgyaltak közérthet® megfogalmazását segítette.

33

HIVATKOZÁSOK

Hivatkozások

[1]

Csiszár Vill® :

Zsugori bank, iid cash-ow esete, kézirat, 2008

[2]

Dr. Farkas Miklós :

Matematikai kislexikon, 3. kiadás, M¶szaki könyvkiadó,

Budapest 1979 [3]

Pénzügyi Matematika, BME Matematika intézet, 2010, http://www.math.bme.hu/ jofri/JOFRI/OKTAT/pmmar.pdf Fritz

József :

[4]

Rónyai L. - Ivanyos G. - Szabó R. :

Algoritmusok, Typotex kiadó 2005

[5]

Wikipédia :

[6]

I. N. Bronstejn - K. A. Szemengyajev - G. Musiol - H. Mühlig :

Markov-láncok,http://hu.wikipedia.org/wiki/Markov-lánc

Matematikai kézikönyv, 8.,

javított, átdolgozott kiadás,

Typotex kiadó, 2006

34

HIVATKOZÁSOK

NYILATKOZAT Név: Halász Sándor ELTE Természettudományi Kar, szak: Matematika BSc ETR azonosító: HASNAAT.ELTE Szakdolgozat címe:

Optimális stratégiák magas tranzakciós költség esetén és a szerencsejátékokban

A szakdolgozat szerz®jeként fegyelmi felel®sségem teljes tudatában kijelentem, hogy a dolgozatom önálló munkám eredménye, saját szellemi termékem, abban a hivatkozások és idézések standard szabályait következetesen alkalmaztam, mások által írt részeket a megfelel® idézés nélkül nem használtam fel.

Budapest, 2010.12.30. a hallgató aláírása

Optimális stratégiák magas tranzakciós költség esetén és a szerencsejátékokban

Recommend Documents