Matematika | Statisztika » Halász Sándor - Optimális stratégiák magas tranzakciós költség esetén és a szerencsejátékokban

http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu Á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 http://www.doksihu 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. http://www.doksihu 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 http://www.doksihu 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é http://www.doksihu 4 2. DINAMIKUS PROGRAMOZÁS 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 http://www.doksihu 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 http://www.doksihu 6 2. DINAMIKUS PROGRAMOZÁS 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 http://www.doksihu 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 http://www.doksihu 8 2. DINAMIKUS PROGRAMOZÁS 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 http://www.doksihu 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). http://www.doksihu 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 < http://www.doksihu 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: http://www.doksihu 12 3. A MAGAS TRANZAKCIÓS KÖLTSÉG PROBLÉMÁJA 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) http://www.doksihu 13 3.3 A h=1 eset 3. ábra [q −1 E(V0 (z + X)) − b(z − ζ)] függvény Q=10, q=11, ζ = 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, http://www.doksihu 14 3. A MAGAS TRANZAKCIÓS KÖLTSÉG PROBLÉMÁJA 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−∞ http://www.doksihu 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:

http://www.doksihu 16 3. A MAGAS TRANZAKCIÓS KÖLTSÉG PROBLÉMÁJA 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 http://www.doksihu 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! http://www.doksihu 18 3. A MAGAS TRANZAKCIÓS KÖLTSÉG PROBLÉMÁJA { 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). http://www.doksihu 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) = ϵ http://www.doksihu 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- http://www.doksihu 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) http://www.doksihu 22 4. SZERENCSEJÁTÉKOK OPTIMÁLIS STRATÉGIÁI 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 ũr (x) = ur (rx), 0 ≤ x ≤ 1, u(x) = limr∞ ũ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 ϵ ) = − ũr (x + ϵ) + + ũr (x − ϵ) 2 2 2 2 ezt átrendezve, és ϵ2 -tel osztva: ũr (x) = ur (rx) = (1 − 1 ( ũr (x + ϵ) − 2ũr (x) + ũr (x − ϵ) ) ũr (x + ϵ) − ũ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, http://www.doksihu 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 http://www.doksihu 24 4. SZERENCSEJÁTÉKOK OPTIMÁLIS STRATÉGIÁI 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 ûr is megoldás, és legyen vr (x) := u∗r (x) − û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 ũr (x) a merész játékos sikerének valószín¶sége, ezt az http://www.doksihu 25 4.2 Kedvez®tlen helyzetben merész a jó játékos { ũr (x) = pũr (2x) ha x ≤ r/2 p + (1 − p)ũr (2x − r) ha x ≥ r/2 (13) rekurzió deniálja. Az r = 2d egyszer¶sít® feltevés mellett, indukcióval bizonyítjuk, hogy ũr megoldja a (12) Bellman egyenletet Ehhez azt kell belátni, hogy ũr (x) ≥ pũr (x + k) + (1 − p)ũr (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 ũ2r (2x) = ũ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 ũ2r (x) = pũ2r (2x), míg ũ2r (x + k) = pũ2r (2x + 2k) és ũ2r (x − k) = pũ2r (2x − 2r), de az indukciós feltevés és ũ2r (2x) = ũr (x) miatt ũ2r (x) = pũ2r (2x) = pũr (x) ≥ p2 ũr (x + k) + p(1 − p)ũr (x − k) = p2 ũ2r (2x+2k)+p(1−p)ũ2r (2x−2k) = pũ2r (x+k)+(1−p)ũ2r (x−2) ha 1 ≤ k ≤ γ̃r (x) amit bizonyítani kellett. Ha x − k ≥ r akkor ũ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 { ũ2r (x) = p2 + (1 − p)ũ2r (2x − r) ha r ≤ 2x ≤ 2r (1 − p)p + pũ2r (2x

− r) ha 2r ≤ 2x ≤ 3r újabb azonosság, ami az els® esetben ũ2r (x) = pũ2r (2x) = p2 + p(1 − p)ũ2r (4x − 2r) = p2 + (1 − p)ũ2r (2x − r) miatt, a második esetben pedig http://www.doksihu 26 4. SZERENCSEJÁTÉKOK OPTIMÁLIS STRATÉGIÁI ũ2r (x) = p + (1 − p)ũ2r (2x − 2r) = p + (1 − p)pũ2r (4x − 4r) és ũ2r (2x − r) = p + (1 − p)ũ2r (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 ũ2r (x) = p2 +(1−p)ũ2r (2x−r) ≥ p2 +p(1−p)ũ2r (2x+2k −2r)+(1−p)2 ũ2r (2x−2k) viszont ũ2r (x + k) = p + (1 − p)ũ2r (2x + 2k − 2r) és ũ2r (x − k) = pũ2r (2x − 2k), amib®l p < 1 − p miatt állításunk következik. Ugyanígy ha 2r ≤ 2x ≤ 3r, akkor ũ2r (x) = (1−p)p+pũ2r (2x−r) ≥ (1−p)p+p2 ũ2r (2x+2k−2r)+p(1−p)ũ2r (2x−2k) Megint ũ2r (x + k) = p + (1 − p)ũ2r (2x + 2k +

2r) és ũ2r (x − k) = pũ2r (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. http://www.doksihu 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 (16) E log ζn = p log(1 + c) + (1 − p) log(1 − c) = max! 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 http://www.doksihu 28 4. SZERENCSEJÁTÉKOK OPTIMÁLIS STRATÉGIÁI 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: http://www.doksihu 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 r 1− βci r ∑ pi 1− 1 β − (β − 1)Γ 1 β−1 Γ= ⇒ = β λ β λ λ= β β = β − (β − 1)Γ β(1 − Γ) + Γ ∑1 βpi ci β p βc − λ + λβ λ= = , Γ , α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: β ≥ http://www.doksihu 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. http://www.doksihu 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. http://www.doksihu 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. http://www.doksihu 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.mathbmehu/ jofri/JOFRI/OKTAT/pmmarpdf 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.wikipediaorg/wiki/Markov-lánc Matematikai kézikönyv, 8., javított, átdolgozott kiadás, Typotex kiadó, 2006