A merész játékok stratégiája

A következő problémával foglalkozunk: Tegyük fel, hogy feltétlenül ki kell fizetnünk 1000 forintos adósságunkat, de csak 600 forintunk van. Egyetlen lehetőségünk, hogy a még szükséges 400 forintot megszerezzük az, hogy egy kaszinóba megyünk, ott játszunk, és a szükséges pénzt megnyerjük. Minden egyes játék során mi dönthetjük el, hogy mekkora tétet teszünk fel. Tegyük fel, hogy egy olyan játékot játszhatunk a kaszinóban, melyben a feltett tétet 0.49 valószínűséggel megduplázzuk, 0.51 valószínűséggel pedig elveszítjük. Kérdés, hogyan érdemes játszani, milyen téteket érdemes feltenni. Belátjuk, hogy az úgynevezett merész játékok módszere optimális stratégia. Ez azt jelenti, hogy minden lépésben vagy a teljes vagyonunkat tesszük fel, (ezt tesszük abban az esetben, ha a pillanatnyi vagyonunk kisebb mint a szükséges 1000 forint fele), vagy pedig pont annyi tétet teszünk fel, ami nyereség esetén biztosítja a szükséges 1000 forint megszerzését a következő lépésben.

Az állítás bizonyítása:

A vizsgálatban hasonló módszert követünk, mint a Szindbád probléma és a secretary probléma megoldásában. Az említett feladatokban az úgynevezett backward induction segítségével kiszámoltuk mi az optimális stratégia és az optimális eredmény abban az esetben, ha csak az utolsó k lépésben állhatunk meg, k = 0, 1, 2, . . .. Tekintsük azt a játékot, melyben a játék minden lépésében a feltetett tétet megduplázzuk p, 0 ≤ p < \frac{1}{2}, valószínűséggel, és elveszítjük 1 − p valószínűséggel. A kezdeti időpontban a szükséges összeg t-szeresével rendelkezünk. Célunk, hogy minél nagyobb valószínűséggel megszerezzük a szükséges összeget.

Belátjuk indukcióval, hogy amennyiben csak k lépésben játszhatunk, k = 0, 1, 2, …, akkor a merész stratégia optimális. Ennek érdekében tekintjük azt az R_{k}(t) függvényt, t ≥ 0, k = 0, 1, 2, …, amelyik azt fejezi ki, hogy ha legfeljebb k játékot játszhatunk, és a kezdeti lépés előtt a szükséges összeg t-szeresével rendelkezünk, akkor mi a valószínűsége annak, hogy optimális stratégia esetén megnyerjük a szükséges összeget. Ezeknek a függvényeknek belátjuk bizonyos tulajdonságait, melyek lehetővé teszik az állítás bizonyítását. Vegyük észre, hogy

R_{0}(t) = \{ \begin{matrix}0 & ha 0 ≤ t < 1, \\ 1 & ha t ≥ 1. \end{matrix}  (1)

és

R_{k}(t) = max_{0≤s≤t}{(1 − p)R_{k−1}(t − s) + pR_{k−1}(t + s)}, k ≥ 1.  (2)

Vezessük be ezen kívül az alábbi R̄_{k}(t), k = 0, 1, 2, …, függvényeket, melyek mint látni fogjuk szoros kapcsolatban vannak az előbbi R_{k}(t) függvényekkel.

\begin{aligned}R̄_{0}(t) & = R_{0}(t) \\ R̄_{k+1}(t) & = \{ \begin{matrix}pR̄_{k}(2t) & ha 0 ≤ t ≤ \frac{1}{2} \\ p + (1 − p)R̄_{k}(2t − 1) & ha \frac{1}{2} ≤ t ≤ 1 \end{matrix} \end{aligned}  (3)

Annak érdekében, hogy a feladatot megoldjuk, meg kell értenünk az indukciós módon definiált R̄_{k}(t) függvények néhány tulajdonságát. Először fogalmazzuk meg e függvények alábbi egyszerű, de fontos tulajdonságát.

Tétel. A (3) formulával definiált R̄_{k}(t), k = 0, 1, 2, …, függvényeknek megvan az alábbi

tulajdonságuk, ha 0 ≤ p ≤ \frac{1}{2}.

a.) Az R̄_{k}(t) függvény konstans minden (j − 1)2^{−k} ≤ t < j2^{−k}, 1 ≤ j ≤ 2^{k} interval-

lumban. b.) Ha l_{0} ≥ k_{0} akkor R̄_{l_{0}}(j2^{−k_{0}}) = R̄_{k_{0}}(j2^{−k_{0}}) minden 0 ≤ j ≤ 2^{k_{0}} indexre. c.) Az R̄_{k}(t) függvény monoton nő a t változóban minden k ≥ 0 számra. d.) Ha t = u2^{−k}, s = v2^{−k}, 0 ≤ u ≤ v egész számok, akkor

