Áttekintés Dynkin, Evgenyij Boriszovics és Yushkevics, Alekszandr Adolfovics Tételek és feladatok Markov folyamatokról című könyvéről

Harmadik fejezet: Az optimális választás feladata.

Ez a fejezet egy az orosz irodalomban válogatós menyasszony, a magyar irodalomban Szindbád problémának nevezett feladat megoldásának az ismertetésével kezdődik. A feladat a következőképp szól.

Egy hölgy (Szindbád) n vőlegény (feleség)jelölt közül választhatja ki leendő férjét (feleségét). A jelöltek minőségének van egy sorrendje, van közöttük egy legjobb, egy második legjobb és így tovább, de a választani akaró hölgy (Szindbád) az egyes jelöltek jóságát kezdetben nem ismeri. Ő csak a jelöltek n számát tudja. A jelöltek véletlen sorrendben jelennek meg egymás után a hölgy (Szindbád) előtt, aki az éppen megjelent jelölt minőségét össze tudja hasonlítani a a korábban megjelentekével. Egy jelölt megjelenése után a hölgynek (Szindbádnak) azonnal el kell döntenie, hogy őt választja-e vagy pedig valamelyik később megjelenő jelöltet, és ezt a döntését később nem változtathatja meg. Tegyük fel, hogy a jelöltek megjelenésének minden lehetséges sorrendje egyformán valószínű. A hölgy (Szindbád) célja az, hogy minél nagyobb valószínűséggel a legjobb jelöltet válassza. Milyen stratégiát érdemes választania, és mekkora a siker valószínűsége az optimális stratégia választása esetén? Mi e valószínűség határértéke, ha n → ∞?

A szerzők e fejezet első részében megoldják ezt a feladatot. Azt is megmutatják, hogy ez a feladat tárgyalható a következő probléma speciális eseteként. Rögzítsünk egy értékeit egy véges vagy megszámlálható sok elemet tartalmazó X halmazon felvevő Markov láncot valamely ismert p(x, y), x, y ∈ X, átmenetvalószínűségekkel, és egy a Markov lánc minden x ∈ X állapotában definiált f(x) függvényt, amelyet nyereményfüggvénynek fogunk nevezni. A következő feladatot tárgyaljuk. Veszünk az X téren egy valamely x ∈ X pontból kiinduló, p(x, y) átmenetvalószínűségekkel rendelkező Markov láncot. Ha a Markov láncot egy véletlen időpontban megállítjuk, és a Markov lánc ebben az időpontban egy u ∈ X állapotban tartózkodik, akkor f(u) nyereményt kapunk. Célunk egy olyan optimális (véletlen időpontbeli) megállási stratégia megadása, amelynek alkalmazása esetén nyereményünk várható értéke a lehető legnagyobb. Ezenkívül szeretnénk kiszámítani a nyeremény várható értékét az optimális stratégia választása esetében.

E probléma vizsgálatában természetes módon megjelenik az első fejezetben bevezetett excesszív függvények fogalma, pontosabban az ott bevezetett fogalom természetes általánosítása arra az esetre, amikor nemcsak bolyongásokat tekintünk az l-dimenziós rácson, hanem általános Markov láncokat egy X állapottéren valamely p(x, y), x, y ∈ X átmenetvalószínűségekkel. Az excesszív függvények és azok tulajdonságai fontos szerepet játszanak az optimális megállási stratégiák megtalálásában és az optimális stratégiához tartozó nyeremény kiszámításában. Ezek az eredmények segítenek az előbb említett optimális párválasztási probléma megoldásában is.

E fejezet tartalmazza a fent megfogalmazott optimális megállási stratégiáról szóló feladat megoldását, illetve az excesszív függvények e feladat megoldásában felhasznált tulajdonságainak vizsgálatát. Végül a fejezet utolsó része egy olyan feladat megoldását tartalmazza, amely úgy tekinthető, mint az előbb megfogalmazott feladat folytonos idejű változatának egy speciális esete. A következő problémáról van szó. Tekintsünk egy [0, a] intervallumot valamely a > 0 számmal, és egy valamely x, 0 ≤ x ≤ a, pontból kiinduló W (t) Wiener folyamatot a 0 és a pontokkal mint elnyelő falakkal. Legyen adva egy folytonos f(x), 0 ≤ x ≤ a, függvény a [0, a] intervallumon. Határozzuk meg azt az optimális τ megállási szabályt erre a W (t) Wiener folyamatra, amelyre az Ef(W (τ)) várható érték maximális, és határozzuk meg ezt a várható értéket.

A kiinduló feladat megoldásában hasznos a következő eredmény.

3.1. Lemma. Legyen adva n különböző a_{1} < a_{2} < ⋯ < a_{n} valós szám, és vegyük egyforma \frac{1}{n!} valószínűséggel e számsorozat összes lehetséges a_{π(1)}, …, a_{π(n)} permutációját. Jelölje minden 1 ≤ j ≤ n számra ξ_{j} azt a valószínűségi változót, amely megmondja, hogy az a_{π(j)} szám nagyság szerint hanyadik az a_{π(1)}, a_{π(2)}, …, a_{π(j)} sorozatban, azaz legyen ξ_{j} = 1, ha ő a legnagyobb, ξ_{j} = 2, ha ő a második legnagyobb e számok között, és így tovább. Ekkor a ξ_{1}, …, ξ_{n} valószínűségi változók függetlenek egymástól, és P (ξ_{j} = s) = \frac{1}{j} minden 1 ≤ s ≤ j számra és 1 ≤ j ≤ n indexre.

Bizonyítás. Elég belátni, hogy P (ξ_{1} = s_{1}, ξ_{2} = s_{2}, …, ξ_{n} = s_{n}) = \frac{1}{n!} minden olyan s_{1}, …, s_{n} sorozatra, amelyre 1 ≤ s_{j} ≤ j minden 1 ≤ j ≤ n indexre. Ennek igazolásához elég megmutatni, hogy kölcsönösen egyértelmű megfeleltetés létesíthető az ilyen tulajdonságú s_{1}, …, s_{n} sorozatok és az 1, …, n számok π = (π(1), …, π(n)) permutációi között a következő módon. Ha adva van egy π = (π(1), …, π(n)) permutáció, akkor tekintjük az általa meghatározott a_{π(1)}, …, a_{π(n)} sorozatot, majd az e sorozat segítségével a lemmában definiált ξ_{1}, …, ξ_{n} valószínűségi változók ezen permutációhoz tartozó s_{1}, …, s_{n} értékeit. Ha a π permutációnak ezt az s_{1}, …, s_{n} sorozatot feleltetjük meg, akkor a kívánt tulajdonságú kölcsönesen egyértelmű megfeleltetést hozunk létre. Valóban, minden π = (π(1), …, π(n)) permutációnak megfelel egy kívánt tulajdonságú s_{1}, …, s_{n} sorozat, és különöző permutációk különböző sorozatokat határoznak meg. (Ezt például úgy lehet látni, hogy követjük a leképezés eredményeként kapott s_{n}, s_{n−1}, … sorozat értékeit egymás után az indexek csökkenő sorrendjében.) Ezenkívül a (π(1), …, π(n)) permutációk és s_{1}, …, s_{n} sorozatok száma megegyezik. Mind a kettő értéke n!.

A későbbi tárgyalás érdekében felidézem a Markov lánc fogalmát. Legyen adva egy (Ω, A, P) valószínűségi mezőn X_{1}, X_{2}, … valószínűségi változók sorozata, amelyek értékeiket valamely véges vagy megszámlálható sok elemet tartalmazó X térben veszik fel. Azt mondjuk, hogy ezek a valószínűségi változók (stacionárius) Markov láncot alkotnak p(x, y), x, y ∈ X, átmenetvalószínűségekkel, ha tetszőleges n ≥ 1 számra, és x_{1}, …, x_{n−1} ∈ X és x, y ∈ X pontokra

P (X_{n+1} = y|X_{n} = x, X_{n−1} = x_{n−1}, …, X_{1} = x_{1}) = p(x, y).

Ezt az azonosságot megköveteljük minden olyan esetben, amikor P (X_{n+1} = y, X_{n} = x, X_{n−1} = x_{n−1}, …, X_{1} = x_{1}) > 0.

Megjegyzem, hogy ebben a definicióban nem követeltük meg a ∑_{y∈X} p(x, y) = 1

feltétel teljesülését. Elég megkövetelni azt, hogy ∑_{y∈X} p(x, y) ≤ 1 minden x ∈ X pontban.

Ez egyben azt jelenti, hogy megengedjük azt, hogy egy X_{n} valószínűségi változó ne legyen definiálva az egész (Ω, A, P) valószínűségi mezőn, hanem csak annak egy 1-nél kisebb mértékű részhalmazán.

Érdemes a Markov láncok definicióját kissé általánosabban megadni. Az általánosabb definicióban megengedjük, hogy azokon az eseményeken kívül, hogy az X_{n} valószínűségi változók milyen értékeket vesznek fel más eseményeket is figyelembe vehessünk a vizsgált feltételes valószínűségek definiciójában szereplő feltételek között. De ezek az új események nem befolyásolják a vizsgált feltételes valószínűségeket.

Legyen adva egy (Ω, A, P) valószínűségi mezőn X_{1}, X_{2}, … valószínűségi változók sorozata, amelyek értékeiket valamely véges vagy megszámlálható elemszámú X térben veszik fel. Legyen ezenkívül adva F_{1} ⊂ F_{2} ⊂ ⋯ ⊂ A σ-algebráknak olyan növekvő sorozata, amelyek részei az A σ-algebrának, és amelyekre igaz az, hogy X_{n} F_{n} mérhető valószínűségi változó minden n = 1, 2, … indexre. (Most is megengedjük, hogy csak a ∑_{y∈X} p(x, y) ≤ 1 feltétel teljesüljön, és az X_{n} valószínűségi változó ne legyen definiálva

az egész téren.) Azt mondjuk, hogy ezek a valószínűségi változók és σ-algebrák (stacionárius) Markov láncot alkotnak p(x, y), x, y ∈ X, átmenetvalószínűségekkel, ha tetszőleges n ≥ 1 számra, és x, y ∈ X pontokra

P (X_{n+1} = y|F_{n})(ω) = p(x, y), ha X_{n}(ω) = x.  (3.1)

A (3.1) pontban felírt azonosság úgy értendő, hogy az teljesül azon ω ∈ Ω pontok halmazán, ahol definiálva van az X_{n}(ω) függvény.

Tekintsük a válogatós menyasszony problémát. Vegyük észre, hogy a 3.1 lemma alapján ezt a feladatot a következőképp is átfogalmazhatjuk. Adott ξ_{1}, …, ξ_{n} független valószínűségi változók sorozata, amelyekre ξ_{j} az 1, …, j számok valamelyikét veszi fel, és P (ξ_{j} = s) = \frac{1}{j} minden 1 ≤ s ≤ j számra. Lehetőségünk van arra, hogy megfigyeljük egymás után a ξ_{1}, ξ_{2}, …, ξ_{n} valószínűségi változókat. A megfigyelést azon j indexre szeretnénk befejezni, amelyre egyrészt ξ_{j} = 1, másrészt ξ_{k} ≥ 2 minden k > j indexre. Hogyan tudjuk elérni, hogy úgy fejezzük be a megfigyelést, hogy ez az esemény minél nagyobb valószínűséggel következzen be? Értsük meg, hogy miért ezt a feladatot kell megoldanunk a válogatós menyasszony problémájának vizsgálatában.

