\magnification=\magstep1
\input amstex
\hsize=16truecm
 
\parskip=3pt 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 egy olyan j\'at\'ekot
j\'atszhatunk a kaszin\'oban, 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, milyen t\'eteket \'erdemes feltenni.
Bel\'atjuk, 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.
C\'elunk, hogy min\'el nagyobb val\'osz\'{\i}n\H{u}s\'eggel
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 $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
$$
R_0(t)=\left\{ \aligned
0&\quad\text{ha }0\le t<1,\\
1&\quad\text{ha } t\ge1.
\endaligned \right. \tag1
$$
\'es
$$
R_k(t)=\max_{0\le s\le t}\{(1-p)R_{k-1}(t-s)+pR_{k-1}(t+s)\},\quad
k\ge1. \tag2
$$
Vezess\"uk be ezen k\'{\i}v\"ul az al\'abbi $\bar R_k(t)$,
$k=0,1,2,\dots$, f\"uggv\'enyeket, melyek mint l\'atni fogjuk szoros
kapcsolatban vannak az el\H{o}bbi $R_k(t)$ f\"uggv\'enyekkel.
$$
\aligned
\bar R_0(t)& =R_0(t)\\
\bar R_{k+1}(t)&=\left\{ \aligned
p\bar R_k(2t)&\quad\text{ha }0\le t\le \frac12\\
p+(1-p)\bar R_k(2t-1)&\quad\text{ha }\frac12\le t\le 1
\endaligned \right.
\endaligned\tag3
$$
 
Annak \'erdek\'eben, hogy a feladatot megoldjuk, meg kell
\'erten\"unk az indukci\'os m\'odon defini\'alt $\bar R_k(t)$
f\"uggv\'enyek n\'eh\'any tulajdons\'ag\'at. El\H{o}sz\"or
fogalmazzuk meg e f\"ugg\-v\'e\-nyek al\'abbi egyszer\H{u}, de fontos
tulajdons\'ag\'at. \medskip\noindent
{\bf T\'etel.} {\it A (3) formul\'aval defini\'alt $\bar R_k(t)$,
$k=0,1,2,\dots$, f\"uggv\'enyeknek megvan az al\'abbi tulajdons\'aguk,
ha $0\le p\le\dfrac12$.
\medskip
\item{a.)} Az $\bar R_k(t)$ f\"uggv\'eny konstans minden
$(j-1)2^{-k}\le t<j2^{-k}$, $1\le j\le 2^k$ intervallumban.
\item{b.)} Ha $l_0\ge k_0$ akkor $\bar R_{l_0}(j2^{-k_0})=\bar
R_{k_0}(j2^{-k_0})$ minden $0\le j\le 2^{k_0}$ indexre.
\item{c.)} Az $\bar R_k(t)$ f\"uggv\'eny monoton n\H{o} a $t$
v\'altoz\'oban minden $k\ge0$ sz\'amra.
\item{d.)} Ha $t=u2^{-k}$, $s=v2^{-k}$, $0\le u\le v$ eg\'esz
sz\'amok, akkor
$$
\bar R_k(t)\ge p \bar R_k(t+s)+(1-p)\bar R_k(t-s).
$$
\item{e.)} $\bar R_k(t)=R_k(t)$, ha $t=j2^{-k}$, $0\le j\le 2^{k}$,
ahol az $R_k(t)$ f\"uggv\'enyt az (1) \'es (2) formula defini\'alja.
S\H{o}t $\bar R_k(t)=R_k(t)$ minden $0\le t\le1$
sz\'amra.}\medskip\noindent
{\it Bizony\'{\i}t\'as:}\/ A T\'etel \'all\'{\i}t\'as\'at teljes
indukci\'oval bizony\'{\i}tjuk. Az \'all\'{\i}t\'as igaz $k=0$-ra.
Ugyancsak k\"onny\H{u} ellen\H{o}rizni az \'all\'{\i}t\'as
helyess\'eg\'et a $k=1$ esetben. Tegy\"uk fel, hogy az igaz $k$-ra,
\'es l\'assuk be $k+1$-re. (A b.) \'all\'{\i}t\'as \'ugy \'ertend\H{o}
a $k$-ik idukci\'os l\'ep\'esben, hogy az \'erv\'enyes minden $0\le
k_0\le l_0\le k$, $0\le j\le 2^{k_0}$, sz\'amp\'arra. A T\'etel
legtartalmasabb r\'esze a d.) pont,
\'es ennek bizony\'{\i}t\'asa ig\'enyli a legt\"obb munk\'at. A
bizony\'{\i}t\'ast ezzel a ponttal kezdj\"uk. \medskip\noindent
{\it A d.) pont (indukci\'os) bizony\'{\i}t\'asa:}\/
 A d.) \'all\'{\i}t\'ast 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$ d) $0\le t-s\le \frac12\le t\le t+s\le1$ esetekben.
 
Az a) esetben, (amikor $t=u2^{-(k+1)}$  $s=v2^{-(k+1)}$, $0\le u\le
v)$,
$$
\align
&\bar R_{k+1}(t)-p\bar R_{k+1}(t+s)-(1-p)\bar R_{k+1}(t-s)\\
&\qquad=p\bar R_k(2t)-p^2\bar R_k(2(t+s))-p(1-p)\bar R_k(2(t-s))\\
&\qquad=p\(\bar R_k(2t)-p \bar R_k(2t+2s)-(1-p)\bar R_k(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
&\bar R_{k+1}(t)-p\bar R_{k+1}(t+s)-(1-p)\bar R_{k+1}(t-s)\\
&\qquad=p+(1-p)\bar R_k(2t-1)-p^2-p(1-p)\bar R_k(2(t+s)-1)\\
&\qquad\qquad -p(1-p)-(1-p)^2\bar R_k(2(t-s)-1)\\
&\qquad=(1-p)\(\bar R_k(2t-1)-p \bar R_k(2t-1+2s)-(1-p)\bar
R_k(2t-1-2s)\)\ge0.
\endalign
$$
 
A c) esetben, amikor $0\le t-s\le t\le \frac12\le t+s\le1$
$$
\align
&\bar R_{k+1}(t)-p\bar R_{k+1}(t+s)-(1-p)\bar R_{k+1}(t-s)\\
&\qquad=p\bar R_k(2t)-p^2-p(1-p)\bar R_k(2(t+s)-1)
-p(1-p)\bar R_k(2(t-s))\\
&\qquad=p\[\bar R_k(2t)-p-(1-p)\bar R_k(2t+2s-1)
-(1-p)\bar R_k(2t-2s)\].
\endalign
$$
Vegy\"uk \'eszre, hogy $t\ge \frac14$, mert $2t\ge t+s\ge\frac12$.
Innen
$$
\align
&\bar R_{k+1}(t)-p\bar R_{k+1}(t+s)-(1-p)\bar R_{k+1}(t-s)\\
&\qquad=p\[p+(1-p)\bar R_k(4t-1)-p-(1-p)\bar R_k(2t+2s-1)
-(1-p)\bar R_k(2t-2s)\]\\
&\qquad=p(1-p)\[\bar R_k(4t-1)-\bar R_k(2t+2s-1)
-\bar R_k(2t-2s)\]\\
&\qquad=(1-p)\[\bar R_k\(2t-\frac12\)-p\bar R_k(2t+2s-1)
-p\bar R_k(2t-2s)\].
\endalign
$$
Most fogjuk kihaszn\'alni a $p\le\frac12$ felt\'etelt. Eszerint,
$$
\align
&(1-p)\[\bar R_k\(2t-\frac12\)-p\bar R_k(2t+2s-1)
-p\bar R_k(2t-2s)\] \\
&\qquad \ge (1-p)\[\bar R_k\(2t-\frac12\)-p\bar R_k(2t+2s-1)
-(1-p)p\bar R_k(2t-2s)\]\ge0,
\endalign
$$
ha $2t+2s-1\ge 2t-2s$, \'es a $2t+2s-1\le 2t-2s$ eset hasonl\'oan
t\'argyalhat\'o. Innen k\"ovetkezik a d.) pont \'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
&\bar R_{k+1}(t)-p\bar R_{k+1}(t+s)-(1-p)\bar R_{k+1}(t-s)\\
&\qquad=p+(1-p)\bar R_k(2t-1)-p^2-p(1-p)\bar R_k(2(t+s)-1))
-p(1-p)\bar R_k(2(t-s))\\
&\qquad=(1-p)\[p+\bar R_k(2t-1)-p\bar R_k(2t+2s-1)
-p\bar R_k(2t-2s)\].
\endalign
$$
Tov\'abb\'a $\frac34\ge t$, mert $1\ge t+s=2t-(t-s)\ge 2t-\frac12$.
Ez\'ert $0\le 2t-1\le \frac12$, $\bar R_k(2t-1)=p\bar R_k(4t-2)$, \'es
$$
\align
&\bar R_{k+1}(t)-p\bar R_{k+1}(t+s)-(1-p)\bar R_{k+1}(t-s)\\
&\qquad=(1-p)\[p+p\bar R_k(4t-2)-p\bar R_k(2t+2s-1)
-p\bar R_k(2t-2s)\]\\
&\qquad=p(1-p)\[1+\bar R_k(4t-2)-\bar R_k(2t+2s-1)
-\bar R_k(2t-2s)\]\\
&\qquad=p\[(1-2p)+\bar R_k\(2t-\frac12\)-(1-p)\bar R_k(2t+2s-1)
-(1-p)\bar R_k(2t-2s)\],
\endalign
$$
mivel $p+(1-p)\bar R_{k-1}(4t-2)=\bar R_k\(2t-\frac12\)$. Innen,
a c) esethez hasonl\'oan, ha $2t+2s-1\ge 2t-2s$, akkor $\bar
R_k\(2t-\frac12\)\ge p\bar R_k(2t+2s-1)+(1-p)\bar R_k(2t-2s)$,
ahonnan
$$
\align
&p\[(1-2p)+\bar R_k\(2t-\frac12\)-(1-p)\bar R_k(2t+2s-1)
-(1-p)\bar R_k(2t-2s)\]\\
&\qquad\ge p\[(1-2p)-(1-2p)\bar R_k(2t+2s-1)\]\ge0.
\endalign
$$
A $2t+2s-1\le 2t-2s$ eset hasonl\'oan t\'argyalhat\'o. Innen
k\"ovetkezik a d) tulajdons\'ag a d.) esetben is.
 