R̄_{k}(t) ≥ pR̄_{k}(t + s) + (1 − p)R̄_{k}(t − s).

e.) R̄_{k}(t) = R_{k}(t), ha t = j2^{−k}, 0 ≤ j ≤ 2^{k}, ahol az R_{k}(t) függvényt az (1) és (2) formula definiálja. Sőt R̄_{k}(t) = R_{k}(t) minden 0 ≤ t ≤ 1 számra.

Bizonyítás: A Tétel állítását teljes indukcióval bizonyítjuk. Az állítás igaz k = 0-ra. Ugyancsak könnyű ellenőrizni az állítás helyességét a k = 1 esetben. Tegyük fel, hogy az igaz k-ra, és lássuk be k +1-re. (A b.) állítás úgy értendő a k-ik idukciós lépésben, hogy az érvényes minden 0 ≤ k_{0} ≤ l_{0} ≤ k, 0 ≤ j ≤ 2^{k_{0}}, számpárra. A Tétel legtartalmasabb része a d.) pont, és ennek bizonyítása igényli a legtöbb munkát. A bizonyítást ezzel a ponttal kezdjük.

A d.) pont (indukciós) bizonyítása: A d.) állítást külön látjuk be az a) 0 ≤ t + s ≤ \frac{1}{2},

b) \frac{1}{2} ≤ t − s ≤ 1, c) 0 ≤ t − s ≤ t ≤ \frac{1}{2} ≤ t + s ≤ 1 d) 0 ≤ t − s ≤ \frac{1}{2} ≤ t ≤ t + s ≤ 1 esetekben.

Az a) esetben, (amikor t = u2^{−(k+1)} s = v2^{−(k+1)}, 0 ≤ u ≤ v),

R̄_{k+1}(t) − pR̄_{k+1}(t + s) − (1 − p)R̄_{k+1}(t − s)
= pR̄_{k}(2t) − p^{2}R̄_{k}(2(t + s)) − p(1 − p)R̄_{k}(2(t − s))
= p (R̄_{k}(2t) − pR̄_{k}(2t + 2s) − (1 − p)R̄_{k}(2t − 2s)) ≥ 0

az indukciós feltevés alapján.

A b) esetben, amikor \frac{1}{2} ≤ t − s ≤ t ≤ t + s ≤ 1

R̄_{k+1}(t) − pR̄_{k+1}(t + s) − (1 − p)R̄_{k+1}(t − s)
= p + (1 − p)R̄_{k}(2t − 1) − p^{2} − p(1 − p)R̄_{k}(2(t + s) − 1)
− p(1 − p) − (1 − p)^{2}R̄_{k}(2(t − s) − 1)
= (1 − p) (R̄_{k}(2t − 1) − pR̄_{k}(2t − 1 + 2s) − (1 − p)R̄_{k}(2t − 1 − 2s)) ≥ 0.

A c) esetben, amikor 0 ≤ t − s ≤ t ≤ \frac{1}{2} ≤ t + s ≤ 1
R̄_{k+1}(t) − pR̄_{k+1}(t + s) − (1 − p)R̄_{k+1}(t − s)
= pR̄_{k}(2t) − p^{2} − p(1 − p)R̄_{k}(2(t + s) − 1) − p(1 − p)R̄_{k}(2(t − s))
= p [R̄_{k}(2t) − p − (1 − p)R̄_{k}(2t + 2s − 1) − (1 − p)R̄_{k}(2t − 2s)] .

Vegyük észre, hogy t ≥ \frac{1}{4}, mert 2t ≥ t + s ≥ \frac{1}{2}. Innen

R̄_{k+1}(t) − pR̄_{k+1}(t + s) − (1 − p)R̄_{k+1}(t − s) = p [p + (1 − p)R̄_{k}(4t − 1) − p − (1 − p)R̄_{k}(2t + 2s − 1) − (1 − p)R̄_{k}(2t − 2s)] = p(1 − p) [R̄_{k}(4t − 1) − R̄_{k}(2t + 2s − 1) − R̄_{k}(2t − 2s)]