Amikor az egyes jelöltek egymás után megjelennek, és összehasonlítjuk őket a korábban megjelentekkel, akkor azokat a ξ_{j} valószínűségi változókat figyeljük meg, amelyek megmondják, hogy az újonnan megjelent jelölt hanyadik az eddigi jelöltek között a jósági sorrendben. Az, hogy ξ_{j} = 1 azt jelenti, hogy a j-ik jelölt minden korábbinál jobb. Az, hogy ξ_{k} ≥ 2 minden k > j indexre azt jelenti, hogy a későbbi jelöltek között sem jelenik meg a j-ik jelöltnél jobb jelölt. Tehát az, hogy sikerült az ilyen tulajdonságú j indexet megtalálni ekvivalens azzal, hogy megtaláltuk a legjobb jelöltet. Másrészt a 3.1 lemma alapján a ξ_{j} valószínűségi változóknak az általunk megadott együttes eloszlása van.

Az előbbiekben megadtuk a válogatós menyasszony probléma egy ekvivalens megfogalmazását. A feladatot meg lehet oldani ebben a formában, de a könyv szerzői leírták a feladat egy olyan ekvivalens megfogalmazását alkalmas Markov láncok segítségével, amelyik kényelmesebben vizsgálható. Ismertetem ezt a megfogalmazást. Ehhez szükségünk van a következő eredményre.

3.2. Lemma. Legyen ξ_{1}, …, ξ_{n} független valószínűségi változók sorozata, amelyre P (ξ_{j} = s) = \frac{1}{j}, 1 ≤ s ≤ j minden 1 ≤ j ≤ n indexre. Definiáljuk a következő η_{1}, η_{2}, …, valószínűségi változókat. η_{1}(ω) ≡ 1, η_{2}(ω) = n_{1}(ω), a legkisebb olyan l = n_{1}(ω) > 1 index-szel, amelyre ξ_{l}(ω) = 1, ha van ilyen l index. Ha nincs ilyen l index akkor sem az η_{2}(ω), sem az η_{k}(ω), k > 2, valószínűségi változókat nem definiáljuk az ω ∈ Ω pontban. Ha az η_{j}(ω) valószínűségi változót már definiáltuk valamely j indexre egy ω ∈ Ω pontban, akkor η_{j+1}(ω) = n_{j+1}(ω) azzal a legkisebb l = n_{j+1}(ω) > η_{j}(ω) index-szel, amelyre ξ_{l}(ω) = 1, feltéve, hogy ilyen l index létezik. Ha ilyen l index nem létezik, akkor sem a η_{j+1}(ω) sem az η_{p}(ω), p ≥ j + 2, valószínűségi változókat nem definiáljuk az ω ∈ Ω pontban.

Az így definiált η_{1}, η_{2}, … valószínűségi változók Markov láncot alkotnak az X = {1, …, n} halmazon felvett értékekkel és a következő átmenetvalószínűségekkel: p(l|k) = P (η_{j+1} = l|η_{j} = k) = \frac{k}{(l−1)l}, ha 1 ≤ k < l ≤ n, és p(l|k) = 0 különben.

Definiáljuk minden j számra az F_{j} σ-algebrát, mint az {ω: ξ_{1}(ω) = s_{1}, ξ_{2}(ω) = s_{2}, …, ξ_{p}(ω) = s_{p}} alakú események által generált σ-algebrát, ahol olyan s_{1}, …, s_{p}, 1 ≤ s_{l} ≤ l minden 1 ≤ l ≤ p sorozatokat tekintünk, amelyekre p ≤ n, és az s_{1}, …, s_{l} sorozat η_{j}(ω) darab egyest tartalmaz. Az (η_{j}, F_{j}), j = 1, 2, … sorozat szintén Markov lánc az előbb definiált p(k|l) átmenetvalószínűségekkel.

Bizonyítás. Ki kell számolnunk a

P (η_{j+1} = l|η_{j} = k, η_{j−1} = k_{j−1}, η_{j−2} = k_{j−2}, …, η_{1} = k_{1})

= \frac{P (η_{j+1} = l, η_{j} = k, η_{j−1} = k_{j−1}, η_{j−2} = k_{j−2}, …, η_{1} = k_{1})}{P (η_{j} = k, η_{j−1} = k_{j−1}, η_{j−2} = k_{j−2}, …, η_{1} = k_{1})}

feltételes valószínűséget minden j indexre, és n ≥ l > k > k_{j−1} > k_{j−2} > ⋯ > k_{1} = 1 feltétel esetén. A fenti törtben szereplő valószínűségeket ki tudjuk számolni, mert olyan események valószínűségét kell kiszámolni, hogy az egymástól független ξ_{p} valószínűségi változók közül egyesek 1-gyel egyenlőek, mások pedig nem egyenlőek 1-gyel. Azt kapjuk, hogy

P (η_{j+1} = l, η_{j} = k, η_{j−1} = k_{j−1}, η_{j−2} = k_{j−2}, …, η_{1} = k_{1})

= \frac{1}{l} · \frac{1}{k} · ∏_{s=1}^{j−1} \frac{1}{k_{s}} ∏_{\begin{matrix}1≤t≤l \\ t∉\{l,k,k_{j},k_{j−1},...,k_{1}\} \end{matrix}} \frac{t − 1}{t},

és hasonlóan

P (η_{j} = k, η_{j−1} = k_{j−1}, η_{j−2} = k_{j−2}, …, η_{1} = k_{1})

= \frac{1}{k} · ∏_{s=1}^{j−1} \frac{1}{k_{s}} ∏_{\begin{matrix}1≤t≤k \\ t∉\{k,k_{j},k_{j−1},...,k_{1}\} \end{matrix}} \frac{t − 1}{t}.

Ezért a keresett feltételes valószínűség

P (η_{j+1} = l|η_{j} = k, η_{j−1} = k_{j−1}, η_{j−2} = k_{j−2}, …, η_{1} = k_{1})

= \frac{1}{l} ∏_{k+1≤t≤l−1} \frac{t − 1}{t} = \frac{k}{(l − 1)l} .

Így a kívánt azonosságot beláttuk minden olyan esetben, amikor P (η_{j+1} = l, η_{j} = k, η_{j−1} = k_{j−1}, η_{j−2} = k_{j−2}, …, η_{1} = k_{1}) > 0.

A 3.2 lemma második felét arról az esetről, amikor a F_{j} σ-algebrákat is tekintjük hasonlóan látjuk be, csak akkor a jelölés kissé bonyolultabbá válik.

Jelenjenek meg a válogatós menyasszony problémájában az egyes jelöltek az 1, 2, 3, … időpontokban. Jelölje η_{1}, η_{2}, … azokat az időpontokat, amikor egy minden korábbinál jobb jelölt jelent meg. A 3.2 lemmában azt bizonyítottuk be, hogy ezek az η_{j} időpontok Markov láncot alkotnak, és megadtuk e Markov lánc átmenetvalószínűségeit. Világos, hogy csak valamelyik η_{j} időpontben megjelent jelöltet érdemes választani, ha az a célunk, hogy a legjobb jelöltet válasszuk minél nagyobb valószínűséggel. (Illetve az utolsó n-ik jelöltet kell választani akkor, amikor már nincs több választható jelölt.) Célunk annak meghatározása, hogy melyik η_{j} időpontban megjelent jelöltet érdemes választani. E kérdés megválaszolásához ad hasznos információt a 3.2 lemma. A lemma második felében megfogalmazott F_{j} σ-algebrákról szóló állításnak az a haszna, hogy segítségével be lehet látni, hogy az a plusz információ hogy tudjuk mi történt az η_{j} és η_{j+1} időpontok között, milyen sorrendben jelentek meg az eleve nem választható jelöltek, nem ad hasznos információt a kérdés megválaszolásához. Annak érdekében, hogy az optimális stratégiát megtaláljuk érdemes bebizonyítani a következő eredményt.

3.3. Lemma. Legyen η_{1}, η_{2}, … egy Markov lánc az X = {1, …, n} halmazon felvett értékekkel a következő p(l|k) átmenetvalószínűségekkel: p(l|k) = P (η_{j+1} = l|η_{j} = k) = \frac{k}{(l−1)l}, ha 1 ≤ k < l ≤ n, és p(l|k) = 0 különben. Jelölje q(k) annak feltételes valószínűségét, hogy nem létezik az η_{j+1} valószínűségi változó, feltéve azt, hogy η_{j} = k. Azaz q(k) annak feltételes valószínűsége, hogy amennyiben a a j időpontban a Markov lánc a k pontban tartozkódik akkor onnan már nem lép sehová. Jelölje q′(k) annak a feltételes valószínűségét, hogy a Markov láncban létezik az η_{j+1} > η_{j} valószínűségi változó, de az η_{j+2} > η_{j+1} valószínűségi változó már nem létezik, feltéve, hogy η_{j} = k. Ez annak a feltételes valószínűsége, hogy amennyiben a Markov lánc a j időpontban a k pontban tartózkodik, akkor az tesz még egy lépést a k pontból, de ez a Markov lánc utolsó lépése.

Azt állítom, hogy q(k) = \frac{k}{n}, 1 ≤ k ≤ n, és
q′(k) = \frac{k}{n} (\frac{1}{k} + \frac{1}{k + 1} + ⋯ + \frac{1}{n − 1}) , ha 1 ≤ k ≤ n − 1,  (3.2)

és q′(n) = 0.

Bizonyítás. Felírhatjuk az 1 − q(k) = ∑_{l=k+1}^{n} p(l|k) azonosságot, ami azért igaz, mert ha

η_{j} = k akkor annak komplementer eseménye, hogy az η_{j+1} valószínűségi változó nem létezik az, hogy η_{j+1} = l valamilyen k + 1 ≤ l ≤ n számmal. Mivel p(l|k) = \frac{k}{(l−1)l} = k(\frac{1}{l−1} − \frac{1}{l}) a 3.2 lemma alapján, ezért igaz az

1 − q(k) = ∑_{l=k+1}^{n} k (\frac{1}{l − 1} − \frac{1}{l}) = k (\frac{1}{k} − \frac{1}{n}) = 1 − \frac{k}{n}

azonosság, és ezt kellett belátni.

Igaz a q′(k) = ∑_{l=k+1}^{n} p(l|k)q(l) = ∑_{l=k+1}^{n} \frac{k}{(l−1)l} · \frac{l}{n} azonosság minden 1 ≤ k ≤ n − 1

számra, mert p(l|k)q(l) annak a feltételes valószínűsége, hogy η_{j+1} = l, és az η_{j+2} valószínűségi változó nem létezik, feltéve, hogy η_{j} = k. Innen következik a (3.2) formula. A q′(n) = 0 azonosság nyilvánvaló.

Az eredeti válogatós menyasszony problémát a következő problémára vezettük vissza. Tekintsünk egy a 3.2. lemmában leírt η_{1}, η_{2}, … Markov láncot. E Markov lánc elemeinek egymás utáni megfigyelése (és a p(y|x) átmenetvalószínűségek ismeretében) próbáljuk e Markov lánc megfigyelését minél nagyobb valószínűséggel abban az időpontban befejezni, amikor e Markov lánc utolsó eleme megjelenik. (Ezt a Markov láncot úgy kaptuk, hogy az eredeti válogatós menyasszony problémában az η_{j} valószínűségi változót úgy definiáltuk, mint azt a számot, amely megmondta, hogy hányadik jelölt volt a j-ik olyan jelölt, amely az összes korábbi jelöltnél jobb volt. Az η_{j} definiciója úgy értendő, hogy amennyiben nem volt j-ik olyan jelölt, aki minden korábbi jelöltnél jobb volt, akkor az η_{j} valószínűségi változót nem definiáltuk. Az így definiált Markov láncban az η_{1} ≡ 1 tulajdonság is teljesül.)

