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 a kaszinóban olyan játékot játszhatunk, 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, mekkora 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, 0 ≤ t ≤ 1. Célunk az, 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+1}(t) = max_{0≤s≤t}{(1 − p)R̄_{k}(t − s) + pR̄_{k}(t + s)}, k ≥ 0.  (2)

Vezessük be ezen kívül az alábbi R_{k}(t), k = 0, 1, 2, …, függvényeket, melyek a merész játék esetén adják meg a siker valószínűségét.

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 \\ 1 & ha t ≥ 1. \end{matrix} ,  k = 0, 1, 2, …  (3)

A feladat megoldásának kulcslépése az alábbi tétel bizonyítása:

Tétel. Tekintsük a (3) formula segítségével definiált R_{k}(t), k = 0, 1, 2, …, t ≥ 0 függvényeket. Ha 0 ≤ p ≤ \frac{1}{2}, akkor az R_{k}(t) függvények monoton növekvőek, és teljesítik az alábbi relációt:

R_{k+1}(t) ≥ sup_{0≤s≤t}[pR_{k}(t + s) + (1 − p)R_{k}(t − s)]
minden k = 0, 1, 2, … és 0 ≤ t ≤ 1 számra.

(4)

Következmény: A (3) formulában definiált R_{k}(t) és az (1) valamint (2) formulában definiált R̄_{k}(t) függvényre teljesül az R_{k}(t) = R̄_{k}(t) azonosság. Ezért abban az esetben, ha legfeljebb k játékot játszhatunk a merész stratégia optimális, és a siker valószínűsége t kiinduló tét esetén R_{k}(t) = R̄_{k}(t). Ha akárhány játékot játszhatunk, akkor is a merész stratégia optimális, a siker valószínűsége pedig t kiinduló tét esetén R(t) = lim_{k→∞} R_{k}(t).

(A fenti határérték létezik.)

A tétel bizonyítása: A Tételt teljes indukcióval bizonyítjuk. A (4) reláció igaz k = 0-ra. Ugyanis R_{1}(t) = 0, ha 0 ≤ t < \frac{1}{2}, R_{1}(t) = p, ha \frac{1}{2} ≤ t < 1, R_{1}(t) = 1, ha t ≥ 1, valamint R_{0}(t) = 0, ha 0 ≤ t < 1, és R_{0}(t) = 1, ha t ≥ 1. Nem nehéz e képletek alapján ellenőrizni a (4) reláció érvényessǵét a k = 0 esetben. Teljes indukcióval könnyű látni azt is, hogy az R_{0}(t) függvénnyel együtt minden R_{k}(t) függvény monoton, és R_{k}(t) = 1, ha t ≥ 1. Innen az is következik, hogy a (4) állítás bizonyításában elég olyan s paraméterekre szorítkozni, melyekre a 0 ≤ s ≤ t feltételen kívül a t + s ≤ 1 feltétel is teljesül.

A (4) relációt 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 és d) 0 ≤ t − s ≤ \frac{1}{2} ≤ t ≤ t + s ≤ 1 esetekben.

Az a) esetben, amikor 0 ≤ t − s ≤ t ≤ t + s ≤ \frac{1}{2},

R_{k+1}(t) − pR_{k}(t + s) − (1 − p)R_{k}(t − s)
= pR_{k}(2t) − p^{2}R_{k−1}(2(t + s)) − p(1 − p)R_{k−1}(2(t − s))
= p (R_{k}(2t) − pR_{k−1}(2t + 2s) − (1 − p)R_{k−1}(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}(t + s) − (1 − p)R_{k}(t − s)

= p + (1 − p)R_{k}(2t − 1) − p^{2} − p(1 − p)R_{k−1}(2(t + s) − 1)

− p(1 − p) − (1 − p)^{2}R_{k−1}(2(t − s) − 1)

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

A c) és d) esetek vizsgálata előtt tegyük a következő észrevételt: Ha 0 ≤ u ≤ \frac{1}{2}, akkor

