\magnification=\magstep1
\input amstex
\hsize=16truecm
 
\parskip=2pt plus 1pt
\define\A{{\bold A}}
\define\BB{{\bold B}}
\define\DD{{\bold D}}
\define\T{{\bold T}}
\define\U{{\bold U}}
\define\({\left(}
\define\){\right)}
\define\[{\left[}
\define\]{\right]}
\define\e{\varepsilon}
\define\oo{\omega}
\define\const{\text{\rm const.}\,}
\define\supp {\sup\limits}
\define\inff{\inf\limits}
\define\summ{\sum\limits}
\define\prodd{\prod\limits}
\define\limm{\lim\limits}
\define\limsupp{\limsup\limits}
\define\liminff{\liminf\limits}
\define\bigcapp{\bigcap\limits}
\define\bigcupp{\bigcup\limits}
\define\Var{\text{\rm Var}\,}
 
\TagsOnRight
 
\centerline{\bf A mer\'esz j\'at\'ekok strat\'egi\'aja}
\medskip
A k\"ovetkez\H{o} probl\'em\'aval foglalkozunk: Tegy\"uk fel, hogy
felt\'etlen\"ul ki kell fizetn\"unk 1000 forintos ad\'oss\'agunkat,
de csak 600 forintunk van. Egyetlen lehet\H{o}s\'eg\"unk, hogy a m\'eg
sz\"uks\'eges 400 forintot megszerezz\"uk az, hogy egy kaszin\'oba
megy\"unk, ott j\'atszunk, \'es a sz\"uks\'eges p\'enzt megnyerj\"uk.
Minden egyes j\'at\'ek sor\'an mi d\"onthetj\"uk el, hogy mekkora
t\'etet tesz\"unk fel. Tegy\"uk fel, hogy a kaszin\'oban olyan
j\'at\'ekot j\'atszhatunk, melyben a feltett t\'etet 0.49
val\'osz\'{\i}n\H{u}s\'eggel megdupl\'azzuk, 0.51
val\'osz\'{\i}n\H{u}s\'eggel pedig elvesz\'{\i}tj\"uk. K\'erd\'es,
hogyan \'erdemes j\'atszani, mekkora t\'eteket \'erdemes feltenni.
Be\-l\'at\-juk, hogy az \'ugynevezett mer\'esz j\'at\'ekok m\'odszere
optim\'alis strat\'egia. Ez azt jelenti, hogy minden l\'ep\'esben
vagy a teljes vagyonunkat tessz\"uk fel, (ezt tessz\"uk abban az
esetben, ha a pillanatnyi vagyonunk kisebb mint a sz\"uks\'eges
1000 forint fele), vagy pedig pont annyi t\'etet tesz\"unk fel, ami
nyeres\'eg eset\'en biztos\'{\i}tja a sz\"uks\'eges 1000 forint
megszerz\'es\'et a k\"ovetkez\H{o} l\'ep\'esben. \medskip\noindent
{\bf Az \'all\'{\i}t\'as bizony\'{\i}t\'asa:}
\medskip
 
A vizsg\'alatban hasonl\'o m\'odszert k\"ovet\"unk, mint a Szindb\'ad
probl\'ema \'es a secretary probl\'ema megold\'as\'aban. Az
eml\'{\i}tett feladatokban az \'ugynevezett backward induction
seg\'{\i}ts\'eg\'evel kisz\'amoltuk mi az optim\'alis
strat\'egia \'es az optim\'alis eredm\'eny abban az esetben, ha csak
az utols\'o $k$ l\'ep\'esben \'allhatunk meg, $k=0,1,2,\dots$.
Te\-kint\-s\"uk azt a j\'at\'ekot, melyben a j\'at\'ek minden
l\'ep\'es\'eben a feltetett t\'etet megdupl\'azzuk $p$,
$0\le p<\frac12$, val\'osz\'{\i}n\H{u}s\'eggel, \'es elvesz\'{\i}tj\"uk
$1-p$ val\'osz\'{\i}n\H{u}s\'eggel. A kezdeti id\H{o}pontban a
sz\"uks\'eges \"osszeg $t$-szeres\'evel rendelkez\"unk, $0\le t\le1$.
C\'elunk az, hogy min\'el nagyobb va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'eg\-gel
megszerezz\"uk a sz\"uks\'eges \"osszeget.
 
Bel\'atjuk indukci\'oval, hogy amennyiben csak $k$ l\'ep\'esben
j\'atszhatunk, $k=0,1,2,\dots$, akkor a mer\'esz strat\'egia
optim\'alis. Ennek \'erdek\'eben tekintj\"uk azt az $\bar R_k(t)$
f\"uggv\'enyt, $t\ge 0$, $k=0,1,2,\dots$, amelyik azt fejezi ki,
hogy ha legfeljebb $k$ j\'at\'ekot j\'atszhatunk, \'es a kezdeti
l\'ep\'es el\H{o}tt a sz\"uks\'eges \"osszeg $t$-szeres\'evel
rendelkez\"unk, akkor mi a val\'osz\'{\i}n\H{u}s\'ege annak, hogy
optim\'alis strat\'egia eset\'en megnyerj\"uk a sz\"uks\'eges
\"osszeget. Ezeknek a f\"uggv\'enyeknek bel\'atjuk bizonyos
tulajdons\'agait, melyek lehet\H{o}v\'e teszik az \'all\'{\i}t\'as
bizony\'{\i}t\'as\'at. Vegy\"uk \'eszre, hogy
$$
\bar R_0(t)=\left\{ \aligned
0&\quad\text{ha }0\le t<1,\\
1&\quad\text{ha } t\ge1.
\endaligned \right.  \tag1
$$
\'es
$$
\bar R_{k+1}(t)=\max_{0\le s\le
t}\{(1-p)\bar R_k(t-s)+p\bar R_k(t+s)\},\quad k\ge0. \tag2
$$
Vezess\"uk be ezen k\'{\i}v\"ul az al\'abbi $R_k(t)$,
$k=0,1,2,\dots$, f\"uggv\'enyeket, melyek a mer\'esz j\'at\'ek
eset\'en adj\'ak meg a siker val\'osz\'{\i}n\H{u}s\'eg\'et.
$$ \allowdisplaybreaks
\align
R_0(t)& =\bar R_0(t)\\
R_{k+1}(t)&=\left\{ \aligned
p R_k(2t)&\quad\text{ha }0\le t\le \frac12\\
p+(1-p)R_k(2t-1)&\quad\text{ha }\frac12\le t\le 1\\
1&\quad\text{ha }t\ge1.
\endaligned \right.,\qquad k=0,1,2,\dots \tag3
\endalign
$$
 
A feladat megold\'as\'anak kulcsl\'ep\'ese az al\'abbi t\'etel
bizony\'{\i}t\'asa: \medskip\noindent
{\bf T\'etel.} {\it Tekints\"uk a (3) formula seg\'{\i}ts\'eg\'evel
defini\'alt $R_k(t)$, $k=0,1,2,\dots$, $t\ge0$ f\"uggv\'enyeket. Ha
$0\le p\le\frac12$, akkor az $R_k(t)$ f\"uggv\'enyek monoton
n\"ovekv\H{o}ek, \'es teljes\'{\i}tik az al\'abbi rel\'aci\'ot:
$$
\aligned
R_{k+1}(t)&\ge\supp_{0\le s\le t} [pR_k(t+s)+(1-p)R_k(t-s)] \\
&\qquad \text{minden } k=0,1,2,\dots \text { \'es } 0\le t\le 1
\text{ sz\'amra.}
\endaligned \tag4
$$
}\medskip\noindent
{\bf K\"ovetkezm\'eny:} {\it A (3) formul\'aban defini\'alt $R_k(t)$
\'es az (1) valamint (2) formul\'aban defini\'alt $\bar R_k(t)$
f\"uggv\'enyre teljes\"ul az $R_k(t)=\bar R_k(t)$ azonoss\'ag.
Ez\'ert abban az esetben, ha legfeljebb $k$ j\'at\'ekot j\'atszhatunk
a mer\'esz strat\'egia optim\'alis, \'es a siker
val\'osz\'{\i}n\H{u}s\'ege $t$ kiindul\'o t\'et eset\'en $R_k(t)=\bar
R_k(t)$. Ha ak\'arh\'any j\'at\'ekot j\'atszhatunk, akkor is a
mer\'esz strat\'egia optim\'alis, a siker val\'osz\'{\i}n\H{u}s\'ege
pedig $t$ kiindul\'o t\'et eset\'en $R(t)=\limm_{k\to\infty} R_k(t)$.
(A fenti hat\'ar\'ert\'ek l\'etezik.)}
\medskip\noindent
{\it A t\'etel bizony\'{\i}t\'asa:}\/
A T\'etelt teljes indukci\'oval bizony\'{\i}tjuk. A (4) rel\'aci\'o
igaz $k=0$-ra. Ugyanis $R_1(t)=0$, ha $0\le t<\frac12$, $R_1(t)=p$,
ha $\frac12\le t<1$, $R_1(t)=1$, ha $t\ge1$, valamint $R_0(t)=0$,
ha $0\le t<1$, \'es $R_0(t)=1$, ha $t\ge1$. Nem neh\'ez e k\'epletek
alapj\'an ellen\H{o}rizni a (4) rel\'aci\'o \'erv\'enyess\'g\'et a
$k=0$ esetben. Teljes indukci\'oval k\"onny\H{u} l\'atni azt is, hogy
az $R_0(t)$ f\"uggv\'ennyel egy\"utt minden $R_k(t)$ f\"uggv\'eny
monoton, \'es $R_k(t)=1$, ha $t\ge1$. Innen az is k\"ovetkezik, hogy
a (4) \'all\'{\i}t\'as bizony\'{\i}t\'as\'aban el\'eg olyan $s$
param\'eterekre szor\'{\i}tkozni, melyekre a $0\le s\le t$
felt\'etelen k\'{\i}v\"ul a $t+s\le1$ felt\'etel is teljes\"ul.
 
A (4) rel\'aci\'ot k\"ul\"on l\'atjuk be az a) $0\le
t+s\le\frac12$, b) $\frac12\le t-s\le1$, c) $0\le t-s\le t\le
\frac12\le t+s\le1$ \'es d) $0\le t-s\le \frac12\le t\le t+s\le1$
esetekben.
 
Az a) esetben, amikor $0\le t-s\le t\le t+s\le \frac12$,
$$
\align
&R_{k+1}(t)-p R_k(t+s)-(1-p) R_k(t-s)\\
&\qquad=p R_k(2t)-p^2 R_{k-1}(2(t+s))-p(1-p) R_{k-1}(2(t-s))\\
&\qquad=p\( R_k(2t)-p R_{k-1}(2t+2s)-(1-p) R_{k-1}(2t-2s)\)\ge0
\endalign
$$
az indukci\'os feltev\'es alapj\'an.
 
A b) esetben, amikor $\frac12\le t-s\le t\le t+s\le 1$
$$
\align
& R_{k+1}(t)-p R_k(t+s)-(1-p) R_k(t-s)\\
&\qquad=p+(1-p) R_k(2t-1)-p^2-p(1-p) R_{k-1}(2(t+s)-1)\\
&\qquad\qquad -p(1-p)-(1-p)^2 R_{k-1}(2(t-s)-1)\\
&\qquad=(1-p)\(R_k(2t-1)-p R_{k-1}(2t-1+2s)-(1-p)
R_{k-1}(2t-1-2s)\)\ge0.
\endalign
$$
 
A c) \'es d) esetek vizsg\'alata el\H{o}tt tegy\"uk a k\"ovetkez\H{o}
\'eszrev\'etelt: Ha $0\le u\le \frac12$, akkor
$$
(1-p)R_k(u)+p^2=pR_k\(u+\frac12\). \tag5
$$
Val\'oban, az (5) azonoss\'ag mind a k\'et oldal\'an \'all\'o
kifejez\'es egyenl\H{o} a $p(1-p)R_{k-1}(2u)+p^2$ sz\'ammal a (3)
formula alapj\'an.
 
A c) esetben, amikor $0\le t-s\le t\le \frac12\le t+s\le1$
$$
\align
&R_{k+1}(t)-p R_k(t+s)-(1-p) R_k(t-s)\\
&\qquad=p R_k(2t)-p^2-p(1-p) R_{k-1}(2(t+s)-1)
-p(1-p) R_{k-1}(2(t-s))\\
&\qquad=(p R_k(2t)-p^2)-p(1-p)\[R_{k-1}(2t+2s-1)
+R_{k-1}(2t-2s)\].
\endalign
$$
Vegy\"uk \'eszre, hogy $t\ge \frac14$, mert $2t\ge t+s\ge\frac12$.
Innen az (5) rel\'aci\'o alapj\'an $u=2t-\frac12$ v\'alaszt\'assal
$pR_k(2t)-p^2=(1-p)R_k\(2t-\frac12\)$, ahonnan
$$
\align
&R_{k+1}(t)-pR_k(t+s)-(1-p)R_k(t-s)\\
&\qquad=(1-p)\[R_k\(2t-\frac12\)-pR_{k-1}(2t+2s-1)
-pR_{k-1}(2t-2s)\].
\endalign
$$
Most fogjuk kihaszn\'alni a $p\le\frac12$ felt\'etelt. Eszerint,
felhaszn\'alva, hogy a (4) rel\'aci\'o \'erv\'enyes $k-1$-re az
indukci\'os feltev\'es alapj\'an kapjuk, hogy
$$
\align
&(1-p)\[R_k\(2t-\frac12\)-p R_{k-1}(2t+2s-1)
-pR_{k-1}(2t-2s)\] \\
&\qquad \ge (1-p)\[ R_k\(2t-\frac12\)-p R_{k-1}(2t+2s-1)
-(1-p) R_{k-1}(2t-2s)\]\ge0,
\endalign
$$
ha $2t+2s-1\ge 2t-2s$. A $2t+2s-1\le 2t-2s$ eset hasonl\'oan
t\'argyalhat\'o. Innen k\"ovetkezik a T\'etel \'all\'{\i}t\'asa a c)
esetben is.
 
A d) esetben, amikor $0\le t-s\le \frac12\le t\le t+s\le1$
$$
\align
& R_{k+1}(t)-p R_k(t+s)-(1-p) R_k(t-s)\\
&\qquad=p+(1-p) R_k(2t-1)-p^2-p(1-p) R_{k-1}(2(t+s)-1)) \\
&\qquad\qquad -p(1-p) R_{k-1}(2(t-s))\\
&\qquad=(1-p)R_k(2t-1)+ (1-p)p\[1- R_{k-1}(2t+2s-1)
-R_{k-1}(2t-2s)\].
\endalign
$$
Tov\'abb\'a $\frac34\ge t$, mert $1\ge t+s=2t-(t-s)\ge 2t-\frac12$.
Ez\'ert az $u=2t-1$ v\'alaszt\'assal az (5) formula adja, hogy
$(1-p)R_k(2t-1)=pR_k\(2t-\frac12\)-p^2$ \'es
$$
\align
&R_{k+1}(t)-p R_k(t+s)-(1-p) R_k(t-s)\\
&\quad=p\[(1-2p)+ R_k\(2t-\frac12\)-(1-p) R_{k-1}(2t+2s-1)
-(1-p)R_{k-1}(2t-2s)\].
\endalign
$$
Innen, a c) esethez hasonl\'oan kapjuk az indukci\'os feltev\'es
alapj\'an, hogy ha $2t+2s-1\ge 2t-2s$, akkor $R_k\(2t-\frac12\)\ge
p R_{k-1}(2t+2s-1)+(1-p) R_{k-1}(2t-2s)$. Ez\'ert
$$
\align
&p\[(1-2p)+ R_k\(2t-\frac12\)-(1-p) R_{k-1}(2t+2s-1)
-(1-p) R_{k-1}(2t-2s)\]\\
&\qquad\ge p\[(1-2p)-(1-2p) R_{k-1}(2t+2s-1)\]\ge0.
\endalign
$$
A $2t+2s-1\le 2t-2s$ eset hasonl\'oan t\'argyalhat\'o. Innen
k\"ovetkezik a T\'etel \'all\'{\i}t\'asa d) esetben is.
\medskip\noindent
{\it A k\"ovetkezm\'eny bizony\'{\i}t\'asa:}\/ Egyszer\H{u}
$k$-szerinti indukci\'oval ad\'odik, hogy $R_k(t)=\bar R_k(t)$, \'es
az $\bar R_k(t)$ f\"uggv\'enyeket defini\'al\'o (2) indukci\'os
formul\'aban a szupr\'emum az $s=t$ esetben \'eretik el, ha
$t\le\frac12$, \'es az $s=1-t$ esetben, ha $\frac12\le t\le1$.
Emiatt az \"osszef\"ugg\'es miatt a Szindb\'ad \'es Secretary
probl\'ema megold\'as\'aban alkalmazott backward indukci\'os
\'ervel\'es azt adja, hogy ha $k$ j\'at\'ekot j\'atszhatunk, akkor
a mer\'esz strat\'egia optim\'alis, \'es a siker
val\'osz\'{\i}n\H{u}s\'ege $\bar R_k(t)=R_k(t)$ $t$ kiindul\'o
t\'et eset\'en.
 
Tekints\"unk ezek ut\'an egy tetsz\H{o}leges strat\'egi\'at.
Jel\"olje ebben $\hat R(t)$ a siker
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\'et
$t$ kiindul\'o t\H{o}ke eset\'en, \'es $\hat R_k(t)$ a siker
val\'osz\'{\i}n\H{u}s\'eget az els\H{o} $k$ l\'ep\'es
bek\"ovetkezt\'eig. Legyen tov\'abb\'a $R(t)=\limm_{k\to\infty}R_k(t)$.
Ekkor az $R(t)$ f\"uggv\'eny adja meg a siker
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\'et a mer\'esz strat\'egia
eset\'en, \'es $\hat R(t)=\limm_{k\to\infty} \hat R_k(t)\le
\limm_{k\to\infty} R_k(t)=R(t)$, mivel $R_k(t)=\bar R_k(t)\ge \hat
R_k(t)$. Ez azt jelenti, hogy a mer\'esz strat\'egia optim\'alis.
\smallskip
 
V\'eg\"ul teszek n\'eh\'any \'eszrev\'etelt az $R_k(t)$,
$k=0,1,2,\dots$ \'es az $R(t)=\limm_{k\to\infty}R_k(t)$ f\"uggv\'eny
viselked\'es\'er\H{o}l. A bizony\'{\i}t\'asok r\'eszleteit nem dolgozom
ki.
 
Indukci\'oval be lehet l\'atni, hogy minden $t=j2^{-k}$ alak\'u
diadikusan racion\'alis pontban $R_k(j2^{-k})=R_l(j2^{-k})$ minden
$l\ge k$ indexre, ez\'ert $R(j2^{-k})=R_k(j2^{-k})$. Val\'oban,
$R_k(1)=1$ minden $k\ge0$ sz\'amra. Tov\'abb\'a a (3) formula alapj\'an
$R_k(\frac12)=p$ minden $k\ge1$ sz\'amra.  A $k$ kitev\H{o} szerinti
teljes indukci\'oval l\'athat\'o a (3) formula seg\'{\i}ts\'eg\'evel,
hogy az $R_l(j2^{-k})$ sz\'am ugyanaz a mennyis\'eg minden $l\ge k$
sz\'amra.Tov\'abb\'a, az $R_k(t)$ f\"uggv\'eny konstans minden
$[j2^{-k},(j+1)2^{-k})$ alak\'u intervallumon. Ugyancsak
in\-duk\-ci\'o\-val be lehet l\'atni, hogy az $R(\cdot)$ illetve
$R_k(\cdot)$ f\"uggv\'eny differenciah\'anyadosai
teljes\'{\i}tik az al\'abbi azonoss\'agot:
$2^k\[R(j+1)2^{-k})-R(j2^{-k})\]
=[2(1-p)]^{\alpha(j,k)}[2p]^{\beta(j,k)}$,
ahol $\alpha(j,k)$ illetve $\beta(j,k)=k-\alpha(j,k)$ a
$j2^{-k}=\summ_{l=1}^{k}\e_l2^{-l}$ sz\'am, $\e_l=1$ vagy $\e_l=0$,
$1\le l\le k$, diadikus ``kettedes t\"ort" alak\'u
el\H{o}\'all\'{\i}t\'as\'aban szerepl\H{o} 1-es illetve nulla
jegyek sz\'ama.
 