Annak érdekében, hogy ezt a feladatot megoldjuk vizsgáljuk először a következő kérdést. Tegyük fel, hogy a vizsgált Markov láncban az η_{j} = k, 1 ≤ k ≤ n, esemény bekövetkezett valamilyen j index-szel, és nekünk el kell dönteni, hogy ezen esemény bekövetkezte után mikor fejezzük be e Markov lánc megfigyelését. Tekintsük a következő két lehetséges stratégiát. Az első stratégia az, hogy a j időpontban azonnal befejezzük a Markov lánc megfigyelését. A második stratégia az, hogy várunk az η_{j+1} valószínűségi változó megjelenésére, és ha ez megjelenik, akkor befejezzük a Markov lánc megfigyelését. (Ha nem jelenik meg az η_{j+1} valószínűségi változó, akkor nem sikerült a Markov lánc megfigyelését a megfelelő időpontban befejezni.) Számoljuk ki a siker valószínűségét e két stratégia alkalmazása esetén, és határozzuk meg, hogy mikor melyik a jobb.

A két stratégia sikerének a valószínűségét a 3.3. lemmában kiszámoltuk. Az első stratégia sikerének a valószínűsége az ott definiált q(k), a másodiké az ott definiált q′(k) mennyiség, és ezen mennyiségeket kiszámoltuk a 3.3. lemmában. Ezek az eredmények lehetővé teszik annak meghatározását is, hogy mikor melyik stratégia a jobb. A válasz megfogalmazása érdekében vezessük be azt a k_{n} pozitív egész számot, amely teljesíti az

\frac{1}{k_{n}} + \frac{1}{k_{n} + 1} + ⋯ + \frac{1}{n − 1} ≤ 1 < \frac{1}{k_{n} − 1} + \frac{1}{k_{n}} + \frac{1}{k_{n} + 1} + ⋯ + \frac{1}{n − 1}  (3.3)

egyenlőtlenséget.

Ha k ≥ k_{n} akkor az első, ha k < k_{n} akkor a második stratégia az előnyösebb. Ez az eredmény a következő képet sugallja. Ha η_{j} = k egy viszonylag kis k számmal akkor nem érdemes a Markov lánc figyelését befejezni, hanem érdemes újabb η_{j+1} szám megjelenésére várni. Ha η_{j} = k egy elég nagy k számra, akkor érdemes a Markov lánc megfigyelését azonnal befejezni. Sőt, azt is megsejthetjük, hogy a k_{n} szám a határ a kis és nagy számok között. Azaz, ha k < k_{n}, akkor az η_{j} = k esemény megjelenésekor nem fejezzük be, és ha k ≥ k_{n}, akkor az η_{j} = k esemény megjelenésekor befejezzük a Markov lánc megfigyelését. Az alábbi eredményben ezt az állítást pontosabban is megfogalmazzuk.

3.4. Lemma. Tekintsük a 3.2 Lemmában definiált η_{1}, η_{2}, … Markov láncot és az η_{j} = k eseményt valamilyen j és k számokkal. Határozzuk meg a Markov lánc j időpont utáni optimális megállási stratégiáját, amelynek alkalmazása esetén a legnagyobb a feltételes valószínűsége annak, hogy a Markov láncot az utolsó η_{l} valószínűségi változó megjelenésekor állítottuk meg, feltéve, hogy η_{j} = k. Számítsuk ki ezt a feltételes valószínűséget.

Ha k ≥ k_{n}, ahol k_{n} a (3.3) formulát teljesítő pozitív egész szám, akkor az optimális stratégia az azonnali, j időpontbeli megállás, és annak feltételes valószínűsége az η_{j} = k feltétel mellett, hogy ez a jó megállási időpont a \frac{k}{n} számmal egyenlő. Ha k ≤ k_{n}−1, akkor az optimális stratégia az, hogy megvárjuk az első olyan η_{l} valószínűségi változó megjelenését, amelyre η_{l} = k̄ valamely k̄ ≥ k_{n} számmal. Ha ilyen η_{l} valószínűségi változó nem létezik, akkor nem sikerült a jó megállási időpontot megtalálni. A jó megállási időpont megtalálásának feltételes valószínűsége az η_{j} = k feltétel mellett ebben az esetben

\frac{k_{n} − 1}{n} (\frac{1}{k_{n} − 1} + \frac{1}{k_{n}} + \frac{1}{k_{n} + 1} + ⋯ + \frac{1}{n − 1}) .  (3.4)

Következmény. Mivel a válogatós menyasszony probléma feladatának megoldását egy olyan a 3.2. lemmában definiált Markov lánc vizsgálatára vezettük vissza, amelyben η_{1} ≡ 1 a 3.4 lemma megadja az optimális stratégiát ebben a feladatban. A k_{n} időpontnál nem korábban megjelent jelöltek közül az első minden korábbinál jobb jelöltet kell választani. A sikeres választás valószínűségét ebben az esetben a (3.4) formula adja meg.

Megjegyzés. A 3.4 lemmában szereplő optimális választás feltételes valószínűsége nem függ az η_{j} valószínűségi változó j indexétől, csak annak k értékétől. Ez azzal függ össze, hogy az η_{1}, η_{2}, … sorozat stacionárius Markov lánc. A lemmát azért fogalmaztuk egy j index segítségével, mert ily módon olyan állítást tudtunk felírni, amelynek bizonyításában könnyebben végrehajtható az ott alkalmazott indukció. Valójában a 3.4 lemmát kissé általánosabban kellett volna megfogalmaznunk egy részletes és pontos bizonyításban. A 3.2 Lemma végén definiált (η_{j}, F_{j}) Markov lánccal kellett volna dolgoznunk annak érdekében, hogy megmutassuk: Az a plusz információ, hogy tudjuk milyen sorrendben érkeztek a nem választható jelöltek nem segít egy jobb stratégia kidolgozásában. A bizonyításban is egy formálisan általánosabb állítást kellett volna bizonyítani. Azt, hogy ha rögzítünk egy olyan eseményt, amelyik az F_{j} σ-algebra valamely az η_{j} = k esemény által tartalmazott atomja, és a j időpont utáni optimális megállást keressük, és az optimális megállás feltételes valószínűségét akarjuk kiszámolni feltéve hogy ez az esemény bekövetkezett, akkor a lemmában az η_{j} = k feltétel esetében kimondott állítások érvényesek. Ezen általánosabb állítás megfogalmazása és bizonyítása csak technikai komplikációt jelentett volna. Később tárgyalni fogjuk a válogatós menyasszony feladat egy másik, általános elveken alapuló megoldását is.

A 3.4. lemma bizonyítása. A lemmát a k szám szerinti backward indukcióval fogjuk bebizonyítani. A k = n esetre igaz az állítás. Vegyünk egy k ≥ k_{n} számot, és tegyük fel, hogy az állítás igaz minden n ≥ k̄ > k számra. Ekkor vagy megállunk az η_{j} = k pontban, és ekkor a siker (feltételes) valószínűsége \frac{k}{n} a 3.3. lemma alapján, vagy teszünk egy lépést és ekkor P (η_{j+1} = k̄|η_{j} = k) = \frac{k}{(k̄−1)k̄} (feltételes) valószínűséggel jutunk a k̄ pontba. Ha a k̄ pontban vagyunk, akkor érdemes az onnan induló optimális stratégiát alkalmazni, ami indukciós feltevésünk szerint a megfigyelések befejezését jelenti, és a siker valószínűsége ekkor \frac{k̄}{n}. Ez azt jelenti, hogy ha η_{j} = k esemény után továbblépünk, és azután az optimális stratégiát alkalmazzuk, akkor a siker (feltételes) valószínűsége

∑_{k̄=k+1}^{n} \frac{k}{(k̄−1)k̄} · \frac{k̄}{n} = \frac{k}{n} ∑_{k̄=k}^{n−1} \frac{1}{k̄}, ami k ≥ k_{n} esetén kisebb, mint \frac{k}{n}, azaz a siker feltételes

valószínűsége az azonnali leállás esetében. Ez azt jelenti, hogy ebben az esetben az azonnali leállás az optimális stratégia.

Ha k = k_{n} − 1, azaz η_{j} = k_{n} − 1 akkor az előző érveléshez hasonlóan beláthatjuk, hogy az optimális stratégia az, hogy várunk az η_{j+1} valószínűségi változó megjelenésére, és utána alkalmazzuk az optimális stratégiát. Mivel η_{j+1} ≥ k_{n}, az optimális stratégia ebben az esetben az η_{j+1} valószínűségi változó megjelenése utáni azonnali megállás. Ezt úgy is megfogalmazhatjuk ebben az esetben, hogy megvárjuk az első olyan η_{l} valószínűségi változó megjelenését, amelynek értéke legalább k_{n}. Backward indukcióval belátjuk, hogy ilyen az optimális stratégia η_{j} = k esetén minden k ≤ k_{n} − 1 számra. Valóban, adva egy k < k_{n} − 1 szám, tegyük fel, hogy ez az állítás igaz minden k̄ > k számra. A 3.3 lemma eredményeiből következik, hogy q′(k) ≥ q(k), ha k ≤ k_{n} − 1, ami azt jelenti, hogy ebben az esetben előnyösebb az, ha nem állítjuk meg a Markov lánc megfigyelését az η_{j} időpontban, hanem várunk az η_{j+1} valószínűségi változó megjelenésére, és azután fejezzük be a Markov lánc megfigyelését. Akkor viszont a legelőnyösebb stratégia az, ha várunk az η_{j+1} valószínűségi változó megjelenésére, és ha η_{j+1} = l, akkor az ehhez az eseményhez tartozó optimális stratégiát követjük. Innen az indukciós feltevés alapján következik, hogy a 3.4. lemmában leírt stratégia az optimális.

Szintén indukcióval látjuk be, hogy k ≤ k_{n} − 1 esetén a (3.4) formula adja meg az optimális stratégia sikerének a (feltételes) valószínűségét. Tegyük fel, hogy tudjuk ezt az állítást minden olyan k̄ számra, amelyre k < k̄ ≤ k_{n} − 1. Ekkor, ha s(l)-lel jelöljük a siker feltételes valószínűségét az optimális stratégia esetén az η_{j+1} = l feltétel teljesülése esetén, akkor azt kapjuk, hogy

s(k) = ∑_{l=k+1}^{n} \frac{k}{(l − 1)l} s(l) = ∑_{l=k+1}^{k_{n}−1} (\frac{k}{(l − 1)} − \frac{k}{l} ) \frac{k_{n} − 1}{n} (\frac{1}{k_{n} − 1} + \frac{1}{k_{n}} + ⋯ + \frac{1}{n − 1})

+ ∑_{l=k_{n}}^{n} \frac{k}{(l − 1)l} · \frac{l}{n}

= [(\frac{k}{k} − \frac{k}{k_{n} − 1}) \frac{k_{n} − 1}{n} + \frac{k}{n}] (\frac{1}{k_{n} − 1} + \frac{1}{k_{n}} + ⋯ + \frac{1}{n − 1})