(1 − p)R_{k}(u) + p^{2} = pR_{k} (u + \frac{1}{2}) .  (5)

Valóban, az (5) azonosság mind a két oldalán álló kifejezés egyenlő a p(1−p)R_{k−1}(2u)+ p^{2} számmal a (3) formula alapján.

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

R_{k+1}(t) − pR_{k}(t + s) − (1 − p)R_{k}(t − s)
= pR_{k}(2t) − p^{2} − p(1 − p)R_{k−1}(2(t + s) − 1) − p(1 − p)R_{k−1}(2(t − s))
= (pR_{k}(2t) − p^{2}) − p(1 − p) [R_{k−1}(2t + 2s − 1) + R_{k−1}(2t − 2s)] .

Vegyük észre, hogy t ≥ \frac{1}{4}, mert 2t ≥ t + s ≥ \frac{1}{2}. Innen az (5) reláció alapján u = 2t − \frac{1}{2} választással pR_{k}(2t) − p^{2} = (1 − p)R_{k} (2t − \frac{1}{2}), ahonnan

R_{k+1}(t) − pR_{k}(t + s) − (1 − p)R_{k}(t − s)

= (1 − p) [R_{k} (2t − \frac{1}{2}) − pR_{k−1}(2t + 2s − 1) − pR_{k−1}(2t − 2s)] .

Most fogjuk kihasználni a p ≤ \frac{1}{2} feltételt. Eszerint, felhasználva, hogy a (4) reláció érvényes k − 1-re az indukciós feltevés alapján kapjuk, hogy

(1 − p) [R_{k} (2t − \frac{1}{2}) − pR_{k−1}(2t + 2s − 1) − pR_{k−1}(2t − 2s)]

≥ (1 − p) [R_{k} (2t − \frac{1}{2}) − pR_{k−1}(2t + 2s − 1) − (1 − p)R_{k−1}(2t − 2s)] ≥ 0,

ha 2t + 2s − 1 ≥ 2t − 2s. A 2t + 2s − 1 ≤ 2t − 2s eset hasonlóan tárgyalható. Innen következik a Tétel á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}(t + s) − (1 − p)R_{k}(t − s)
= p + (1 − p)R_{k}(2t − 1) − p^{2} − p(1 − p)R_{k−1}(2(t + s) − 1))
− p(1 − p)R_{k−1}(2(t − s))
= (1 − p)R_{k}(2t − 1) + (1 − p)p [1 − R_{k−1}(2t + 2s − 1) − R_{k−1}(2t − 2s)] .

Továbbá \frac{3}{4} ≥ t, mert 1 ≥ t + s = 2t − (t − s) ≥ 2t − \frac{1}{2}. Ezért az u = 2t − 1 választással az (5) formula adja, hogy (1 − p)R_{k}(2t − 1) = pR_{k} (2t − \frac{1}{2}) − p^{2} és

R_{k+1}(t) − pR_{k}(t + s) − (1 − p)R_{k}(t − s)

= p [(1 − 2p) + R_{k} (2t − \frac{1}{2}) − (1 − p)R_{k−1}(2t + 2s − 1) − (1 − p)R_{k−1}(2t − 2s)] .

Innen, a c) esethez hasonlóan kapjuk az indukciós feltevés alapján, hogy ha 2t+2s−1 ≥ 2t − 2s, akkor R_{k} (2t − \frac{1}{2}) ≥ pR_{k−1}(2t + 2s − 1) + (1 − p)R_{k−1}(2t − 2s). Ezért

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

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

A 2t + 2s − 1 ≤ 2t − 2s eset hasonlóan tárgyalható. Innen következik a Tétel állítása d) esetben is.

A következmény bizonyítása: Egyszerű k-szerinti indukcióval adódik, hogy R_{k}(t) = R̄_{k}(t), és az R̄_{k}(t) függvényeket definiáló (2) indukciós formulában a szuprémum az s = t esetben éretik el, ha t ≤ \frac{1}{2}, és az s = 1 − t esetben, ha \frac{1}{2} ≤ t ≤ 1. Emiatt az összefüggés miatt a Szindbád és Secretary probléma megoldásában alkalmazott backward indukciós érvelés azt adja, hogy ha k játékot játszhatunk, akkor a merész stratégia optimális, és a siker valószínűsége R̄_{k}(t) = R_{k}(t) t kiinduló tét esetén.

