Kahden pelaajan stokastiset nollasummapelit ja niiden yhteys p-Laplacen operaattoriin

Kahden pelaajan stokastiset nollasummapelit ja niiden yhteys p-Laplacen operaattoriin

Ky¨ osti Salonen

1.4.2022

Tiivistelm¨a:Ky¨osti Salonen, Kahden pelaajan stokastiset nollasummapelit ja niiden yhteysp-Laplacen operaattoriin (engl. Two-player stochastic zero-sum games and their connection with the p-Laplace operator), matematiikan pro gradu -tutkielma, 33 sivua, Jyv¨askyl¨an yliopisto, Matematiikan ja tilastotieteen laitos, kev¨at 2022.

T¨am¨an tutkielman tarkoituksena on n¨aytt¨a¨a p-Laplacen yht¨al¨on, joka on Laplacen yht¨al¨on ep¨alineaarinen yleistys, yhteys kahden pelaajan stokastisiin nollasummapeleihin. Tutkielmassa k¨aytetty stokastinen nollasummapeli on niin sanottu h¨airitty k¨oydenvetopeli (tug-of-war with noise), jolle rakennetaan arvo- funktiokandidaatti dynaamisen ohjelmoinnin periaatteen avulla.

Ty¨oss¨a n¨aytet¨a¨an pelin arvofunktiokandidaatin ratkaisun olemassaolo ja sen yksik¨asitteisyys. Lis¨aksi ty¨oss¨a n¨aytet¨a¨an martingaalien avulla arvofunktiokan- didaatin olevan sama kuin pelin p¨a¨attymisen odotusarvon minimointi ja maksi- mointi pelaajien strategioiden mukaisesti. Pelin p¨a¨attymisen odotusarvon kans- sa joudutaan erityisesti varmistamaan, ett¨a mitallisten strategioiden valinta on mahdollista.

Lopuksi ty¨oss¨a muodostetaan jono pelien arvofunktioita. Jono rakennetaan kutistamalla pelien askelpituutta kohti 0:aa. Ty¨on p¨a¨atuloksena osoitetaan, ett¨a kyseisen jonon raja-arvo on t¨all¨oin viskositeettiratkaisu p-Laplacen yht¨al¨o¨on.

Ty¨oss¨a joudutaan k¨aytt¨am¨a¨an viskositeettiteoriaa derivoituvuusongelmien ta- kia.

Avainsanat: p-Laplace, stokastiset nollasummapelit, h¨airitty k¨oydenveto- peli, dynaamisen ohjelmoinnin periaate, viskositeettiratkaisu.

Sis¨ allys

1 Johdanto 3

2 Yleisi¨a merkint¨oj¨a ja esitietoja 4 2.1 Martingaalit ja Doobin pys¨aytyslause. . . 7

3 Dynaamisen ohjelmoinnin periaate 11

4 K¨oydenvetopeli 17

4.1 Mitallisen strategian olemassaolo . . . 18 4.2 Arvofunktioiden yksik¨asitteisyys . . . 19

5 p-Laplacen yht¨al¨o 21

5.1 Johtaminen ja taustoja. . . 22 5.2 Suppeneminen ja DOP . . . 24

1 Johdanto

Jo klassisesti on tunnettu yhteys satunnaisk¨avelyn ja Laplacen yht¨al¨on v¨alill¨a, tai ajasta riippuvassa tapauksessa l¨amp¨oyht¨al¨on ja satunnaisk¨avelyn v¨alill¨a.

T¨all¨a on hyvin tunnettuja sovelluksia esimerkiksi talousteoriaan, jossa Black- Scholesin yht¨al¨o¨a voidaan hy¨odynt¨a¨a optioiden hinnoittelussa.

Klassisesti tunnetaan, ett¨a harmoniset funktiot, eli funktiot jotka toteuttavat Laplacen yht¨al¨on

∆u= 0, toteuttavat keskiarvoperiaatteen

u(x) = Z

B_ε(x)

u.

Keskiarvoperiaatteen tulkinta satunnaisk¨avelyn yhteydess¨a on seuraava. Odo- tusarvo pisteess¨a voidaan laskea tarkastelemalla yht¨a askelta ja summaamalla naapuriodotusarvot ottamalla huomioon yhden askeleen todenn¨ak¨oisyysmitan.

Keskiarvoperiaate on lineaarinen ominaisuus, ja ei ole ilmeisen selv¨a¨a, miten se yleistyy ep¨alineaariseen tapaukseen. Niinp¨a t¨ass¨a ty¨oss¨a on tarkoitus k¨asitell¨a keskiarvoperiaatteen ep¨alineaarinen yleistys

uε(x) = α 2 sup

B_ε(x)

uε+α 2 inf

Bε(x)

uε+β Z

Bε(x)

uε (1.1)

p-Laplacen yht¨al¨olle

∆_pu:=|∇u|^p−2 ∆u+ (p−2)∆^N_∞u

= 0,

joka palautuu Laplacen yht¨al¨oksi tapauksessa p = 2. Yll¨a merkint¨a R

B_ε(x)

tarkoittaa keskiarvointegraalia ja ∆^N_∞ normalisoitua ¨a¨aret¨on-Laplacen operaat- toria, jotka m¨a¨aritell¨a¨an tarkemmin my¨ohemmin. T¨am¨a keskiarvoperiaate ei ole aivan vastaava kuin tavallisen Laplacen yht¨al¨on tapauksessa, sill¨a uε ap- proksimoi p-Laplacen yht¨al¨on ratkaisua u, kun ε → 0 (lause 5.6). Lis¨aksi to- denn¨ak¨oisyydet α ja β eiv¨at ole mielivaltaisia, vaan ne riippuvat p:st¨a. Eri- tyisesti ty¨oss¨a n¨aytet¨a¨an keskiarvoperiaatteen approksimaation yhteys kahden pelaajan stokastisen nollasummapelin arvofunktioon (lauseet3.1ja4.2).

Lauseen 3.1, jossa osoitetaan ratkaisun olemassaolo yht¨al¨olle (1.1), todis- tus perustuu sopivalla operaattorilla iteroimiseen ja kiintopisteen l¨oyt¨amiseen.

Todistuksen vaikeus on yht¨al¨oss¨a esiintyvien sup ja inf k¨asittely raja-arvon yh- teydess¨a, joten sen avuksi osoitetaan, ett¨a suppeneminen on tasaista. Lauseen 4.2, jossa osoitetaan, ett¨a pelin arvofunktiot yhtyv¨at lauseen3.1antamaan funk- tioon, todistuksessa edellisen lauseen funktiota apuna k¨aytt¨aen arvioidaan pe- laajien strategioita. Todistuksessa rakennetaan supermartingaali ja Doobin op- tionaalisen pys¨aytyslauseen avulla osoitetaan pelin odotusarvon ja dynaamisen ohjelmoinnin periaatteen yhteys. Lauseessa joudutaan varmistamaan, ett¨a va- lituilla strategioilla saadaan aikaiseksi Borel-mitallisia funktioita. Ty¨on lopuksi todistetaan lause5.6. Koska lauseen5.6todistuksessa funktion derivoituvuutta

ei voida taata, niin esitietoina k¨asitell¨a¨an viskositeettiratkaisuja. Todistukses- sa hy¨odynnet¨a¨an aikaisemmin osoitettua tasaista suppenemista ja integroidaan testifunktion Taylorin-sarjaa.

A¨¨aret¨onharmonisten funktioiden ja k¨oydenvetopelin yhteys havaittiin ja to- distettiin l¨ahteess¨a [PSSW09]. H¨airityn k¨oydenvetopelin yhteysp-Laplacen yh- t¨al¨o¨on havaittiin pelin hieman erilaiselle versiolle viitteess¨a [PS08]. T¨ass¨a ty¨oss¨a seurataan papereissa [MPR12, LPS13, LPS14] esitettyj¨a tuloksia. Erityisesti ty¨oss¨a keskityt¨a¨an k¨asittelem¨a¨an l¨ahteen [MPR12] k¨aytt¨am¨a¨a peli¨a ja keskiar- voperiaatetta.