= \frac{k_{n} − 1}{n} (\frac{1}{k_{n} − 1} + \frac{1}{k_{n}} + ⋯ + \frac{1}{n − 1}) ,

és ezt kellett belátni.

Megadtuk az optimális stratégiát a válogatós menyasszony problémájában, és kiszámoltuk a siker valószínűségét is. Nem nehéz belátni, hogy n → ∞ esetén k_{n} ∼ \frac{n}{e}, és a siker valószínüsége az \frac{1}{e} számhoz tart.

Rátérünk az általános Markov láncok optimális megállításának problémájára ismert nyereményfüggvény esetén. Először megfogalmazzuk a feladatot.

Markov láncok optimális megállításának problémája. Legyen adva egy értékeit egy X állapottéren felvevő valamely (Ω, A, P) valószínűségi mezőn defininiált X_{0}(ω), X_{1}(ω), … Markov lánc ismert p(x, y), x, y ∈ X, átmenetvalószínűségekkel, és egy szintén ismert, korlátos f(u), u ∈ X, nyereményfüggvény az X téren. Tekintsünk egy olyan p(x, y) átmenetvalószínűségekkel rendelkező X_{0}(ω), X_{1}(ω), … Markov láncot, amely egy rögzített x ∈ X pontból indul, azaz P (X_{0}(ω) = x) = 1, és tekintsük e Markov lánc f(X_{τ(ω)}(ω)) nyereményét a Markov lánc minden lehetséges τ(ω) megállási szabálya esetén. Ha nem definiáltuk a τ(ω) < ∞ számot egy ω pontban, amit úgy is megfogalmazhatunk, hogy τ(ω) = ∞, akkor definició szerint f(X_{τ(ω)}(ω)) = 0. Számítsuk ki a v(x) = sup_{τ} E_{x}f(X_{τ(ω)}(ω)) mennyiséget, ahol a szuprémumot a Markov lánc összes

lehetséges τ megállási szabályára vesszük. Határozzunk meg egy optimális τ megállási szabályt, amelyre E_{x}f(X_{τ(ω)}(ω)) = v(x), feltéve, hogy ilyen τ megállási szabály létezik. Ha ilyen megállási szabály nem létezik, akkor találjunk minden ε > 0 számra olyan τ ε-optimális megállási szabályt, amelyre E_{x}f(X_{τ(ω)}(ω)) ≥ v(x) − ε.

A most megfogalmazott probléma megfogalmazásában szerepelt a megállási szabály fogalma. Ezt a fogalmat bevezettük a könyv 2. fejezetének ismertetésében. De ott ezt a fogalmat csak időben folytonos sztochasztikus folyamatok esetében definiáltuk. A teljesség kedvéért itt megadjuk e fogalom diszkrét időre vonatkozó természetes megfelelőjét.

A megállási szabály fogalmának definiciója. Legyen adva F_{n}, n = 0, 1, …, σalgebráknak nem-negatív egész számokkal indexezett növekvő családja, azaz legyen F_{m} ⊂ F_{n}, ha m ≤ n, és legyenek ezek a σ-algebrák rész σ-algebrái egy (Ω, A, P) valószínűségi mező A σ-algebrájának. Egy nem-negatív egész értékeket felvevő τ valószínűségi változót megállási szabálynak nevezünk az F_{n}, n = 0, 1, …, σ-algebra rendszerre nézve, ha minden n ≥ 0 egész számra {τ = n} ∈ F_{n}. Megengedjük azt is, hogy a τ valószínűségi változó ne legyen mindenütt definiálva, azaz lehetséges az is, hogy P (τ < ∞) < 1.

Legyen adva egy X_{n}, n = 0, 1, …, sztochasztikus folyamat egy (Ω, A, P) valószínűségi mezőn. Azt mondjuk, hogy egy nem-negatív egész értékeket felvevő τ valószínűségi változó megállási szabály erre a sztochasztikus folyamatra nézve, ha az megállási szabály az F_{n} = σ(X_{m}, m ≤ n), n = 0, 1 …, növekvő σ-algebra családra nézve.

A Markov láncoknak e fejezetben ismertetett fogalmát fogjuk használni, azaz nem követeljük meg a ∑_{y∈X} p(x, y) = 1, hanem csak a ∑_{y∈X} p(x, y) ≤ 1 reláció teljesülését

minden x ∈ X pontra. A később tárgyalandó eredményeket lehetséges általánosítani a szintén definiált (X_{n}, F_{n}), n = 0, 1, …, valószínűségi változó és σ-algebra párokból álló Markov láncokra is. Itt és a továbbiakban E_{x} és P_{x} egy olyan Markov lánc esetén fog várható értéket és valószínűséget jelölni, amely egy valószínűséggel az x pontból indul.

Az előbb megfogalmazott feladat megoldásában fontos szerepet játszanak az úgynevezett excesszív függvények. A könyv első fejezetének ismertetésében bevezettük ezt a fogalmat egy speciális esetben. Most definiáljuk ezt általános Markov láncok esetében is.

Excesszív függvények definiciója. Legyen p(x, y), x, y ∈ X, egy az értékeit az X állapottéren felvevő Markov lánc átmenetvalószínűségfüggvénye. Definiáljuk azt az ezen p(x, y) átmenetvalószínűségfüggvényhez tartozó P leképezést, amely egy az X téren definiált f(x) függvénynek egy szintén az X téren értelmezett P f függvényt feleltet meg a P f(x) = ∑_{y∈X} p(x, y)f(y), x ∈ X, képlet segítségével. Egy az X téren definiált f(x),

x ∈ X, függvény excesszív (a p(x, y) átmenetvalószínűségekre nézve), ha f(x) ≥ 0, és f(x) ≥ P f(x) minden x ∈ X pontra.

Mint később be fogjuk bizonyítani fogjuk, ha a nyereményfüggvény excesszív, akkor az optimális megállási szabály a τ(ω) ≡ 0 azonnali megállás, bármely x pontból indultunk ki. Ez heurisztikus szinten könnyen magyarázható. Ugyanis az f(x) ≥ P f(x) egyenlőtlenség azt jelenti, hogy nem érdemes a lépéseket későbbre halasztani, az f(x) ≥ 0 egyenlőtlenség pedig azt, hogy nem érdemes a soha meg nem állás stratégiáját választani. Annak érdekében, hogy jól tudjunk dolgozni érdemes megadni az excesszív függvények egy jó jellemzését.

Az első fejezet ismertetésében egy speciális Markov lánc esetében felírtuk az ex-

cesszív függvényeket f(x) = Gφ(x) + C alakban, ahol G = ∑_{n=0}^{∞} P^{n}φ, φ(x) = f(x) −

P f(x) ≥ 0 minden x ∈ X pontban, és C ≥ 0 alkalmas konstans. Az általános esetben az excesszív függvényeket kissé módosított formában fogjuk felírni. Ennek érdekében definiáljuk a G_{a} operátort minden 0 < a < 1 számra és korlátos φ függvényre a

G_{a}φ(x) = φ(x) + aP φ(x) + a^{2}P^{2}φ(x) + ⋯  (3.5)

képlet segítségével, és vizsgálni fogjuk ennek viselkedését a → 1 esetén. Ehhez hasonló módszert (egy 0 < a < 1 paraméter bevezetését, majd az a → 1 határátmenet alkalmazását) gyakran használják a Markov folyamatok elméletében.

Adva egy korlátos f(x) függvény és egy 0 < a < 1 szám, definiáljuk a φ_{a}(x) = f(x) − aP f(x) függvényt. Nem nehéz belátni, hogy f(x) = G_{a}φ_{a}(x) minden x ∈ X pontban. Ezen azonosság igazolásához az a^{n}P^{n}φ(x) = a^{n}P^{n}f(x) − a^{n+1}P^{n+1}f(x) azonosságot adjuk össze minden n = 0, 1, 2, … számra. Ha a korlátos f(x) függvény excesszív, akkor φ_{a}(x) ≥ 0 minden x ∈ X pontban. Ezen két reláció segítségével belátjuk a következő lemmát az excesszív függvények tulajdonságairól.

3.5. Lemma. Legyen adva egy X_{0}(ω), X_{1}(ω), … Markov lánc egy X téren valamely p(x, y), x, y ∈ X, átmenetvalószínűségekkel és egy f(x) korlátos, excesszív függvény ezen az X téren. Tegyük fel, hogy a Markov lánc az x pontból indul, azaz P (X_{0}(ω) = x) = 1. Ekkor a Markov lánc tetszőleges τ megállási szabályára f(x) ≥ E_{x}f(X_{τ(ω)}(ω)), sőt ha τ_{1} és τ_{2} két olyan megállási szabály, amelyekre τ_{1}(ω) ≤ τ_{2}(ω) minden ω ∈ Ω pontban, akkor E_{x}f(X_{τ_{1}(ω)}(ω)) ≥ E_{x}f(X_{τ_{2}(ω)}(ω)).

Véve az X halmaz egy tetszőleges A ⊂ X részhalmazát és egy tetszőleges x ∈ X pontból kiinduló X_{0}(ω), X_{1}(ω), … Markov láncot, definiálhatjuk azt a továbbiakban τ_{A}- val jelölt valószínűségi változót, amelynek értéke az a legkisebb (az ω ponttól függő) n nem-negatív egész szám, amelyre X_{n}(ω) ∈ A. Ekkor τ_{A}(ω) a Markov lánc megállási szabálya. Ha f(x) korlátos, excesszív függvény, akkor h_{A}(x) = E_{x}f(X_{τ_{A}(ω)}(ω)), x ∈ X, szintén korlátos, excesszív függvény.

A 3.5. lemma bizonyítása. A bizonyításban fel fogjuk használni, hogy a lemmában bevezetett P operátor teljesíti az E_{x}φ(X_{n}(ω)) = P_{n}φ(x) azonosságot minden n = 0, 1, … indexre és korlátos φ(·) függvényre. Ezért minden 0 < a < 1 számra és korlátos és az X téren definiált korlátos f(x) függvényre

f(x) = G_{a}φ_{a}(x) = φ_{a}(x) + aP φ_{a}(x) + a^{2}P^{2}φ_{a}(x) + ⋯ = E_{x} (∑_{n=0}^{∞} a^{n}φ_{a}(X_{n}(ω))) ,

ahol φ_{a}(x) = f(x) − aP f(x). Némi számolással azt kapjuk, hogy minden τ megállási szabályra, y ∈ X pontra, 0 < a < 1 számra és N = 0, 1, 2, … indexre

E_{x} (a^{τ(ω)}f(X_{τ(ω)}(ω))|τ = N, X_{N}(ω) = y) = ∑_{n=N}^{∞} a^{n}E_{y}φ_{a}(X_{n}(ω)).

Ezt az azonosságot összegezve először az y ∈ X pontokra, majd az N = 0, 1, 2, … számokra azt kapjuk, hogy

E_{x}a^{τ(ω)}f(X_{τ(ω)}(ω)) = E_{x} ( ∑_{n=τ(ω)}^{∞} a^{n}φ_{a}(X_{n}(ω)))

minden τ megállási szabályra.