= (1 − p) [R̄_{k} (2t − \frac{1}{2}) − pR̄_{k}(2t + 2s − 1) − pR̄_{k}(2t − 2s)] .

Most fogjuk kihasználni a p ≤ \frac{1}{2} feltételt. Eszerint,

(1 − p) [R̄_{k} (2t − \frac{1}{2}) − pR̄_{k}(2t + 2s − 1) − pR̄_{k}(2t − 2s)]

≥ (1 − p) [R̄_{k} (2t − \frac{1}{2}) − pR̄_{k}(2t + 2s − 1) − (1 − p)pR̄_{k}(2t − 2s)] ≥ 0,

ha 2t + 2s − 1 ≥ 2t − 2s, és a 2t + 2s − 1 ≤ 2t − 2s eset hasonlóan tárgyalható. Innen következik a d.) pont állítása a c) esetben is.

A d) esetben, amikor 0 ≤ t − s ≤ \frac{1}{2} ≤ t ≤ t + s ≤ 1 R̄_{k+1}(t) − pR̄_{k+1}(t + s) − (1 − p)R̄_{k+1}(t − s)

= p + (1 − p)R̄_{k}(2t − 1) − p^{2} − p(1 − p)R̄_{k}(2(t + s) − 1)) − p(1 − p)R̄_{k}(2(t − s))

= (1 − p) [p + R̄_{k}(2t − 1) − pR̄_{k}(2t + 2s − 1) − pR̄_{k}(2t − 2s)] .

Továbbá \frac{3}{4} ≥ t, mert 1 ≥ t + s = 2t − (t − s) ≥ 2t − \frac{1}{2}. Ezért 0 ≤ 2t − 1 ≤ \frac{1}{2}, R̄_{k}(2t − 1) = pR̄_{k}(4t − 2), és

R̄_{k+1}(t) − pR̄_{k+1}(t + s) − (1 − p)R̄_{k+1}(t − s) = (1 − p) [p + pR̄_{k}(4t − 2) − pR̄_{k}(2t + 2s − 1) − pR̄_{k}(2t − 2s)] = p(1 − p) [1 + R̄_{k}(4t − 2) − R̄_{k}(2t + 2s − 1) − R̄_{k}(2t − 2s)]

= p [(1 − 2p) + R̄_{k} (2t − \frac{1}{2}) − (1 − p)R̄_{k}(2t + 2s − 1) − (1 − p)R̄_{k}(2t − 2s)] ,

mivel p+(1−p)R̄_{k−1}(4t−2) = R̄_{k} (2t − \frac{1}{2}). Innen, a c) esethez hasonlóan, ha 2t+2s−1 ≥ 2t − 2s, akkor R̄_{k} (2t − \frac{1}{2}) ≥ pR̄_{k}(2t + 2s − 1) + (1 − p)R̄_{k}(2t − 2s), ahonnan

p [(1 − 2p) + R̄_{k} (2t − \frac{1}{2}) − (1 − p)R̄_{k}(2t + 2s − 1) − (1 − p)R̄_{k}(2t − 2s)]

≥ p [(1 − 2p) − (1 − 2p)R̄_{k}(2t + 2s − 1)] ≥ 0.

A 2t + 2s − 1 ≤ 2t − 2s eset hasonlóan tárgyalható. Innen következik a d) tulajdonság a d.) esetben is.

Az indukciós feltevésből és a (3) formulából azonnal következik, hogy az a) és c) tulajdonságok érvényesek maradnak a k + 1 esetben is. A b) állítás igazolásához elég ellenőrizni azt, hogy R̄_{k+1}(j2^{−k}) = R̄_{k}(j2^{−k}) minden 0 ≤ j ≤ 2^{k} számra. Viszont, ha j2^{−k} ≤ \frac{1}{2}, akkor R̄_{k+1}(j2^{−k}) = pR̄_{k}(j2^{−k+1}), és R̄_{k}(j2^{−k+1}) = pR̄_{k−1}(j2^{−k+1}) = pR̄_{k}(j2^{−k+1}) az indukciós feltevés alapján. Hasonlóan, ha \frac{1}{2} ≤ j2^{−k} ≤ 1, akkor R̄_{k+1}(j2^{−k}) = p + (1 − p)R̄_{k}(j2^{−k+1}) = p + (1 − p)R̄_{k−1}(j2^{−k+1} = R_{k}(j2^{−k}).

Az e.) állítás bizonyítása érdekében vegyük észre, hogy a (k + 1 paraméterre már bizonyított) d.), b.) és a.) tulajdonságok alapján