Az indukci\'os feltev\'esb\H{o}l \'es a (3) formul\'ab\'ol azonnal
k\"ovetkezik, hogy az a) \'es c) tulajdons\'agok \'erv\'enyesek
maradnak a $k+1$ esetben is. A b) \'all\'{\i}t\'as igazol\'as\'ahoz
el\'eg ellen\H{o}rizni azt, hogy $\bar R_{k+1}(j2^{-k})=
\bar R_{k}(j2^{-k})$ minden $0\le j\le 2^k$ sz\'amra. Viszont, ha
$j2^{-k}\le\frac12$, akkor $\bar R_{k+1}(j2^{-k})=p\bar R_k(j2^{-k+1})$,
\'es $\bar R_k(j2^{-k+1})=p\bar R_{k-1}(j2^{-k+1})= p\bar
R_k(j2^{-k+1})$
az indukci\'os feltev\'es alapj\'an. Hasonl\'oan, ha $\frac12\le
j2^{-k}\le1$, akkor $\bar R_{k+1}(j2^{-k})=p+(1-p)\bar R_k(j2^{-k+1})=
p+(1-p)\bar R_{k-1}(j2^{-k+1}=R_k(j2^{-k})$.
 
Az e.) \'all\'{\i}t\'as bizony\'{\i}t\'asa \'erdek\'eben vegy\"uk
\'eszre, hogy a ($k+1$ param\'eterre m\'ar bizony\'{\i}tott) d.), b.)
\'es a.) tulajdons\'agok alapj\'an
$$
\align
\bar R_{k+1}(j2^{-(k+1)})&\ge\supp\Sb 0\le l\le j\\ l+j\text{ p\'aros
sz\'am} \endSb \(p\bar R_{k+1}((j+l)2^{-(k+1)})+
(1-p)\bar R_{k+1}((j-l)2^{-(k+1)})\)\\
&=\supp\Sb 0\le l\le j \\ l+j\text {p\'aros sz\'am}\endSb
\(p\bar R_k((j+l)2^{-(k+1)})+ (1-p)\bar R_k((j-l)2^{-(k+1)})\) \\
&=\supp_{0\le s\le j2^{-(k+1)}}
\(p\bar R_k(j2^{-(k+1)}+s)+(1-p)\bar R_k(j2^{-(k+1)}-s)\),
\endalign
$$
ahonnan $\bar R_{k+1}(j2^{-(k+1)})\ge R_{k+1}(j2^{-(k+1)})$.
(Kihaszn\'altuk azt is, hogy a $\bar R_k(t)$ f\"ugg\-v\'eny konstans
minden $[u2^{-k},(u+1)2^{-k})$ alak\'u intervallumban. Az ellenkez\H{o}
ir\'a\-ny\'u egyen\-l\H{o}t\-len\-s\'eg ny\'{\i}lv\'anval\'o, ez\'ert
$\bar R_{k+1}(j2^{-(k+1)})= R_{k+1}(j2^{-(k+1)})$.
 
Vegy\"uk \'eszre, hogy az indukci\'os felt\'etel alapj\'an k\"onnyen
l\'athat\'o, hogy nemcsak az $\bar R_{k+1}(t)$  hanem az $R_{k+1}(t)$
f\"uggv\'eny is konstans minden  $[u2^{-k},(u+1)2^{-k})$ alak\'u
intervallumban. (M\'eg nem l\'attuk be, hogy $\bar
R_{k+1}(t)=R_{k+1}(t)$.) Ugyanis, az $R_k(t)=\bar R_k(t)$ f\"uggv\'eny
tulajdons\'agai alapj\'an elegend\H{o} az $R_{k+1}(t)$ f\"uggv\'enyt
defini\'al\'o (2) formula szupr\'emum\'aban csak olyan $s$ sz\'amokat
venni, melyekre $t-s=j2^{-k}$ alak\'u. Ez\'ert, ha  $t\in
[u2^{-(k+1)},(u+1)2^{-(k+1)})$ akkor \"osszehasonl\'{\i}tva azon
$(s,\bar s)$ p\'arokat, melykre
$R_k(u2^{-(k+1)}-s)=R_k(t-\bar s)=R_k(j2^{-k})$, kapjuk, hogy
$pR_k(t+\bar s)+(1-p)R_k(t-\bar s)=
pR_k(u2^{-(k+1)}+s)+(1-p)R_k(u2^{-(k+1)}-s)$, ez\'ert
$R_{k+1}(t)=R_{k+1}(u2^{-(k+1)})$. Az e.) \'all\'{\i}t\'as tov\'abbi
r\'esze innen k\"ovetkezik, hiszen mind az $R_k(t)$ mind a $\bar
R_k(t)$ f\"uggv\'eny konstans a megfelel\H{o} intervallumon. \medskip
 
A fenti T\'etelb\H{o}l k\"ovetkezik a mer\'esz strat\'egia
optimal\'{\i}t\'asa. Val\'oban, ebb\H{o}l az eredm\'enyb\H{o}l
indukci\'oval k\"ovetkezik, hogy ha $k$ l\'ep\'est tehet\"unk,
akkor a mer\'esz strat\'egia optim\'alis, \'es
nyerem\'enyf\"uggv\'enye $t$ kiindul\'o t\H{o}ke eset\'en $R_k(t)=\bar
R_k(t)$. Ez az \'all\'{\i}t\'as ugyanis $k=0$ eset\'en \'erv\'enyes,
\'es ha $k-1$-re igaz, akkor $t$ kiindul\'o t\H{o}ke eset\'en $s$,
$0\le s\le t$ kezdeti t\'et eset\'en a siker
val\'osz\'{\i}n\H{u}s\'ege  $pR_{k-1}(t+s)+(1-p)R_{k-1}(t-s)$. A
t\'etel azt mondja ki, hogy ez a kifejez\'es $0\le t\le \frac12$
eset\'en $s=t$ pontban, $\frac12\le t\le 1$ eset\'en pedig az
$s=1-t$ pontban veszi fel. Ez azt jelenti, hogy a $k$ l\'ep\'eses
strat\'egi\'ak k\"oz\"ul az optim\'alis strat\'egia els\H{o}
l\'ep\'ese megegyezik a mer\'esz strat\'egia els\H{o}
l\'ep\'es\'evel. Indukci\'oval innen k\"ovetkezik, hogy a
mer\'esz strat\'egia optim\'alis a $k$ l\'ep\'eses
strat\'egi\'ak k\"oz\"ott.
 
Tekints\"unk ezek ut\'an egy tetsz\H{o}leges strat\'egi\'at,
\'es 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 az optim\'alis 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)$. Ezt kellett bizony\'{\i}tanunk.
 
\bye
 