Ha az f függvény excesszív akkor φ_{a}(x) ≥ 0 minden 0 < a < 1 számra, és x ∈ X pontra. Ezért a fenti relációkból következik, hogy f(x) ≥ E_{x}a^{τ(ω)}f(X_{τ(ω)}), és E_{x}a^{τ_{1}(ω)(ω)}f(X_{τ_{1}(ω)}(ω)) ≥ E_{x}a^{τ_{2}(ω)}f(X_{τ_{2}(ω)}), ha τ_{1}(ω) ≤ τ_{2}(ω) minden 0 < a < 1 számra. Alkalmazva az a → 1 határátmenetet megkapjuk a lemma első paragrafusának állításait.

Annak érdekében, hogy belássuk a lemma utolsó állítását is, definiáljuk azt a τ′_{A}(ω) valószínűségi változót, amelynek értéke az a legkisebb n ≥ 1 szám, amelyre X_{n}(ω) ∈ A. Ez a τ′_{A}(ω) valószínűségi változó szintén a Markov lánc megállási szabálya, és mivel τ′_{A}(ω) ≥ τ_{A}(ω) minden ω ∈ Ω pontban ezért a lemma már bebizonyított része alapján egy korlátos, excesszív f(·) függvényre E_{x}f(X_{τ_{A}(ω)}(ω)) ≥ E_{x}f(X_{τ′_{A}(ω)}(ω)). Másrészt E_{x}f(X_{τ_{A}(ω)}(ω)) = h_{A}(x), és

E_{x}f(X_{τ′_{A}(ω)}(ω)) = ∑_{y∈A} p(x, y)E_{y}f(X_{τ_{A}(ω)}(ω)) = ∑_{y∈X} p(x, y)h(y) = P h_{A}(x).

Ezért a fenti egyenlőtlenségből következik, hogy h_{A}(x) ≥ P h_{A}(x) minden x ∈ X pontban. A h_{A}(x) ≥ 0 egyenlőtlenség nyilvánvaló. Ezért h_{A}(·) excesszív függvény. A 3.5. lemmát beláttuk.

A következő lemma jellemzi egy adott Markov lánchoz és nyereményfüggvényhez tartozó optimális megállási stratégia nyereményének várható értékét.

3.6. Lemma. Rögzítsük egy Markov lánc p(x, y), x, y ∈ X, átmenetvalószínűségeit és egy f(x), x ∈ X, korlátos nyereményfüggvényt ezen a téren. Vegyünk minden x ∈ X pontra egy x pontból kiinduló, és p(x, y) átmenetvalószínűségekkel rendelkező X_{0}(ω), X_{1}(ω), …, P (X_{0}(ω) = x) = 1, Markov láncot, és tekintsük az f(x) nyereményfüggvényhez tartozó nyeremény várható értékének a szuprémumát az összes lehetséges megállás esetén, azaz a v(x) = sup_{τ} E_{x}f(X_{τ(ω)}(ω)) függvényt, ahol a szuprémumot a

Markov lánc összes lehetséges τ megállási szabályára vesszük. Az így definiált v(x) függvény az f(x) függvényt majorizáló minimális excesszív függvény, azaz v(x) ≥ f(x) minden x ∈ X pontban, v(x) excesszív függvény, és ha h(x) olyan excesszív függvény, amelyre h(x) ≥ f(x) minden x ∈ X pontban, akkor h(x) ≥ v(x) minden x ∈ X pontban.

Megjegyzés. Nem magától értetődő, hogy egy korlátos f(x) függvényre létezik egy azt majorizáló minimális excesszív függvény. Az, hogy ilyen függvény létezik a lemma egyik következménye.

