\magnification=\magstep1
\hsize=16truecm
 
\input amstex
\TagsOnRight
\parindent=20pt
%\parskip=2pt plus 1.2pt
\parskip=3pt plus 1.5pt
%\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}
\def\Re{\text{\rm Re}\,}
\def\Im{\text{\rm Im}\,}
\font\script =cmcsc10
\font\BBB=msbm10

\centerline{ \'Attekint\'es }
\centerline{\bf  Dynkin, Evgenyij Boriszovics  \'es Yushkevics, 
Alekszandr Adolfovics}
\centerline{\it T\'etelek \'es feladatok Markov folyamatokr\'ol}
\centerline{ c\'{\i}m\H{u} k\"onyv\'er\H{o}l}

\medskip\noindent
{\it Harmadik fejezet: Az optim\'alis v\'alaszt\'as feladata.}

\medskip\noindent
Ez a fejezet egy az orosz irodalomban v\'alogat\'os 
menyasszony, a magyar irodalomban Szindb\'ad probl\'em\'anak 
nevezett feladat megold\'as\'anak az ismertet\'es\'evel 
kez\-d\H{o}\-dik. A feladat a k\"ovetkez\H{o}k\'epp sz\'ol. 

Egy h\"olgy (Szindb\'ad) $n$ v\H{o}leg\'eny (feles\'eg)jel\"olt 
k\"oz\"ul v\'alaszthatja ki leend\H{o} f\'erj\'et (feles\'eg\'et). 
A jel\"oltek min\H{o}s\'eg\'enek van egy sorrendje, van 
k\"oz\"ott\"uk egy legjobb, egy m\'asodik legjobb \'es 
\'{\i}gy tov\'abb, de a v\'alasztani akar\'o h\"olgy 
(Szindb\'ad) az egyes jel\"oltek j\'os\'ag\'at kezdetben nem 
ismeri. \H{O} csak a jel\"oltek $n$ sz\'am\'at tudja. A 
jel\"oltek v\'eletlen sorrendben jelennek meg egym\'as ut\'an 
a h\"olgy (Szindb\'ad) el\H{o}tt, aki az \'eppen 
megjelent jel\"olt min\H{o}s\'eg\'et \"ossze tudja 
hasonl\'{\i}tani a a kor\'abban megjelentek\'evel. Egy 
jel\"olt megjelen\'ese ut\'an a h\"olgynek (Szindb\'adnak) 
azonnal el kell d\"ontenie, hogy \H{o}t v\'alasztja-e vagy 
pedig valamelyik k\'es\H{o}bb megjelen\H{o} jel\"oltet, \'es 
ezt a d\"ont\'es\'et  k\'es\H{o}bb nem v\'altoztathatja meg. 
Tegy\"uk fel, hogy a jel\"oltek  megjelen\'es\'enek minden 
lehets\'eges sorrendje egyform\'an val\'osz\'{\i}n\H{u}. A 
h\"olgy (Szindb\'ad) c\'elja az, hogy min\'el nagyobb 
val\'osz\'{\i}n\H{u}s\'eggel a legjobb jel\"oltet v\'alassza.
Milyen strat\'egi\'at \'erdemes v\'alasztania, \'es mekkora 
a siker val\'osz\'{\i}n\H{u}s\'ege az optim\'alis strat\'egia 
v\'alaszt\'asa eset\'en? Mi e val\'osz\'{\i}n\H{u}s\'eg 
hat\'ar\'ert\'eke, ha $n\to\infty$?

A szerz\H{o}k e fejezet els\H{o} r\'esz\'eben megoldj\'ak ezt 
a feladatot. Azt is megmutatj\'ak, hogy ez a feladat 
t\'argyalhat\'o a k\"ovetkez\H{o} probl\'ema speci\'alis 
esetek\'ent. R\"ogz\'{\i}ts\"unk egy \'ert\'ekeit egy v\'eges 
vagy megsz\'aml\'alhat\'o sok elemet tartalmaz\'o $X$ halmazon 
felvev\H{o} Markov l\'ancot valamely ismert $p(x,y)$, 
$x,y\in X$, \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel, \'es 
egy a Markov l\'anc minden $x\in X$ \'allapot\'aban defini\'alt 
$f(x)$ f\"uggv\'enyt, amelyet 
nye\-re\-m\'eny\-f\"ugg\-v\'eny\-nek fogunk nevezni. A 
k\"ovetkez\H{o} feladatot t\'argyaljuk.  Vesz\"unk az $X$ 
t\'eren egy valamely $x\in X$ pontb\'ol kiindul\'o, $p(x,y)$ 
\'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gek\-kel
rendelkez\H{o} Markov l\'ancot. Ha a Markov l\'ancot egy 
v\'eletlen id\H{o}pontban meg\'all\'{\i}tjuk, \'es a Markov 
l\'anc ebben az id\H{o}pontban egy $u\in X$ \'allapotban 
tart\'ozkodik, akkor $f(u)$ nyerem\'enyt kapunk. C\'elunk egy 
olyan optim\'alis (v\'eletlen id\H{o}pontbeli)  meg\'all\'asi 
strat\'egia megad\'asa, amely\-nek al\-kal\-ma\-z\'a\-sa 
eset\'en nyerem\'eny\"unk v\'arhat\'o \'ert\'eke a lehet\H{o} 
legnagyobb. Ezenk\'{\i}v\"ul szeretn\'enk kisz\'am\'{\i}tani 
a nyerem\'eny v\'arhat\'o \'ert\'ek\'et az optim\'alis 
strat\'egia v\'alaszt\'asa eset\'eben.

E probl\'ema vizsg\'alat\'aban term\'eszetes m\'odon megjelenik
az els\H{o} fejezetben be\-ve\-ze\-tett excessz\'{\i}v
f\"uggv\'enyek fogalma, pontosabban az ott bevezetett fogalom 
term\'eszetes \'al\-ta\-l\'a\-no\-s\'{\i}\-t\'a\-sa arra az 
esetre, amikor nemcsak bolyong\'asokat tekint\"unk az 
$l$-dimenzi\'os r\'acson, hanem \'altal\'anos Markov 
l\'ancokat egy $X$ \'allapott\'eren valamely $p(x,y)$, 
$x,y\in X$ \'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gek\-kel. 
Az excessz\'{\i}v f\"uggv\'enyek \'es azok tulajdons\'agai
fontos szerepet j\'atszanak az optim\'alis meg\'all\'asi 
strat\'egi\'ak megtal\'al\'as\'aban \'es az optim\'alis 
strat\'egi\'ahoz tartoz\'o nyerem\'eny kisz\'am\'{\i}t\'as\'aban. 
Ezek az eredm\'enyek seg\'{\i}tenek az el\H{o}bb eml\'{\i}tett
optim\'alis p\'arv\'alaszt\'asi probl\'ema megold\'as\'aban is.

E fejezet tartalmazza a fent megfogalmazott optim\'alis 
meg\'all\'asi strat\'egi\'ar\'ol sz\'ol\'o feladat megold\'as\'at, 
illetve az excessz\'{\i}v f\"uggv\'enyek e feladat 
megold\'as\'aban felhaszn\'alt tulajdons\'againak vizsg\'alat\'at. 
V\'eg\"ul a fejezet utols\'o r\'esze egy olyan feladat
megold\'as\'at tartalmazza, amely \'ugy tekinthet\H{o}, mint az 
el\H{o}bb megfogalmazott feladat folytonos idej\H{u} 
v\'altozat\'anak egy speci\'alis esete. A k\"ovetkez\H{o} 
probl\'em\'ar\'ol van sz\'o. Tekints\"unk egy $[0,a]$ 
intervallumot valamely $a>0$ sz\'ammal, \'es egy valamely $x$, 
$0\le x\le a$, pontb\'ol kiindul\'o $W(t)$ Wiener folyamatot 
a $0$ \'es $a$ pontokkal mint elnyel\H{o} falakkal. Legyen 
adva egy foly\-to\-nos $f(x)$, $0\le x\le a$, f\"uggv\'eny a 
$[0,a]$ intervallumon. Hat\'arozzuk meg azt az optim\'alis 
$\tau$ meg\'all\'asi szab\'alyt erre a $W(t)$ Wiener folyamatra, 
amelyre az $Ef(W(\tau))$ v\'arhat\'o \'ert\'ek maxim\'alis, \'es 
hat\'arozzuk meg ezt a v\'arhat\'o \'ert\'eket. 

\medskip
A kiindul\'o feladat megold\'as\'aban hasznos a k\"ovetkez\H{o} 
eredm\'eny.

\medskip\noindent
{\bf 3.1. Lemma.} {\it Legyen adva $n$ k\"ul\"onb\"oz\H{o} 
$a_1<a_2<\cdots<a_n$ val\'os sz\'am, \'es vegy\"uk egyforma 
$\frac1{n!}$ val\'osz\'{\i}n\H{u}s\'eggel e sz\'amsorozat 
\"osszes lehets\'eges $a_{\pi(1)},\dots,a_{\pi(n)}$ 
permut\'aci\'oj\'at. Jel\"olje minden $1\le j\le n$ sz\'amra 
$\xi_j$ azt  a val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot, amely 
megmondja, hogy az $a_{\pi(j)}$ sz\'am nagys\'ag szerint
hanyadik az $a_{\pi(1)},a_{\pi(2)},\dots,a_{\pi(j)}$ sorozatban,
azaz legyen $\xi_j=1$, ha \H{o} a legnagyobb, $\xi_j=2$, ha \H{o} 
a m\'asodik legnagyobb e sz\'amok k\"oz\"ott, \'es \'{\i}gy 
tov\'abb. Ekkor a $\xi_1,\dots,\xi_n$  val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'ok f\"uggetlenek egym\'ast\'ol, \'es $P(\xi_j=s)=\frac1j$ 
minden $1\le s\le j$ sz\'amra \'es $1\le j\le n$ indexre.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ El\'eg bel\'atni, hogy 
$P(\xi_1=s_1,\xi_2=s_2,\dots,\xi_n=s_n)=\frac1{n!}$ minden olyan
$s_1,\dots,s_n$ sorozatra, amelyre $1\le s_j\le j$ minden 
$1\le j\le n$ indexre. Ennek igazol\'as\'ahoz el\'eg megmutatni, 
hogy k\"olcs\"on\"osen egy\'ertelm\H{u} megfeleltet\'es 
l\'etes\'{\i}thet\H{o} az ilyen tulajdons\'ag\'u
$s_1,\dots,s_n$ sorozatok \'es az $1,\dots,n$ sz\'amok 
$\pi=(\pi(1),\dots,\pi(n))$ permut\'aci\'oi k\"oz\"ott a 
k\"ovetkez\H{o} m\'odon. Ha adva van egy
$\pi=(\pi(1),\dots,\pi(n))$ permut\'aci\'o, akkor tekintj\"uk 
az \'altala meghat\'arozott $a_{\pi(1)},\dots,a_{\pi(n)}$ 
sorozatot, majd az e sorozat seg\'{\i}ts\'eg\'evel a 
lemm\'aban defini\'alt $\xi_1,\dots,\xi_n$ 
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'ok ezen 
permut\'aci\'ohoz tartoz\'o $s_1,\dots,s_n$ \'ert\'ekeit. 
Ha a $\pi$ permut\'aci\'onak ezt az $s_1,\dots,s_n$ sorozatot 
feleltetj\"uk meg, akkor a k\'{\i}v\'ant tulajdons\'ag\'u
k\"olcs\"onesen egy\'ertelm\H{u} megfeleltet\'est hozunk
l\'etre. Val\'oban, minden $\pi=(\pi(1),\dots,\pi(n))$ 
per\-mu\-t\'a\-ci\'onak megfelel egy k\'{\i}v\'ant 
tulajdons\'ag\'u $s_1,\dots,s_n$ sorozat, \'es k\"ul\"on\"oz\H{o} 
permut\'aci\'ok k\"ul\"onb\"oz\H{o} sorozatokat hat\'aroznak 
meg. (Ezt p\'eld\'aul \'ugy lehet l\'atni, hogy k\"ovetj\"uk 
a lek\'epez\'es eredm\'enyek\'ent kapott $s_n,s_{n-1},\dots$ 
sorozat \'ert\'ekeit egym\'as ut\'an az indexek cs\"okken\H{o} 
sorrendj\'eben.) Ezenk\'{\i}v\"ul a $(\pi(1),\dots,\pi(n))$ 
permut\'aci\'ok \'es $s_1,\dots,s_n$ sorozatok sz\'ama megegyezik. 
Mind a kett\H{o} \'ert\'eke $n!$.

\medskip
A k\'es\H{o}bbi t\'argyal\'as \'erdek\'eben felid\'ezem a 
Markov l\'anc fogalm\'at. Legyen adva egy $(\Omega,\Cal A,P)$ 
val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n $X_1,X_2,\dots$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok sorozata, amelyek 
\'ert\'ekeiket valamely v\'eges vagy megsz\'aml\'alhat\'o 
sok elemet tartalmaz\'o $X$ t\'erben veszik fel. Azt 
mondjuk, hogy ezek a val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok 
(stacion\'arius) Markov l\'ancot alkotnak $p(x,y)$,
$x,y\in X$, \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel, ha 
tetsz\H{o}leges $n\ge1$ sz\'amra, \'es 
$x_1,\dots,x_{n-1}\in X$ \'es $x,y\in X$ pontokra 
$$
P(X_{n+1}=y|X_n=x,X_{n-1}=x_{n-1},\dots,X_1=x_1)=p(x,y).
$$
Ezt az azonoss\'agot megk\"ovetelj\"uk minden olyan esetben,
amikor $P(X_{n+1}=y,X_n=x,X_{n-1}=x_{n-1},\dots,X_1=x_1)>0$.
 
Megjegyzem, hogy ebben a definici\'oban nem k\"ovetelt\"uk meg a 
$\summ_{y\in X}p(x,y)=1$ felt\'etel teljes\"ul\'es\'et. El\'eg 
megk\"ovetelni azt, hogy $\summ_{y\in X}p(x,y)\le1$ minden $x\in X$
pontban. Ez egyben azt jelenti, hogy megengedj\"uk azt, hogy egy 
$X_n$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o ne legyen 
defini\'alva az eg\'esz $(\Omega,\Cal A,P)$  
val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n, hanem csak annak egy 
1-n\'el kisebb m\'ert\'ek\H{u} r\'esz\-hal\-ma\-z\'an.

\'Erdemes a Markov l\'ancok definici\'oj\'at kiss\'e 
\'altal\'anosabban megadni. Az \'al\-ta\-l\'a\-no\-sabb 
definici\'oban megengedj\"uk, hogy azokon az esem\'enyeken 
k\'{\i}v\"ul, hogy  az $X_n$ val\'osz\'{\i}n\H{u}s\'egi 
v\'al\-to\-z\'ok milyen \'ert\'ekeket vesznek fel m\'as 
esem\'enyeket is figyelembe vehess\"unk a vizsg\'alt 
felt\'eteles val\'osz\'{\i}n\H{u}s\'egek definici\'oj\'aban
szerepl\H{o} felt\'etelek k\"oz\"ott. De ezek az \'uj 
esem\'enyek nem befoly\'asolj\'ak a vizs\-g\'alt felt\'eteles 
val\'osz\'{\i}n\H{u}s\'egeket.

Legyen adva egy $(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi 
mez\H{o}n $X_1,X_2,\dots$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok 
sorozata, amelyek \'ert\'ekeiket valamely v\'eges vagy 
megsz\'aml\'alhat\'o elemsz\'am\'u $X$ t\'erben veszik fel. 
Legyen ezenk\'{\i}v\"ul adva 
$\Cal F_1\subset\Cal F_2\subset\cdots\subset\Cal A$ 
$\sigma$-algebr\'aknak olyan n\"o\-vek\-v\H{o} sorozata, amelyek 
r\'eszei az $\Cal A$ $\sigma$-algebr\'anak, \'es amelyekre igaz 
az, hogy $X_n$ $\Cal F_n$ m\'er\-he\-t\H{o} val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'o minden $n=1,2,\dots$ indexre. (Most is megengedj\"uk, 
hogy csak a $\summ_{y\in X}p(x,y)\le1$ felt\'etel teljes\"ulj\"on,
\'es az $X_n$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o ne legyen 
defini\'alva az eg\'esz t\'eren.) Azt mondjuk, hogy ezek a
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \'es 
$\sigma$-algebr\'ak (stacion\'arius) Markov l\'ancot alkotnak 
$p(x,y)$, $x,y\in X$, \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel, 
ha tetsz\H{o}leges $n\ge1$ sz\'amra, \'es $x,y\in X$ pontokra 
$$
P(X_{n+1}=y|\Cal F_n)(\oo)=p(x,y), \quad \text{ha } X_n(\oo)=x. \tag3.1
$$ 
%Ez  a definici\'o magyar\'azatra szorul abban az esetben, amikor
%az $X_n$ val\'osz\'{\i}n\H{u}s\'egi v\'al\-to\-z\'ok nincsenek
%minden pontban defini\'alva, ez\'ert az $X_n(\oo)=x$ felt\'etel
%nem mindig \'er\-tel\-mez\-het\-\H{o}. Tegy\"uk fel az 
%egyszer\H{u}s\'eg kedv\'e\'ert, hogy a definici\'oban 
%szerepl\H{o} $\Cal F_n$ $\sigma$-algebr\'ak egyszer\H{u} 
%szerkezet\H{u}ek. Azok tartalmaznak v\'eges vagy 
%megsz\'aml\'alhat\'oan sok pozi\-t\'{\i}v 
%val\'osz\'{\i}n\H{u}s\'eg\H{u} atomot, \'es a $\Cal F_n$ 
%$\sigma$-algebra elemei az ilyen atomok uni\'oib\'ol \'allnak.
%A minket \'erdekl\H{o} esetekben ez a felt\'etel teljes\"ul. 
A (3.1) pontban fel\'{\i}rt azonoss\'ag \'ugy \'ertend\H{o},
hogy az teljes\"ul azon $\oo\in\Omega$ pontok halmaz\'an, ahol 
defini\'alva van az $X_n(\oo)$ f\"uggv\'eny. 
%Ekkor a $P(X_{n+1}=y|\Cal F_n)(\oo)$ felt\'eteles 
%val\'osz\'{\i}n\H{u}s\'eget \'ugy defini\'aljuk, mint az
%$X_{n+1}(\oo)=y$ esem\'eny felt\'eteles 
%val\'osz\'{\i}n\H{u}s\'eg\'et felt\'eve a $\Cal F_n$ 
%$\sigma$-algebra $\oo$ pontot tartalmaz\'o atomj\'at.

\medskip
Tekints\"uk a v\'alogat\'os menyasszony probl\'em\'at. Vegy\"uk 
\'eszre, hogy a  3.1~lemma alapj\'an ezt a feladatot a 
k\"ovetkez\H{o}k\'epp is \'atfogalmazhatjuk. Adott $
\xi_1,\dots,\xi_n$ f\"uggetlen val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'ok sorozata, amelyekre $\xi_j$ az $1,\dots,j$ 
sz\'amok valamelyik\'et veszi fel, \'es $P(\xi_j=s)=\frac1j$ 
minden $1\le s\le j$ sz\'amra. Lehet\H{o}s\'eg\"unk van
arra, hogy megfigyelj\"uk egym\'as ut\'an
a $\xi_1,\xi_2,\dots,\xi_n$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'okat. A megfigyel\'est azon $j$ indexre 
szeretn\'enk befejezni, amely\-re egyr\'eszt $\xi_j=1$, 
m\'asr\'eszt $\xi_k\ge2$ minden $k>j$ indexre. Hogyan tudjuk 
el\'erni, hogy \'ugy fejezz\"uk be a megfigyel\'est, hogy ez 
az esem\'eny min\'el nagyobb val\'osz\'{\i}n\H{u}s\'eggel 
k\"ovetkezzen be? \'Erts\"uk meg, hogy mi\'ert ezt a feladatot 
kell megoldanunk a v\'alogat\'os menyasszony 
probl\'em\'aj\'anak vizsg\'alat\'aban. 

Amikor az egyes jel\"oltek egym\'as ut\'an megjelennek, \'es 
\"osszehasonl\'{\i}tjuk \H{o}ket a kor\'abban megjelentekkel, 
akkor azokat a $\xi_j$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'okat figyelj\"uk meg, amelyek megmondj\'ak, hogy 
az \'ujonnan megjelent jel\"olt hanyadik az eddigi jel\"oltek 
k\"oz\"ott a j\'os\'agi sorrendben. Az, hogy $\xi_j=1$ azt 
jelenti, hogy a $j$-ik jel\"olt minden kor\'abbin\'al jobb. Az, 
hogy $\xi_k\ge2$ minden $k>j$ indexre azt jelenti, hogy a 
k\'es\H{o}bbi jel\"oltek k\"oz\"ott sem jelenik meg a $j$-ik 
jel\"oltn\'el jobb jel\"olt. Teh\'at az, hogy siker\"ult az 
ilyen tulajdons\'ag\'u $j$ indexet megtal\'alni ekvivalens 
azzal, hogy megtal\'altuk a legjobb jel\"oltet. M\'asr\'eszt 
a 3.1~lemma alapj\'an a $\xi_j$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'oknak az \'altalunk megadott egy\"uttes 
eloszl\'asa van.

Az el\H{o}bbiekben megadtuk a v\'alogat\'os menyasszony 
probl\'ema egy ekvivalens megfogalmaz\'as\'at. A feladatot 
meg lehet oldani ebben a form\'aban, de a k\"onyv szerz\H{o}i 
le\'{\i}rt\'ak a feladat egy olyan ekvivalens megfogalmaz\'as\'at
alkalmas Markov l\'ancok seg\'{\i}ts\'eg\'evel, amelyik 
k\'enyelmesebben vizsg\'alhat\'o. Ismertetem ezt a 
megfogalmaz\'ast. Ehhez sz\"uks\'eg\"unk van a k\"ovetkez\H{o}
eredm\'enyre.

\medskip\noindent
{\bf 3.2. Lemma.} {\it Legyen $\xi_1,\dots,\xi_n$ f\"uggetlen 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok sorozata, amelyre 
$P(\xi_j=s)=\frac1j$, $1\le s\le j$ minden $1\le j\le n$ 
indexre. Defini\'aljuk a k\"ovetkez\H{o} $\eta_1$, 
$\eta_2$,\dots, val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okat. 
$\eta_1(\oo)\equiv1$, $\eta_2(\oo)=n_1(\oo)$, a legkisebb 
olyan $l=n_1(\oo)>1$ index-szel, amelyre $\xi_l(\oo)=1$, 
ha van ilyen $l$ index. Ha nincs ilyen $l$ index akkor sem 
az $\eta_2(\oo)$, sem az $\eta_k(\oo)$, $k>2$, 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okat nem defini\'aljuk
az $\oo\in\Omega$ pontban. Ha az $\eta_j(\oo)$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot m\'ar defini\'altuk 
valamely $j$ indexre egy $\oo\in\Omega$ pontban, akkor 
$\eta_{j+1}(\oo)=n_{j+1}(\oo)$ azzal a legkisebb
$l=n_{j+1}(\oo)>\eta_j(\oo)$ index-szel, amelyre 
$\xi_l(\oo)=1$, felt\'eve, hogy ilyen $l$ index l\'etezik. 
Ha ilyen $l$ index nem l\'etezik, akkor sem a $\eta_{j+1}(\oo)$ 
sem az $\eta_p(\oo)$, $p\ge j+2$, val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okat nem defini\'aljuk az $\oo\in\Omega$ pontban.

Az \'{\i}gy defini\'alt $\eta_1,\eta_2,\dots$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok Markov
l\'ancot alkotnak az $X=\{1,\dots,n\}$ halmazon felvett 
\'ert\'ekekkel \'es a k\"ovetkez\H{o} 
\'atmenetval\'osz\'{\i}n\H{u}s\'egekkel: 
$p(l|k)=P(\eta_{j+1}=l|\eta_j=k)=\frac k{(l-1)l}$,
ha $1\le k<l\le n$, \'es $p(l|k)=0$ k\"ul\"onben.

Defini\'aljuk minden $j$ sz\'amra az $\Cal F_j$ 
$\sigma$-algebr\'at, mint az 
$\{\oo\colon\;\xi_1(\oo)=s_1,\xi_2(\oo)=s_2,\dots,\xi_p(\oo)=s_p\}$ 
alak\'u esem\'enyek \'altal gener\'alt $\sigma$-algebr\'at, ahol 
olyan $s_1,\dots,s_p$, $1\le s_l\le l$ minden $1\le l\le p$ 
sorozatokat tekint\"unk, amelyekre $p\le n$, \'es az 
$s_1,\dots,s_l$ sorozat $\eta_j(\oo)$ darab egyest tartalmaz. 
Az $(\eta_j,\Cal F_j)$, $j=1,2,\dots$ sorozat szint\'en Markov 
l\'anc az el\H{o}bb defini\'alt $p(k|l)$ 
\'atmenetval\'osz\'{\i}n\H{u}s\'egekkel.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Ki kell sz\'amolnunk a
$$
\align
&P(\eta_{j+1}=l|\eta_j=k,\eta_{j-1}=k_{j-1},\eta_{j-2}=k_{j-2}
,\dots,\eta_1=k_1) \\
&\qquad =
\frac{P(\eta_{j+1}=l,\eta_j=k,\eta_{j-1}=k_{j-1},
\eta_{j-2}=k_{j-2},\dots,\eta_1=k_1)}
{P(\eta_j=k,\eta_{j-1}=k_{j-1},\eta_{j-2}=k_{j-2},\dots,\eta_1=k_1)}
\endalign
$$
felt\'eteles val\'osz\'{\i}n\H{u}s\'eget minden $j$ indexre, \'es
$n\ge l>k>k_{j-1}>k_{j-2}>\cdots> k_1=1$ felt\'etel eset\'en. 
A fenti t\"ortben szerepl\H{o} val\'osz\'{\i}n\H{u}s\'egeket 
ki tudjuk sz\'amolni, mert olyan esem\'enyek 
val\'osz\'{\i}n\H{u}s\'eg\'et kell kisz\'amolni, hogy az
egym\'ast\'ol f\"uggetlen $\xi_p$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'ok k\"oz\"ul egyesek 1-gyel egyenl\H{o}ek, m\'asok 
pedig nem egyenl\H{o}ek 1-gyel. Azt kapjuk, hogy
$$
\align
&P(\eta_{j+1}=l,\eta_j=k,\eta_{j-1}=k_{j-1},
\eta_{j-2}=k_{j-2},\dots,\eta_1=k_1) \\
&\qquad=\frac1l\cdot \frac1k\cdot\prod_{s=1}^{j-1}\frac1{k_s}
\prod\Sb 1\le t\le l\\ t\notin\{l,k,k_j,k_{j-1},\dots,k_1\}\endSb 
\frac{t-1}t,
\endalign
$$
\'es hasonl\'oan
$$
\align
&P(\eta_j=k,\eta_{j-1}=k_{j-1},
\eta_{j-2}=k_{j-2},\dots,\eta_1=k_1) \\
&\qquad=\frac1k\cdot\prod_{s=1}^{j-1}\frac1{k_s}
\prod\Sb 1\le t\le k\\ t\notin\{k,k_j,k_{j-1},\dots,k_1\}\endSb \frac{t-1}t.
\endalign
$$
Ez\'ert a keresett felt\'eteles val\'osz\'{\i}n\H{u}s\'eg
$$
\align
&P(\eta_{j+1}=l|\eta_j=k,\eta_{j-1}=k_{j-1},\eta_{j-2}=k_{j-2},
\dots,\eta_1=k_1) \\
&\qquad =\frac1l\prod_{k+1\le t\le l-1}\frac{t-1}t=\frac k{(l-1)l}.
\endalign
$$
\'Igy a k\'{\i}v\'ant azonoss\'agot bel\'attuk minden olyan 
esetben, amikor $P(\eta_{j+1}=l,\eta_j=k,\eta_{j-1}=k_{j-1},
\eta_{j-2}=k_{j-2},\dots,\eta_1=k_1)>0$.

A 3.2 lemma m\'asodik fel\'et arr\'ol az esetr\H{o}l, amikor a 
$\Cal F_j$ $\sigma$-algebr\'akat is tekintj\"uk hasonl\'oan 
l\'atjuk be, csak akkor a jel\"ol\'es kiss\'e bonyolultabb\'a 
v\'alik.

\medskip
Jelenjenek meg a v\'alogat\'os menyasszony probl\'em\'aj\'aban 
az egyes jel\"oltek az 1, 2, 3,\dots id\H{o}pontokban. Jel\"olje 
$\eta_1$, $\eta_2$,\dots azokat az id\H{o}pontokat, amikor egy
minden ko\-r\'ab\-bi\-n\'al jobb jel\"olt jelent meg. A 
3.2 lemm\'aban azt bizony\'{\i}tottuk be, hogy ezek az $\eta_j$ 
id\H{o}\-pon\-tok Markov l\'ancot alkotnak, \'es megadtuk e 
Markov l\'anc \'atmenetval\'osz\'{\i}n\H{u}s\'egeit. Vi\-l\'a\-gos, 
hogy csak valamelyik $\eta_j$ id\H{o}pontben megjelent 
jel\"oltet \'erdemes v\'alasztani, ha az a c\'elunk, hogy a 
legjobb jel\"oltet v\'alasszuk min\'el nagyobb 
val\'osz\'{\i}n\H{u}s\'eggel. (Illetve az utols\'o $n$-ik 
jel\"oltet kell v\'alasztani akkor, amikor m\'ar nincs t\"obb 
v\'alaszthat\'o jel\"olt.) C\'elunk annak meghat\'aroz\'asa, 
hogy melyik $\eta_j$ id\H{o}pontban megjelent jel\"oltet 
\'erdemes v\'alasztani. E k\'erd\'es megv\'alaszol\'as\'ahoz 
ad hasznos inform\'aci\'ot a 3.2 lemma. A lemma m\'asodik 
fel\'eben megfogalmazott $\Cal F_j$ $\sigma$-algebr\'akr\'ol 
sz\'ol\'o \'all\'{\i}t\'asnak az a haszna, hogy 
seg\'{\i}ts\'eg\'evel be lehet l\'atni, hogy az a plusz 
inform\'aci\'o hogy tudjuk mi t\"ort\'ent az $\eta_j$ \'es 
$\eta_{j+1}$ id\H{o}pontok k\"oz\"ott, milyen sorrendben 
jelentek meg az eleve nem v\'alaszthat\'o jel\"oltek, 
nem ad hasznos inform\'aci\'ot a k\'erd\'es
megv\'alaszol\'as\'ahoz. Annak \'erdek\'eben, hogy az 
optim\'alis strat\'egi\'at megtal\'aljuk \'erdemes 
bebizony\'{\i}tani a k\"ovetkez\H{o} eredm\'enyt.

\medskip\noindent
{\bf 3.3. Lemma.} {\it Legyen $\eta_1,\eta_2,\dots$ egy Markov 
l\'anc az $X=\{1,\dots,n\}$ halmazon felvett \'ert\'ekekkel 
a k\"ovetkez\H{o} $p(l|k)$ \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel:
$p(l|k)=P(\eta_{j+1}=l|\eta_j=k)=\frac k{(l-1)l}$, ha 
$1\le k<l\le n$, \'es $p(l|k)=0$ k\"ul\"onben. Jel\"olje 
$q(k)$ annak felt\'eteles val\'osz\'{\i}n\H{u}s\'eg\'et, hogy 
nem l\'etezik az $\eta_{j+1}$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'o, felt\'eve azt, hogy $\eta_j=k$. Azaz
$q(k)$ annak felt\'eteles val\'osz\'{\i}n\H{u}s\'ege, hogy 
amennyiben a a $j$ id\H{o}pontban a Markov l\'anc a $k$ pontban 
tartozk\'odik akkor onnan m\'ar nem l\'ep sehov\'a. Jel\"olje 
$q'(k)$ annak a felt\'eteles val\'osz\'{\i}n\H{u}s\'eg\'et,
hogy a Markov l\'ancban l\'etezik az $\eta_{j+1}>\eta_j$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, de az 
$\eta_{j+2}>\eta_{j+1}$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'o m\'ar nem l\'etezik, felt\'eve, hogy $\eta_j=k$. 
Ez annak a felt\'eteles val\'osz\'{\i}n\H{u}s\'ege, hogy amennyiben
a  Markov l\'anc a $j$ id\H{o}pontban a $k$ pontban tart\'ozkodik,
akkor az tesz m\'eg egy l\'ep\'est a $k$ pontb\'ol, de ez a Markov 
l\'anc utol\-s\'o l\'ep\'ese.

Azt \'all\'{\i}tom, hogy $q(k)=\frac kn$, $1\le k\le n$, \'es 
$$
q'(k)=\frac kn\(\frac1k+\frac1{k+1}+\cdots+\frac1{n-1}\), \quad\text{ha }
 1\le k\le n-1, \tag3.2
$$
\'es $q'(n)=0$.}

\medskip\noindent
{\it Bizony\'{\i}t\'as.}\/ Fel\'{\i}rhatjuk az 
$1-q(k)=\summ_{l=k+1}^n p(l|k)$ azonoss\'agot, ami az\'ert igaz, 
mert ha $\eta_j=k$ akkor annak komplementer esem\'enye,
hogy az $\eta_{j+1}$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o 
nem l\'etezik az, hogy $\eta_{j+1}=l$ valamilyen
$k+1\le l\le n$ sz\'ammal. Mivel 
$p(l|k)=\frac k{(l-1)l}=k(\frac1{l-1}-\frac1l)$
a 3.2~lemma alapj\'an, ez\'ert igaz az
$$
1-q(k)=\sum_{l=k+1}^n k\(\frac1{l-1}-\frac1l\)
=k\(\frac1k-\frac1n\)=1-\frac kn
$$
azonoss\'ag, \'es ezt kellett bel\'atni.

Igaz a $q'(k)=\summ_{l=k+1}^{n}p(l|k)q(l)
=\summ_{l=k+1}^{n}\frac k{(l-1)l}\cdot\frac ln$ azonoss\'ag minden 
$1\le k\le n-1$ sz\'amra, mert $p(l|k)q(l)$ annak a felt\'eteles
val\'osz\'{\i}n\H{u}s\'ege, hogy $\eta_{j+1}=l$, \'es az 
$\eta_{j+2}$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o nem 
l\'etezik, felt\'eve, hogy $\eta_j=k$. Innen k\"ovetkezik a 
(3.2)~formula. A $q'(n)=0$ azonoss\'ag nyilv\'anval\'o.

\medskip\noindent
Az eredeti v\'alogat\'os menyasszony probl\'em\'at a 
k\"ovetkez\H{o} probl\'em\'ara vezett\"uk vissza. Tekints\"unk 
egy a 3.2. lemm\'aban le\'{\i}rt $\eta_1,\eta_2,\dots$ 
Markov l\'ancot. E Markov l\'anc ele\-mei\-nek 
egym\'as ut\'ani megfigyel\'ese (\'es a $p(y|x)$ 
\'atmenetval\'osz\'{\i}n\H{u}s\'egek ismeret\'eben) 
pr\'ob\'aljuk e Markov l\'anc megfigyel\'es\'et min\'el
 nagyobb val\'osz\'{\i}n\H{u}s\'eggel abban az 
id\H{o}\-pont\-ban befejezni, amikor e Markov l\'anc 
utols\'o eleme megjelenik. 
(Ezt a Markov l\'ancot \'ugy kaptuk, hogy az eredeti 
v\'alogat\'os menyasszony probl\'em\'aban az $\eta_j$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot \'ugy defini\'altuk, 
mint azt a sz\'amot, amely megmondta, hogy h\'anyadik jel\"olt 
volt  a $j$-ik olyan jel\"olt, amely az \"osszes kor\'abbi 
jel\"oltn\'el jobb volt. Az $\eta_j$ definici\'oja \'ugy 
\'ertend\H{o}, hogy amennyiben nem volt $j$-ik olyan jel\"olt, 
aki minden kor\'abbi jel\"oltn\'el jobb volt, akkor az $\eta_j$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot nem defini\'altuk. Az 
\'{\i}gy defini\'alt Markov l\'ancban az $\eta_1\equiv1$ 
tulajdons\'ag is teljes\"ul.) 

Annak \'erdek\'eben, hogy ezt a feladatot megoldjuk vizsg\'aljuk 
el\H{o}sz\"or a k\"ovetkez\H{o} k\'erd\'est. Tegy\"uk fel, hogy 
a vizsg\'alt Markov l\'ancban az $\eta_j=k$, $1\le k\le n$, 
esem\'eny bek\"ovetkezett valamilyen $j$ index-szel, \'es 
nek\"unk el kell d\"onteni, hogy ezen esem\'eny bek\"ovetkezte
ut\'an mikor fejezz\"uk be e Markov l\'anc megfigyel\'es\'et. 
Tekints\"uk a k\"ovetkez\H{o} k\'et lehets\'eges strat\'egi\'at. 
Az els\H{o} strat\'egia az, hogy a $j$ id\H{o}pontban azonnal 
befejezz\"uk a Markov l\'anc megfigyel\'es\'et. A m\'asodik 
strat\'egia az, hogy v\'arunk az $\eta_{j+1}$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o megjelen\'es\'ere, 
\'es ha ez megjelenik, akkor befejezz\"uk a Markov l\'anc 
megfigyel\'es\'et. (Ha nem jelenik meg az $\eta_{j+1}$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, akkor nem siker\"ult 
a Markov l\'anc megfigyel\'es\'et a megfelel\H{o} 
id\H{o}pontban befejezni.) Sz\'amoljuk ki a siker 
val\'osz\'{\i}n\H{u}s\'eg\'et e k\'et strat\'egia 
alkalmaz\'asa eset\'en, \'es hat\'arozzuk meg, hogy
mikor melyik a jobb. 

A k\'et strat\'egia siker\'enek a val\'osz\'{\i}n\H{u}s\'eg\'et 
a 3.3. lemm\'aban kisz\'amoltuk. Az els\H{o} strat\'egia 
siker\'enek a val\'osz\'{\i}n\H{u}s\'ege az ott defini\'alt 
$q(k)$, a m\'asodik\'e az ott defini\'alt $q'(k)$ mennyis\'eg, 
\'es ezen mennyis\'egeket kisz\'amoltuk a 3.3. lemm\'aban. 
Ezek az eredm\'enyek lehet\H{o}v\'e teszik annak 
meghat\'aroz\'as\'at is, hogy mikor melyik strat\'egia a jobb. 
A v\'alasz megfogalmaz\'asa \'erdek\'eben vezess\"uk be azt 
a $k_n$ pozit\'{\i}v eg\'esz sz\'amot, amely teljes\'{\i}ti az
$$
\frac1{k_n}+\frac1{k_n+1}+\cdots+\frac1{n-1}\le 1<
\frac1{k_n-1}+\frac1{k_n}+\frac1{k_n+1}+\cdots+\frac1{n-1} \tag3.3
$$
egyenl\H{o}tlens\'eget.

Ha $k\ge k_n$ akkor az els\H{o}, ha $k<k_n$ akkor a m\'asodik 
strat\'egia az el\H{o}ny\"osebb. Ez az eredm\'eny a 
k\"ovetkez\H{o} k\'epet sugallja. Ha $\eta_j=k$ egy viszonylag 
kis $k$ sz\'ammal akkor nem \'erdemes a Markov l\'anc figyel\'es\'et
befejezni, hanem \'erdemes \'ujabb $\eta_{j+1}$ sz\'am 
megjelen\'es\'ere v\'arni. Ha $\eta_j=k$ egy el\'eg nagy $k$ 
sz\'amra, akkor \'erdemes a Markov l\'anc megfigyel\'es\'et 
azonnal befejezni.  S\H{o}t, azt is megsejthetj\"uk, hogy 
a $k_n$ sz\'am a hat\'ar a kis \'es nagy sz\'amok k\"oz\"ott.
Azaz, ha $k<k_n$, akkor az $\eta_j=k$ esem\'eny megjelen\'esekor 
nem fejezz\"uk be, \'es ha $k\ge k_n$, akkor az $\eta_j=k$ 
esem\'eny megjelen\'esekor befejezz\"uk a Markov l\'anc 
megfigyel\'es\'et. Az al\'abbi eredm\'enyben ezt az 
\'all\'{\i}t\'ast pontosabban is megfogalmazzuk.
 
\medskip\noindent
{\bf 3.4. Lemma.} {\it Tekints\"uk a 3.2 Lemm\'aban defini\'alt
$\eta_1,\eta_2,\dots$ Markov l\'ancot \'es az $\eta_j=k$ 
esem\'enyt valamilyen $j$ \'es $k$ sz\'amokkal. Hat\'arozzuk 
meg a Markov l\'anc  $j$ id\H{o}pont ut\'ani optim\'alis 
meg\'all\'asi strat\'egi\'aj\'at, amelynek alkalmaz\'asa 
eset\'en a leg\-na\-gyobb a felt\'eteles 
val\'osz\'{\i}n\H{u}s\'ege annak, hogy a Markov l\'ancot 
az utols\'o $\eta_l$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o 
megjelen\'esekor \'all\'{\i}tottuk meg, felt\'eve, hogy 
$\eta_j=k$. Sz\'am\'{\i}tsuk ki ezt a felt\'eteles 
val\'osz\'{\i}n\H{u}s\'eget. 

Ha $k\ge k_n$, ahol $k_n$ a (3.3) formul\'at teljes\'{\i}t\H{o} 
pozit\'{\i}v eg\'esz sz\'am, akkor az optim\'alis strat\'egia 
az azonnali, $j$ id\H{o}pontbeli meg\'all\'as, \'es annak 
felt\'eteles val\'osz\'{\i}n\H{u}s\'ege az $\eta_j=k$ 
felt\'etel mellett, hogy ez a j\'o meg\'all\'asi id\H{o}pont 
a $\frac kn$ sz\'ammal egyenl\H{o}. Ha $k\le k_n-1$, akkor 
az optim\'alis strat\'egia az, hogy megv\'arjuk az els\H{o} 
olyan $\eta_l$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o 
megjelen\'es\'et, amelyre $\eta_l=\bar k$ valamely 
$\bar k\ge k_n$ sz\'ammal. Ha ilyen $\eta_l$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o nem l\'etezik, 
akkor nem siker\"ult a j\'o meg\'all\'asi id\H{o}pontot 
megtal\'alni. A j\'o meg\'all\'asi id\H{o}pont 
megtal\'al\'as\'anak felt\'eteles val\'osz\'{\i}n\H{u}s\'ege 
az $\eta_j=k$ felt\'etel mellett ebben az esetben 
$$
\frac {k_n-1}n\(\frac1{k_n-1}+\frac1{k_n}+\frac1{k_n+1}+\cdots+\frac1{n-1}\).
\tag3.4
$$
}

\medskip\noindent
{\it K\"ovetkezm\'eny.} Mivel a v\'alogat\'os menyasszony 
probl\'ema feladat\'anak megold\'as\'at egy olyan a 
3.2.~lemm\'aban defini\'alt Markov l\'anc vizsg\'alat\'ara
vezett\"uk vissza, amelyben $\eta_1\equiv1$ a 3.4 lemma 
megadja az optim\'alis strat\'egi\'at ebben a feladatban. 
A $k_n$  id\H{o}pontn\'al nem kor\'abban megjelent jel\"oltek 
k\"oz\"ul az els\H{o} minden kor\'abbin\'al jobb jel\"oltet 
kell v\'alasztani. A sikeres v\'alaszt\'as 
val\'osz\'{\i}n\H{u}s\'eg\'et ebben az esetben a (3.4)~formula
adja meg.

\medskip\noindent
{\it Megjegyz\'es.}\/ A 3.4 lemm\'aban szerepl\H{o} optim\'alis 
v\'alaszt\'as felt\'eteles val\'osz\'{\i}n\H{u}s\'ege nem f\"ugg 
az $\eta_j$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o $j$ 
index\'et\H{o}l, csak annak $k$ \'ert\'ek\'et\H{o}l. Ez azzal 
f\"ugg \"ossze, hogy az $\eta_1,\eta_2,\dots$ sorozat 
stacion\'arius Markov  l\'anc. A lemm\'at az\'ert
fogalmaztuk egy $j$ index seg\'{\i}ts\'eg\'evel, mert ily 
m\'odon olyan \'all\'{\i}t\'ast tudtunk fel\'{\i}rni, amelynek
bizony\'{\i}t\'as\'aban  k\"onnyebben v\'egrehajthat\'o az ott 
alkalmazott indukci\'o. Val\'oj\'aban a 3.4 lemm\'at kiss\'e 
\'altal\'anosabban kellett volna megfogalmaznunk egy r\'eszletes
\'es pontos bizony\'{\i}t\'asban. A 3.2 Lemma v\'eg\'en 
defini\'alt $(\eta_j,\Cal F_j)$ Markov l\'anccal kellett volna 
dol\-goz\-nunk annak \'erdek\'eben, hogy megmutassuk: Az a 
plusz inform\'aci\'o, hogy tudjuk milyen sorrendben \'erkeztek
a nem v\'alaszthat\'o jel\"oltek nem seg\'{\i}t egy jobb 
strat\'egia kidolgoz\'as\'aban. A bizony\'{\i}t\'asban is egy 
form\'alisan \'altal\'anosabb \'all\'{\i}t\'ast kellett volna
bizony\'{\i}tani. Azt, hogy ha r\"ogz\'{\i}t\"unk egy
olyan ese\-m\'enyt, amelyik az $\Cal F_j$ $\sigma$-algebra 
valamely az $\eta_j=k$ esem\'eny \'altal tartalmazott atomja, 
\'es a $j$ id\H{o}pont ut\'ani optim\'alis meg\'all\'ast 
keress\"uk, \'es az optim\'alis meg\'all\'as felt\'eteles 
val\'osz\'{\i}n\H{u}s\'eg\'et akarjuk kisz\'amolni  
felt\'eve hogy ez az ese\-m\'eny bek\"ovetkezett, 
akkor a lemm\'aban az $\eta_j=k$ felt\'etel eset\'eben
 kimondott \'all\'{\i}t\'asok \'erv\'enyesek. Ezen 
\'altal\'anosabb \'all\'{\i}t\'as megfogalmaz\'asa \'es 
bi\-zo\-ny\'{\i}\-t\'a\-sa csak technikai komplik\'aci\'ot 
jelentett volna. K\'es\H{o}bb t\'argyalni fogjuk a 
v\'alogat\'os meny\-asszony feladat egy m\'asik, 
\'altal\'anos elveken alapul\'o megold\'as\'at is.

\medskip\noindent
{\it A 3.4. lemma bizony\'{\i}t\'asa.}\/ A lemm\'at a $k$ 
sz\'am szerinti backward indukci\'oval fogjuk 
bebizony\'{\i}tani. A $k=n$ esetre igaz az \'all\'{\i}t\'as.
Vegy\"unk egy $k\ge k_n$ sz\'amot, \'es tegy\"uk fel, hogy 
az \'all\'{\i}t\'as igaz minden $n\ge\bar k>k$ sz\'amra. 
Ekkor vagy meg\'allunk az $\eta_j=k$ pontban, \'es ekkor a 
siker (felt\'eteles) val\'osz\'{\i}n\H{u}s\'ege $\frac kn$ 
a 3.3.~lemma alapj\'an, vagy tesz\"unk egy l\'ep\'est \'es 
ekkor 
$P(\eta_{j+1}=\bar k|\eta_j=k)=\frac k{(\bar k-1)\bar k}$ 
(felt\'eteles) val\'osz\'{\i}n\H{u}s\'eggel jutunk a 
$\bar k$ pontba. Ha a $\bar k$ pontban vagyunk, akkor 
\'erdemes az onnan indul\'o optim\'alis strat\'egi\'at 
alkalmazni, ami indukci\'os feltev\'es\"unk szerint a 
megfigyel\'esek befejez\'es\'et jelenti, \'es a siker 
val\'osz\'{\i}n\H{u}s\'ege ekkor $\frac{\bar k}n$. Ez azt 
jelenti, hogy ha $\eta_j=k$ esem\'eny ut\'an 
tov\'abbl\'ep\"unk, \'es azut\'an az optim\'alis 
strat\'egi\'at alkalmazzuk, akkor a siker (felt\'eteles) 
val\'osz\'{\i}n\H{u}s\'ege 
$\summ_{\bar k=k+1}^n\frac k{(\bar k-1)\bar k}\cdot\frac{\bar k}n
=\frac kn\summ_{\bar k=k}^{n-1}\frac1{\bar k}$, 
ami $k\ge k_n$ eset\'en kisebb, mint $\frac kn$, azaz a 
siker felt\'eteles val\'osz\'{\i}n\H{u}s\'ege az 
azonnali le\'all\'as eset\'eben. Ez azt jelenti, hogy ebben 
az esetben az azonnali le\'all\'as az optim\'alis strat\'egia.

Ha $k=k_n-1$, azaz $\eta_j=k_n-1$ akkor az el\H{o}z\H{o} 
\'ervel\'eshez hasonl\'oan  bel\'athatjuk, hogy az 
optim\'alis strat\'egia az, hogy v\'arunk az $\eta_{j+1}$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o megjelen\'es\'ere, 
\'es ut\'ana alkalmazzuk az optim\'alis strat\'egi\'at. Mivel
$\eta_{j+1}\ge k_n$, az optim\'alis strat\'egia ebben az 
esetben az $\eta_{j+1}$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
megjelen\'ese ut\'ani azonnali meg\'all\'as. Ezt \'ugy 
is megfogalmazhatjuk ebben az esetben, hogy megv\'arjuk az 
els\H{o} olyan $\eta_l$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi
v\'altoz\'o megjelen\'es\'et, amelynek \'ert\'eke 
legal\'abb $k_n$. Backward indukci\'oval bel\'atjuk, hogy 
ilyen az optim\'alis strat\'egia $\eta_j=k$ eset\'en minden 
$k\le k_n-1$ sz\'amra. Val\'oban, adva egy $k<k_n-1$ sz\'am, 
tegy\"uk fel, hogy ez az \'all\'{\i}t\'as igaz minden 
$\bar k>k$ sz\'amra. A 3.3 lemma eredm\'enyeib\H{o}l 
k\"ovetkezik, hogy $q'(k)\ge q(k)$, ha $k\le k_n-1$, ami 
azt jelenti, hogy ebben az esetben el\H{o}ny\"osebb az, ha 
nem \'all\'{\i}tjuk meg a Markov l\'anc megfigyel\'es\'et 
az $\eta_j$ id\H{o}pontban, hanem v\'arunk az $\eta_{j+1}$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o megjelen\'es\'ere, 
\'es azut\'an fejezz\"uk be a Markov l\'anc 
megfigyel\'es\'et. Akkor viszont a legel\H{o}ny\"osebb 
strat\'egia az, ha v\'arunk az $\eta_{j+1}$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o megjelen\'es\'ere, 
\'es ha $\eta_{j+1}=l$, akkor az ehhez az esem\'enyhez 
tartoz\'o optim\'alis strat\'egi\'at k\"ovetj\"uk. Innen az
indukci\'os feltev\'es alapj\'an k\"ovetkezik, hogy a 
3.4. lemm\'aban le\'{\i}rt strat\'egia az optim\'alis.

Szint\'en indukci\'oval l\'atjuk be, hogy $k\le k_n-1$ eset\'en 
a (3.4) formula adja meg az optim\'alis strat\'egia siker\'enek 
a (felt\'eteles) val\'osz\'{\i}n\H{u}s\'eg\'et. Tegy\"uk fel, 
hogy tudjuk ezt az \'all\'{\i}t\'ast minden olyan $\bar k$ sz\'amra, 
amelyre $k<\bar k\le k_n-1$. Ekkor, ha $s(l)$-lel jel\"olj\"uk 
a siker felt\'eteles val\'osz\'{\i}n\H{u}s\'eg\'et az 
optim\'alis strat\'egia eset\'en az $\eta_{j+1}=l$ felt\'etel 
teljes\"ul\'ese eset\'en, akkor azt kapjuk, hogy
$$
\align
s(k)&=\sum_{l=k+1}^n\frac k{(l-1)l}s(l)=\sum_{l=k+1}^{k_n-1}
\(\frac k{(l-1)}-\frac kl\)
\frac {k_n-1}n\(\frac1{k_n-1}+\frac1{k_n}+\cdots+\frac1{n-1}\)\\
&\qquad +\sum_{l=k_n}^n\frac k{(l-1)l}\cdot \frac ln \\
&=\[\(\frac kk-\frac k{k_n-1}\)\frac{k_n-1}n+\frac kn\]
\(\frac1{k_n-1}+\frac1{k_n}+\cdots+\frac1{n-1}\) \\
&=\frac {k_n-1}n\(\frac1{k_n-1}+\frac1{k_n}+\cdots+\frac1{n-1}\),
\endalign
$$
\'es ezt kellett bel\'atni.

\medskip\noindent
Megadtuk az optim\'alis strat\'egi\'at a v\'alogat\'os menyasszony 
probl\'em\'aj\'aban, \'es ki\-sz\'a\-mol\-tuk a siker 
val\'osz\'{\i}n\H{u}s\'eg\'et is. Nem neh\'ez bel\'atni, hogy 
$n\to\infty$ eset\'en $k_n\sim\frac ne$, \'es a siker 
val\'osz\'{\i}n\"us\'ege az $\frac1e$ sz\'amhoz tart.

\medskip
R\'at\'er\"unk az \'altal\'anos Markov l\'ancok optim\'alis 
meg\'all\'{\i}t\'as\'anak probl\'em\'aj\'ara ismert 
nyerem\'enyf\"uggv\'eny eset\'en. El\H{o}sz\"or 
megfogalmazzuk a feladatot.

\medskip\noindent
{\bf Markov l\'ancok optim\'alis meg\'all\'{\i}t\'as\'anak 
probl\'em\'aja.} {\it Legyen adva egy \'ert\'ekeit egy $X$ 
\'allapott\'eren felvev\H{o} valamely $(\Omega,\Cal A,P)$ 
val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n definini\'alt 
$X_0(\oo)$, $X_1(\oo)$,\dots Markov l\'anc ismert $p(x,y)$, 
$x,y\in X$, \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel, \'es 
egy szint\'en ismert, korl\'atos $f(u)$, $u\in X$, 
nyerem\'enyf\"uggv\'eny az $X$ t\'eren. Tekints\"unk egy 
olyan $p(x,y)$ \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel 
rendelkez\H{o} $X_0(\oo),X_1(\oo),\dots$ Markov l\'ancot,
amely egy r\"ogz\'{\i}tett $x\in X$ pontb\'ol indul, 
azaz $P(X_0(\oo)=x)=1$, \'es tekints\"uk e Markov l\'anc 
$f(X_{\tau(\oo)}(\oo))$ nyerem\'eny\'et a Markov l\'anc 
minden lehets\'eges $\tau(\oo)$  meg\'all\'asi sza\-b\'a\-lya
eset\'en. Ha nem defini\'altuk a $\tau(\oo)<\infty$ sz\'amot 
egy $\oo$ pontban, amit \'ugy is megfogalmazhatunk, hogy 
$\tau(\oo)=\infty$, akkor definici\'o szerint 
$f(X_{\tau(\oo)}(\oo))=0$. Sz\'am\'{\i}tsuk ki a 
$v(x)=\supp_\tau E_x f(X_{\tau(\oo)}(\oo))$ mennyis\'eget, 
ahol a szupr\'emumot a Markov l\'anc \"osszes lehets\'eges 
$\tau$ meg\'all\'asi szab\'aly\'ara vessz\"uk. 
Hat\'arozzunk meg egy optim\'alis $\tau$ meg\'all\'asi 
szab\'alyt, amelyre $E_x f(X_{\tau(\oo)}(\oo))=v(x)$,
felt\'eve, hogy ilyen $\tau$ meg\'all\'asi szab\'aly 
l\'etezik. Ha ilyen meg\'all\'asi szab\'aly nem l\'etezik, 
akkor tal\'aljunk minden $\e>0$ sz\'amra olyan $\tau$
$\e$-optim\'alis meg\'all\'asi szab\'alyt, amelyre
$E_x f(X_{\tau(\oo)}(\oo))\ge v(x)-\e$.}

\medskip
A most megfogalmazott probl\'ema megfogalmaz\'as\'aban szerepelt 
a meg\'all\'asi szab\'aly fogalma. Ezt a fogalmat bevezett\"uk 
a k\"onyv 2. fejezet\'enek ismertet\'es\'eben. De ott ezt a 
fogalmat csak id\H{o}ben folytonos sztochasztikus folyamatok
eset\'eben defini\'altuk. A teljess\'eg kedv\'e\'ert itt 
megadjuk e fogalom diszkr\'et id\H{o}re vonatkoz\'o 
term\'eszetes meg\-fe\-le\-l\H{o}\-j\'et.

\medskip\noindent
{\bf A meg\'all\'asi szab\'aly fogalm\'anak definici\'oja.}\/ 
{\it Legyen adva $\Cal F_n$, $n=0,1,\dots$, $\sigma$-algebr\'aknak  
nem-negat\'{\i}v eg\'esz sz\'amokkal indexezett n\"ovekv\H{o} 
csal\'adja, azaz legyen $\Cal F_m\subset\Cal F_n$, ha $m\le n$, 
\'es legyenek ezek a $\sigma$-algebr\'ak r\'esz $\sigma$-algebr\'ai 
egy $(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi mez\H{o} 
$\Cal A$ $\sigma$-algebr\'aj\'anak. Egy nem-negat\'{\i}v 
eg\'esz \'ert\'ekeket felvev\H{o} $\tau$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'ot meg\'all\'asi szab\'alynak nevez\"unk
az $\Cal F_n$, $n=0,1,\dots$, $\sigma$-algebra rendszerre 
n\'ezve, ha minden $n\ge0$ eg\'esz sz\'amra 
$\{\tau=n\}\in\Cal F_n$.  Megengedj\"uk azt is, hogy a $\tau$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o ne legyen minden\"utt 
de\-fi\-ni\-\'al\-va, azaz lehets\'eges az is, hogy 
$P(\tau<\infty)<1$.

Legyen adva egy $X_n$, $n=0,1,\dots$, sztochasztikus folyamat 
egy $(\Omega,\Cal A,P)$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi 
mez\H{o}n. Azt mondjuk, hogy egy nem-negat\'{\i}v eg\'esz 
\'ert\'ekeket felvev\H{o} $\tau$ val\'osz\'{\i}n\H{u}s\'egi 
v\'altoz\'o meg\'all\'asi szab\'aly erre a sztochasztikus 
folyamatra n\'ezve, ha az meg\'all\'asi szab\'aly az 
$\Cal F_n=\sigma(X_m,\,m\le n)$, $n=0,1\dots$, n\"ovekv\H{o} 
$\sigma$-algebra csal\'adra n\'ezve.}

\medskip
A Markov l\'ancoknak e fejezetben ismertetett fogalm\'at fogjuk
haszn\'alni, azaz nem k\"ovetelj\"uk meg a 
$\summ_{y\in X}p(x,y)=1$, hanem csak a
$\summ_{y\in X}p(x,y)\le1$ rel\'aci\'o teljes\"ul\'es\'et 
minden $x\in X$ pontra. A k\'es\H{o}bb t\'argyaland\'o 
eredm\'enyeket lehets\'eges \'altal\'anos\'{\i}tani a 
szint\'en defini\'alt $(X_n,\Cal F_n)$, $n=0,1,\dots$, 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'es $\sigma$-algebra 
p\'arokb\'ol \'all\'o Markov l\'an\-cok\-ra is. Itt \'es a 
tov\'abbiakban $E_x$ \'es $P_x$ egy olyan Markov l\'anc 
eset\'en fog v\'arhat\'o \'ert\'eket \'es 
val\'osz\'{\i}n\H{u}s\'eget jel\"olni, amely egy 
val\'osz\'{\i}n\H{u}s\'eggel az $x$ pontb\'ol indul.

Az el\H{o}bb megfogalmazott feladat megold\'as\'aban fontos 
szerepet j\'atszanak az \'ugy\-ne\-ve\-zett excessz\'{\i}v 
f\"uggv\'enyek. A k\"onyv els\H{o} fejezet\'enek 
ismertet\'es\'eben bevezett\"uk ezt a fogalmat egy 
speci\'alis esetben. Most defini\'aljuk ezt \'altal\'anos
Markov l\'ancok eset\'eben is.

\medskip\noindent
{\bf Excessz\'{\i}v f\"uggv\'enyek definici\'oja.} {\it 
Legyen $p(x,y)$, $x,y\in X$, egy az \'ert\'ekeit az $X$ 
\'allapott\'eren felvev\H{o} Markov l\'anc 
\'atmenetval\'osz\'{\i}n\H{u}s\'egf\"uggv\'enye.
Defini\'aljuk azt az ezen $p(x,y)$ 
\'atmenetval\'osz\'{\i}n\H{u}s\'egf\"uggv\'enyhez tartoz\'o 
$P$ lek\'epez\'est, amely egy az $X$ t\'eren defini\'alt 
$f(x)$ f\"uggv\'enynek egy szint\'en az $X$ t\'eren 
\'ertelmezett $Pf$ f\"uggv\'enyt feleltet meg a 
$Pf(x)=\summ_{y\in X}p(x,y)f(y)$, $x\in X$, k\'eplet 
seg\'{\i}ts\'eg\'evel. Egy az $X$ t\'eren defini\'alt 
$f(x)$, $x\in X$, f\"uggv\'eny excessz\'{\i}v (a $p(x,y)$
\'atmenetval\'osz\'{\i}n\H{u}s\'egekre n\'ezve), ha $f(x)\ge0$,
\'es $f(x)\ge Pf(x)$ minden $x\in X$ pontra.}

\medskip
Mint k\'es\H{o}bb be fogjuk bizony\'{\i}tani fogjuk, ha a 
nyerem\'enyf\"uggv\'eny excessz\'{\i}v, akkor az optim\'alis 
meg\'all\'asi szab\'aly a $\tau(\oo)\equiv0$  azonnali 
meg\'all\'as, b\'armely $x$ pontb\'ol indultunk ki. Ez 
heurisztikus szinten k\"onnyen magyar\'azhat\'o. Ugyanis az 
$f(x)\ge Pf(x)$ egyenl\H{o}tlens\'eg azt jelenti, hogy nem 
\'erdemes a l\'ep\'eseket k\'es\H{o}bbre halasztani, az 
$f(x)\ge0$ egyenl\H{o}tlens\'eg pedig azt, hogy nem \'erdemes 
a soha meg nem \'all\'as strat\'egi\'aj\'at v\'a\-lasz\-ta\-ni. 
Annak \'erdek\'eben, hogy j\'ol tudjunk dolgozni \'erdemes 
megadni az excessz\'{\i}v f\"uggv\'enyek egy j\'o 
jellemz\'es\'et. 

Az els\H{o} fejezet ismertet\'es\'eben egy speci\'alis Markov 
l\'anc eset\'eben fel\'{\i}rtuk az excessz\'{\i}v 
f\"uggv\'enyeket $f(x)=G\varphi(x)+C$ alakban, ahol 
$G=\summ_{n=0}^\infty P^n\varphi$, $\varphi(x)=f(x)-Pf(x)\ge0$ 
minden $x\in X$ pontban, \'es $C\ge0$ alkalmas konstans. 
Az \'altal\'anos esetben az excessz\'{\i}v f\"uggv\'enyeket
kiss\'e m\'odos\'{\i}tott form\'aban fogjuk fel\'{\i}rni.
Ennek \'erdek\'eben defini\'aljuk a $G_a$ oper\'atort minden 
$0<a<1$ sz\'amra \'es korl\'atos $\varphi$ f\"uggv\'enyre a
$$
G_a\varphi(x)=\varphi(x)+aP\varphi(x)+a^2P^2\varphi(x)+\cdots \tag3.5
$$
k\'eplet seg\'{\i}ts\'eg\'evel, \'es vizsg\'alni fogjuk ennek 
viselked\'es\'et $a\to1$ eset\'en. Ehhez hasonl\'o m\'odszert 
(egy $0<a<1$ param\'eter bevezet\'es\'et, majd az $a\to1$
hat\'ar\'atmenet alkalmaz\'as\'at) gyakran haszn\'alj\'ak a 
Markov folyamatok elm\'elet\'eben.

Adva egy korl\'atos $f(x)$ f\"uggv\'eny \'es egy $0<a<1$ 
sz\'am, defini\'aljuk a $\varphi_a(x)=f(x)-aPf(x)$ f\"uggv\'enyt. 
Nem neh\'ez bel\'atni, hogy  $f(x)=G_a\varphi_a(x)$ minden 
$x\in X$ pontban. Ezen azonoss\'ag igazol\'as\'ahoz az 
$a^nP^n\varphi(x)=a^n P^n f(x)-a^{n+1}P^{n+1}f(x)$ azonoss\'agot
adjuk \"ossze minden $n=0,1,2,\dots$ sz\'amra. Ha a korl\'atos 
$f(x)$ f\"uggv\'eny excessz\'{\i}v, akkor $\varphi_a(x)\ge0$ 
minden $x\in X$ pontban. Ezen k\'et rel\'aci\'o 
seg\'{\i}ts\'eg\'evel bel\'atjuk a k\"ovetkez\H{o} lemm\'at az 
excessz\'{\i}v f\"uggv\'enyek tulajdons\'agair\'ol.

\medskip\noindent
{\bf 3.5. Lemma.} {\it Legyen adva egy $X_0(\oo),X_1(\oo),\dots$ 
Markov l\'anc egy $X$ t\'eren valamely $p(x,y)$, $x,y\in X$, 
\'atmenetval\'osz\'{\i}n\H{u}s\'egekkel \'es egy $f(x)$ 
korl\'atos, excessz\'{\i}v f\"uggv\'eny ezen az $X$ t\'eren. 
Tegy\"uk fel, hogy a Markov l\'anc az $x$ pontb\'ol indul, 
azaz $P(X_0(\oo)=x)=1$. Ekkor a Markov l\'anc tetsz\H{o}leges 
$\tau$ meg\'all\'asi szab\'aly\'ara 
$f(x)\ge E_x f(X_{\tau(\oo)}(\oo))$, s\H{o}t ha $\tau_1$ \'es 
$\tau_2$ k\'et olyan meg\'all\'asi szab\'aly, amelyekre 
$\tau_1(\oo)\le\tau_2(\oo)$ minden $\oo\in\Omega$ pontban, akkor
$E_x f(X_{\tau_1(\oo)}(\oo))\ge E_x f(X_{\tau_2(\oo)}(\oo))$. 

V\'eve az $X$ halmaz egy tetsz\H{o}leges $A\subset X$ 
r\'eszhalmaz\'at \'es egy tetsz\H{o}leges $x\in X$ pontb\'ol 
kiindul\'o $X_0(\oo),X_1(\oo),\dots$ Markov l\'ancot, 
defini\'alhatjuk azt a tov\'abbiakban $\tau_A$-val jel\"olt 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot, amelynek \'ert\'eke 
az a legkisebb (az $\oo$ pontt\'ol f\"ugg\H{o}) $n$  
nem-negat\'{\i}v eg\'esz sz\'am, amelyre $X_n(\oo)\in A$. Ekkor
$\tau_A(\oo)$ a Markov l\'anc meg\'all\'asi szab\'alya. Ha 
$f(x)$ korl\'atos, excessz\'{\i}v f\"uggv\'eny, akkor 
$h_A(x)=E_x f(X_{\tau_A(\oo)}(\oo))$, $x\in X$, szint\'en 
korl\'atos, excessz\'{\i}v f\"uggv\'eny.}

\medskip\noindent
{\it A 3.5. lemma bizony\'{\i}t\'asa.}\/ A bizony\'{\i}t\'asban 
fel fogjuk haszn\'alni, hogy a lemm\'aban be\-ve\-ze\-tett $P$ 
oper\'ator teljes\'{\i}ti az $E_x\varphi(X_n(\oo))=P_n\varphi(x)$ 
azonoss\'agot minden $n=0,1,\dots$ indexre \'es korl\'atos 
$\varphi(\cdot)$ f\"uggv\'enyre. Ez\'ert minden $0<a<1$
sz\'amra \'es korl\'atos \'es az $X$ t\'eren defini\'alt 
korl\'atos $f(x)$ f\"uggv\'enyre
$$
f(x)=G_a\varphi_a(x)
=\varphi_a(x)+aP\varphi_a(x)+a^2P^2\varphi_a(x)+\cdots
=E_x\(\sum_{n=0}^\infty a^n \varphi_a(X_n(\oo))\),
$$
ahol $\varphi_a(x)=f(x)-aPf(x)$. N\'emi sz\'amol\'assal azt kapjuk, 
hogy minden $\tau$ meg\'all\'asi szab\'alyra, $y\in X$ pontra, 
$0<a<1$ sz\'amra \'es $N=0,1,2,\dots$ indexre 
$$
E_x \(a^{\tau(\oo)} f(X_{\tau(\oo)}(\oo))|\tau=N,\,X_N(\oo)=y\)
=\sum_{n=N}^\infty a^n E_y \varphi_a(X_n(\oo)).
$$ 
Ezt az azonoss\'agot \"osszegezve el\H{o}sz\"or az $y\in X$ 
pontokra, majd az $N=0,1,2,\dots$ sz\'amokra azt kapjuk, hogy
$$
E_xa^{\tau(\oo)} f(X_{\tau(\oo)}(\oo))
=E_x\(\sum_{n=\tau(\oo)}^\infty a^n \varphi_a(X_n(\oo))\)
$$
minden $\tau$ meg\'all\'asi szab\'alyra.

Ha az $f$ f\"uggv\'eny excessz\'{\i}v akkor $\varphi_a(x)\ge0$ 
minden $0<a<1$ sz\'amra,  \'es $x\in X$ pontra. Ez\'ert a fenti 
rel\'aci\'okb\'ol k\"ovetkezik, hogy 
$f(x)\ge E_xa^{\tau(\oo)} f(X_{\tau(\oo)})$, \'es
$E_xa^{\tau_1(\oo)(\oo)} f(X_{\tau_1(\oo)}(\oo))\ge 
E_xa^{\tau_2(\oo)} f(X_{\tau_2(\oo)})$, ha 
$\tau_1(\oo)\le\tau_2(\oo)$ minden $0<a<1$ sz\'amra. Alkalmazva 
az $a\to1$ hat\'ar\'atmenetet megkapjuk a lemma els\H{o} 
paragrafus\'anak \'all\'{\i}t\'asait.

Annak \'erdek\'eben, hogy bel\'assuk a lemma utols\'o 
\'all\'{\i}t\'as\'at is, defini\'aljuk azt a $\tau'_A(\oo)$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot, amelynek \'ert\'eke 
az a legkisebb  $n\ge1$ sz\'am, amelyre $X_n(\oo)\in A$. 
Ez a $\tau'_A(\oo)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
szint\'en a Markov l\'anc meg\'all\'asi szab\'alya, \'es mivel
$\tau'_A(\oo)\ge\tau_A(\oo)$ minden $\oo\in\Omega$ pontban 
ez\'ert a lemma m\'ar bebizony\'{\i}tott r\'esze alapj\'an
egy korl\'atos, excessz\'{\i}v $f(\cdot)$ f\"uggv\'enyre  
$E_x f(X_{\tau_A(\oo)}(\oo))\ge E_x f(X_{\tau_A'(\oo)}(\oo))$. 
M\'asr\'eszt $E_x f(X_{\tau_A(\oo)}(\oo))=h_A(x)$, \'es 
$$
E_x f(X_{\tau'_A(\oo)}(\oo))
=\summ_{y\in A}p(x,y)E_y f(X_{\tau_A(\oo)}(\oo))
=\summ_{y\in X}p(x,y) h(y)=Ph_A(x).
$$ 
Ez\'ert a fenti egyenl\H{o}tlens\'egb\H{o}l k\"ovetkezik, 
hogy $h_A(x)\ge Ph_A(x)$ minden $x\in X$ pontban. A $h_A(x)\ge0$
egyenl\H{o}tlens\'eg nyilv\'anval\'o. Ez\'ert $h_A(\cdot)$ 
excessz\'{\i}v f\"uggv\'eny. A 3.5. lemm\'at bel\'attuk.

\medskip
A k\"ovetkez\H{o} lemma jellemzi egy adott Markov l\'anchoz \'es 
nyerem\'enyf\"uggv\'enyhez tartoz\'o optim\'alis meg\'all\'asi 
strat\'egia nyerem\'eny\'enek v\'arhat\'o \'ert\'ek\'et.

\medskip\noindent
{\bf 3.6. Lemma.} {\it R\"ogz\'{\i}ts\"uk egy Markov l\'anc 
$p(x,y)$, $x,y\in X$, \'atmenetval\'osz\'{\i}n\H{u}s\'egeit 
\'es egy $f(x)$, $x\in X$, korl\'atos nyerem\'enyf\"uggv\'enyt
ezen a t\'eren. Vegy\"unk minden $x\in X$ pontra egy $x$ 
pontb\'ol kiindul\'o, \'es $p(x,y)$ 
\'atmenetval\'osz\'{\i}n\H{u}s\'egekkel rendelkez\H{o} 
$X_0(\oo),X_1(\oo),\dots$, $P(X_0(\oo)=x)=1$, Markov 
l\'ancot, \'es tekints\"uk az $f(x)$ 
nye\-re\-m\'eny\-f\"ugg\-v\'eny\-hez tartoz\'o 
nyerem\'eny v\'arhat\'o \'ert\'ek\'enek a szupr\'emum\'at 
az \"osszes lehets\'eges meg\'all\'as eset\'en, azaz a
$v(x)=\supp_\tau E_x f(X_{\tau(\oo)}(\oo))$ f\"uggv\'enyt, 
ahol a szupr\'emumot a Markov l\'anc \"osszes lehets\'eges 
$\tau$ meg\'all\'asi szab\'aly\'ara vessz\"uk. Az \'{\i}gy 
defini\'alt $v(x)$ f\"uggv\'eny az $f(x)$ f\"ugg\-v\'enyt 
majoriz\'al\'o minim\'alis excessz\'{\i}v f\"uggv\'eny, 
azaz $v(x)\ge f(x)$ minden $x\in X$ pontban, $v(x)$ 
excessz\'{\i}v f\"uggv\'eny, \'es ha $h(x)$ olyan 
excessz\'{\i}v f\"uggv\'eny, amelyre $h(x)\ge f(x)$
minden $x\in X$ pontban, akkor $h(x)\ge v(x)$ minden 
$x\in X$ pontban.}  

\medskip\noindent
{\it Megjegyz\'es.}\/ Nem mag\'at\'ol \'ertet\H{o}d\H{o}, 
hogy egy korl\'atos $f(x)$ f\"uggv\'enyre l\'etezik egy 
azt majoriz\'al\'o minim\'alis excessz\'{\i}v f\"uggv\'eny. 
Az, hogy ilyen f\"uggv\'eny l\'etezik a lemma egyik 
k\"ovetkezm\'enye.

\medskip\noindent
{\it A 3.6. lemma bizony\'{\i}t\'asa.}\/ Az nyilv\'anval\'o, 
hogy $v(x)\ge f(x)$, \'es $v(x)\ge0$. (Ez ut\'obbi 
\'all\'{\i}t\'as az\'ert igaz, mert ha azt a $\tau$
meg\'all\'asi szab\'alyt alkalmazzuk, hogy sehol sem \'allunk 
meg, akkor nyerem\'eny\"unk \'ert\'eke 0. Annak \'erdek\'eben, 
hogy bel\'assuk a $v(x)\ge Pv(x)$ egyenl\H{o}tlens\'eget 
defini\'aljunk minden $\e>0$ sz\'amra \'es $y\in X$ pontra
olyan egy $y$ pontb\'ol kiindul\'o Markov l\'ancra vonatkoz\'o
$\tau_y(\oo)=\tau_{y,\e}(\oo)$ meg\'all\'asi szab\'alyt, amelyre
$E_y f(X_{\tau_y(\oo)}(\oo))>v(y)-\e$. Alkalmazzuk az $x$ 
pontb\'ol kiindul\'o Markov l\'ancra azt a $\tau$ meg\'all\'asi 
szab\'alyt, hogy tesz\"unk egy l\'ep\'est, \'es ha 
$X_1(\oo)=y$, akkor az $X_1(\oo),X_2(\oo),\dots$ sorozat 
\'ert\'ekeinek figyelembe v\'etel\'evel a $\tau_y$ 
meg\'all\'asi szab\'alyt alkalmazzuk. Ekkor
$$
E_x f(X({\tau(\oo)}(\oo))=\summ_{y\in X}p(x,y)
E_y f(X_{\tau_y(\oo)}(\oo))\ge
\summ_{y\in X}p(x,y)[v(y)-\e]\ge Pv(x)-\e.
$$ 
Innen k\"ovetkezik, hogy $v(x)\ge Pv(x)-\e$, \'es mivel ez 
az \'all\'{\i}t\'as minden $\e>0$ sz\'amra igaz, $v(x)\ge Pv(x)$. 

Legyen $h(x)$ olyan excessz\'{\i}v f\"uggv\'eny, amelyre 
$h(x)\ge f(x)$. Ekkor a 3.5. lemma alapj\'an tetsz\H{o}leges 
$\tau$ meg\'all\'asi szab\'alyra 
$h(x)\ge E_x h(X_{\tau(\oo)}(\oo))\ge E_x f(X_{\tau(\oo)}(\oo))$. 
Ez\'ert $h(x)\ge \supp_\tau E_x f(X_{\tau(\oo)}(\oo))=v(x)$, 
ahol a szupr\'emumot az \"osszes lehets\'eges $\tau$ 
meg\'all\'asi szab\'alyra vett\"uk. A 3.6 lemm\'at
bebizony\'{\i}tottuk.

\medskip\noindent
{\it Megjegyz\'es.}\/ A 3.6. lemma alapj\'an egy v\'eges sok
elemb\H{o}l \'all\'o $X$ \'allapott\'er eset\'en a $v(x)$ 
nyerem\'enyf\"uggv\'eny \'ert\'ek\'enek meghat\'aroz\'asa 
megfogalmazhat\'o, mint a k\"ovetkez\H{o} line\'aris
programoz\'asi feladat. Oldjuk meg a $v(x)$, $x\in X$,
v\'altoz\'okra a k\"ovetkez\H{o} line\'aris 
prog\-ra\-mo\-z\'a\-si feladatot.
$$
\align
v(x)&\ge f(x) \quad \text{minden } x\in X \text{ pontban.} \\
v(x)&\ge 0 \quad \text{minden } x\in X \text{ pontban.} \\
v(x)&\ge \sum_{y\in X} p(x,y)v(y) \quad \text{minden } x\in X 
\text{ pontban.} \\
& \qquad \min\sum_{x\in X} v(x)
\endalign
$$

\medskip
A k\"ovetkez\H{o} eredm\'enyben megadunk egy optim\'alis 
\'es egy $\e$-optim\'alis meg\'all\'asi stra\-t\'e\-gi\'at.

\medskip\noindent
{\bf 3.7. Lemma.} {\it Tekints\"unk egy $X_0(\oo),X_1(\oo),\dots$ 
Markov l\'ancot egy $X$ \'allapott\'eren valamilyen $x\in X$,
 $P(X_0(\oo)=x)=1$ kezd\H{o}ponttal \'es  egy korl\'atos 
$f(x)$, $x\in X$, nye\-re\-m\'eny\-f\"ugg\-v\'ennyel. C\'elunk egy 
optim\'alis $\tau(\oo)$ meg\'all\'asi szab\'alyt tal\'alni,
 amely maximaliz\'alja az $E_xf(X_{\tau(\oo)}(\oo))$ 
v\'arhat\'o \'ert\'eket. Ennek meghat\'aroz\'asa 
\'erdek\'eben defini\'aljuk a 
$v(x)=\supp_\tau E_x f(X_{\tau(\oo)}(\oo))$ f\"uggv\'enyt, 
ahol a szupr\'emumot a Markov l\'anc \"osszes lehets\'eges 
$\tau$ meg\'all\'asi szab\'aly\'ara vessz\"uk.  
Ha az $X$ halmaz v\'eges, akkor a k\"ovetkez\H{o}
strat\'egia optim\'alis. Defini\'aljuk a k\"ovetkez\H{o} 
$A\subset X$ halmazt. $A=\{u\colon\; f(u)=v(u)\}$. Legyen 
$\tau_A(\oo)$ az a legkisebb $n\ge0$ index, amelyre 
$X_n(\oo)\in A$. Ez a $\tau_A(\oo)$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o optim\'alis meg\'all\'asi szab\'aly, azaz 
$E_x f(X_{\tau_A(\oo)}(\oo))=v(x)$.

Ha az $X$ \'allapott\'er megsz\'aml\'alhat\'o, akkor nem 
felt\'etlen\"ul van optim\'alis meg\'all\'asi szab\'aly, de 
az al\'abbi m\'odon minden $\e>0$ sz\'amra defini\'alni 
lehet egy $\e$-optim\'alis meg\'all\'asi szab\'alyt. 
Defini\'aljuk az $A_\e=\{u\colon\; u\in X,\,f(u)>v(u)-\e\}$ 
halmazt, \'es legyen $\tau_{A_\e}(\oo)$ az a legkisebb 
$n\ge0$ index, amelyre $X_n(\oo)\in A_\e$. Ez a 
$\tau_{A_\e}(\oo)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o 
$\e$-op\-ti\-m\'a\-lis meg\'all\'asi szab\'aly, azaz 
$E_x f(X_{\tau_{A_\e}(\oo)}(\oo))\ge v(x)-\e$.}

\medskip\noindent
{\it 1. megjegyz\'es.}\/ A k\"onyv p\'eld\'at mutat egy olyan
Markov l\'ancra \'es nye\-re\-m\'eny\-f\"ugg\-v\'eny\-re, 
amelyekre nincs optim\'alis meg\'all\'as. A p\'elda a 
k\"ovetkez\H{o}. Legyen az \'allapott\'er az 
$X=\{0,1,2,\dots\}$ halmaz, az 
\'atmenetval\'osz\'{\i}n\H{u}s\'egek legyenek $p(0,0)=1$, 
$p(n,0)=\frac1{n^2}$, $p(n,n+1)=1-\frac1{n^2}$ minden 
$n=1,2,\dots$ sz\'amra, \'es legyen a 
nyerem\'enyf\"uggv\'eny $f(0)=1$, \'es $f(n)=1-\frac1n$, 
$n=1,2,\dots$. Ezzel a v\'alaszt\'assal $v(u)\equiv1$, 
$A=\{0\}$, ez\'ert a $\tau_A(\oo)$ meg\'all\'asi szab\'aly
\'ugy adhat\'o meg, hogy a Markov l\'ancot akkor 
\'all\'{\i}tjuk meg, amikor az el\'eri a 0 pontot. De, mint azt 
n\'emi, a k\"onyvben is elv\'egzett sz\'amol\'as mutatja, ha a 
Markov l\'anc egy t\'avoli $n$ pontb\'ol indul, akkor ezt
a strat\'egi\'at v\'alasztva a Markov l\'ancot nagy 
val\'osz\'{\i}n\H{u}s\'eggel sehol sem \'all\'{\i}tjuk meg, \'es 
ekkor a nyerem\'eny\"unk 0. \'Altal\'anosabban, nincs olyan 
meg\'all\'asi strat\'egia, amelynek alkalmaz\'as\'aval egy $n\neq0$
pontb\'ol kiindulva el\'erhetn\'enk azt, hogy a nyerem\'eny\"unk
v\'arhat\'o \'ert\'eke 1 legyen.

\medskip\noindent
{\it 2. megjegyz\'es.}\/ Egyszer\H{u} \'es term\'eszetes 
magyar\'azata van annak, hogy mi\'ert \'erdemes egy Markov 
l\'anc optim\'alis \'es majdnem optim\'alis meg\'all\'asi
szab\'aly\'at a 3.7. lemm\'aban megadott m\'odon keresni. A
Markov tulajdons\'ag alapj\'an term\'eszetes azt v\'arni, hogy
csak az $x\in X$ pont \'ert\'ek\'et\H{o}l f\"ugg, hogy ebben 
az $x$ pontban \'erdemes-e meg\'allni. Teh\'at nincs 
jelent\H{o}s\'ege annak, hogy milyen \'utvonalon \'es hanyadik
l\'ep\'esben jutottunk oda. Akkor \'erdemes meg\'allni, ha az 
optim\'alis meg\'all\'as $v(x)$ nyerem\'enye egyenl\H{o} az 
azonnali meg\'all\'as $f(x)$ nyerem\'eny\'evel. Ellenkez\H{o}
esetben tov\'abb megy\"unk eg\'esz addig, m\'{\i}g egy 
meg\'all\'asra \'erdemes pontba, azaz egy olyan $x\in X$ pontba 
nem jutunk, amelyre $f(x)=v(x)$. Ha majdnem optim\'alis
strat\'egi\'at keres\"unk, akkor hasonl\'oan \'ervelhet\"unk.
Csak ebben az esetben m\'ar akkor is \'erdemes meg\'allni, ha
$f(x)>v(x)-\e$.

\medskip\noindent
{\it A 3.7. lemma bizony\'{\i}t\'asa.}\/ Tekints\"uk el\H{o}sz\"or 
azt az esetet, amikor az $X$ \'allapott\'er v\'eges. Tekints\"uk a 
$h(x)=E_x f(X_{\tau_A(\oo)}(\oo))$ f\"uggv\'enyt. A $\tau_A(\oo)$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o definici\'oja miatt
$h(x)=E_x v(X_{\tau_A(\oo)}(\oo))$, ez\'ert a 3.5 \'es 3.6 lemma
szerint $h(x)$ excessz\'{\i}v f\"uggv\'eny. (A 3.6 lemm\'ara
az\'ert hivatkoztunk, mert ez biztos\'{\i}tja azt, hogy $v(x)$ 
excessz\'{\i}v f\"uggv\'eny.) Azt akarjuk bel\'atni, hogy 
$h(x)\ge v(x)$ minden $x\in X$ pontban. Ehhez a 3.6 lemma 
szerint elegend\H{o} azt bel\'atni, hogy $h(x)\ge f(x)$  
minden $x\in X$ pontban. 

Tegy\"uk fel indirekt m\'odon, hogy 
$\max\limits_{x\in X}[f(x)-h(x)]=c>0$. Ekkor l\'etezik 
olyan $a\in X$ pont, amelyre $f(a)-h(a)=c>0$. Erre az 
$a$ pontra \'es a 3.7. lemm\'aban defini\'alt $A$ halmazra
$a\notin A$, ugyanis minden $x\in A$ pontra
$\tau_A(x)=0$, ez\'ert $f(x)=h(x)$. M\'asr\'eszt 
$h_1(x)=h(x)+c$ olyan excessz\'{\i}v f\"uggv\'eny, 
amelyre $h_1(x)\ge f(x)$ minden $x\in X$ pontban. Val\'oban, 
$h_1(\cdot)$ excessz\'{\i}v f\"uggv\'eny, mert egy 
excessz\'{\i}v f\"uggv\'eny plusz egy pozit\'{\i}v konstans, 
\'es $h_1(x)\ge h(x)+[f(x)-h(x)]=f(x)$ minden $x\in X$ 
pontban. Ebb\H{o}l k\"ovetkezik, hogy $h_1(x)\ge v(x)$
minden $x\in X$ pontban, speci\'alisan $h_1(a)\ge v(a)$. De
$h_1(a)=h(a)+[f(a)-h(a)]=f(a)$. Ez\'ert $f(a)=h_1(a)\ge v(a)$, 
ahonnan $f(a)=v(a)$, \'es $a\in A$ a 3.7. lemm\'aban 
defini\'alt $A$ halmazra. \'Igy az a felt\'etelez\'es,
hogy l\'etezik olyan $x\in X$ pont, amelyre $h(x)<f(x)$ 
ellentmond\'asra vezetett, ez\'ert $f(x)\le h(x)$ minden 
$x\in X$ pontban.

A lemma m\'asodik fel\'et, amikor az $X$ \'allapott\'er 
tartalmazhat megsz\'aml\'alhat\'oan v\'egtelen sok pontot 
hasonl\'oan bizony\'{\i}tjuk. Ebben az esetben a 
$h(x)=E_x v(X_{\tau_A(\oo)}(\oo))$ f\"uggv\'enyt tekintj\"uk 
(teh\'at a $v(\cdot)$ \'es nem az $f(\cdot)$ f\"uggv\'ennyel 
dolgozunk), \'es ez a f\"uggv\'eny hasonl\'oan az el\H{o}z\H{o} 
r\'eszben tekintett esethez excessz\'{\i}v. Elegend\H{o} azt 
bel\'atni, hogy $h(x)\ge f(x)$ minden $x\in X$ pontban, mert 
innen k\"ovetkezik, hogy $h(x)\ge v(x)$ minden $x\in X$ pontban, 
\'es a $\tau_{A_\e}$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o 
definici\'oja szerint
$$
E_x f(X_{\tau_{A_\e}(\oo)}(\oo))\ge
E_x[ v(X_{\tau_{A_\e}(\oo)}(\oo))-\e]=h(x)-\e\ge v(x)-\e
$$ 
minden $x\in X$ pontban.

Tegy\"uk fel indirekt m\'odon, hogy $\supp_{x\in X}[f(x)-h(x)]=c>0$.
Ekkor l\'etezik olyan $a\in X$ pont, amelyre $f(a)-h(a)>0$, 
\'es $f(a)-h(a)>c-\e$. Minden $x\in A_\e$ pontra 
$\tau_{A_\e}(\oo)\equiv0$, ez\'ert 
$h(x)=E_xv(\tau_{A_\e}(\oo))=v(x)\ge f(x)$. Mivel $h(a)<f(a)$ 
innen k\"ovetkezik, hogy $a\notin A_\e$. M\'asr\'eszt 
$h(x)+c\ge f(x)$, \'es $h(x)$ excessz\'{\i}v
f\"uggv\'eny, ahonnan k\"ovetkezik, hogy $h(x)+c\ge v(x)$. 
Ez\'ert $f(a)>h(a)+c-\e\ge v(a)-\e$, teh\'at $a\in A_\e$. 
Felt\'etelez\'es\"unk ellentmond\'ashoz vezetett, ez\'ert 
$f(x)\le h(x)$ minden $x\in X$ pontban. A 3.7. lemm\'at 
bebizony\'{\i}tottuk.

\medskip
A k\"onyv k\'et p\'eld\'at mutat a fenti eredm\'enyek 
alkalmaz\'as\'ara. Az els\H{o} p\'elda a v\'alogat\'os
menyasszony probl\'em\'aja. A k\"onyv azt t\'argyalja, hogy 
hogyan lehet megtal\'alni az optim\'alis strat\'egi\'at ebben 
a feladatban a kor\'abbi eredm\'enyek seg\'{\i}ts\'eg\'evel.

A fejezet kor\'abbi r\'esz\'eben a szerz\H{o}k 
megmutatt\'ak, hogy a feladat visszavezethet\H{o} a 
k\"ovetkez\H{o} probl\'em\'ara. Legyen adva egy
$\eta_1,\eta_2,\dots$ Markov l\'anc az 
$X=\{1,2,\dots,n\}$ \'allapott\'eren 
$p(k,l)=P(\eta_{j+1}=l|\eta_j=k)=\frac k{(l-1)l}$ 
\'atmenetval\'osz\'{\i}n\H{u}s\'egekkel, ha $1\le k<l\le n$, 
\'es $p(k,l)=0$ \'atmenetval\'osz\'{\i}n\H{u}s\'egekkel 
egy\'ebk\'ent. Legyen adva e Markov l\'anc $X$ 
\'allapotter\'en az $f(k)=\frac kn$, $1\le k\le n$,
nyerem\'enyf\"uggv\'eny, \'es hat\'arozzuk meg az 
optim\'alis meg\'all\'asi szab\'alyt \'es a
hozz\'atartoz\'o nyerem\'enyf\"uggv\'enyt.

E feladat megold\'as\'ahoz ki kell sz\'amolnunk az 
$f(k)$, $1\le k\le n$, f\"uggv\'enyt majoriz\'al\'o 
legkisebb $v(k)$, $1\le k\le n$, excessz\'{\i}v f\"uggv\'enyt. 
Az, hogy $v(k)$, $1\le k\le n$, az $f(k)$ f\"uggv\'enyt 
majoriz\'al\'o excessz\'{\i}v f\"uggv\'eny azt jelenti, hogy
$$
\align
v(k)&\ge \frac kn, \quad 1\le k\le n,\\
v(k)&\ge \sum_{l=k+1}^n \frac k{(l-1)l}v(l), \quad 1\le k\le n-1.
\endalign
$$
Nem neh\'ez bel\'atni, hogy a k\'{\i}v\'ant tulajdons\'ag\'u, 
minim\'alis $v(\cdot)$ f\"uggv\'enyt a
$$
v(n)=1,\quad v(k)=\max\left\{ \frac kn, k\sum_{l=k+1}^n
\frac{v(l)}{(l-1)l}\right\}, 
\quad 1\le k\le n-1,
$$
k\'eplettel lehet megadni. Innen backward indukci\'oval 
k\"ovetkezik, hogy $v(k)=\frac kn$, ha $k\ge k_n$, a (3.3) 
formul\'aban defini\'alt $k_n$ sz\'ammal, \'es 
$v(k)=k\summ_{l=k+1}^n\frac{v(l)}{(l-1)l}$, ha $k<k_n$.
Innen a 3.4. lemma bizony\'{\i}t\'as\'anak v\'eg\'en 
v\'egzett sz\'amol\'as mutatja, hogy a $v(k)$ f\"uggv\'enyt 
a $k<k_n$ sz\'amokra a (3.4) k\'eplettel lehet megadni. 
V\'eg\"ul tudjuk, hogy az optim\'alis strat\'egi\'at \'ugy
adhatjuk, meg, hogy az  els\H{o} olyan $k$ sz\'am 
megjelen\'es\'en\'el kell meg\'allni, amelyre $v(k)=f(k)$. 
Ez jelen esetben azt jelenti, hogy akkor \'allunk meg, ha 
a Markov l\'anc megl\'atogatta a $\{k_n,k_n+1,\dots,n\}$ 
halmazt.

\medskip
A m\'asik itt t\'argyalt probl\'ema a k\"ovetkez\H{o}. 
Tekints\"uk az $X=\{0,1,\dots,n\}$ halmazt, \'es 
rajta egy bolyong\'ast a hat\'aron elnyel\H{o} falakkal, 
azaz tekints\"unk egy Markov l\'ancot a k\"ovetkez\H{o}
\'atmenetval\'osz\'{\i}n\H{u}s\'egekkel. Legyen 
$p(j,j-1)=p(j,j+1)=\frac12$, ha $1\le j\le n-1$, \'es 
$p(0,0)=1$, $P(n,n)=1$. Legyen adva egy $f(j)$, 
$1\le j\le n-1$,  nyerem\'enyf\"uggv\'eny az $X$ halmazon, 
\'es sz\'am\'{\i}tsuk ki az optim\'alis meg\'all\'asi 
strat\'egi\'at ebben a modellben.

Ezt a feladatot a k\"ovetkez\H{o} m\'odon oldhatjuk meg a 
k\"onyv eredm\'enyeinek ismeret\'eben. Azt kell meghat\'arozni,
hogy melyek az e feladatban szerepl\H{o} Markov l\'anc
\'at\-me\-net\-va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gei szerint  
excessz\'{\i}v f\"uggv\'enyek. Egy $v(k)$, $0\le k\le n$, 
f\"uggv\'eny akkor \'es csak akkor excessz\'{\i}v ezen
\'atmenetval\'osz\'{\i}n\H{u}s\'egek szerint, ha
$\frac{v(j-1)+v(j+1)}2\le v(j)$ minden $1\le j\le n-1$ 
sz\'amra, \'es $v(j)\ge0$, ha $0\le j\le n$. Nem neh\'ez 
bel\'atni, (\'es a k\"onyvben ezt megteszik), hogy az e 
Markov l\'anchoz tartoz\'o excessz\'{\i}v f\"uggv\'enyek
megegyeznak a $\{0,1,\dots,n\}$ halmazon defini\'alt 
nem-negat\'{\i}v konk\'av f\"uggv\'enyekkel. Az eredeti 
fel\-ada\-tot \'ugy tudjuk megoldani, hogy megkeress\"uk az 
$f(\cdot)$ f\"uggv\'eny nem-negat\'{\i}v, konk\'av
burkol\'oj\'at, azaz azt a legkisebb nem-negat\'{\i}v, 
konk\'av $v(\cdot)$ f\"uggv\'enyt, amely nagyobb vagy 
egyenl\H{o} minden pontban, mint a feladatban megadott 
$f(\cdot)$ f\"uggv\'eny. Ezut\'an meg kell hat\'arozni 
az  $A=\{x\colon\;f(x)=v(x)\}$ halmazt, \'es az 
optim\'alis strat\'egia az, hogy akkor \'all\'{\i}tjuk 
meg a Markov folyamatot, amikor az el\H{o}sz\"or
megl\'atogatta ezt az $A$ halmazt.

\medskip
A kor\'abban vizsg\'alt probl\'em\'akban olyan Markov l\'ancokat 
tekintett\"unk, amelyekben az $X$ \'allapott\'er v\'eges vagy 
megsz\'aml\'alhat\'oan v\'egtelen sz\'amoss\'ag\'u, az id\H{o} 
pedig diszkr\'et, $t=0,1,2,\dots$. Term\'eszetesen felmer\"ul
a k\'erd\'es, hogy mit lehet mondani az \'altal\'anos esetben, 
amikor egy \'ert\'ekeit egy \'altal\'anos $X$ \'allapott\'erben 
felvev\H{o} Markov folyamatot tekint\"unk, \'es az id\H{o} 
folytonosan is v\'altozhat, azaz az id\H{o}pontok minden 
$t\ge0$ \'ert\'eket is felvehetnek. Az az eset, amikor az 
id\H{o} diszkr\'et, de az $X$ \'allapott\'er egy 
\'altal\'anos halmaz lehet, hasonl\'oan t\'argyalhat\'o a 
kor\'abban vizsg\'alt probl\'em\'akhoz. Ugyanez elmondhat\'o 
a folytonos idej\H{u} Markov folyamatok vizsg\'alat\'ar\'ol 
is, de ekkor sok \'uj, neh\'ez \'es a Markov folyamatok 
\'altal\'anos elm\'elet\'ehez tartoz\'o probl\'ema is 
megjelenik. Az al\'abbiakban egy speci\'alis, id\H{o}ben 
folytonos Markov folyamatot vizsg\'alunk, de ez seg\'{\i}t 
az \'altal\'anos esetben megjelen\H{o} probl\'em\'ak 
meg\'ert\'es\'eben is. A k\"ovetkez\H{o} feladatot t\'argyaljuk.

\medskip
Tekints\"unk egy 0 \'es $a$ pontokban elnyel\H{o} 
hat\'arfalakkal rendelkez\H{o}, valamely $x$, $0\le x\le a$, 
pontb\'ol kiindul\'o $W(t,\oo)$, $t\ge0$, Wiener folyamatot,
azaz egy olyan $W(t,\oo)$, $t\ge0$, szto\-chasz\-ti\-kus 
folyamatot, amely \'ugy viselkedik, mint egy Wiener folyamat 
mind\-addig, am\'{\i}g el nem \'eri a $0$ vagy $a$ hat\'arpontot, 
ut\'ana pedig \"or\"okk\'e ebben a pontban marad. Azaz, ha 
$W(T,\oo)=0$ vala\-mely $T\ge0$ id\H{o}pontban, akkor 
$W(t,\oo)=0$ minden $t\ge T$ id\H{o}pontban, \'es ha 
$W(T,\oo)=a$, akkor $W(t,\oo)=a$ minden $t\ge T$ 
id\H{o}pontban. Legyen adva egy folytonos $f(u)$, 
$0\le u\le a$, nyerem\'enyf\"uggv\'eny a $[0,a]$ 
intervallumban, \'es hat\'arozzuk meg a most defini\'alt
elnyel\H{o} hat\'arfalakkal rendelkez\H{o} Wiener folyamatnak 
azt a $\tau$ meg\'all\'asi szab\'aly\'at, amelyre az 
$E_x f(W(\tau(\oo),\oo))$ v\'arhat\'o \'ert\'ek a 
lehet\H{o} legnagyobb.

Az al\'abbi feladat vizsg\'alat\'aban kulcsszerepet j\'atszik a
k\"ovetkez\H{o} eredm\'eny.

\medskip\noindent
{\bf 3.8. Lemma.} {\it Legyen $W(t,\oo)$, $t\ge0$, egy 
valamely $x$, $0\le x\le a$, pontb\'ol kiindul\'o  Wiener 
folyamat $0$ \'es $a$ pontbeli elnyel\H{o} hat\'arfalakkal. 
Egy korl\'atos $g(u)$, $0\le u\le a$,  f\"uggv\'eny akkor 
\'es csak akkor teljes\'{\i}ti minden  $0\le x\le a$ pontra 
\'es $\tau$ meg\'all\'asi szab\'alyra a  
$g(x)\ge E_xg(W(\tau(\oo),\oo))$ egyenl\H{o}tlens\'eget, ha 
$g(\cdot)$ olyan konk\'av f\"uggv\'eny, amelyre $g(u)\ge0$ 
minden $0\le u\le a$ sz\'amra.}

\medskip
Eml\'ekeztetek arra, hogy $\tau(\oo)=\infty$ eset\'en definici\'o
szerint $g(W(\tau(\oo),\oo))=0$. A 3.8. lemma azt jelenti, hogy
az e probl\'em\'aban vizsg\'alt folytonos idej\H{u} Wiener 
folyamatban a nem-negat\'{\i}v, konk\'av f\"uggv\'enyek 
j\'atssz\'ak az excessz\'{\i}v f\"uggv\'enyek szerep\'et. A 
3.8. lemma e fejezet legnehezebben bizony\'{\i}that\'o 
eredm\'enye. A fejezet utols\'o alfejezete, a 3.8 pont ezen 
eredm\'eny bizony\'{\i}t\'as\'aval foglalkozik. A fejezet 
ismertet\'es\'enek a v\'eg\'en fogom ismertetni e 
bizony\'{\i}t\'as v\'az\'at \'es legfontosabb gondolatait.

A Wiener folyamatokkal kapcsolatos eredm\'enyek 
bizony\'{\i}t\'as\'aban fontos szerepet j\'atszik az 
al\'abbi eredm\'eny.

\medskip\noindent
{\bf 3.9. Lemma.} {\it Tekints\"unk egy valamely $[a,b]$ 
intervallum belsej\'eben lev\H{o} $x\in[a,b]$ pontb\'ol 
kiindul\'o Wiener folyamatot, \'es defini\'aljuk a 
$\tau_{a,b}$ meg\'all\'asi szab\'alyt, amelyiknek \'ert\'eke
az a legkisebb $t\ge0$ sz\'am, amelyre $W(t)=a$ vagy $W(t)=b$. 
Ekkor 
$$
P(W(\tau_{a,b}(\oo),\oo)=a)=\frac{b-x}{b-a},\quad \text{\'es} \quad
P(W(\tau_{a,b}(\oo),\oo)=b)=\frac{x-a}{b-a}.
$$
}

\medskip\noindent
{\it A 3.9. lemma bizony\'{\i}t\'asa.}\/ A lemma e k\"onyvben 
ismertetett bizony\'{\i}t\'asa azon alapul, hogy a 2. fejezet 
eredm\'enyei alapj\'an a $P(W(\tau_{a,b}(\oo))=a)$
val\'osz\'{\i}n\H{u}s\'eget megkaphatjuk, mint annak az 
1-dimenzi\'os esetben vizsg\'alt harmonikus (teh\'at 
line\'aris) f\"uggv\'enynek az $x$ helyen felvett 
\'ert\'ek\'et, amelyre $f(a)=1$, \'es  $f(b)=0$. A m\'asik 
val\'osz\'{\i}n\H{u}s\'eget hasonl\'oan sz\'amolhatjuk ki. 

\medskip
A k\"ovetkez\H{o} eredm\'enyben megfogalmazzuk a Wiener 
folyamatok optim\'alis meg\-\'all\'{\i}\-t\'a\-s\'a\-r\'ol 
sz\'ol\'o k\'erd\'esre adott v\'a\-laszt.

\medskip\noindent
{\bf 3.10. Lemma.} {\it Tekints\"unk egy a 0 \'es $a$ pontban 
elnyel\H{o}  hat\'arfalakkal rendelkez\H{o}, valamely $x$, 
$0\le x\le a$,  pontb\'ol kiindul\'o $W(t,\oo)$, $t\ge0$, 
Wiener folyamatot, \'es egy korl\'atos $f(u)$, $0\le u\le a$, 
nyerem\'enyf\"uggv\'enyt a $[0,a]$ intervallumban. 
Defini\'aljuk a $v(x)=\supp_\tau E_x f(W(\tau(\oo),\oo))$ 
f\"uggv\'enyt, ahol a szupr\'emumot ezen elnyel\H{o} 
hat\'arfalakkal rendelkez\H{o}  Wiener folyamat \"osszes 
meg\'all\'asi szab\'aly\'ara vessz\"uk. Ez a $v(x)$ 
f\"uggv\'eny az $f(x)$ f\"uggv\'eny  nem-negat\'{\i}v 
konk\'av burkol\'oja, azaz $v(x)$, $0\le x\le a$, 
olyan konk\'av f\"uggv\'eny, amelyre $v(x)\ge \max(0,f(x))$ 
minden $0\le x\le a$ sz\'amra,\'es $v(x)\le g(x)$ minden 
$0\le x\le a$ sz\'amra, ha $g(\cdot)$ olyan a $[0,a]$ 
intervallumban konk\'av f\"uggv\'eny, amelyre 
$g(x)\ge \max(0,f(x))$ minden $0\le x\le a$ sz\'amra. 

Ha az $f(x)$ nyerem\'enyf\"uggv\'eny nemcsak korl\'atos, 
hanem folytonos is, akkor az al\'abb defini\'alt $\bar\tau$ 
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o az elnyel\H{o} 
hat\'arfalakkal rendelkez\H{o} Wiener folyamatra vett 
optim\'alis meg\'all\'asi szab\'aly az $f(\cdot)$ 
nyerem\'enyf\"uggv\'ennyel, azaz ez a $\bar\tau(\oo)$ 
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'o 
meg\'all\'asi szab\'aly, \'es $v(x)=E_x f(W(\bar\tau(\oo),\oo))$.
Defini\'aljuk a $\Gamma\subset [0,a]$ halmazt a 
$\Gamma=\{x\colon\; x\in[0,a],\, f(x)=v(x)\}$
k\'eplet seg\'{\i}ts\'eg\'evel. A $\Gamma$ halmaz z\'art, 
\'es defini\'alhatjuk a 
$\bar\tau(\oo)=\min\{t\colon\; W(t,\oo)\in\Gamma\}$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ot. Ez a $\bar\tau(\oo))$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o a keresett 
optim\'alis meg\'all\'asi szab\'aly, azaz 
$v(x)=E_xf(W(\bar\tau(\oo),\oo))$.} 

\medskip\noindent
{\it Megjegyz\'es.}\/ A k\"onyv egy (egyszer\H{u}) p\'eld\'at 
mutat arra, hogy ha az $f(x)$ nye\-re\-m\'eny\-f\"ugg\-v\'eny 
nem folytonos, akkor lehets\'eges, hogy a 3.10 lemm\'aban 
defini\'alt $\bar\tau$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi 
v\'altoz\'o nem optim\'alis meg\'all\'asi szab\'aly.

\medskip\noindent
{\it A 3.10 lemma bizony\'{\i}t\'asa.}\/
A bizony\'{\i}t\'as sok hasonl\'os\'agot mutat a feladat 
diszkr\'et megfelel\H{o}j\'enek a bizony\'{\i}t\'as\'aval.

El\H{o}sz\"or bel\'atjuk a 3.9 lemma \'es a Wiener folyamat 
er\H{o}s Markov tulajdons\'aga seg\'{\i}ts\'eg\'evel, hogy 
$v(x)$ konk\'av f\"uggv\'eny. Ennek \'erdek\'eben, ha adva 
van egy $x$ pontb\'ol kiindul\'o Wiener folyamat elnyel\H{o} 
falakkal a 0 \'es $a$ pontban, akkor tekint\"unk 
tetsz\H{o}leges olyan $p$ \'es $q$ pontokat, amelyekre 
$0\le p\le x\le q\le a$, \'es defini\'alunk a $p$ illetve 
$q$ pontb\'ol kiindul\'o elnyel\H{o} fal\'u hat\'arral 
rendelkez\H{o} Wiener folyamatokhoz olyan $\tau_p$ \'es 
$\tau_q$ meg\'all\'asi szab\'alyt, amelyekre 
$E_p f(W(\tau_p(\oo),\oo))\ge v(p)-\e$, 
\'es $E_q f(W(\tau_q(\oo),\oo))\ge v(q)-\e$ valamely 
el\H{o}re r\"ogz\'{\i}tett kis $\e>0$ sz\'ammal. Defini\'aljuk 
egy $x$ pontb\'ol indul\'o elnyel\H{o} falakkal rendelkez\H{o}
Wiener folyamatra a k\"ovetkez\H{o} $\tau(\oo)$ meg\'all\'asi 
szab\'alyt. Elind\'{\i}tjuk a Wiener folyamatot az $x$ pontb\'ol, 
\'es megv\'arjuk, hogy az vagy a $p$ vagy a $q$ pontot el\'erje.
Ha a $p$ pontot \'eri el el\H{o}bb, akkor a Wiener folyamat 
$p$ pontb\'ol kiindul\'o darabj\'ara a $\tau_p$, ha a $q$ 
pontot \'eri el el\H{o}bb akkor a Wiener folyamat $q$ 
pontb\'ol kiindul\'o darabj\'ara $\tau_q$ meg\'all\'asi 
szab\'alyt alkalmazzuk. Ekkor
$$
\align
v(x)&\ge E_xf(W(\tau(\oo),\oo))=\frac{q-x}{q-p} E_pf(W(\tau_p(\oo))
+\frac{x-p}{q-p} E_qf(W(\tau_q(\oo)) \\
&\ge \frac{q-x}{q-p}[v(p)-\e]+\frac{x-p}{q-p}[v(q)-\e]
=\frac{q-x}{q-p}v(p)+\frac{x-p}{q-p}v(q)-\e
\endalign
$$
a (3.9) lemma \'es az er\H{o}s Markov tulajdons\'ag miatt. 
Mivel ez minden $\e>0$ sz\'amra igaz, ez\'ert 
$v(x)\ge\frac{q-x}{q-p}v(p)+\frac{x-p}{q-p}v(q)$. Ez\'ert
a $v(x)$, $0\le x\le a$ f\"uggv\'eny konk\'av. M\'asr\'eszt 
$v(x)\ge0$, minden  $0\le x\le a$ sz\'amra, mert alkalmazhatjuk 
a soha meg nem \'all\'as $\tau(\oo)\equiv\infty$ strat\'egi\'aj\'at.

M\'asr\'eszt, ha $g(x)$ olyan konk\'av f\"uggv\'eny a $[0,a]$ 
intervallumban, amelyre $g(x)\ge \max(0,f(x))$ minden $0\le x\le a$ 
sz\'amra, akkor a 3.8 lemma alapj\'an
$$
g(x)\ge E_x g((W(\tau(\oo),\oo))\ge E_x f((W(\tau(\oo),\oo))
$$
minden $0\le x\le a$ pontra \'es $\tau$ meg\'all\'asi szab\'alyra. 
Ez\'ert
$$
g(x)\ge\supp_\tau  E_x f((W(\tau(\oo),\oo))=v(x)
$$ 
minden $0\le x\le a$ sz\'amra, azaz $v(x)$ az $f(x)$ 
f\"uggv\'eny nem-negat\'{\i}v konk\'av burkol\'oja.

A 3.10. lemma m\'asodik fel\'enek bizony\'{\i}t\'as\'at 
annak igazol\'as\'aval kezdj\"uk, hogy $v(x)$ folytonos 
f\"uggv\'eny. Mivel $v(x)$ konk\'av, ez\'ert ez a 
f\"uggv\'eny folytonos a $(0,a)$ ny\'{\i}lt intervallum 
minden pontj\'aban, de az intervallum v\'egpontjaiban csak 
azt tudjuk eredetileg, hogy $\limm_{x\to0} v(x)\ge v(0)$, 
\'es $\limm_{x\to a} v(x)\ge v(a)$. Ez\'ert az kell 
bel\'atni, hogy $\limm_{x\to0} v(x)\le v(0)$, \'es 
$\limm_{x\to a} v(x)\le v(a)$. Tekints\"uk a megfelel\H{o} 
\'all\'{\i}t\'ast a 0 pontban, \'es vezess\"uk be a
$c(u)=\max\limits_{0\le x\le u}f(x)$, $0\le u\le a$ 
f\"uggv\'enyt. A $c(u)$ f\"uggv\'eny folytonos. 
R\"ogz\'{\i}ts\"unk egy $0<u<a$ pontot, \'es tekints\"uk 
minden $0\le x\le u$ pontra az $x$ pontb\'ol kiindul\'o
$W(t,\oo)$ Wiener folyamatot, \'es egy $\tau$ 
meg\'all\'asi szab\'alyt erre a Wiener folyamatra. A 
3.9 lemma alapj\'an  $P_x(W(\tau(\oo))\ge u)\le \frac xu$, 
mert a $W(\tau(\oo))\ge u$ esem\'eny csak \'ugy 
k\"ovetkezhet be, ha az $x$ pontb\'ol kiindul\'o Wiener 
folyamat el\H{o}bb \'eri el az $u$ mint a 0 pontot. M\'asr\'eszt
$W(f(W(\tau(\oo),\oo))\le c(u)$, ha $\tau(\oo)\le u$, 
\'es $W(f(W(\tau(\oo),\oo))\le c(a)$ mindig. Ez\'ert
$$
E_x f(W(\tau(\oo),\oo))\le\max[c(u),0]+\frac xu\max[c(a),0]
$$
minden $\tau$ meg\'all\'asi szab\'alyra. Ez\'ert
$$
v(x)\le\max[c(u),0]+\frac xu\max[c(a),0],
$$
\'es $x\to0$ hat\'ar\'atmenettel
$$
\lim_{x\to0}v(x)\le\max[c(u),0]
$$
minden $u>0$ sz\'amra. Ezut\'an v\'eve az $u\to0$ 
hat\'ar\'atmenetet, \'es felhaszn\'alva a 
$\limm_{u\to0}c(u)=f(0)$ rel\'aci\'ot azt kapjuk, hogy
$$
\lim_{x\to0}v(x)\le\max\[\lim_{u\to0}c(u),0\]=\max[f(0),0]\le v(0).
$$
A $\limm_{x\to a} v(x)\le v(a)$ rel\'aci\'ot 
hasonl\'oan bizony\'{\i}thatjuk.

Mivel, mind $f(x)$ mind $v(x)$ folytonos f\"uggv\'eny, 
ez\'ert a $\Gamma=\{x\colon\; x\in[0,a],\, f(x)=v(x)\}$ 
halmaz z\'art, \'es a
$\bar\tau(\oo)=\min\{t\colon\; W(t,\oo)\in\Gamma\}$ 
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o j\'ol van 
defini\'alva  (jogunk volt mimimumot \'{\i}rni a 
definici\'oban), \'es meg\'all\'asi szab\'aly.
A bizony\'{\i}t\'as k\"ovetkez\H{o} l\'ep\'es\'eben azt 
mutatjuk meg, hogy
$h(x)=E_xf(W(\bar\tau(\oo),\oo))=E_xv(W(\bar\tau(\oo),\oo))$
nem-negat\'{\i}v, konk\'av f\"uggv\'eny. Az indokl\'asban 
a konk\'av f\"ugg\-v\'e\-nyek\-nek n\'eh\'any 
szeml\'eletesen nyilv\'anval\'o \'es a k\"onyv 
kieg\'esz\'{\i}t\'es\'eben bizony\'{\i}tott
tulajdons\'ag\'ara hivatkozunk.

A $h(x)$ f\"uggv\'eny megszor\'{\i}t\'asa a $\Gamma$ 
halmazra megegyezik a nem-negat\'{\i}v, konk\'av $v(x)$ 
f\"uggv\'eny \'ert\'ek\'evel. A komplementer ny\'{\i}lt 
halmaz ny\'{\i}lt intervallumok uni\'oja, \'es ezen 
intervallumok v\'egpontjai a $\Gamma$ halmaz pontjai, 
\'es lehet m\'eg v\'egpont a 0 vagy az $a$ pont, amelyek 
nem felt\'etlen\"ul elemei a $\Gamma$ halmaznak. Ha egy 
$x\notin\Gamma$ pontra $p$ \'es $q$ az $x$ pontot 
tartalmaz\'o ny\'{\i}lt intervallum v\'egpontjai, $p<q$, 
akkor a 3.9. lemma  alapj\'an 
$h(x)=\frac{q-x}{q-p}v(p)+\frac{x-p}{q-p}v(q)$, azaz a 
$h(x)$ f\"uggv\'eny a $[p,q]$ intervallumon megegyezik a 
$p$ pontban $v(p)$ \'es $q$ pontban $v(q)$ \'ert\'eket 
felvev\H{o} line\'aris f\"uggv\'ennyel. Ha az $x$ pontot 
tartalmaz\'o ny\'{\i}lt intervallum egyik v\'egpontja a 
0 vagy $a$ pont, akkor a k\'ep kiss\'e m\'odosul. Ha 
p\'eld\'aul $x$ a $[0,q]$ intervallumban van, 
$0\neq\Gamma$ \'es $q\in\Gamma$, akkor $h(x)=\frac xq v(q)$ 
\'es $h(0)=0$. (Lehets\'eges, hogy $v(0)>0$ ebben az 
esetben.) A k\"onyv kieg\'esz\'{\i}t\'es\'enek egyik
eredm\'enye alapj\'an egy ilyen tulajdons\'ag\'u $h(x)$ 
f\"uggv\'eny konk\'av, folytonos, \'es nem-negat\'{\i}v.

A bizony\'{\i}t\'ast befejezz\"uk, ha megmutatjuk, hogy 
$h(x)=v(x)$. Ennek bizony\'{\i}t\'asa hasonl\'o a 3.7. lemma 
els\H{o} fel\'enek bizony\'{\i}t\'as\'ahoz. El\'eg azt 
megmutatni, hogy $h(x)\ge f(x)$ minden $x\in[0,a]$ pontban,
mert $h(x)$ nem-negat\'{\i}v, konk\'av f\"uggv\'eny, 
ez\'ert a lemma m\'ar bebizony\'{\i}tott r\'esze alapj\'an 
innen k\"ovetkezik, hogy $h(x)\ge v(x)$ minden $x\in [0,a]$ 
pontban. M\'asr\'eszt a $h(x)$ \'es $v(x)$ f\"uggv\'enyek 
definici\'oja  alapj\'an $h(x)\le v(x)$. 

Tegy\"uk fel indirekt m\'odon, hogy 
$c=\min_{u\in[0,a]}[f(u)-h(u)]>0$. Ekkor l\'etezik 
olyan $s\in[0,a]$ pont, melyre $f(s)-h(s)=c>0$. 
Egyr\'eszt $s\notin\Gamma$, mert egy $s\in\Gamma$ 
pontb\'ol kiindul\'o Wiener folyamat eset\'eben 
$\bar\tau(\oo)\equiv0$, \'es $f(s)-h(s)=0$. M\'asr\'eszt 
$h(x)+c$ nem-negat\'{\i}v, konk\'av f\"uggv\'eny, \'es 
$h(x)+c\ge f(x)$ minden $x\in[0,a]$ pontban. Ez\'ert 
$h(x)+c\ge v(x)$ minden $x\in[a,b]$ pontban. Speci\'alisan 
$h(s)+c=f(s)\ge v(s)$, ahonnan $s\in\Gamma$, ami 
ellentmond\'as. A 3.10. lemma bizony\'{\i}t\'as\'at 
befejezt\"uk.

\medskip
Ismertetem a 3.8 lemma bizony\'{\i}t\'as\'anak legfontosabb 
gondolatait. Ez hasonl\'o elveken alapul, mint a 3.5. lemma 
bizony\'{\i}t\'asa. A 3.5. lemma \'ugy tekinthet\H{o}, mint 
a 3.8. lemma diszkr\'et idej\H{u} megfelel\H{o}je. Ennek 
bizony\'{\i}t\'as\'aban bevezett\"unk egy $P$ oper\'atort, 
amely az \'allapott\'eren defini\'alt korl\'atos 
f\"uggv\'enyek ter\'et k\'epezi \"onmag\'ara, \'es ennek, 
illetve ezen oper\'ator hatv\'anyainak a
seg\'{\i}ts\'eg\'evel defini\'altunk minden $0<a<1$
param\'eterre egy ett\H{o}l a param\'etert\H{o}l 
f\"ugg\H{o} $G_a$ oper\'atort, (l\'asd a (3.5) formul\'at), 
amely a Markov folyamatok elm\'elet\'eben haszn\'alt 
potenci\'al alkalmas m\'odos\'{\i}t\'asa. Ezen $G_a$ 
oper\'atorok seg\'{\i}ts\'eg\'evel az excessz\'{\i}v 
f\"uggv\'enyeket olyan alakban tudtuk megadni, amely 
egyszer\H{u}v\'e tette  a 3.5. lemma bizony\'{\i}t\'as\'at 
egy $a\to1$ hat\'ar\'atmenet alkalmaz\'as\'aval.

Megpr\'ob\'aljuk ezt a m\'odszert adapt\'alni folytonos 
idej\H{u} Markov folyamatok vizs\-g\'a\-la\-t\'a\-ra. Ennek 
\'erdek\'eben bevezetj\"uk a $P$ \'es $G_\alpha$
oper\'atorok term\'eszetes megfelel\H{o}it folytonos 
idej\H{u} Markov folyamatokra, \'es bebizony\'{\i}tjuk ezen 
oper\'atorok legfontosabb tulajdons\'agait. Nem tudjuk 
k\"ozvetlen\"ul adapt\'alni a diszkr\'et idej\H{u} Markov 
l\'ancok vizs\-g\'a\-la\-t\'a\-ban al\-kal\-ma\-zott 
m\'odszert, de egy hasonl\'o, b\'ar bonyolultabb elj\'ar\'as 
seg\'{\i}ts\'eg\'evel c\'elhoz \'er\"unk. Al\'abb 
r\'eszletesebben ismertetem ezt a m\'odszert.

\medskip\noindent
{\it A 3.8 lemma bizony\'{\i}t\'as\'anak v\'aza.}\/ Az, hogy a 
$g(x)\ge E_xg(W(\tau(\oo),\oo))$ 
egyen\-l\H{o}t\-len\-s\'e\-gek\-b\H{o}l (minden $0\le x\le a$ 
sz\'amra es $\tau$ meg\'all\'asi szab\'alyra) k\"ovetkezik, 
hogy $g(x)$ nem-negat\'{\i}v, konk\'av f\"uggv\'eny k\"onnyen
igazolhat\'o a 3.9. lemma seg\'{\i}ts\'eg\'evel. El\'eg minden 
$0\le x\le a$  pontra \'es olyan $[p,q]$ intervallumra, amelyre 
$x\in[p,q]\subset[0,a]$ az $x$ pontb\'ol kiindul\'o Wiener 
folyamatot \'es azt a meg\'all\'asi szab\'alyt tekinteni, 
amely szerint akkor \'allunk meg, amikor el\H{o}sz\"or 
el\'ert\"uk a $[p,q]$ intervallum valamelyik v\'egpontj\'at.
Ezut\'an  fel\'{\i}rjuk a megfelel\H{o} egyenl\H{o}tlens\'eget
erre a Wiener folyamatra \'es meg\'all\'asi szab\'alyra \'es a
$g(x)$ f\"uggv\'enyre a 3.9. lemma seg\'{\i}ts\'eg\'evel. 
Ezenk\'{\i}v\"ul tekintj\"uk a $\tau(\oo)\equiv\infty$ 
meg\'all\'asi szab\'alyt, annak \'erdek\'eben, hogy l\'assuk, 
$g(x)\ge0$.

A m\'asik ir\'any\'u \'all\'{\i}t\'as bizony\'{\i}t\'asa 
\'erdek\'eben vezess\"uk be el\H{o}sz\"or a $P_t$, $t\ge0$, 
oper\'atorokat a 
$$
P_tf(x)=E_xf(W(t,\oo))=\int _0^a f(y)\mu_{x,t}(\,dy),\quad 0\le x\le a,
$$
k\'eplet seg\'{\i}ts\'eg\'evel a $[0,a]$ intervallumon 
defini\'alt korl\'atos f\"uggv\'enyek ter\'en, ahol $\mu_{x,t}$ 
az $x$ pontb\'ol kiindul\'o, a 0 \'es $a$ pontban elnyel\H{o} 
hat\'arfalakkal rendelkez\H{o} Wiener folyamat $t$ 
id\H{o}pontbeli \'ert\'ek\'enek az eloszl\'asa.

Nem neh\'ez bel\'atni a $P_t$, $t\ge0$, oper\'atorok 
k\"ovetkez\H{o} tulajdons\'agait. $P_sP_t=P_{s+t}$. A $P_t$ 
oper\'atorok pozit\'{\i}vak a k\"ovetkez\H{o} \'ertelemben.
Ha $f(x)\ge0$ minden $x$ pontban, akkor $P_tf(x)\ge0$ minden 
$x$ pontban.  Ez\'ert, ha $f(x)\ge g(x)$ minden $x$ pontban, 
akkor $P_tf(x)\ge P_tg(x)$ minden $x$ pontban. Tov\'abb\'a 
l\'etezik a $P_\infty=\limm_{t\to\infty}P_t$ oper\'ator, 
azaz l\'etezik a $\limm_{t\to\infty}P_t f(x)=P_\infty f(x)$
hat\'ar\'ert\'ek minden korl\'atos $f$ f\"uggv\'enyre \'es
$x$ pontra. Meg lehet adni  a $P_\infty$ oper\'atort explicit 
m\'odon a $P_\infty f(x)=\frac{a-x}a f(0)+\frac xaf(a)$ 
k\'eplet seg\'{\i}t\'eg\'evel. E rel\'aci\'o bizony\'{\i}t\'asa 
azon m\'ulik, hogy egy $x$ pontb\'ol kiindul\'o a 
0 \'es $a$ pontban elnyel\H{o} fal\'u Wiener folyamatra
$\limm_{t\to\infty}P(W(t,\oo)=0)=\frac{a-x}a$ \'es
$\limm_{t\to\infty}P(W(t,\oo)=a)=\frac xa$.

A $[0,a]$ intervallumban line\'aris f\"uggv\'enyek fixpontjai 
a $P_\infty$ oper\'atoroknak. Innen \'es a $P_t$ oper\'atorok 
monotonit\'as\'ab\'ol (azaz a $P_t\ge P_s$, ha $t>s$ 
k\"ovetkezik, hogy az $f(x)=ax+b$ f\"uggv\'enyekre 
$P_tf(x)=f(x)$ minden $x$ pontra. Tov\'abb\'a e 
rel\'aci\'ob\'ol, a $P_t$ oper\'atorok 
pozit\'{\i}vit\'as\'ab\'ol, \'es a konk\'av f\"uggv\'enyek 
alkalmas jellemz\'es\'eb\H{o}l k\"ovetkezik az, hogy ha 
$f(x)$ korl\'atos konk\'av f\"uggv\'eny, akkor 
$P_tf(x)\le f(x)$ minden $t\ge 0$ \'es $0\le x\le a$ 
sz\'amp\'arra. Ez a tulajdons\'ag a konkavit\'as olyan 
k\"ovetkezm\'enye (val\'oj\'aban jellemz\'ese) a Markov 
folyamatok nyelv\'en, amely fontos szerepet j\'atszik a 
bizony\'{\i}t\'asban. 

A bizony\'{\i}t\'as k\"ovetkez\H{o} l\'ep\'es\'eben 
bevezetj\"uk a (3.5) k\'epletben defini\'alt $P_a$ oper\'ator 
folytonos v\'altozat\'at. Defini\'aljuk minden $0\le\alpha<1$
sz\'amra \'es a $[0,a]$ intervallumon defini\'alt, 
nem-negat\'{\i}v, korl\'atos korl\'atos $g(x)$ f\"uggv\'enyre a
$$
G_\alpha g(x)=\int_0^\infty\alpha^t P_t g(x)\,dt
=E_x\int_0^\infty \alpha^tg(W(t,\oo))\,dt
$$
oper\'atort. Eml\'ekeztetek arra, hogy a 3.5. lemma 
bizony\'{\i}t\'as\'anak fontos l\'ep\'ese volt az 
excessz\'{\i}v f\"uggv\'enyek k\"ovetkez\H{o} jellemz\'ese. 
Ha $f(x)$ excessz\'{\i}v f\"uggv\'eny, akkor az 
fel\'{\i}rhat\'o $f(x)=G_ag_a(x)$ alakban tetsz\H{o}leges
$0\le a<1$ sz\'amra a (3.5) k\'epletben defini\'alt $G_a$ 
oper\'atorral \'es alkalmas $g_a(x)\ge0$ f\"uggv\'ennyel. 
A nem-negat\'{\i}v konvex f\"uggv\'enyek hasonl\'o 
jellemz\'es\'et szeretn\'enk megadni a most defini\'alt 
$G_\alpha$ oper\'ator seg\'{\i}ts\'eg\'evel.

Csak egy valamivel gyeng\'ebb \'all\'{\i}t\'ast tudunk 
bel\'atni, de az is elegend\H{o} lesz sz\'a\-munk\-ra. Nem 
tudunk minden nem-negat\'{\i}v f\"uggv\'enyt ilyen alakban
fel\'{\i}rni, de el\H{o} tudjuk \H{o}ket \'all\'{\i}tani 
ilyen alak\'u f\"uggv\'enyek alkalmas tulajdons\'agokkal 
rendelkez\H{o} limeszek\'ent, \'es a k\'{\i}v\'ant 
\'all\'{\i}t\'ast be tudjuk bizony\'{\i}tani ennek az 
eredm\'enynek a seg\'{\i}ts\'eg\'evel. Felhaszn\'aljuk, 
hogy a $[0,a]$ intervallumban nem-negat\'{\i}v, korl\'atos, 
konk\'av $f(x)$  f\"uggv\'enyek olyan nem-negat\'{\i}v, 
korl\'atos $f(x)$ f\"uggv\'enyek, amelyek folytonosak
a $(0,a)$ ny\'{\i}lt intervallumban, \'es teljes\'{\i}tik 
a $P_tf(x)\le f(x)$ tulajdons\'agot minden $x\in[0,a]$ 
\'es $t\ge0$ sz\'amra.

R\"ogz\'{\i}ts\"unk egy $0\le\alpha<1$ sz\'amot. Bel\'atjuk, 
hogy ha  $f(x)$ olyan a $[0,a]$ intervallumon defini\'alt 
nem-negat\'{\i}v, korl\'atos a $(0,a)$ ny\'{\i}lt 
intervallumban folytonos f\"uggv\'eny, amelyre 
$P_tf(x)\le f(x)$, $t\ge0$, $x\in[0,a]$, akkor 
fel\'{\i}rhat\'o $f(x)=\limm_{s\to0} h_s(x)$ alakban, ahol 
a $h_s(x)$ f\"uggv\'enyek monoton cs\"okken\H{o} m\'odon 
konverg\'alnak a $f(x)$ f\"uggv\'enyhez minden $x$ pontban, 
\'es $h_s(x)=G_\alpha g_s(x)$ az el\H{o}bb defini\'alt
$G_\alpha$ oper\'atorral \'es alkalmas $g_s(x)\ge0$ 
f\"uggv\'ennyel. Ismertetem, hogyan lehet az $f(x)$ 
f\"uggv\'eny egy k\'{\i}v\'ant el\H{o}\'all\'{\i}t\'as\'at 
megtal\'alni, de a bizony\'{\i}t\'as r\'eszleteit, (ami 
megtal\'alhat\'o a k\"onyvben) elhagyom.

Legyen $h_s(x)=\frac1s\int_0^s \alpha^t P_tf(x)\,dt$. Akkor 
igazolhat\'o, hogy $f(x)=\limm_{s\to0}h_s(x)$, \'es az,
hogy e formul\'aban monoton konvergencia \'erv\'enyes. 
A $h_s(x)$ f\"uggv\'enyek  alkalmas reprezent\'aci\'oj\'at 
a k\"ovetkez\H{o} sz\'amol\'assal kaphatjuk meg:
$$
\align
h_s(x)&=\frac1s\int_0^\infty \alpha^t P_tf(x)\,dt
-\frac1s\int_s^\infty \alpha^t P_tf(x)\,dt
=\int_0^\infty\frac{ (\alpha^t P_tf(x)-\alpha^{t+s}P_{t+s}f(x))}s\,dt \\
&=\int_0^\infty \alpha^t P_t\(\frac{f(x)-\alpha^s P_sf(x)}s\)\,dt
=G_\alpha g_s(x),
\endalign
$$
ahol $g_s(x)=\frac{f(x)-P_sf(x)}s$. Mivel $f(x)\ge P_sf(x)$ 
ez\'ert  $g_s(x)\ge0$, \'es megkaptuk az $f$ f\"uggv\'eny 
k\'{\i}v\'ant el\H{o}\'all\'{\i}t\'as\'at.

A bizony\'{\i}t\'as k\"ovetkez\H{o} l\'ep\'es\'eben bel\'atjuk, 
felhaszn\'alva a $h_s(x)=G_\alpha g_s(x)$ \'es $g_s(x)\ge0$ 
formul\'at, hogy 
$h_s(x)\ge E_x\alpha^{\tau(\oo)} h_s(W(\tau(\oo),\oo))$ 
tetsz\H{o}leges $\tau$ meg\'all\'asi szab\'alyra. E formula 
bizony\'{\i}t\'asa hasonl\'o a 3.5 lemma 
bizony\'{\i}t\'as\'anak megfelel\H{o} r\'e\-sz\'e\-hez, b\'ar 
technikailag nehezebb, mert \'altal\'anos mez\H{o}k\"on 
\'ertelmezett felt\'eteles v\'arhat\'o \'ert\'ekekkel kell 
dolgoznunk. A bizony\'{\i}t\'as azon alapul, hogy az 
er\H{o}s Markov tulajdons\'ag 
fel\-hasz\-n\'a\-l\'a\-s\'a\-val be tudjuk bizony\'{\i}tani, hogy
$$
E_x\alpha^{\tau(\oo)} h_s(W(\tau(\oo),\oo))
=E_x\int_{\tau(\oo)}^\infty\alpha^t g_s(W(t,\oo))\,dt, 
$$
m\'{\i}g $h_s(x)=G_\alpha g_s(x)
=E_x\int_0^\infty \alpha^tg_s(W(t,\oo))\,dt$.
 
Ezut\'an  felhaszn\'alva a $\limm_{s\to0}h_s(x)=f(x)$ 
rel\'aci\'ot be tudjuk bizony\'{\i}tani az 
$f(x)\ge E_x \alpha^\tau f(W(\tau(\oo),\oo))$ 
egyenl\H{o}tlens\'eget tetsz\H{o}leges $0\le\alpha<1$
sz\'amra, majd $\alpha\to1$ hat\'ar\'atmenettel 
megkapjuk a 3.8. lemma bizony\'{\i}t\'as\'at.

\medskip
Felmer\"ulhet a k\'erd\'es, hogyan lehet a 3.8. lemma 
eredm\'eny\'et \'altal\'anos, folytonos idej\H{u} Markov
folyamatokra \'altal\'anos\'{\i}tani. E k\'erd\'es 
vizsg\'alat\'aban \'erdemes bevezetni az excessz\'{\i}v
f\"uggv\'eny definici\'oj\'at folytonos idej\H{u} Markov
folyamatokra.

\medskip\noindent
{\bf Excessz\'{\i}v f\"uggv\'eny definici\'oja.} {\it Legyen
$X(t,\oo)$, $t\ge0$  egy \'ert\'ekeit valamely $(X,\Cal X)$ 
t\'eren felvev\H{o} Markov folyamat, \'es defini\'aljuk az $X$
t\'eren defini\'alt korl\'atos, m\'erhet\H{o} f\"uggv\'enyek
ter\'en a $P_tf(x)=E_x f(X(t,\oo))$ oper\'atort minden $t\ge0$
sz\'amra. Egy az $X$ t\'eren defini\'alt korl\'atos, 
m\'erhet\H{o} $f(x)$ f\"uggv\'eny  excessz\'{\i}v e Markov
folyamatra n\'ezve, ha 
$$
f(x)\ge0, \quad P_t f(x)\le f(x), \quad\text{\'es } 
\lim_{t\to0}P_tf(x)=f(x)
$$
minden $x\in X$ pontra \'es $t\ge0$ sz\'amra.}

\medskip
Az el\H{o}z\H{o} bizony\'{\i}t\'as m\'odszer\'evel be lehet 
bizony\'{\i}tani a 3.8 lemma megfelel\H{o}j\'et egy az 
er\H{o}s Markov tulajdons\'aggal is rendelkez\H{o} Markov 
folyamatra n\'ezve excessz\'{\i}v f\"uggv\'enyre. Azt, hogy ha 
$f(x)$ korl\'atos, excessz\'{\i}v f\"uggv\'eny egy az er\H{o}s
Markov tulajdons\'aggal ren\-del\-ke\-z\H{o} $X(t,\oo)$, $t\ge0$,
Markov folyamatra n\'ezve, akkor $E_xf(X(\tau(\oo),\oo))\le f(x)$
minden $x\in X$ pontra \'es a Markov folyamat minden $\tau$ 
meg\'all\'asi szab\'aly\'ara. Az elm\'elet f\H{o} neh\'ezs\'ege 
az excessz\'{\i}v f\"uggv\'enyek jellemz\'ese.

\bye