2 Yleisi¨ a merkint¨ oj¨ a ja esitietoja

Aloitetaan k¨aym¨all¨a l¨api ty¨oss¨a k¨aytett¨avi¨a merkint¨oj¨a ja joitakin esitietoja.

1. Merkit¨a¨anr-s¨ateist¨a x0-keskist¨a avointa palloa merkinn¨all¨a Br(x0) ={x∈Rⁿ:|x−x0|< r}. 2. Merkit¨a¨ana∧b:= min{a, b}.

3. Keskiarvointegraalille k¨aytet¨a¨an merkint¨a¨a Z

A

f := 1

|A|

Z

A

f,

jossa|A|tarkoittaa Lebesguen mittaa joukostaA. Lis¨aksi ty¨oss¨a j¨atet¨a¨an yleens¨a merkitsem¨att¨a, mink¨a suhteen integroidaan, ellei sit¨a tarvita sel- keytt¨am¨a¨an tilannetta.

4. Gradientti on

∇f(x) := (∂f

∂x1

(x), . . . , ∂f

∂xn

(x))^T, miss¨a T on vektorin transpoosi.

5. Laplacen operaattori on

∆f(x) :=

n

X

i=1

∂²f

∂x²_i(x).

6. Olkoon∇f ̸= 0. T¨all¨oinnormalisoitu ¨a¨aret¨on-Laplacen operaattori on

∆^N_∞f(x) :=|∇f(x)|⁻²⟨D²f(x)∇f(x),∇f(x)⟩

=|∇f(x)|⁻²(∇f(x))^TD²f(x)∇f(x)

=|∇f(x)|⁻²

n

X

i=1 n

X

j=1

Dijf(x)Dif(x)Djf(x).

Ty¨oss¨a k¨aytet¨a¨an osittaisderivaatoista molempia merkint¨oj¨a sekaisin

∂f

∂xi

(x) jaDif(x).

7. Olkoon∇f ̸= 0 kuten edell¨a. T¨all¨oinp-Laplacen operaattori on

∆pf(x) := div(|∇f|^p−2∇f)

=|∇f(x)|^p−2((p−2)∆^N_∞f(x) + ∆f(x)).

8. O-notaatiolla O(g(x)) kuvataan funktion asymptoottista k¨aytt¨aytymist¨a.

Merkint¨a¨an liittyy aina raja-arvo

f(x) =O(g(x)), kunx→x0,

mutta se j¨atet¨a¨an v¨alill¨a mainitsematta. Merkint¨a tarkoittaa, ett¨a on ole- massaC siten, ett¨a

|f(x)| ≤C|g(x)|

kaikillextarpeeksi l¨ahell¨a x0:aa.

9. FunktionuTaylorin-sarja O-notaatiota k¨aytt¨aen on u(y) =u(x)∇u(x)·(y−x) +1

2⟨D²u(x)(y−x),(y−x)⟩+O(|y−x|³), kuny→x, josuon kolmesti derivoituva.

Luvussa 5 t¨aytyy laskea pallointegraaleja, jotka katoavat, joten lasketaan sit¨a varten pieni aputulos.

Lemma 2.1. Olkoona, b∈R jaε >0 T¨all¨oin Z

Bε(0)

(axi+bxixj)dx= 0.

Todistus. Ajatellaan pallo B_ε(0) koordinaattien tulojoukkona, jotta p¨a¨ast¨a¨an hy¨odynt¨am¨a¨an Fubinin lausetta. J¨arjestet¨a¨an tulojoukko siten, ett¨a seuraavan koordinaatin rajat riippuvat edellisist¨a, ja ett¨a viimeinen koordinaatti vastaa integroitavaa komponenttiax_i. Merkit¨a¨an

Si:=

n

X

k=1k̸=i

x²_k.

N¨ain ollen Fubinin lauseen nojalla integraali palautuu 1-ulotteisten integraalien laskemiseksi

Z

B_ε(0)

(axi+bxixj)dx= Z

· · · Z

√ε²−S_i

−√ ε²−Si

(axi+bxixj) dxi. . .dx1

ja symmetrian nojalla Z

√ε²−Si

−√ ε²−Si

(ax_i+bx_ix_j) dx_i= (a+bx_j) Z

√ε²−Si

−√ ε²−Si

x_i dx_i

= 0,

joten n¨ain ollen

Z

B_ε(0)

(axi+bxixj)dx= 0 kaikillai, j∈ {1, . . . , n},j̸=i.

My¨os dominoidun konvergenssin lausetta tarvitaan useaan otteeseen, joten k¨ayd¨a¨an se kertauksen vuoksi l¨api ilman todistusta.

Lause 2.2 (Dominoidun Konvergenssin lause). Olkoon (f_n)^∞_n=1 jono integroi- tuvia funktioita siten, ett¨a raja-arvo

n→∞lim f_n(x) =f(x)

on olemassa melkein kaikillex∈A. Olkoon lis¨aksi g integroituva funktio siten, ett¨a

|fn(x)| ≤g(x) m.k. x∈A.

T¨all¨oinf on integroituva ja

n→∞lim Z

A

fn= Z

A

f.

Lauseen termimelkein kaikilla (m.k.) tarkoittaa, ett¨a on mahdollisesti ole- massa nollamittainen joukko, jossa kyseinen v¨aite ei p¨ade. Vastaava termi tulee vastaan my¨os stokastiikassa. Siell¨a k¨aytet¨a¨an ilmaisuamelkein varmasti (m.v.), joka tarkoittaa k¨ayt¨ann¨oss¨a samaa. T¨all¨oin v¨aitteen rikkova tapahtumien jouk- ko on todenn¨ak¨oisyysmitan suhteen nollamittainen.

M¨a¨aritelm¨a 2.3(Puolijatkuvuus). Funktiou: Ω→(−∞,∞] onalhaalta puo- lijatkuva, jos joukko{x∈Ω :u(x)> λ}on avoin kaikilleλ∈R. Toinen ekviva- lentti m¨a¨aritelm¨a on, ett¨a funktiou: Ω→(−∞,∞] on alhaalta puolijatkuva, jos

r→0lim inf

y∈Br(x)\{x}u(y)≥u(x) kaikillex∈Ω.

Vastaavasti funktio u: Ω → [−∞,∞) on ylh¨a¨alt¨a puolijatkuva, jos joukko {x∈Ω :u(x)< λ}on avoin kaikilleλ∈Rtai ekvivalentisti

r→0lim sup

y∈Br(x)\{x}

u(y)≤u(x)

kaikillex∈Ω.

Esimerkki 2.4. Paloittain m¨a¨aritelty funktio f(x) =