A 3.6. lemma bizonyítása. Az nyilvánvaló, hogy v(x) ≥ f(x), és v(x) ≥ 0. (Ez utóbbi állítás azért igaz, mert ha azt a τ megállási szabályt alkalmazzuk, hogy sehol sem állunk meg, akkor nyereményünk értéke 0. Annak érdekében, hogy belássuk a v(x) ≥ P v(x) egyenlőtlenséget definiáljunk minden ε > 0 számra és y ∈ X pontra olyan egy y pontból kiinduló Markov láncra vonatkozó τ_{y}(ω) = τ_{y,ε}(ω) megállási szabályt, amelyre E_{y}f(X_{τ_{y}(ω)}(ω)) > v(y) − ε. Alkalmazzuk az x pontból kiinduló Markov láncra azt a τ megállási szabályt, hogy teszünk egy lépést, és ha X_{1}(ω) = y, akkor az X_{1}(ω), X_{2}(ω), … sorozat értékeinek figyelembe vételével a τ_{y} megállási szabályt alkalmazzuk. Ekkor

E_{x}f(X(τ(ω)(ω)) = ∑_{y∈X} p(x, y)E_{y}f(X_{τ_{y}(ω)}(ω)) ≥ ∑_{y∈X} p(x, y)[v(y) − ε] ≥ P v(x) − ε.

Innen következik, hogy v(x) ≥ P v(x) − ε, és mivel ez az állítás minden ε > 0 számra igaz, v(x) ≥ P v(x).

Legyen h(x) olyan excesszív függvény, amelyre h(x) ≥ f(x). Ekkor a 3.5. lemma alapján tetszőleges τ megállási szabályra h(x) ≥ E_{x}h(X_{τ(ω)}(ω)) ≥ E_{x}f(X_{τ(ω)}(ω)). Ezért h(x) ≥ sup_{τ} E_{x}f(X_{τ(ω)}(ω)) = v(x), ahol a szuprémumot az összes lehetséges τ

megállási szabályra vettük. A 3.6 lemmát bebizonyítottuk.

Megjegyzés. A 3.6. lemma alapján egy véges sok elemből álló X állapottér esetén a v(x) nyereményfüggvény értékének meghatározása megfogalmazható, mint a következő lineáris programozási feladat. Oldjuk meg a v(x), x ∈ X, változókra a következő lineáris programozási feladatot.

v(x) ≥ f(x) minden x ∈ X pontban.
v(x) ≥ 0 minden x ∈ X pontban.
v(x) ≥ ∑_{y∈X} p(x, y)v(y) minden x ∈ X pontban.

min ∑_{x∈X} v(x)

A következő eredményben megadunk egy optimális és egy ε-optimális megállási stratégiát.

3.7. Lemma. Tekintsünk egy X_{0}(ω), X_{1}(ω), … Markov láncot egy X állapottéren valamilyen x ∈ X, P (X_{0}(ω) = x) = 1 kezdőponttal és egy korlátos f(x), x ∈ X, nyereményfüggvénnyel. Célunk egy optimális τ(ω) megállási szabályt találni, amely maximalizálja az E_{x}f(X_{τ(ω)}(ω)) várható értéket. Ennek meghatározása érdekében definiáljuk a v(x) = sup_{τ} E_{x}f(X_{τ(ω)}(ω)) függvényt, ahol a szuprémumot a Markov lánc összes

lehetséges τ megállási szabályára vesszük. Ha az X halmaz véges, akkor a következő stratégia optimális. Definiáljuk a következő A ⊂ X halmazt. A = {u: f(u) = v(u)}. Legyen τ_{A}(ω) az a legkisebb n ≥ 0 index, amelyre X_{n}(ω) ∈ A. Ez a τ_{A}(ω) valószínűségi változó optimális megállási szabály, azaz E_{x}f(X_{τ_{A}(ω)}(ω)) = v(x).

Ha az X állapottér megszámlálható, akkor nem feltétlenül van optimális megállási szabály, de az alábbi módon minden ε > 0 számra definiálni lehet egy ε-optimális megállási szabályt. Definiáljuk az A_{ε} = {u: u ∈ X, f(u) > v(u) − ε} halmazt, és legyen τ_{A_{ε}}(ω) az a legkisebb n ≥ 0 index, amelyre X_{n}(ω) ∈ A_{ε}. Ez a τ_{A_{ε}}(ω) valószínűségi változó ε-optimális megállási szabály, azaz E_{x}f(X_{τ_{Aε} (ω)}(ω)) ≥ v(x) − ε.

1. megjegyzés. A könyv példát mutat egy olyan Markov láncra és nyereményfüggvényre, amelyekre nincs optimális megállás. A példa a következő. Legyen az állapottér az X = \{0, 1, 2, … \} halmaz, az átmenetvalószínűségek legyenek p(0, 0) = 1, p(n, 0) = \frac{1}{n^{2}} , p(n, n + 1) = 1 − \frac{1}{n^{2}} minden n = 1, 2, … számra, és legyen a nyereményfüggvény f(0) = 1, és f(n) = 1 − \frac{1}{n}, n = 1, 2, . . .. Ezzel a választással v(u) ≡ 1, A = \{0\}, ezért a τ_{A}(ω) megállási szabály úgy adható meg, hogy a Markov láncot akkor állítjuk meg, amikor az eléri a 0 pontot. De, mint azt némi, a könyvben is elvégzett számolás mutatja, ha a Markov lánc egy távoli n pontból indul, akkor ezt a stratégiát választva a Markov láncot nagy valószínűséggel sehol sem állítjuk meg, és ekkor a nyereményünk 0. Általánosabban, nincs olyan megállási stratégia, amelynek alkalmazásával egy n ≠ 0 pontból kiindulva elérhetnénk azt, hogy a nyereményünk várható értéke 1 legyen.

2. megjegyzés. Egyszerű és természetes magyarázata van annak, hogy miért érdemes egy Markov lánc optimális és majdnem optimális megállási szabályát a 3.7. lemmában megadott módon keresni. A Markov tulajdonság alapján természetes azt várni, hogy csak az x ∈ X pont értékétől függ, hogy ebben az x pontban érdemes-e megállni. Tehát nincs jelentősége annak, hogy milyen útvonalon és hanyadik lépésben jutottunk oda. Akkor érdemes megállni, ha az optimális megállás v(x) nyereménye egyenlő az azonnali megállás f(x) nyereményével. Ellenkező esetben tovább megyünk egész addig, míg egy megállásra érdemes pontba, azaz egy olyan x ∈ X pontba nem jutunk, amelyre f(x) = v(x). Ha majdnem optimális stratégiát keresünk, akkor hasonlóan érvelhetünk. Csak ebben az esetben már akkor is érdemes megállni, ha f(x) > v(x) − ε.

A 3.7. lemma bizonyítása. Tekintsük először azt az esetet, amikor az X állapottér véges. Tekintsük a h(x) = E_{x}f(X_{τ_{A}(ω)}(ω)) függvényt. A τ_{A}(ω) valószínűségi változó definiciója miatt h(x) = E_{x}v(X_{τ_{A}(ω)}(ω)), ezért a 3.5 és 3.6 lemma szerint h(x) excesszív függvény. (A 3.6 lemmára azért hivatkoztunk, mert ez biztosítja azt, hogy v(x) excesszív függvény.) Azt akarjuk belátni, hogy h(x) ≥ v(x) minden x ∈ X pontban. Ehhez a 3.6 lemma szerint elegendő azt belátni, hogy h(x) ≥ f(x) minden x ∈ X pontban.

Tegyük fel indirekt módon, hogy max_{x∈X}[f(x) − h(x)] = c > 0. Ekkor létezik olyan

a ∈ X pont, amelyre f(a)−h(a) = c > 0. Erre az a pontra és a 3.7. lemmában definiált A halmazra a ∉ A, ugyanis minden x ∈ A pontra τ_{A}(x) = 0, ezért f(x) = h(x). Másrészt h_{1}(x) = h(x) + c olyan excesszív függvény, amelyre h_{1}(x) ≥ f(x) minden x ∈ X pontban. Valóban, h_{1}(·) excesszív függvény, mert egy excesszív függvény plusz egy pozitív konstans, és h_{1}(x) ≥ h(x) + [f(x) − h(x)] = f(x) minden x ∈ X pontban. Ebből következik, hogy h_{1}(x) ≥ v(x) minden x ∈ X pontban, speciálisan h_{1}(a) ≥ v(a). De h_{1}(a) = h(a)+[f(a)−h(a)] = f(a). Ezért f(a) = h_{1}(a) ≥ v(a), ahonnan f(a) = v(a), és a ∈ A a 3.7. lemmában definiált A halmazra. Így az a feltételezés, hogy létezik olyan x ∈ X pont, amelyre h(x) < f(x) ellentmondásra vezetett, ezért f(x) ≤ h(x) minden x ∈ X pontban.

A lemma második felét, amikor az X állapottér tartalmazhat megszámlálhatóan végtelen sok pontot hasonlóan bizonyítjuk. Ebben az esetben a h(x) = E_{x}v(X_{τ_{A}(ω)}(ω)) függvényt tekintjük (tehát a v(·) és nem az f(·) függvénnyel dolgozunk), és ez a függvény hasonlóan az előző részben tekintett esethez excesszív. Elegendő azt belátni, hogy h(x) ≥ f(x) minden x ∈ X pontban, mert innen következik, hogy h(x) ≥ v(x) minden x ∈ X pontban, és a τ_{A_{ε}} valószínűségi változó definiciója szerint

E_{x}f(X_{τ_{Aε} (ω)}(ω)) ≥ E_{x}[v(X_{τ_{Aε} (ω)}(ω)) − ε] = h(x) − ε ≥ v(x) − ε

minden x ∈ X pontban.

Tegyük fel indirekt módon, hogy sup_{x∈X}[f(x) − h(x)] = c > 0. Ekkor létezik olyan

a ∈ X pont, amelyre f(a) − h(a) > 0, és f(a) − h(a) > c − ε. Minden x ∈ A_{ε} pontra τ_{A_{ε}}(ω) ≡ 0, ezért h(x) = E_{x}v(τ_{A_{ε}}(ω)) = v(x) ≥ f(x). Mivel h(a) < f(a) innen következik, hogy a ∉ A_{ε}. Másrészt h(x)+c ≥ f(x), és h(x) excesszív függvény, ahonnan következik, hogy h(x) + c ≥ v(x). Ezért f(a) > h(a) + c − ε ≥ v(a) − ε, tehát a ∈ A_{ε}. Feltételezésünk ellentmondáshoz vezetett, ezért f(x) ≤ h(x) minden x ∈ X pontban. A 3.7. lemmát bebizonyítottuk.

A könyv két példát mutat a fenti eredmények alkalmazására. Az első példa a válogatós menyasszony problémája. A könyv azt tárgyalja, hogy hogyan lehet megtalálni az optimális stratégiát ebben a feladatban a korábbi eredmények segítségével.

A fejezet korábbi részében a szerzők megmutatták, hogy a feladat visszavezethető a következő problémára. Legyen adva egy η_{1}, η_{2}, … Markov lánc az X = {1, 2, …, n} állapottéren p(k, l) = P (η_{j+1} = l|η_{j} = k) = \frac{k}{(l−1)l} átmenetvalószínűségekkel, ha 1 ≤ k < l ≤ n, és p(k, l) = 0 átmenetvalószínűségekkel egyébként. Legyen adva e Markov lánc X állapotterén az f(k) = \frac{k}{n}, 1 ≤ k ≤ n, nyereményfüggvény, és határozzuk meg az optimális megállási szabályt és a hozzátartozó nyereményfüggvényt.

E feladat megoldásához ki kell számolnunk az f(k), 1 ≤ k ≤ n, függvényt majorizáló legkisebb v(k), 1 ≤ k ≤ n, excesszív függvényt. Az, hogy v(k), 1 ≤ k ≤ n, az f(k) függvényt majorizáló excesszív függvény azt jelenti, hogy

v(k) ≥ \frac{k}{n}, 1 ≤ k ≤ n,
v(k) ≥ ∑_{l=k+1}^{n} \frac{k}{(l − 1)l} v(l), 1 ≤ k ≤ n − 1.

Nem nehéz belátni, hogy a kívánt tulajdonságú, minimális v(·) függvényt a

v(n) = 1, v(k) = max \{\frac{k}{n}, k ∑_{l=k+1}^{n} \frac{v(l)}{(l − 1)l} \} , 1 ≤ k ≤ n − 1,

képlettel lehet megadni. Innen backward indukcióval következik, hogy v(k) = \frac{k}{n}, ha k ≥

k_{n}, a (3.3) formulában definiált k_{n} számmal, és v(k) = k ∑_{l=k+1}^{n} \frac{v(l)}{(l−1)l}, ha k < k_{n}. Innen

a 3.4. lemma bizonyításának végén végzett számolás mutatja, hogy a v(k) függvényt a k < k_{n} számokra a (3.4) képlettel lehet megadni. Végül tudjuk, hogy az optimális stratégiát úgy adhatjuk, meg, hogy az első olyan k szám megjelenésénél kell megállni, amelyre v(k) = f(k). Ez jelen esetben azt jelenti, hogy akkor állunk meg, ha a Markov lánc meglátogatta a {k_{n}, k_{n} + 1, …, n} halmazt.

A másik itt tárgyalt probléma a következő. Tekintsük az X = {0, 1, …, n} halmazt, és rajta egy bolyongást a határon elnyelő falakkal, azaz tekintsünk egy Markov láncot a következő átmenetvalószínűségekkel. Legyen p(j, j − 1) = p(j, j + 1) = \frac{1}{2}, ha 1 ≤ j ≤ n − 1, és p(0, 0) = 1, P (n, n) = 1. Legyen adva egy f(j), 1 ≤ j ≤ n − 1, nyereményfüggvény az X halmazon, és számítsuk ki az optimális megállási stratégiát ebben a modellben.

Ezt a feladatot a következő módon oldhatjuk meg a könyv eredményeinek ismeretében. Azt kell meghatározni, hogy melyek az e feladatban szereplő Markov lánc átmenetvalószínűségei szerint excesszív függvények. Egy v(k), 0 ≤ k ≤ n, függvény akkor és csak akkor excesszív ezen átmenetvalószínűségek szerint, ha \frac{v(j−1)+v(j+1)}{2} ≤ v(j) minden 1 ≤ j ≤ n−1 számra, és v(j) ≥ 0, ha 0 ≤ j ≤ n. Nem nehéz belátni, (és a könyvben ezt megteszik), hogy az e Markov lánchoz tartozó excesszív függvények megegyeznak a {0, 1, …, n} halmazon definiált nem-negatív konkáv függvényekkel. Az eredeti feladatot úgy tudjuk megoldani, hogy megkeressük az f(·) függvény nem-negatív, konkáv burkolóját, azaz azt a legkisebb nem-negatív, konkáv v(·) függvényt, amely nagyobb vagy egyenlő minden pontban, mint a feladatban megadott f(·) függvény. Ezután meg kell határozni az A = {x: f(x) = v(x)} halmazt, és az optimális stratégia az, hogy akkor állítjuk meg a Markov folyamatot, amikor az először meglátogatta ezt az A halmazt.

A korábban vizsgált problémákban olyan Markov láncokat tekintettünk, amelyekben az X állapottér véges vagy megszámlálhatóan végtelen számosságú, az idő pedig diszkrét, t = 0, 1, 2, . . .. Természetesen felmerül a kérdés, hogy mit lehet mondani az általános esetben, amikor egy értékeit egy általános X állapottérben felvevő Markov folyamatot tekintünk, és az idő folytonosan is változhat, azaz az időpontok minden t ≥ 0 értéket is felvehetnek. Az az eset, amikor az idő diszkrét, de az X állapottér egy általános halmaz lehet, hasonlóan tárgyalható a korábban vizsgált problémákhoz. Ugyanez elmondható a folytonos idejű Markov folyamatok vizsgálatáról is, de ekkor sok új, nehéz és a Markov folyamatok általános elméletéhez tartozó probléma is megjelenik. Az alábbiakban egy speciális, időben folytonos Markov folyamatot vizsgálunk, de ez segít az általános esetben megjelenő problémák megértésében is. A következő feladatot tárgyaljuk.

Tekintsünk egy 0 és a pontokban elnyelő határfalakkal rendelkező, valamely x, 0 ≤ x ≤ a, pontból kiinduló W (t, ω), t ≥ 0, Wiener folyamatot, azaz egy olyan W (t, ω), t ≥ 0, sztochasztikus folyamatot, amely úgy viselkedik, mint egy Wiener folyamat mindaddig, amíg el nem éri a 0 vagy a határpontot, utána pedig örökké ebben a pontban marad. Azaz, ha W (T, ω) = 0 valamely T ≥ 0 időpontban, akkor W (t, ω) = 0 minden t ≥ T időpontban, és ha W (T, ω) = a, akkor W (t, ω) = a minden t ≥ T időpontban. Legyen adva egy folytonos f(u), 0 ≤ u ≤ a, nyereményfüggvény a [0, a] intervallumban, és határozzuk meg a most definiált elnyelő határfalakkal rendelkező Wiener folyamatnak azt a τ megállási szabályát, amelyre az E_{x}f(W (τ(ω), ω)) várható érték a lehető legnagyobb.

Az alábbi feladat vizsgálatában kulcsszerepet játszik a következő eredmény.

3.8. Lemma. Legyen W (t, ω), t ≥ 0, egy valamely x, 0 ≤ x ≤ a, pontból kiinduló Wiener folyamat 0 és a pontbeli elnyelő határfalakkal. Egy korlátos g(u), 0 ≤ u ≤ a, függvény akkor és csak akkor teljesíti minden 0 ≤ x ≤ a pontra és τ megállási szabályra a g(x) ≥ E_{x}g(W (τ(ω), ω)) egyenlőtlenséget, ha g(·) olyan konkáv függvény, amelyre g(u) ≥ 0 minden 0 ≤ u ≤ a számra.

Emlékeztetek arra, hogy τ(ω) = ∞ esetén definició szerint g(W (τ(ω), ω)) = 0. A 3.8. lemma azt jelenti, hogy az e problémában vizsgált folytonos idejű Wiener folyamatban a nem-negatív, konkáv függvények játsszák az excesszív függvények szerepét. A 3.8. lemma e fejezet legnehezebben bizonyítható eredménye. A fejezet utolsó alfejezete, a 3.8 pont ezen eredmény bizonyításával foglalkozik. A fejezet ismertetésének a végén fogom ismertetni e bizonyítás vázát és legfontosabb gondolatait.

A Wiener folyamatokkal kapcsolatos eredmények bizonyításában fontos szerepet játszik az alábbi eredmény.

3.9. Lemma. Tekintsünk egy valamely [a, b] intervallum belsejében levő x ∈ [a, b] pontból kiinduló Wiener folyamatot, és definiáljuk a τ_{a,b} megállási szabályt, amelyiknek értéke az a legkisebb t ≥ 0 szám, amelyre W (t) = a vagy W (t) = b. Ekkor

P (W (τ_{a,b}(ω), ω) = a) = \frac{b − x}{b − a}, és P (W (τ_{a,b}(ω), ω) = b) = \frac{x − a}{b − a}.

A 3.9. lemma bizonyítása. A lemma e könyvben ismertetett bizonyítása azon alapul, hogy a 2. fejezet eredményei alapján a P (W (τ_{a,b}(ω)) = a) valószínűséget megkaphatjuk, mint annak az 1-dimenziós esetben vizsgált harmonikus (tehát lineáris) függvénynek az x helyen felvett értékét, amelyre f(a) = 1, és f(b) = 0. A másik valószínűséget hasonlóan számolhatjuk ki.

A következő eredményben megfogalmazzuk a Wiener folyamatok optimális megállításáról szóló kérdésre adott választ.

3.10. Lemma. Tekintsünk egy a 0 és a pontban elnyelő határfalakkal rendelkező, valamely x, 0 ≤ x ≤ a, pontból kiinduló W (t, ω), t ≥ 0, Wiener folyamatot, és egy korlátos f(u), 0 ≤ u ≤ a, nyereményfüggvényt a [0, a] intervallumban. Definiáljuk a v(x) = sup_{τ} E_{x}f(W (τ(ω), ω)) függvényt, ahol a szuprémumot ezen elnyelő határfalakkal

rendelkező Wiener folyamat összes megállási szabályára vesszük. Ez a v(x) függvény az f(x) függvény nem-negatív konkáv burkolója, azaz v(x), 0 ≤ x ≤ a, olyan konkáv függvény, amelyre v(x) ≥ max(0, f(x)) minden 0 ≤ x ≤ a számra,és v(x) ≤ g(x) minden 0 ≤ x ≤ a számra, ha g(·) olyan a [0, a] intervallumban konkáv függvény, amelyre g(x) ≥ max(0, f(x)) minden 0 ≤ x ≤ a számra.

Ha az f(x) nyereményfüggvény nemcsak korlátos, hanem folytonos is, akkor az alább definiált τ̄ valószínűségi változó az elnyelő határfalakkal rendelkező Wiener folyamatra vett optimális megállási szabály az f(·) nyereményfüggvénnyel, azaz ez a τ̄(ω) valószínűségi változó megállási szabály, és v(x) = E_{x}f(W (τ̄(ω), ω)). Definiáljuk a Γ ⊂ [0, a] halmazt a Γ = {x: x ∈ [0, a], f(x) = v(x)} képlet segítségével. A Γ halmaz zárt, és definiálhatjuk a τ̄(ω) = min{t: W (t, ω) ∈ Γ} valószínűségi változót. Ez a τ̄(ω)) valószínűségi változó a keresett optimális megállási szabály, azaz v(x) = E_{x}f(W (τ̄(ω), ω)).

Megjegyzés. A könyv egy (egyszerű) példát mutat arra, hogy ha az f(x) nyereményfüggvény nem folytonos, akkor lehetséges, hogy a 3.10 lemmában definiált τ̄ valószínűségi változó nem optimális megállási szabály.

A 3.10 lemma bizonyítása. A bizonyítás sok hasonlóságot mutat a feladat diszkrét megfelelőjének a bizonyításával.

Először belátjuk a 3.9 lemma és a Wiener folyamat erős Markov tulajdonsága segítségével, hogy v(x) konkáv függvény. Ennek érdekében, ha adva van egy x pontból kiinduló Wiener folyamat elnyelő falakkal a 0 és a pontban, akkor tekintünk tetszőleges olyan p és q pontokat, amelyekre 0 ≤ p ≤ x ≤ q ≤ a, és definiálunk a p illetve q pontból kiinduló elnyelő falú határral rendelkező Wiener folyamatokhoz olyan τ_{p} és τ_{q} megállási szabályt, amelyekre E_{p}f(W (τ_{p}(ω), ω)) ≥ v(p) − ε, és E_{q}f(W (τ_{q}(ω), ω)) ≥ v(q) − ε valamely előre rögzített kis ε > 0 számmal. Definiáljuk egy x pontból induló elnyelő falakkal rendelkező Wiener folyamatra a következő τ(ω) megállási szabályt. Elindítjuk a Wiener folyamatot az x pontból, és megvárjuk, hogy az vagy a p vagy a q pontot elérje. Ha a p pontot éri el előbb, akkor a Wiener folyamat p pontból kiinduló darabjára a τ_{p}, ha a q pontot éri el előbb akkor a Wiener folyamat q pontból kiinduló darabjára τ_{q} megállási szabályt alkalmazzuk. Ekkor

v(x) ≥ E_{x}f(W (τ(ω), ω)) = \frac{q − x}{q − p}E_{p}f(W (τ_{p}(ω)) + \frac{x − p}{q − p}E_{q}f(W (τ_{q}(ω))

≥ \frac{q − x}{q − p}[v(p) − ε] + \frac{x − p}{q − p}[v(q) − ε] = \frac{q − x}{q − p}v(p) + \frac{x − p}{q − p}v(q) − ε

a (3.9) lemma és az erős Markov tulajdonság miatt. Mivel ez minden ε > 0 számra igaz, ezért v(x) ≥ \frac{q−x}{q−p}v(p) + \frac{x−p}{q−p}v(q). Ezért a v(x), 0 ≤ x ≤ a függvény konkáv. Másrészt v(x) ≥ 0, minden 0 ≤ x ≤ a számra, mert alkalmazhatjuk a soha meg nem állás τ(ω) ≡ ∞ stratégiáját.

Másrészt, ha g(x) olyan konkáv függvény a [0, a] intervallumban, amelyre g(x) ≥ max(0, f(x)) minden 0 ≤ x ≤ a számra, akkor a 3.8 lemma alapján

g(x) ≥ E_{x}g((W (τ(ω), ω)) ≥ E_{x}f((W (τ(ω), ω))

minden 0 ≤ x ≤ a pontra és τ megállási szabályra. Ezért

g(x) ≥ sup_{τ} E_{x}f((W (τ(ω), ω)) = v(x)

minden 0 ≤ x ≤ a számra, azaz v(x) az f(x) függvény nem-negatív konkáv burkolója.

A 3.10. lemma második felének bizonyítását annak igazolásával kezdjük, hogy v(x) folytonos függvény. Mivel v(x) konkáv, ezért ez a függvény folytonos a (0, a) nyílt intervallum minden pontjában, de az intervallum végpontjaiban csak azt tudjuk eredetileg, hogy lim_{x→0} v(x) ≥ v(0), és lim_{x→a} v(x) ≥ v(a). Ezért az kell belátni, hogy

lim_{x→0} v(x) ≤ v(0), és lim_{x→a} v(x) ≤ v(a). Tekintsük a megfelelő állítást a 0 pontban, és

vezessük be a c(u) = max_{0≤x≤u} f(x), 0 ≤ u ≤ a függvényt. A c(u) függvény folytonos.

Rögzítsünk egy 0 < u < a pontot, és tekintsük minden 0 ≤ x ≤ u pontra az x pontból kiinduló W (t, ω) Wiener folyamatot, és egy τ megállási szabályt erre a Wiener folyamatra. A 3.9 lemma alapján P_{x}(W (τ(ω)) ≥ u) ≤ \frac{x}{u}, mert a W (τ(ω)) ≥ u esemény csak úgy következhet be, ha az x pontból kiinduló Wiener folyamat előbb éri el az u mint a 0 pontot. Másrészt W (f(W (τ(ω), ω)) ≤ c(u), ha τ(ω) ≤ u, és W (f(W (τ(ω), ω)) ≤ c(a) mindig. Ezért

E_{x}f(W (τ(ω), ω)) ≤ max[c(u), 0] + \frac{x}{u} max[c(a), 0]

minden τ megállási szabályra. Ezért

v(x) ≤ max[c(u), 0] + \frac{x}{u} max[c(a), 0],

és x → 0 határátmenettel

lim_{x→0} v(x) ≤ max[c(u), 0]

minden u > 0 számra. Ezután véve az u → 0 határátmenetet, és felhasználva a lim_{u→0} c(u) = f(0) relációt azt kapjuk, hogy

lim_{x→0} v(x) ≤ max [ lim_{u→0} c(u), 0] = max[f(0), 0] ≤ v(0).

A lim_{x→a} v(x) ≤ v(a) relációt hasonlóan bizonyíthatjuk.

Mivel, mind f(x) mind v(x) folytonos függvény, ezért a Γ = {x: x ∈ [0, a], f(x) = v(x)} halmaz zárt, és a τ̄(ω) = min{t: W (t, ω) ∈ Γ} valószínűségi változó jól van definiálva (jogunk volt mimimumot írni a definicióban), és megállási szabály. A bizonyítás következő lépésében azt mutatjuk meg, hogy h(x) = E_{x}f(W (τ̄(ω), ω)) = E_{x}v(W (τ̄(ω), ω)) nem-negatív, konkáv függvény. Az indoklásban a konkáv függvényeknek néhány szemléletesen nyilvánvaló és a könyv kiegészítésében bizonyított tulajdonságára hivatkozunk.

A h(x) függvény megszorítása a Γ halmazra megegyezik a nem-negatív, konkáv v(x) függvény értékével. A komplementer nyílt halmaz nyílt intervallumok uniója, és ezen intervallumok végpontjai a Γ halmaz pontjai, és lehet még végpont a 0 vagy az a pont, amelyek nem feltétlenül elemei a Γ halmaznak. Ha egy x ∉ Γ pontra p és q az x pontot tartalmazó nyílt intervallum végpontjai, p < q, akkor a 3.9. lemma alapján h(x) = \frac{q−x}{q−p}v(p) + \frac{x−p}{q−p}v(q), azaz a h(x) függvény a [p, q] intervallumon megegyezik a p pontban v(p) és q pontban v(q) értéket felvevő lineáris függvénnyel. Ha az x pontot tartalmazó nyílt intervallum egyik végpontja a 0 vagy a pont, akkor a kép kissé módosul.

Ha például x a [0, q] intervallumban van, 0 ≠ Γ és q ∈ Γ, akkor h(x) = \frac{x}{q}v(q) és h(0) = 0. (Lehetséges, hogy v(0) > 0 ebben az esetben.) A könyv kiegészítésének egyik eredménye alapján egy ilyen tulajdonságú h(x) függvény konkáv, folytonos, és nem-negatív.

A bizonyítást befejezzük, ha megmutatjuk, hogy h(x) = v(x). Ennek bizonyítása hasonló a 3.7. lemma első felének bizonyításához. Elég azt megmutatni, hogy h(x) ≥ f(x) minden x ∈ [0, a] pontban, mert h(x) nem-negatív, konkáv függvény, ezért a lemma már bebizonyított része alapján innen következik, hogy h(x) ≥ v(x) minden x ∈ [0, a] pontban. Másrészt a h(x) és v(x) függvények definiciója alapján h(x) ≤ v(x).

Tegyük fel indirekt módon, hogy c = min_{u∈[0,a]}[f(u) − h(u)] > 0. Ekkor létezik olyan s ∈ [0, a] pont, melyre f(s) − h(s) = c > 0. Egyrészt s ∉ Γ, mert egy s ∈ Γ pontból kiinduló Wiener folyamat esetében τ̄(ω) ≡ 0, és f(s) − h(s) = 0. Másrészt h(x) + c nem-negatív, konkáv függvény, és h(x) + c ≥ f(x) minden x ∈ [0, a] pontban. Ezért h(x) + c ≥ v(x) minden x ∈ [a, b] pontban. Speciálisan h(s) + c = f(s) ≥ v(s), ahonnan s ∈ Γ, ami ellentmondás. A 3.10. lemma bizonyítását befejeztük.

Ismertetem a 3.8 lemma bizonyításának legfontosabb gondolatait. Ez hasonló elveken alapul, mint a 3.5. lemma bizonyítása. A 3.5. lemma úgy tekinthető, mint a 3.8. lemma diszkrét idejű megfelelője. Ennek bizonyításában bevezettünk egy P operátort, amely az állapottéren definiált korlátos függvények terét képezi önmagára, és ennek, illetve ezen operátor hatványainak a segítségével definiáltunk minden 0 < a < 1 paraméterre egy ettől a paramétertől függő G_{a} operátort, (lásd a (3.5) formulát), amely a Markov folyamatok elméletében használt potenciál alkalmas módosítása. Ezen G_{a} operátorok segítségével az excesszív függvényeket olyan alakban tudtuk megadni, amely egyszerűvé tette a 3.5. lemma bizonyítását egy a → 1 határátmenet alkalmazásával.

Megpróbáljuk ezt a módszert adaptálni folytonos idejű Markov folyamatok vizsgálatára. Ennek érdekében bevezetjük a P és G_{α} operátorok természetes megfelelőit folytonos idejű Markov folyamatokra, és bebizonyítjuk ezen operátorok legfontosabb tulajdonságait. Nem tudjuk közvetlenül adaptálni a diszkrét idejű Markov láncok vizsgálatában alkalmazott módszert, de egy hasonló, bár bonyolultabb eljárás segítségével célhoz érünk. Alább részletesebben ismertetem ezt a módszert.

A 3.8 lemma bizonyításának váza. Az, hogy a g(x) ≥ E_{x}g(W (τ(ω), ω)) egyenlőtlenségekből (minden 0 ≤ x ≤ a számra es τ megállási szabályra) következik, hogy g(x) nemnegatív, konkáv függvény könnyen igazolható a 3.9. lemma segítségével. Elég minden 0 ≤ x ≤ a pontra és olyan [p, q] intervallumra, amelyre x ∈ [p, q] ⊂ [0, a] az x pontból kiinduló Wiener folyamatot és azt a megállási szabályt tekinteni, amely szerint akkor állunk meg, amikor először elértük a [p, q] intervallum valamelyik végpontját. Ezután felírjuk a megfelelő egyenlőtlenséget erre a Wiener folyamatra és megállási szabályra és a g(x) függvényre a 3.9. lemma segítségével. Ezenkívül tekintjük a τ(ω) ≡ ∞ megállási szabályt, annak érdekében, hogy lássuk, g(x) ≥ 0.

A másik irányú állítás bizonyítása érdekében vezessük be először a P_{t}, t ≥ 0, operátorokat a

P_{t}f(x) = E_{x}f(W (t, ω)) = ∫_{0}^{a} f(y)μ_{x,t}( dy), 0 ≤ x ≤ a,

képlet segítségével a [0, a] intervallumon definiált korlátos függvények terén, ahol μ_{x,t} az x pontból kiinduló, a 0 és a pontban elnyelő határfalakkal rendelkező Wiener folyamat t időpontbeli értékének az eloszlása.

Nem nehéz belátni a P_{t}, t ≥ 0, operátorok következő tulajdonságait. P_{s}P_{t} = P_{s+t}. A P_{t} operátorok pozitívak a következő értelemben. Ha f(x) ≥ 0 minden x pontban, akkor P_{t}f(x) ≥ 0 minden x pontban. Ezért, ha f(x) ≥ g(x) minden x pontban, akkor P_{t}f(x) ≥ P_{t}g(x) minden x pontban. Továbbá létezik a P_{∞} = lim_{t→∞} P_{t} operátor, azaz létezik a lim_{t→∞} P_{t}f(x) = P_{∞}f(x) határérték minden korlátos f függvényre és x pontra.

Meg lehet adni a P_{∞} operátort explicit módon a P_{∞}f(x) = \frac{a−x}{a}f(0) + \frac{x}{a}f(a) képlet segítégével. E reláció bizonyítása azon múlik, hogy egy x pontból kiinduló a 0 és a pontban elnyelő falú Wiener folyamatra lim_{t→∞} P (W (t, ω) = 0) = \frac{a−x}{a} és lim_{t→∞} P (W (t, ω) = a) = \frac{x}{a}.

A [0, a] intervallumban lineáris függvények fixpontjai a P_{∞} operátoroknak. Innen és a P_{t} operátorok monotonitásából (azaz a P_{t} ≥ P_{s}, ha t > s következik, hogy az f(x) = ax + b függvényekre P_{t}f(x) = f(x) minden x pontra. Továbbá e relációból, a P_{t} operátorok pozitívitásából, és a konkáv függvények alkalmas jellemzéséből következik az, hogy ha f(x) korlátos konkáv függvény, akkor P_{t}f(x) ≤ f(x) minden t ≥ 0 és 0 ≤ x ≤ a számpárra. Ez a tulajdonság a konkavitás olyan következménye (valójában jellemzése) a Markov folyamatok nyelvén, amely fontos szerepet játszik a bizonyításban.

A bizonyítás következő lépésében bevezetjük a (3.5) képletben definiált P_{a} operátor folytonos változatát. Definiáljuk minden 0 ≤ α < 1 számra és a [0, a] intervallumon definiált, nem-negatív, korlátos korlátos g(x) függvényre a

G_{α}g(x) = ∫_{0}^{∞} α^{t}P_{t}g(x) dt = E_{x} ∫_{0}^{∞} α^{t}g(W (t, ω)) dt

operátort. Emlékeztetek arra, hogy a 3.5. lemma bizonyításának fontos lépése volt az excesszív függvények következő jellemzése. Ha f(x) excesszív függvény, akkor az felírható f(x) = G_{a}g_{a}(x) alakban tetszőleges 0 ≤ a < 1 számra a (3.5) képletben definiált G_{a} operátorral és alkalmas g_{a}(x) ≥ 0 függvénnyel. A nem-negatív konvex függvények hasonló jellemzését szeretnénk megadni a most definiált G_{α} operátor segítségével.

Csak egy valamivel gyengébb állítást tudunk belátni, de az is elegendő lesz számunkra. Nem tudunk minden nem-negatív függvényt ilyen alakban felírni, de elő tudjuk őket állítani ilyen alakú függvények alkalmas tulajdonságokkal rendelkező limeszeként, és a kívánt állítást be tudjuk bizonyítani ennek az eredménynek a segítségével. Felhasználjuk, hogy a [0, a] intervallumban nem-negatív, korlátos, konkáv f(x) függvények olyan nem-negatív, korlátos f(x) függvények, amelyek folytonosak a (0, a) nyílt intervallumban, és teljesítik a P_{t}f(x) ≤ f(x) tulajdonságot minden x ∈ [0, a] és t ≥ 0 számra.

Rögzítsünk egy 0 ≤ α < 1 számot. Belátjuk, hogy ha f(x) olyan a [0, a] intervallumon definiált nem-negatív, korlátos a (0, a) nyílt intervallumban folytonos függvény, amelyre P_{t}f(x) ≤ f(x), t ≥ 0, x ∈ [0, a], akkor felírható f(x) = lim_{s→0} h_{s}(x) alakban, ahol

a h_{s}(x) függvények monoton csökkenő módon konvergálnak a f(x) függvényhez minden x pontban, és h_{s}(x) = G_{α}g_{s}(x) az előbb definiált G_{α} operátorral és alkalmas g_{s}(x) ≥ 0 függvénnyel. Ismertetem, hogyan lehet az f(x) függvény egy kívánt előállítását megtalálni, de a bizonyítás részleteit, (ami megtalálható a könyvben) elhagyom.

Legyen h_{s}(x) = \frac{1}{s} ∫_{0}^{s} α^{t}P_{t}f(x) dt. Akkor igazolható, hogy f(x) = lim_{s→0} h_{s}(x), és

az, hogy e formulában monoton konvergencia érvényes. A h_{s}(x) függvények alkalmas reprezentációját a következő számolással kaphatjuk meg:

h_{s}(x) = \frac{1}{s} ∫_{0}^{∞} α^{t}P_{t}f(x) dt − \frac{1}{s} ∫_{s}^{∞} α^{t}P_{t}f(x) dt = ∫_{0}^{∞} \frac{(α^{t}P_{t}f(x) − α^{t+s}P_{t+s}f(x))}{s} dt

= ∫_{0}^{∞} α^{t}P_{t} (\frac{f(x) − α^{s}P_{s}f(x)}{s}) dt = G_{α}g_{s}(x),

ahol g_{s}(x) = \frac{f(x)−P_{s}f(x)}{s}. Mivel f(x) ≥ P_{s}f(x) ezért g_{s}(x) ≥ 0, és megkaptuk az f függvény kívánt előállítását.

A bizonyítás következő lépésében belátjuk, felhasználva a h_{s}(x) = G_{α}g_{s}(x) és g_{s}(x) ≥ 0 formulát, hogy h_{s}(x) ≥ E_{x}α^{τ(ω)}h_{s}(W (τ(ω), ω)) tetszőleges τ megállási szabályra. E formula bizonyítása hasonló a 3.5 lemma bizonyításának megfelelő részéhez, bár technikailag nehezebb, mert általános mezőkön értelmezett feltételes várható értékekkel kell dolgoznunk. A bizonyítás azon alapul, hogy az erős Markov tulajdonság felhasználásával be tudjuk bizonyítani, hogy

E_{x}α^{τ(ω)}h_{s}(W (τ(ω), ω)) = E_{x} ∫_{τ(ω)}^{∞} α^{t}g_{s}(W (t, ω)) dt,

míg h_{s}(x) = G_{α}g_{s}(x) = E_{x} ∫_{0}^{∞} α^{t}g_{s}(W (t, ω)) dt.

Ezután felhasználva a lim_{s→0} h_{s}(x) = f(x) relációt be tudjuk bizonyítani az f(x) ≥

E_{x}α^{τ} f(W (τ(ω), ω)) egyenlőtlenséget tetszőleges 0 ≤ α < 1 számra, majd α → 1 határátmenettel megkapjuk a 3.8. lemma bizonyítását.

Felmerülhet a kérdés, hogyan lehet a 3.8. lemma eredményét általános, folytonos idejű Markov folyamatokra általánosítani. E kérdés vizsgálatában érdemes bevezetni az excesszív függvény definicióját folytonos idejű Markov folyamatokra.

Excesszív függvény definiciója. Legyen X(t, ω), t ≥ 0 egy értékeit valamely (X, X) téren felvevő Markov folyamat, és definiáljuk az X téren definiált korlátos, mérhető függvények terén a P_{t}f(x) = E_{x}f(X(t, ω)) operátort minden t ≥ 0 számra. Egy az X téren definiált korlátos, mérhető f(x) függvény excesszív e Markov folyamatra nézve, ha

f(x) ≥ 0, P_{t}f(x) ≤ f(x), és lim_{t→0} P_{t}f(x) = f(x)

minden x ∈ X pontra és t ≥ 0 számra.

Az előző bizonyítás módszerével be lehet bizonyítani a 3.8 lemma megfelelőjét egy az erős Markov tulajdonsággal is rendelkező Markov folyamatra nézve excesszív függvényre. Azt, hogy ha f(x) korlátos, excesszív függvény egy az erős Markov tulajdonsággal rendelkező X(t, ω), t ≥ 0, Markov folyamatra nézve, akkor E_{x}f(X(τ(ω), ω)) ≤ f(x) minden x ∈ X pontra és a Markov folyamat minden τ megállási szabályára. Az elmélet fő nehézsége az excesszív függvények jellemzése.