Tekintsünk ezek után egy tetszőleges stratégiát. 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 a merész stratégia esetén, és R̂(t) = lim_{k→∞} R̂_{k}(t) ≤ lim_{k→∞} R_{k}(t) =

R(t), mivel R_{k}(t) = R̄_{k}(t) ≥ R̂_{k}(t). Ez azt jelenti, hogy a merész stratégia optimális.

Végül teszek néhány észrevételt az R_{k}(t), k = 0, 1, 2, … és az R(t) = lim_{k→∞} R_{k}(t) függvény viselkedéséről. A bizonyítások részleteit nem dolgozom ki.

Indukcióval be lehet látni, hogy minden t = j2^{−k} alakú diadikusan racionális pontban R_{k}(j2^{−k}) = R_{l}(j2^{−k}) minden l ≥ k indexre, ezért R(j2^{−k}) = R_{k}(j2^{−k}). Valóban, R_{k}(1) = 1 minden k ≥ 0 számra. Továbbá a (3) formula alapján R_{k}(\frac{1}{2}) = p minden k ≥ 1 számra. A k kitevő szerinti teljes indukcióval látható a (3) formula segítségével, hogy az R_{l}(j2^{−k}) szám ugyanaz a mennyiség minden l ≥ k számra.Továbbá, az R_{k}(t) függvény konstans minden [j2^{−k}, (j +1)2^{−k}) alakú intervallumon. Ugyancsak indukcióval be lehet látni, hogy az R(·) illetve R_{k}(·) függvény differenciahányadosai teljesítik az alábbi azonosságot: 2^{k} [R(j + 1)2^{−k}) − R(j2^{−k})] = [2(1−p)]^{α(j,k)}[2p]^{β(j,k)}, ahol α(j, k)

illetve β(j, k) = k − α(j, k) a j2^{−k} = ∑_{l=1}^{k} ε_{l}2^{−l} szám, ε_{l} = 1 vagy ε_{l} = 0, 1 ≤ l ≤ k,

diadikus “kettedes tört” alakú előállításában szereplő 1-es illetve nulla jegyek száma.

Az utolsó összefüggés segítségével be lehet látni, hogy az R(t) függvény szigorúan folytonos monoton függvény, amelyik szinguláris 0 ≤ p < \frac{1}{2} paraméter esetén, azaz ebben az esetben az R(·) függvény deriváltja majdnem minden pontban zéró. Ez utóbbi állítás bizonyításához azt az észrevételt kell tennünk, hogy majdnem minden t, 0 ≤ t ≤ 1, szám diadikus előállításában az 1-es jegyek relativ gyakorisága \frac{1}{2}. Ekkor nagy k számra egy tipikus t ∈ [0, 1] pontra véve azt a [j2^{−k}, (j + 1)2^{−k}) intervallumot, melyre t ∈ [j2^{−k}, (j + 1)2^{−k}), kapjuk, hogy a megfelelő differenciahányadosok logaritmusának a normalizáltja az alábbi módon viselkedik:

\frac{1}{k} log (2^{k} [R(j + 1)2^{−k}) − R(j2^{−k})]) = \frac{α(j, k)}{k} log(2(1 − p)) + \frac{β(j, k)}{k} log(2p)

∼ \frac{1}{2} log(4p(1 − p)) < 0, ha 0 ≤ p < \frac{1}{2}.

Ez azt jelenti, hogy lim_{k→∞} log (2^{k} [R(j + 1)2^{−k}) − R(j2^{−k})]) = −∞, azaz

lim_{k→∞} 2^{k} [R(j + 1)2^{−k}) − R(j2^{−k})] = 0 a megfelelő differenciahányadosokra.