(0 kun x <0 1 kun x≥0 on ylh¨a¨alt¨a mutta ei alhaalta puolijatkuva.

Puolijatkuvuutta tullaan k¨aytt¨am¨a¨an viskositeettiratkaisun m¨a¨arittelemi- sess¨a. Tarkemmin puolijatkuvuuteen liittyvi¨a tuloksia k¨asitell¨a¨an esimerkiksi l¨ahteiss¨a [HKM06,Par15].

2.1 Martingaalit ja Doobin pys¨ aytyslause

K¨ayd¨a¨an seuraavaksi hyvin pintapuolisesti l¨api joitain stokastiikan perusteita, joita tulemme tarvitsemaan k¨oydenvetopelin kanssa. Tarkempien perusteluiden ja tulosten suhteen viitataan l¨ahteeseen [Gei20].

Todenn¨ak¨oisyysavaruutta merkit¨a¨an (X,F,P),

jossaX on perusjoukko,Ftapahtuma-avaruus jaPtodenn¨ak¨oisyysmitta. Ty¨os- s¨a k¨aytet¨a¨an satunnaismuuttujia, jotka ovat mitallisia funktioita perusjoukolta XavaruuksilleRtaiRⁿ. Tyypillinen satunnaismuuttuja t¨ass¨a ty¨oss¨a on k¨oyden- vetopelin sijainti kierroksellak, jota merkit¨a¨anxk:lla. Lis¨aksi ty¨oss¨a k¨aytet¨a¨an satunnaismuuttujien odotusarvoja. Tarkemmin ne m¨a¨aritelt¨aisiin integraalina todenn¨ak¨oisyysmitan Psuhteen. Tyypillinen odotusarvon merkint¨a ty¨oss¨a on

E[F(xk)] taiE^xS⁰_I,S_II[F(xk)],

miss¨a alaindeksin¨a olevia strategioitaSIjaSIIk¨asitell¨a¨an yksityiskohtaisemmin my¨ohemmin pelin m¨a¨aritelm¨an yhteydess¨a. My¨osk¨a¨an ehdollista odotusarvoa ei t¨ass¨a ty¨oss¨a m¨a¨aritell¨a tarkasti, mutta se l¨oytyy esimerkiksi m¨a¨aritelm¨ast¨a [Gei20, Definition 4.1.8]. T¨ass¨a ty¨oss¨a tyypillinen merkint¨a sille on

E[F(x_k)|Fk−1] taiE[F(x_k)|(x0, x₁, . . . x_k−1)].

Heuristisesti t¨am¨a tarkoittaa odotusarvoa, kun tiedet¨a¨an satunnaismuuttujien (x0, x1, . . . x_k−1) sis¨alt¨am¨a informaatio. Toista merkint¨a¨aE[F(xk)|F_k−1] k¨aytet- t¨aess¨a t¨am¨a sama informaatio on koodattu satunnaismuuttujien (x0, x1, . . . x_k−1) generoimaanσ-algebraanF_k−1.

Tavoitteena on todistaa Doobin optionaalisen pys¨aytyksen lause supermar- tingaaleille, joista molemmat pohjautuvat filtraation k¨asitteeseen.

M¨a¨aritelm¨a 2.5 (Filtraatio). Olkoon (X,F,P) todenn¨ak¨oisyysavaruus. Filt- raatio (F_n)^∞_n=0 on kasvava jonoσ-algebroja

F0⊂ F1⊂ · · · ⊂ F.

Filtraation idea on rajoittaa k¨aytett¨aviss¨a olevaa informaatiota mallintamal- la tapahtuneiden tapahtumien sarjaa. Annetaan seuraavaksi esimerkki ehdolli- sista odotusarvoista filtraation havainnollistamiseksi.

Esimerkki 2.6. Tarkastellaan v¨alill¨a [0,1[ m¨a¨aritelty¨a funktiota f(x) := sin(2x²−3x) +x

ja sen ehdollisia odotusarvoja. V¨aliksi on valittu puoliavoin vain kosmeettisista syist¨a, sill¨a v¨alien p¨a¨atepisteill¨a ei ole v¨ali¨a integroitaessa.

Suoritetaan er¨a¨anlainen puolitushaku funktion kuvaajalle filtraatiota k¨aytt¨a- en. Voidaan ajatella, ett¨a satunnaismuuttujana toimii kolikonheitto, jonka tulos

kertoo menn¨a¨ank¨o oikeaan vai vasempaan aliv¨aliin. Kolikonheiton tulos on 0 tai 1, jotka per¨akk¨ain asetettuna muodostavat bin¨a¨ariluvun 0, . . . Joka askeleella hakuv¨alin pituus puolitetaan ja funktion arvoa estimoidaan sen odotusarvolla kyseisell¨a v¨alill¨a. Filtraation tihetess¨a tarkoitus olisi, ett¨a funktion ehdollinen odotusarvo l¨ahestyy funktion arvoja.

Kun yht¨a¨an jakoa ei ole viel¨a tehty, tilannetta vastaavaσ-algebraF0on jouk- ko{∅,[0,1[}. T¨all¨oin funktionf ehdollinen odotusarvo on pelkk¨a vakiofunktio.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-0.4 -0.3 -0.2 -0.1 0 0.1 0.2

(a) Funktion kuvaaja

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-0.4 -0.3 -0.2 -0.1 0 0.1 0.2

(b) Odotusarvoσ-algebranF0suhteen Ensimm¨aisen jaon j¨alkeen odotusarvon kuvaaja jakautuu kahdeksi palaseksi, mit¨a vastaavaσ-algebra on

F1=

∅; [0,1[; [0,1 2[; [1

2,1[

.

Toiseen jakoon liittyv¨aσ-algebra F2=

∅; [0,1[; [0,1 4[; [1

4,1 2[; [1

2,3 4[; [3

4,1[;

[0,1 2[; [1

4,3 4[; [1

2,1[; [0,1 4[∪[3

4,1[;. . .

on jo huomattavasti suurempi, ja funktion ehdollinen odotusarvo alkaa mukailla funktion muotoa.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 -0.4

-0.3 -0.2 -0.1 0 0.1 0.2

(a) Odotusarvoσ-algebranF1 suhteen

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

-0.4 -0.3 -0.2 -0.1 0 0.1 0.2

(b) Odotusarvoσ-algebranF2suhteen Ehdollinen odotusarvo filtraation suhteen on siis heuristisesti paras arvaus funktion arvosta, kun tiedet¨a¨an, ett¨a ollaan saatu tietty kolikonheittojen sarja, eik¨a se erota v¨aleill¨a olevia funktion arvoja toisistaan.

Niin kuin esimerkiss¨a2.6huomattiin, niinσ-algebrojen varsinainen auki kir- joittaminen on turhan ty¨ol¨ast¨a. T¨am¨an takia olisi olemassa funktiojoukon ge- neroima luonnollinen σ-algebra. Koska filtraation tarkoitus on kuitenkin vain mallintaa tiedossa olevien tapahtumien historiaa, niin yksinkertaistamme mer- kint¨oj¨a k¨aytt¨am¨all¨a k¨oydenvetopeliss¨a luvussa 4 vain viimeisint¨a pelinappulan paikkaa, sill¨a osoittautuu, ett¨a sit¨a edelt¨av¨all¨a pelihistorialla ei ole vaikutusta peliin.

M¨a¨aritell¨a¨an seuraavaksi toinen t¨arke¨a apuv¨aline reilun pelin k¨asittelemises- s¨a. M¨a¨aritelm¨ass¨a merkint¨a Mn ∈ L1(X,F,P) tarkoittaa k¨ayt¨ann¨oss¨a, ett¨a sa- tunnaismuuttujaMnon integroituva todenn¨ak¨oisyysmitanPsuhteen. Tarkempi m¨a¨aritelm¨a sille l¨oytyy kohdasta [Gei20, Definition 4.1.1].

M¨a¨aritelm¨a 2.7(Martingaali). Jono satunnaismuuttujiaM = (M_n)^∞_n=0,M_n∈ L1(X,F,P), onmartingaali filtraation (Fn)^∞_n=0 suhteen, jos∀n∈Np¨atee, ett¨a

1. Mn onFn-mitallinen 2. E(|Mn|)<∞

3. E(Mn+1|Fn) =Mn melkein varmasti.

M onsubmartingaali, jos kohdassa 3 p¨atee ep¨ayht¨al¨o E(Mn+1|Fn)≥Mn

ja vastaavastisupermartingaali, jos

E(M_n+1|Fn)≤M_n.

Eli martingaali on jono satunnaismuuttujia, jossa jonon seuraavan alkion ehdollinen odotusarvo on sama kuin jonon sen hetkinen alkio riippumatta ai- kaisemmista arvoista.

M¨a¨aritelm¨a 2.8 (Pys¨aytyshetki). KuvausT :X →N∪ {+∞} on pys¨aytys- hetki, jos

{T =n}:={x∈X :T(x) =n} ∈ Fn ∀n∈N.

Pys¨aytyshetki onmelkein varmasti ¨a¨arellinen, josP({T =∞}) = 0, eli kuvaus saa arvokseen∞vain nollamittaisessa joukossa.

T¨ass¨a ty¨oss¨a tyypillinen pys¨aytyshetki T on poistumiskierros alueesta Ω.

Seuraavassa lauseessa osoitetaan, ett¨a jos peli¨a ei voi jatkaa mielivaltaisen pit- k¨a¨an, niin pys¨aytyshetke¨a vastaavaan pelin lopputulokseen ei voi vaikuttaa, mik¨ali tapahtumaketju on martingaalien mieless¨a reilu. Lauseen todistuksessa mukaillaan l¨ahteen [LaL13] l¨ahes vastaavaa todistusta.

Lause 2.9(Doobin optionaalisen pys¨aytyksen lause). Olkoon(Fn)^∞_n=0filtraatio todenn¨ak¨oisyysavaruudessa (X,F,P) ja olkoon M = (Mn)^∞_n=0 martingaali filt- raation(Fn)^∞_n=0suhteen siten, ett¨aMn on tasaisesti rajoitettu kaikillan. Olkoon lis¨aksiT pys¨aytyshetki siten, ett¨aT on melkein varmasti ¨a¨arellinen. T¨all¨oinMT

on integroituva ja

E(MT) =E(M0).

JosM on supermartingaali, niin

E(M_T)≤E(M₀).

Jos vastaavastiM on submartingaali, niin

E(M_T)≥E(M₀).

Todistus. Koska pys¨aytyshetki T on melkein varmasti ¨a¨arellinen, niin MT on melkein kaikkialla m¨a¨aritelty. Lis¨aksi koska T on melkein varmasti ¨a¨arellinen, niinT∧n→Tmelkein kaikkialla, kunn→ ∞. N¨ain ollenM_T∧n →MT melkein kaikkialla.

Selv¨asti m¨a¨aritelm¨an nojallaM_T∧n on integroituva ja martingaalien ominai- suuksiin kuuluuE(MT∧n) =E(M0). T¨alle l¨oytyy tarkempi perustelu l¨ahteest¨a [Gei20, Proposition 4.3.1].

KoskaMn on oletuksen nojalla tasaisesti rajoitettu, niin on olemassaK∈R siten, ett¨a |MT∧n| < K. N¨ain ollen dominoidun konvergenssin lauseen nojalla M_T on integroituva ja

n→∞lim E(M_T∧n) =E(M_T).

Ja koskaE(MT∧n) =E(M0) kaikillan, niinE(MT) =E(M0).

Jos taasM on supermartingaali, niin p¨a¨attely eroaa siin¨a, ett¨a E(M_T∧n)≤ E(M₀). T¨all¨oin

E(M₀)≥ lim

n→∞E(M_T∧n) =E(M_T).

Submartingaalin tapauksessa p¨a¨attely on aivan vastaava, mutta ep¨ayht¨al¨on suunta vain muuttuu.

3 Dynaamisen ohjelmoinnin periaate

T¨ass¨a luvussa on tarkoitus osoittaa, ett¨a yht¨al¨oll¨a u(x) = α

2 sup

Bε(x)

u+α 2 inf

B_ε(x)u+β Z

B_ε(x)

u (DOP)

on olemassa yksik¨asitteinen ratkaisu. Todistus seuraa ja tarkentaa vastaavaa todistusta l¨ahteess¨a [LPS14].

Koska yht¨al¨oss¨a (DOP) tarkastellaanε-s¨ateisi¨a palloja, on m¨a¨arittelyjoukkoa Ω laajennettavaε:n levyisen kaistaleen verran, jotta yht¨al¨o olisin hyvin m¨a¨ari- telty my¨os Ω:n reunalla. Joten olkoon ε >0,Ω⊂Rⁿ rajoitettu alue jaα, β >0 siten, ett¨aα+β = 1. M¨a¨aritell¨a¨an Ω:nε-levyinen reunakaistale

Γε={x∈Rⁿ\Ω : dist(x, ω)≤ε}

ja merkit¨a¨an Ω_ε= Γ_ε∪Ω. Kutsutaan funktionuarvoja joukossa Γ_εfunktionu reuna-arvoiksi.

OlkoonFεjoukko ei-negatiivisia Borel-mitallisia rajoitettuja funktioita, jot- ka on m¨a¨aritelty Ωε→R. M¨a¨aritell¨a¨an lis¨aksi operaattoriT :Fε→ Fε,

T u(x) = (_α

2sup_Bε(x)u+^α₂inf_Bε(x)u+βR

B_ε(x)u kun x∈Ω

u(x) kun x∈Γε. (3.1)

Tarkoitus on rakentaaT:n avulla rekursiivisesti ratkaisu yht¨al¨olle (DOP).

Varmistetaan viel¨a, ett¨a T on hyvin m¨a¨aritelty. Funktio T u on selv¨asti ei- negatiivinen, rajoitettu ja m¨a¨aritelty edelleen Ωε:ssa, joten jottaT u ∈ Fε kai- killa u ∈ Fε t¨aytyy osoittaa, ett¨a T u on Borel-mitallinen. Sit¨a varten riitt¨a¨a osoittaa, ett¨a kaikille Borel-funktioillev joukossa Ω_εfunktiot

sup

y∈B_ε(x)

v(y) ja inf

y∈B_ε(x)v(y), x∈Ω

ovat Borel-mitallisia joukossa Ω. T¨am¨a seuraa suoraan siit¨a, ett¨a kaikilleλ∈R joukko

(

x∈Ω : sup

B_ε(x)

v > λ )

= Ω∩

[

y∈Ωε:v(y)>λ

Bε(y)

on avoin.

Osoitetaan seuraavaksi, ett¨a operaattorillaT iteroimalla saadaan luotua so- piva funktiou, joka toteuttaa (DOP):n halutuilla reuna-arvoilla.

Lause 3.1. Olkoon F : Γ_ε →R rajoitettu Borel-funktio. T¨all¨oin on olemassa rajoitettu Borel-funktio u : Ω_ε → R, joka toteuttaa yht¨al¨on (DOP) ja jolle u

_Γ

ε=F.

Todistus. Olkoonu_j+1=T u_j kaikillaj = 0,1,2, . . . ja u0(x) =

(inf_y∈ΓεF kun x∈Ω F(x) kun x∈Γε.

Osoitetaan induktiolla, ett¨a n¨ain m¨a¨ariteltyn¨a jonouj on kasvava. Nytu1(x) = u0(x), kun x∈Γε, ja

u₁(x) = α 2( sup

Bε(x)

u₀+ inf

Bε(x)

u₀) +β Z

B_ε(x)

u₀

≥ α 2( inf

y∈Γε

F+ inf

y∈Γε

F) +β Z

Bε(x) y∈Γinfε

F

=α inf

y∈Γε

F +β inf

y∈Γε

F

= inf

y∈Γε

F =u₀(x), kunx∈Ω. Eliu₁(x)≥u₀(x) kaikilla x∈Ω_ε.

Oletetaan sitten, ett¨auj+1≥uj jollainj. T¨all¨oin u_j+2=T u_j+1

=α 2 sup

B_ε(x)

uj+1+α 2 inf

Bε(x)

uj+1+β Z

Bε(x)

uj+1

≥α 2 sup

B_ε(x)

uj+α 2 inf

B_ε(x)uj+β Z

B_ε(x)

uj

=uj+1,

joten induktioperiaatteen nojallauj+1≥uj kaikilla j= 0,1,2, . . ..

Operaattorilla T iteroimalla saadaan siis kasvava jono funktioita uj, joita rajoittaa ylh¨a¨alt¨asupy∈Γ_εF <∞. N¨ain ollen voidaan m¨a¨aritell¨aupisteitt¨aisen¨a raja-arvona

u(x) := lim

j→∞uj(x), x∈Ωε.

Osoitetaan, ett¨a suppeneminen on tasaista tekem¨all¨a vastaoletus. Josu_j →u ei suppene tasaisesti, niin p¨atee

M := lim

j→∞ sup

x∈Ωε

(u−uj)(x)>0. (3.2) Olkoonδ >0 ja valitaank≥1 tarpeeksi suuri, ett¨a joukossa Ω_ε

u−u_k ≤M +δ, (3.3)

ja ett¨a

sup

x∈Ω

β Z

Bε(x)

(u−uk)(y)dy≤δ. (3.4)

Kohdan (3.4) valinta voidaan tehd¨a, koska funktiot uj ovat vakiolla ylh¨a¨alt¨a rajoitettuja, ja siten dominoidun konvergenssin lausetta soveltaen p¨atee, ett¨a

Z

B_ε(x)

(u−u_k)→0 kaikilla x∈Ω.

Nyt (3.2):n nojalla voidaan valitax0∈Ω siten, ett¨au(x0)−uk+1(x0)≥M−δ.

Valitaan viel¨a tarpeeksi suuri l > k siten, ett¨a u(x0)−ul+1(x0) < δ. T¨ast¨a seuraa, ett¨a

ul+1(x0)−uk+1(x0)≥M−2δ. (3.5) Lis¨aksi tiedet¨a¨an, ett¨a mielivaltaiselle joukolleAp¨atee

sup

A

u_l−sup

A

u_k≤sup

A

(u_l−u_k). (3.6)

Vastaava p¨atee my¨os, kun yht¨al¨on vasemman puolen supremum korvataan infi- mumilla. Joten funktiojononujm¨a¨aritelm¨an ja monotonisuuden nojalla yhdess¨a ep¨ayht¨al¨oiden (3.2)-(3.6) kanssa saadaan, ett¨a

M−2δ≤ul+1(x0)−uk+1(x0)

=α 2 sup

Bε(x0)

u_l+α 2 inf

B_ε(x₀)

u_l+β Z

B_ε(x₀)

u_l

− α 2 sup

B_ε(x₀)

uk+α 2 inf

B_ε(x₀)uk+β Z

Bε(x0)

uk

!

≤α sup

B_ε(x₀)

(ul−uk) +β Z

Bε(x0)

(ul−uk)

≤α sup

B_ε(x₀)

(ul−uk) +β Z

B_ε(x₀)

(u−uk)

≤α(M+δ) +δ.

Jos ep¨ayht¨al¨on j¨arjest¨a¨a uuteen muotoon

(1−α)M ≤(α+ 3)δ,

niin huomaa, ett¨a se johtaa ristiriitaan, mik¨ali δ valitaan tarpeeksi pieneksi, koskaα <1.

Nyt koska u_j → usuppenee tasaisesti, niin mielivaltaiselle ε₀ >0 voidaan valitaksiten, ett¨a|u(x)−u_j(x)| ≤ε₀kaikilla j≥kjax∈Ω_ε. T¨all¨oin yht¨al¨on (3.6) nojalla

0≤ sup

B_ε(x)

u− sup

B_ε(x)

uj

≤ sup

B_ε(x)

(u−uj)

≤ sup

B_ε(x)

ε0

≤ε0.

Eli saadaan, ett¨a

j→∞lim sup

B_ε(x)

uj = sup

B_ε(x)

u.

Koska yht¨al¨o¨a (3.6) vastaava v¨aite p¨atee my¨os infimumille, niin soveltamalla samaa p¨a¨attely¨a saadaan, ett¨a

j→∞lim inf

B_ε(x)

u_j = inf

B_ε(x)

u.

N¨ain ollen kaikille x∈Ω p¨atee u(x) = lim

j→∞u_j+1(x)

= lim

j→∞T uj(x)

= lim

j→∞

α 2 sup

B_ε(x)

uj(x) +α 2 inf

B_ε(x)uj(x) +β Z

Bε(x)

uj(y)dy

!

= α 2 sup

B_ε(x)

u(x) +α 2 inf

B_ε(x)u(x) +β Z

Bε(x)

u(y)dy.

Tasaisen suppenemisen nojalla raja-arvousiis toteuttaa dynaamisen ohjelmoin- nin periaatteen ja sill¨a on oikeat reuna-arvot konstruktiosta johtuen.

Eli yht¨al¨oll¨a (DOP) on olemassa ratkaisu. Seuraava lause takaa, ett¨a anne- tuilla reuna-arvoilla ratkaisu on my¨os yksik¨asitteinen.

Lause 3.2. Olkoon u ja u^′ ratkaisuja yht¨al¨o¨on (DOP) reuna-arvoilla g ja g^′ joukossaΓε. T¨all¨oin

sup

x∈Ω

|u^′−u|(x)≤ sup

x∈Γ_ε

|g^′−g|(x).

Todistus. Riitt¨a¨a osoittaa, ett¨a M := sup

x∈Ω

(u^′−u)(x)≤ sup

x∈Γ_ε

(g^′−g)(x) =:m,

koska loppu tuloksesta voidaan osoittaa t¨aysin vastaavalla p¨a¨attelyll¨a.

Oletetaan, ett¨a v¨aite ei p¨ade, eli M > m. Joten koska uja u^′ toteuttavat (DOP):n, niin hy¨odynt¨am¨all¨a ep¨ayht¨al¨o¨a (3.6) saadaan, ett¨a kaikillex∈Ω p¨atee

u^′(x)−u(x) =α 2( sup

B_ε(x)

u^′− sup

B_ε(x)

u) +α 2( inf

Bε(x)

u^′− inf

Bε(x)

u)

+β(

Z

Bε(x)

u^′− Z

Bε(x)

u)

≤α sup

y∈Bε(x)

(u^′−u)(y) +β Z

B_ε(x)

(u^′−u)(y)dy

≤αM+β Z

Bε(x)

(u^′−u)(y)dy.

(3.7)

Tarkastellaan seuraavaksi joukkoa

G:={x∈Ωε:u^′(x)−u(x) =M}.

Vastaoletuksen nojallaG⊂Ω. Osoitetaan ensin, ett¨a G on ep¨atyhj¨a. Valitaan jonoxk∈Ω siten, ett¨a (u^′−u)(xk)→M, kunk→ ∞jaxk→x0∈Ω.

Koska Z

B_ε(x_k)

(u^′−u)(y)dy= Z

Ω

χ_Bε(xk)(y)(u^′−u)(y)dy ja

|χ_Bε(xk)(y)(u^′−u)(y)| ≤ sup

x∈Ωε

|u^′−u| kaikillak= 1,2, . . . , miss¨aχ on karakteristinen funktio

χ_Bε(xk)(x) :=

(1 kun x∈Bε(xk) 0 kun x /∈B_ε(x_k), niin dominoidun konvergenssin lauseen nojalla

k→∞lim Z

B_ε(x_k)

(u^′−u)(y)dy= lim

k→∞

Z

Ω

χB_ε(x_k)(y)(u^′−u)(y)dy

= Z

Ω

k→∞lim χ_Bε(xk)(y)(u^′−u)(y)dy

= Z

Ω

χ_Bε(x0)(y)(u^′−u)(y)dy

= Z

Bε(x0)

(u^′−u)(y)dy.

Koska lis¨aksi kaikillax∈Ω p¨ateeM:n m¨a¨aritelm¨an takia αM+β

Z

Bε(x)

(u^′−u)(y)dy≤αM+β Z

Bε(x)

M

=αM+βM=M, niin yht¨al¨on (3.7) nojalla erityisesti kaikille xk p¨atee, ett¨a

(u^′−u)(xk)≤αM+β Z

B_ε(x_k)

(u^′−u)(y)dy≤M.

Koska jonoxk oli valittu siten, ett¨a

k→∞lim(u^′−u)(xk) =M, niin suppiloperiaatteen nojalla

k→∞lim αM+β Z

Bε(xk)

(u^′−u)(y)dy

!

=M, josta seuraa, ett¨a

k→∞lim Z

Bε(xk)

(u^′−u)(y)dy=M,

koskaα+β= 1. N¨ain ollen Z

B_ε(x₀)

(u^′−u)(y)dy=M.

Koskau^′−u≤M pallossaB_ε(x₀)∈Ω_εM:n m¨a¨aritelm¨an nojalla, niin saadaan ett¨a u^′ −u = M melkein kaikkialla B_ε(x₀):ssa ja siten |B_ε(x₀)\G| = 0. Eli erityisestiG̸=∅.

Nyt vastaavalla p¨a¨attelyll¨aG:ll¨a on ominaisuus:

Josx∈G, niin|Bε(x)\G|= 0. (3.8) Ominaisuus (3.8) johtaa kuitenkin ristiriitaan. Olkoone1 ensimm¨ainen kanta- vektori. Jos x∈G, niin (3.8):n nojalla G∩B^ε

4(x+^ε₂e1)̸=∅. N¨ain l¨oydet¨a¨an helposti uusi alkioG:st¨a, jonka ensimm¨ainen koordinaatti on suurempi kuinx:n.

Erityisesti voidaan valita sellainen jono alkioita, joiden ensimm¨aiset koordinaa- tit l¨ahetyv¨at ¨a¨aret¨ont¨a, mik¨a on ristiriita, sill¨aG⊂Ω ja Ω on rajoitettu.

Lauseen3.2seuraus osoittaa, ett¨a iterointiprosessin tuottama funktio ei riipu l¨aht¨oarvonu₀valinnasta.

Seuraus 3.2.1. OlkoonF : Γ_ε→Rjau₀: Ω_ε→Rrajoitettuja Borel-funktioita siten, ett¨au₀

_Γ

ε=F. Olkoon lis¨aksi funktiot u_j m¨a¨aritelty kuten lauseessa 3.1.

T¨all¨oin jonou_j suppenee tasaisesti yksik¨asitteiseen funktioonu, joka on yht¨al¨on (DOP)ratkaisu reuna-arvoilla F.

Todistus. Oletetaan, ett¨a on olemassa funktio C joukossa Γε, jolle |F| ≤ C.

T¨all¨oin lauseen 3.1 todistus pysyy samana, jos valitaan iteroinnin aloituspis- teeksi joko u^′₀ = −C tai u^′′₀ = C. Ainut ero n¨aiden v¨alill¨a on, ett¨a funktioon u^′′₀ liittyv¨a jono u^′′_j on v¨ahenev¨a. Mutta koska operaattori T on j¨arjestyksen s¨ailytt¨av¨a, niinu^′_j≤uj≤u^′′_j. Lauseen3.2nojalla ne kaikki suppenevat kuiten- kin samaan funktioon.

Havainnollistetaan seuraavaksi iterointiprosessia.

Esimerkki 3.3. Olkoon Ω =]0,1[,ε= 0,1 ja reuna-arvofunktioF : Ω_ε→R F(x) =

(0 kun x≤0 1 kun x≥1.

M¨a¨aritell¨a¨an aluksi funktioureuna-alueen arvojen minimiksi ja l¨ahdet¨a¨an ite- roimaan operaattorillaT, joka m¨a¨ariteltiin kaavassa (3.1). Kuvista n¨akyy kuin- kaualkaa nousemaan ja 100-1000 iteroinnin kohdalla funktion kuvaajan muoto ei juuri en¨a¨a muutu. Funktion kuvaaja j¨a¨a katkonaiseksi k¨aytetyst¨a askeleesta εjohtuen. Jos tilannetta ajattelee pelim¨aisesti, niin on huomattavasti parempi olla alleεp¨a¨ass¨a reunasta kuin yli. Tilanne on luonnostaan diskreettinen.

-0.2 0 0.2 0.4 0.6 0.8 1 1.2 0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

(a) 1 iteraatio

-0.2 0 0.2 0.4 0.6 0.8 1 1.2

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

(b) 10 iteraatiota

-0.2 0 0.2 0.4 0.6 0.8 1 1.2

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

(c) 100 iteraatiota

-0.2 0 0.2 0.4 0.6 0.8 1 1.2

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

(d) 1000 iteraatiota

Kuva 3: OperaattorillaT iteroimalla muodostuva kuvaaja

Seuraavassa luvussa k¨aymme kahden pelaajan stokastisen k¨oydenvetopelin m¨a¨arittely¨a tarkemmin l¨api. Viidenness¨a luvussa taas tarkastelemme, mit¨a ta- pahtuu, kun askeleenεpituutta l¨ahdet¨a¨an kutistamaan kohti 0.

4 K¨ oydenvetopeli

T¨ass¨a luvussa tarkastellaan kahden pelaajan stokastista nollasummapeli¨a ja tarkoituksena on osoittaa, ett¨a pelin arvofunktio itse asiassa onkin ratkaisu yht¨al¨o¨on (DOP). Todistuksissa seurataan paperissa [LPS14] osoitettuja tulok- sia.

Pelin ideana on, ett¨a kaksi pelaajaa pelaa er¨a¨anlaista yleistetty¨a k¨oyden- vetopeli¨a, jossa pelinappulan paikkaa h¨airit¨a¨an satunnaisesti. Pelialueena toi- mii rajoitettu avoin ja yhten¨ainen joukko Ω ja pelin aloituspiste on x₀ ∈ Ω.

Peliss¨a heitet¨a¨an kahdenlaista kolikkoa. Toinen kolikoista on painotettu to- denn¨ak¨oisyyksilleαjaβ ja toinen kolikoista on rehellinen.

Jokaisen vuoron alussa heitet¨a¨an ensin painotettua kolikkoa, joka m¨a¨ar¨a¨a siirt¨av¨atk¨o pelaajat pelinappulaa vai siirtyyk¨o se satunnaisesti. Todenn¨ak¨oisyy- dell¨aβ pelinappula siirret¨a¨an satunnaiseen paikkaanxi+1∈Bε(xi) tasaisen to- denn¨ak¨oisyysjakauman mukaan. Nappulan uusi paikka arvotaan tasaisesti jou-

kosta Bε(xi), jonka j¨alkeen vuoro p¨a¨attyy. Todenn¨ak¨oisyydell¨a α taas pelaa- jat heitt¨av¨at rehti¨a kolikkoa selvitt¨a¨akseen kumpi nappulaa saa siirt¨a¨a. My¨os pelaajat joutuvat valitsemaan siirtonsa avoimesta pallostaBε(xi) haluamansa strategian perusteella.

x₀

xτ

Ω

Γ_ε

Kuva 4: Esimerkki pelin kulusta

Peli p¨a¨attyy, kun pelinappula poistuu alueesta Ω, ja pelin p¨a¨atytty¨a pelaaja II maksaa pelaajalle I summan, joka riippuu siit¨a, mihin pelinappula p¨a¨atyi.

Eli josxτ on ensimm¨ainen piste alueen Ω ulkopuolella ja F : Γε →Rpeliss¨a sovittu maksufunktio, niin pelaajan II pelin p¨a¨atytty¨a maksettava summa on silloinF(xτ).

T¨allainen maksufunktion m¨a¨aritelm¨a on mielek¨as, koska pelialue Ω on ra- joitettu ja satunnaisen siirron todenn¨ak¨oisyysβ >0. N¨ain ollen voidaan valita tarpeeksi suuriN0∈Nsiten, ett¨aN0askeleen satunnaisk¨avelyε-mittaisia siirto- ja p¨a¨atyy pelialueen ulkopuolelle jollain positiivisella todenn¨ok¨oisyydell¨ap >0.

Ja koska peli sis¨alt¨a¨a melkein varmasti ¨a¨arett¨om¨an monta t¨allaista k¨avely¨a, niin peli p¨a¨attyy melkein varmasti strategoista riippumatta. Todistus t¨alle sivuute- taan, mutta se l¨oytyy lemmasta [Har16, Lemma 3.1].

4.1 Mitallisen strategian olemassaolo

Koska pelaajat joutuvat valitsemaan pelin seuraavan pisteen avoimesta pallosta, niin heid¨an t¨aytyy pysty¨a valitsemaan piste mahdollisimman l¨ahelt¨a funktion supremumia tai infimumia. Seuraavan lauseen todistuksessa joudumme integroi- maan n¨ait¨a strategioita, joten on t¨arke¨a¨a, ett¨a ne ovat Borel-mitallisia. Lusinin mitallisen valinnan lausetta hy¨odynt¨aen osoittautuu onneksi niin, ett¨a t¨allaiset strategiat on mahdollista rakentaa.

Lemma 4.1. Olkoon u : Ωε → R rajoitettu Borel-funktio ja δ > 0. T¨all¨oin on olemassa rajoitetut Borel-funktiot Ssup, Sinf: Ω →Ωε siten, ett¨a Ssup(x)∈ B_ε(x),S_inf(x)∈B_ε(x)ja

u(S_sup(x))≥ sup

Bε(x)

u−δ u(S_inf(x))≤ inf

Bε(x)

u+δ kaikillex∈Ω.

Todistus. Riitt¨a¨a osoittaa v¨aite funktiolle Ssup, sill¨a toinen osa v¨aitteest¨a seu- raavaa vastaavalla argumentilla.

Merkit¨a¨an B:ll¨a numeroituvaa kokoelmaa palloja B ⊂ Ωε, joiden s¨ade ja keskipisteen koordinaatit ovat rationaalisia. JokaiselleB∈ Bvalitaan pistexB∈ B siten, ett¨a

u(x_B)≥sup

B

u−δ 2.

Merkit¨a¨an n¨ain valittujen pisteiden kokoelmaaS:={xB :B ∈ B}. KoskaBon numeroituva, niin my¨osS on numeroituva.

Koska mielivaltainen avoin pallo Br(x)⊂Ωε voidaan kirjoittaa yhdisteen¨a B:n palloista, niin jokaisellex∈Ω

sup

B_ε(x)

u≤ sup

S∩B_ε(x)

u+δ 2.

FunktioSsup saadaan siten soveltamalla Lusinin lausetta, joka on muotoiltu ja todistettu esimerkiksi lauseessa [Sri98, Theorem 5.8.11], Borel-joukkoon

(x, y)∈Ω×Ωε:|x−y|< εja sup

B_ε(x)

u < u(y)−δ ∩(Rⁿ×S).

4.2 Arvofunktioiden yksik¨ asitteisyys

Pelaajan I strategia on Borel-mitallinen funktio, joka pelin t¨am¨an hetkisen tilan perusteella antaa seuraavan siirron. Eli esimerkiksi, jos kyseess¨a on pelaajan I vuoro ja peli¨a on pelattu jo k vuoroa siirroilla (x₀, x₁, . . . , x_k), niin pelaajan I seuraava siirto m¨a¨ar¨aytyy strategianS_I mukaan

S_I(x₀, x₁, . . . , x_k) =x_k+1∈B_ε(x_k).

VastaavastiSII on pelaajan II strategia.

Strategioissa voisi ottaa huomioon pelin aiemmat tilat tai jopa pelin aikana tapahtuneet kolikonheitot. Osoittautuu kuitenkin, ett¨a n¨am¨a eiv¨at tuo mit¨a¨an uutta pelaajien strategioihin [LPS14, Corollary 3.3]. K¨aytet¨a¨an siksi startegiois- ta merkint¨a¨a

SI(xk) =xk+1∈Bε(xk),

jossa pelin seuraavan siirron ajatellaan riippuvan vain t¨am¨an hetkisest¨a peli- nappulan paikasta.

Koska pelaajien tavoite on maksimoida ja minimoida pelin p¨a¨attyess¨a mak- settava summa, on luonnollista valita pelin arvofunktioksi pelaajalle I

u^ε_I(x₀) = sup

S_I

inf

S_IIE^xS⁰I,SII[F(x_τ)]

ja pelaajalle II

u^ε_II(x0) = inf

S_IIsup

S_I E^xS⁰_I,S_II[F(xτ)],

miss¨a E^xS⁰_I,S_II[F(xτ)] on pelin lopun odotusarvo, joka lasketaan kaikkien mah- dollisten polkujen yli. Odotusarvossa k¨aytetty todenn¨ak¨oisyysmitta rakentuu viitteen [MPR12, s. 6-7] mukaisesti yhden askeleen todennk¨oisyysmitoista.

Seuraavaksi huomaamme, ett¨a n¨ain m¨a¨aritellyt arvofunktiot itse asiassa joh- tavat samaan kuin (DOP):n ratkaiseminen.

Lause 4.2. Olkoonu^ε_I ja u^ε_II pelaajien I ja II arvofunktiot, kuten edell¨a m¨a¨ari- teltiin, ja u (DOP):n ratkaisu. T¨all¨oin

u=u^ε_I =u^ε_II.

Erityisesti pelin arvofunktio on Borel ja se on m¨a¨aritelty koko joukossa Ω.

Todistus. Koska inf

SII

E^xS⁰_I,S_II[F(xτ)]≤E^xS⁰_I,S_II[F(xτ)]≤sup

SI

E^xS⁰_I,S_II[F(xτ)], niin

sup

S_I

infS_IIE^xS⁰_I,S_II[F(xτ)]≤sup

S_I E^xS⁰_I,S_II[F(xτ)].

Ja vastaavasti sup

S_I

inf

SII

E^xS⁰_I,S_II[F(xτ)]≤inf

SII

sup

S_I E^xS⁰_I,S_II[F(xτ)].

Joten n¨ain ollen

u^ε_I ≤u^ε_II. Riitt¨a¨a siis osoittaa, ett¨a

u^ε_II≤u, (4.1)

sill¨a vastaavan argumentin nojallau^ε_I ≥u.

Valitaan pelaajan II strategia S_II⁰ siten, ett¨a pisteess¨a x_k−1 ∈ Ω pelaaja siirt¨a¨a pelinappulan pisteeseen, joka melkein minimoi u:n pallossa Bε(xk−1).

Eli jos kiinnitet¨a¨anη >0, niinS_II⁰(xk−1) =xk siten, ett¨a u(xk)≤ inf

B_ε(xk−1)u+η2^−k. (4.2) Lemman4.1nojalla n¨ain rakennettu strategia voidaan valita Borel-mitalliseksi.

Valitaan seuraavaksi pelaajalle I mielivaltainen strategiaSI. T¨all¨oin kun peli on pisteess¨ax_k−1, niin pelin m¨a¨aritelm¨an mukaan

E^x_S⁰_I,S⁰

II

u(x_k) +η2^−k|x_k−1

= α

2 u(S_II⁰(xk−1)) +u(SI(xk−1)) +β

Z

B_ε(x_k−1)

udy+η2^−k.

Joten jos k¨aytet¨a¨an ep¨ayht¨al¨o¨a (4.2) ja arvioidaan pelaajan I strategiaa yl¨osp¨ain pelk¨all¨a supremumilla, niin saadaan, ett¨a

α

2 u(S_II⁰(x_k−1)) +u(S_I(x_k−1)) +β

Z

B_ε(xk−1)

udy+η2^−k

≤α

2 inf

B_ε(x_k−1)u+η2^−k+ sup

B_ε(xk−1)

u

! +β

Z

Bε(xk−1)

udy+η2^−k. Koskautoteuttaa yht¨al¨on (DOP), niin itseasiassa

α

2 inf

Bε(xk−1)

u+η2^−k+ sup

Bε(xk−1)

u

! +β

Z

Bε(xk−1)

udy+η2^−k

=u(x_k−1) +η2^−k(1 + α 2)

≤u(xk−1) +η2^−(k−1). Eli yhdess¨a n¨aist¨a seuraa, ett¨a

E^x_S⁰_I,S0 II

u(x_k) +η2^−k|xk−1

≤u(x_k−1) +η2^−(k−1).

N¨ain ollen riippumatta strategiasta S_I prosessi M_k = u(x_k) +η2^−k on super- martingaali. Lis¨aksi koskauon rajoitettu, niin t¨all¨oin my¨osM_k on rajoitettu.

Koska peli loppuu melkein varmasti, niin pys¨aytyhetki τ on t¨all¨oin m.v.

¨a¨arellinen, ja koskaF(x_τ) =u(x_τ), niinM_τ =F(x_τ) +η2^−τ. T¨all¨oin u^ε_II(x0) = inf

SII

sup

SI

E^xS⁰_I,S_II[F(xτ)]

≤sup

SI

E^x_S⁰_I,S0 II

[F(xτ) +η2^−τ]. (4.3) Nyt Doobin optionaalisen pys¨aytyksen lauseen (lause2.9) nojalla

sup

S_I E^x_S⁰_I,S0 II

[F(xτ) +η2^−τ]

= sup

S_I E^x_S⁰_I,S0 II

[Mτ]

≤sup

S_I E^x_S⁰_I,S0 II

[M0]

=u(x0) +η.

Koskaη >0 oli valittu mielivaltaisesti, niin yhdess¨a yht¨al¨on (4.3) kanssa se todistaa v¨aitteen (4.1). Todistuksen toinen suunta saadaan tekem¨all¨a vastaava strategian valinta pelaajalle I.

5 p-Laplacen yht¨ al¨ o

T¨ass¨a luvussa on tarkoitus tarkastella mit¨a tapahtuu, kun yht¨al¨oss¨a (DOP) pal- lon s¨adett¨aεl¨ahdet¨a¨an kutistamaan kohti 0:aa. Tavoitteena on osoittaa, ett¨a ta- saisesti suppenevan jononun →uraja-arvo on viskositeettiratkaisup-Laplacen

yht¨al¨olle

(∆pu(x) = 0 x∈Ω

u(x) =F(x) x∈∂Ω. (5.1)

P¨a¨attely nojaa artikkelissa [MPR12] tehtyyn todistukseen. Ongelmana on se, ett¨a on mahdollista l¨oyt¨a¨au, joka ei ole kaikkialla derivoituva. Niinp¨a joudum- me k¨asittelem¨a¨anu:taviskositeettiratkaisuna. Esimerkkej¨ap-harmonisista funk- tioista ja niiden ominaisuuksista l¨oytyy l¨ahteest¨a [Aro89].

5.1 Johtaminen ja taustoja

Aikaisemmin m¨a¨ariteltiin p-Laplacen operaattori

∆pf = div(|∇f|^p−2∇f), joka on Euler-Lagrangen yht¨al¨op-Dirichlet’n integraalille

1 p

Z

Ω

|∇f|^pdx.

Johdetaan se hieman eri muotoon. Muistetaan, ett¨aLaplacen operaattori on

∆f(x) :=

n

X

i=1

∂²f

∂x²_i(x).

Olkoon∇f(x)̸= 0. M¨a¨aritell¨a¨annormalisoitu ¨a¨aret¨on-Laplacen operaattori

∆^N_∞f(x) :=|∇f(x)|⁻²⟨D²f(x)∇f(x),∇f(x)⟩

=|∇f(x)|⁻²(∇f(x))^TD²f(x)∇f(x)

=|∇f(x)|⁻²

n

X

i=1 n

X

j=1

Dijf(x)Dif(x)Djf(x),

miss¨a D²f on Hessen matriisi. N¨ain ollen

∆pf = div(|∇f|^p−2∇f)

=|∇f|^p−2div(∇f) + (∇|∇f|^p−2)· ∇f. (5.2) Divergenssin m¨a¨aritelm¨an mukaan

div(∇f) =

n

X

i=1

∂(∇f)_i

∂xi

=

n

X

i=1

∂²f

∂x²_i

= ∆f.

Nyt

∇|∇f|^p−2=∇

n

X

i=1

∂f

∂xi

2!^p−2₂

=





∂

∂x1 n

X

i=1

∂f

∂xi

2!^p−2₂ , . . .





=



 p−2

2

n

X

i=1

∂f

∂x_i

²!^p−4₂ 2

n

X

i=1

∂f

∂x_i

∂²f

∂x₁∂x_i

! , . . .





= (p−2)|∇f|^p−4

n

X

i=1

∂f

∂xi

∂²f

∂x1∂xi

, . . .

! ,

joten

(∇|∇f|^p−2)· ∇f = (p−2)|∇f|^p−4





n

X

j=1 n

X

i=1

∂f

∂x_i

∂²f

∂x_j∂x_i

! ∂f

∂x_j





= (p−2)|∇f|^p−4

n

X

j=1 n

X

i=1

∂f

∂xj

∂f

∂xi

∂²f

∂xj∂xi

= (p−2)|∇f|^p−2∆^N_∞f.

N¨ain ollen yht¨al¨on (5.2) nojalla

∆pf =|∇f|^p−2∆f+ (p−2)|∇f|^p−2∆^N_∞f

=|∇f|^p−2 ∆f+ (p−2)∆^N_∞f .

Eli olemme kiinnostuneita siis k¨ayt¨ann¨oss¨a yht¨al¨on

∆f+ (p−2)∆^N_∞f = 0 (5.3)

ratkaisuista ainakin, kun ∇f(x) ̸= 0. Koska funktion derivoituvuutta ei voida taata kaikkialla, m¨a¨aritell¨a¨an avuksi viskositeettiratkaisu, jossa derivoituvuus vaaditaan vain apuna k¨aytett¨avilt¨a testifunktioilta.

M¨a¨aritelm¨a 5.1. Funktioϕkoskettaa funktiota u alhaaltapisteess¨ax∈Ω, jos ϕ(x) =u(x) jau(y)> ϕ(y) kuny̸=x.

Vastaavasti funktioϕkoskettaa funktiota u ylh¨a¨alt¨a pisteess¨a x∈Ω, jos ϕ(x) =u(x) jau(y)< ϕ(y) kuny̸=x.

Jotta koskettaminen olisi ylip¨a¨at¨a¨an hyvin m¨a¨aritelty, funktiosta t¨aytyy olet- taa sopiva puolijatkuvuus.

M¨a¨aritelm¨a 5.2 (Viskositeettiratkaisu). Olkoon 1 < p < ∞. Alhaalta puo- lijatkuva funktio u on superratkaisu yht¨al¨o¨on (5.3), jos kaikilleϕ ∈ C², jotka koskettavat funktiotaualhaalta pisteess¨a x∈Ω, ja joille∇ϕ(x)̸= 0, p¨atee

(p−2)∆^N_∞ϕ(x) + ∆ϕ(x)≤0.

Vastaavasti ylh¨a¨alt¨a puolijatkuva funktio u onsubratkaisu yht¨al¨o¨on (5.3), jos kaikilleϕ∈C², jotka koskettavat funktiota uylh¨a¨alt¨a pisteess¨a x∈Ω, ja joille

∇ϕ(x)̸= 0, p¨atee

(p−2)∆^N_∞ϕ(x) + ∆ϕ(x)≥0.

Funktiouonviskositeettiratkaisu, jos se onsuper- ja subratkaisu.

M¨a¨aritelm¨a 5.3. Funktio u∈W_loc^1,p(Ω) onheikko ratkaisu yht¨al¨o¨on (5.1), jos Z

Ω

|∇u|^p−2⟨∇u,∇ϕ⟩= 0 kaikillaϕ∈C₀^∞(Ω).

Lis¨atietoja Sobolev-avaruuksista l¨oytyy l¨ahteist¨a [Par19,Eva98]. Tarkemmin p-Laplacen yht¨al¨on heikoista ratkaisuista l¨oytyy tietoa l¨ahteest¨a [HKM06]. Vis- kositeettiratkaisut ja heikot ratkaisut ovat osoitettu ekvivalenteiksi l¨ahteess¨a [JLM01].

5.2 Suppeneminen ja DOP

Koska perhe{uε}on ylinumeroituva, niin valitaan tarkasteltavaksi siit¨a osajono {uεn}, jota merkit¨a¨an yksinkertaisuuden vuoksi{un}. Valitaan osajonon alkiot siten, ett¨aε_n→0. Koska yht¨al¨oll¨a (5.1) on yksik¨asitteinen viskositeettiratkaisu, mik¨a on osoitettu l¨ahteiss¨a [JLM01,KMP12], niin itseasiassa koko perheu_ε→u.

Muistetaan, ett¨ap-Laplacen operaattorille p¨atee, jos oletetaan, ett¨a∇u̸= 0 jauon sile¨a

∆pu(x) =|∇u(x)|^p−2((p−2)∆^N_∞u(x) + ∆u(x)).

T¨all¨oinuon ratkaisu yht¨al¨o¨on ∆pu= 0, jos ja vain jos

(p−2)∆^N_∞u+ ∆u= 0. (5.4)

T¨ah¨an asti DOP:n kertoimetαjaβ ovat olleet tuntemattomia. Osoittautuu, ett¨a valitsemalla

α= p−2

n+p β= n+ 2

n+p (5.5)

saadaan muodostettua yhteys (DOP):n ja (5.1) v¨alille. Sen havainnollistamiseksi t¨aytyy kuitenkin tehd¨a ensin kaksi arviota.

Lemma 5.4. Olkoonu C²-funktio. T¨all¨oin

u(x)− Z

Bε(x)

u(y)dy=− ε²

2(n+ 2)∆u(x) +O(ε³).