R̄_{k+1}(j2^{−(k+1)}) ≥ sup_{0≤l≤j l+j páros szám} (pR̄_{k+1}((j + l)2^{−(k+1)}) + (1 − p)R̄_{k+1}((j − l)2^{−(k+1)}))

= sup_{0≤l≤j l+jpáros szám} (pR̄_{k}((j + l)2^{−(k+1)}) + (1 − p)R̄_{k}((j − l)2^{−(k+1)}))

= sup_{0≤s≤j2^{−(k+1)}} (pR̄_{k}(j2^{−(k+1)} + s) + (1 − p)R̄_{k}(j2^{−(k+1)} − s)) ,

ahonnan R̄_{k+1}(j2^{−(k+1)}) ≥ R_{k+1}(j2^{−(k+1)}). (Kihasználtuk azt is, hogy a R̄_{k}(t) függvény konstans minden [u2^{−k}, (u + 1)2^{−k}) alakú intervallumban. Az ellenkező irányú egyenlőtlenség nyílvánvaló, ezért R̄_{k+1}(j2^{−(k+1)}) = R_{k+1}(j2^{−(k+1)}).

Vegyük észre, hogy az indukciós feltétel alapján könnyen látható, hogy nemcsak az R̄_{k+1}(t) hanem az R_{k+1}(t) függvény is konstans minden [u2^{−k}, (u + 1)2^{−k}) alakú intervallumban. (Még nem láttuk be, hogy R̄_{k+1}(t) = R_{k+1}(t).) Ugyanis, az R_{k}(t) = R̄_{k}(t) függvény tulajdonságai alapján elegendő az R_{k+1}(t) függvényt definiáló (2) formula szuprémumában csak olyan s számokat venni, melyekre t − s = j2^{−k} alakú. Ezért, ha t ∈ [u2^{−(k+1)}, (u + 1)2^{−(k+1)}) akkor összehasonlítva azon (s, s̄) párokat, melykre R_{k}(u2^{−(k+1)} − s) = R_{k}(t − s̄) = R_{k}(j2^{−k}), kapjuk, hogy pR_{k}(t + s̄) + (1 − p)R_{k}(t − s̄) = pR_{k}(u2^{−(k+1)} + s) + (1 − p)R_{k}(u2^{−(k+1)} − s), ezért R_{k+1}(t) = R_{k+1}(u2^{−(k+1)}). Az e.) állítás további része innen következik, hiszen mind az R_{k}(t) mind a R̄_{k}(t) függvény konstans a megfelelő intervallumon.

A fenti Tételből következik a merész stratégia optimalítása. Valóban, ebből az eredményből indukcióval következik, hogy ha k lépést tehetünk, akkor a merész stratégia optimális, és nyereményfüggvénye t kiinduló tőke esetén R_{k}(t) = R̄_{k}(t). Ez az állítás ugyanis k = 0 esetén érvényes, és ha k − 1-re igaz, akkor t kiinduló tőke esetén s, 0 ≤ s ≤ t kezdeti tét esetén a siker valószínűsége pR_{k−1}(t + s) + (1 − p)R_{k−1}(t − s). A tétel azt mondja ki, hogy ez a kifejezés 0 ≤ t ≤ \frac{1}{2} esetén s = t pontban, \frac{1}{2} ≤ t ≤ 1 esetén pedig az s = 1 − t pontban veszi fel. Ez azt jelenti, hogy a k lépéses stratégiák közül az optimális stratégia első lépése megegyezik a merész stratégia első lépésével. Indukcióval innen következik, hogy a merész stratégia optimális a k lépéses stratégiák között.

Tekintsünk ezek után egy tetszőleges stratégiát, és jelölje ebben R̂(t) a siker valószínűségét t kiinduló tőke esetén, és R̂_{k}(t) a siker valószínűséget az első k lépés bekövetkeztéig. Legyen továbbá R(t) = lim_{k→∞} R_{k}(t). Ekkor az R(t) függvény adja meg a siker valószínűségét az optimális stratégia esetén, és R̂(t) = lim_{k→∞} R̂_{k}(t) ≤ lim_{k→∞} R_{k}(t) = R(t). Ezt kellett bizonyítanunk.