Az utols\'o \"osszef\"ugg\'es seg\'{\i}ts\'eg\'evel be lehet l\'atni,
hogy az $R(t)$ f\"uggv\'eny szigor\'uan folytonos monoton f\"uggv\'eny,
amelyik szingul\'aris $0\le p<\frac12$ param\'eter eset\'en, azaz
ebben az esetben az $R(\cdot)$ f\"uggv\'eny deriv\'altja majdnem
minden pontban z\'er\'o. Ez ut\'obbi \'all\'{\i}t\'as
bizony\'{\i}t\'as\'ahoz azt az \'eszrev\'etelt kell
tenn\"unk, hogy majdnem minden $t$, $0\le t\le1$, sz\'am diadikus
el\H{o}\-\'al\-l\'{\i}\-t\'a\-s\'a\-ban az 1-es jegyek relativ
gyakoris\'aga $\frac12$. Ekkor nagy $k$ sz\'amra egy tipikus
$t\in[0,1]$ pontra v\'eve azt a $[j2^{-k},(j+1)2^{-k})$ intervallumot,
melyre $t\in [j2^{-k},(j+1)2^{-k})$, kapjuk, hogy a megfelel\H{o}
differenciah\'anyadosok logaritmus\'anak a normaliz\'altja az al\'abbi
m\'odon viselkedik:
$$
\align
\dfrac1k\log \(2^k\[R(j+1)2^{-k})-R(j2^{-k})\]\)
&=\dfrac{\alpha(j,k)}k\log(2(1-p))+
\dfrac{\beta(j,k)}k\log (2p)\\
&\sim\dfrac12\log(4p(1-p))<0, \quad\text{ha } 0\le p<\dfrac12.
\endalign
$$
Ez azt jelenti, hogy
$\limm_{k\to\infty}\log \(2^k\[R(j+1)2^{-k})-R(j2^{-k})\]\)=-\infty$,
azaz
$$
\limm_{k\to\infty}2^k\[R(j+1)2^{-k})-R(j2^{-k})\]=0
\quad \text{a megfelel\H{o} differenciah\'anyadosokra.}
$$
 
 
\bye
 
