Technische Universiteit Delft Faculteit Elektrotechniek, Wiskunde en Informatica Delft Institute of Applied Mathematics
Optimale strategie¨ en voor gunstige binomiale spellen (Engelse titel: Optimal control of favourable binomial games)
Verslag ten behoeve van het Delft Institute of Applied Mathematics als onderdeel ter verkrijging van de graad van BACHELOR OF SCIENCE in TECHNISCHE WISKUNDE door MEREL ISABEL STOUT Delft, Nederland Juni 2012 c 2012 door M.I. Stout. Alle rechten voorbehouden. Copyright
BSc verslag TECHNISCHE WISKUNDE
”Optimale strategie¨ en voor gunstige binomiale spellen” (Engelse titel: ”Optimal control of favourable binomial games”)
MEREL ISABEL STOUT
Technische Universiteit Delft
Begeleider Dr. J.A.M. van der Weide
Overige commissieleden Prof.dr.ir. C. Vuik
Dr.ir. M.C. Veraar
Dr. J.G. Spandaw
Juni, 2012
Delft
Voorwoord Dit verslag is ten behoeve van het Delft Institute of Applied Mathematics als onderdeel ter verkrijging van de graad van Bachelor of Science in Technische Wiskunde. In het verslag wordt er gekeken naar een gunstig spel in een eindig binomiaal model. De vraag is welke strategie er toegepast moet worden om gegeven een startkapitaal ft en nog t spellen te gaan de kans dat je portfolio uiteindelijk meer dan c waard is te maximaliseren, waarbij c > ft een van tevoren vastgestelde positieve constante is. Ik wil graag dr. J.A.M. van der Weide bedanken voor zijn begeleiding gedurende het project.
4
Inhoudsopgave 1 Inleiding
6
2 Binomiaal spel 2.1 Inzet en strategie . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Nutsfunctie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Gunstig spel . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 7 7 8
3 Binomiale kansverdelingen 10 3.1 Eigenschappen van de binomiale verdeling . . . . . . . . . . . 10 3.2 Verband tussen het kapitaal en de uitbetalingsfactor . . . . . 12 4 Optimale inzetten met nog weing spellen te gaan 15 4.1 Nog ´e´en spel te gaan . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Nog twee spellen te gaan . . . . . . . . . . . . . . . . . . . . . 17 4.3 Nog drie spellen te gaan . . . . . . . . . . . . . . . . . . . . . 19 5 Binaire strategie¨ en 5.1 Binaire kapitalen . . . . . . . . . . . . . . . . 5.2 Binaire inzet . . . . . . . . . . . . . . . . . . 5.3 Binaire strategie . . . . . . . . . . . . . . . . 5.4 Numeriek bepalen van U (ft , t) en st (ft ) . . . 5.5 Verwachte nutsfunctie . . . . . . . . . . . . . 5.6 Boven- en ondergens voor een optimale inzet 6 Binomiale strategie¨ en 6.1 Binomiale kapitalen . . . . . . . . . . 6.2 Nog ´e´en spel te gaan . . . . . . . . . . 6.3 Nog twee spellen te gaan . . . . . . . . 6.4 Nutsverwachting en optimale inzetten
. . . .
. . . .
. . . .
. . . .
. . . . . .
. . . .
. . . . . .
. . . .
. . . . . .
. . . .
. . . . . .
. . . .
. . . . . .
. . . .
. . . . . .
. . . .
. . . . . .
. . . .
. . . . . .
. . . .
. . . . . .
21 21 23 24 30 32 35
. . . .
39 39 40 40 42
7 Conclusie
46
A Bijlagen A.1 Bewijs stelling 6.1 . . . . . . . . . . . . . . . . . . . . . . A.2 Matlab code voor numeriek bepalen van U (ft , t) en st (ft ) A.3 Matlab code voor een binaire inzet . . . . . . . . . . . . . A.4 Matlab code voor een binaire strategie . . . . . . . . . . . A.5 Matlab code voor simulaties onder een binaire strategie . A.6 Matlab code voor U (ft , t) binair . . . . . . . . . . . . . . A.7 Matlab code voor U (ft , t) binomiaal . . . . . . . . . . . .
5
. . . . . . .
. . . . . . .
50 50 60 61 63 63 64 66
1
Inleiding
Na het volgen van de minor Finance is mijn interesse gewekt voor financi¨ele wiskunde. Uit het boek van Shreve [1] dat gebruikt wordt voor het vak Kansmodellen voor Finance is de beginopdracht afgeleid: Een rijke investeerder stelt een klein budget ter beschikking om je beleggingsstrategie over de komende t periodes te testen in een binomiaal model. Als aan het einde je portfolio minstens een waarde c heeft, een positieve constante vastgelegd door de investeerder, dan is het doel bereikt en wordt er een groter budget tot je beschikking gesteld. De vraag is welke strategie aangehouden moet worden om de kans dat het portfolio uiteindelijk een waarde c heeft bereikt te maximaliseren. Vanuit dit probleem kwam ik al snel uit op een artikel van M. Kulldorff [2] waarin gezocht wordt naar optimale strategie¨en voor gunstige spellen in een casino. Het merendeel van de stellingen en proposities die in dit verslag zijn afgeleid vinden hun oorsprong in dit artikel. Daarnaast is ook het artikel van Breiman [3] dat vooraf gaat aan [2] gebruikt. Binnen het vinden van optimale strategie¨en kan er onderscheid gemaakt worden tussen de volgende gevallen: gunstig of niet-gunstig en een eindige of oneindige beschikbare tijd. Een optimale strategie hoeft niet uniek te zijn. In dit verslag wordt er gekeken naar een optimale strategie en het bijbehorende verwachte nut voor een gunstig spel in een eindig binomiaal model. Er wordt steeds hetzelfde spel in het casino gespeeld. Per spel zijn er twee mogelijke uitkomsten, winst of verlies die onder een vaste kans voorkomen. Voor ons kansmodel zullen we dus veel gebruik maken van de binomiale verdeling die de kans geeft dat een uitkomst, winst of verlies, een bepaald aantal keer voorkomt. Voor de binomiale kansverdeling worden enkele eigenschappen afgeleid die zowel bij het modelleren van het spel, als bij het bepalen van een optimale inzet toepasbaar zijn. Om het verloop van het spel beter te begrijpen wordt er vervolgens gekeken naar optimale strategie¨en met nog een klein aantal spellen te gaan. Daarna wordt er binnen een speciaal geval uitdrukkingen gevonden voor het verwachte nut en een optimale strategie voor n eindige t ∈ N, de zogenaamde n+1 binaire strategie. De partitie intervallen 2t , 2t zullen hierbij een belangrijke rol spellen. Vervolgens kan deze strategie uitgebreid worden naar het algemene geval: de binomiale strategie.
6
2
Binomiaal spel
Beschouw de volgende situatie: we spelen steeds hetzelfde spel in het casino, met per spel winst of verlies als mogelijke uitkomsten. De winstkans wordt gegeven door w. Noem het toegewezen beginkapitaal met nog t spellen te gaan ft . De uitbetaling die per spel gedaan wordt hangt af van die inzet s ∈ [0, ft ] en de uitbetalingsfactor (1 − r)/r bij winst ft + 1−r r s met kans w; ft−1 = ft − s met kans (1 − w). waarbij w ∈ (0, 1) en r ∈ (0, 1) door het casino bepaald worden en vast liggen. Hierbij loopt t, het aantal nog te spelen spellen, dus af naar nul: t, t − 1, . . . , 2, 1, 0. We willen met het spel een eindkapitaal c > ft bereiken. De vraag is hoe het spel gespeeld dient te worden om de kans op het bereiken van c te maximaliseren. Een eindkapitaal dat meer dan c waard is, heeft geen meerwaarde ten opzichte van precies op c uit komen. Opmerking. Door herschaling naar het eenheidsinterval [0, 1] kan zonder verlies van algemeenheid gesteld worden: ft ∈ [0, 1) en c = 1 Het startkapitaal ft wordt dan als percentage van het te bereiken doel c gezien.
2.1
Inzet en strategie
Een strategie met nog t spellen die gespeeld kunnen worden, wordt gegeven door een rij inzetfuncties st , st−1 , . . . s1 , waarbij si (fi ) de inzet is als met nog i spellen te gaan het kapitaal gelijk aan fi is. Het is niet mogelijk om een negatief bedrag in te zetten en de inzet kan het budget ook niet overschrijden: si (fi ) ∈ [0, fi ]. De optimale strategie is die strategie waarbij de inzetten zo gekozen worden dat de kans dat het kapitaal uiteindelijk c waard is maximaal is. Een optimale strategie hoeft niet uniek te zijn, daar komen we later op terug.
2.2
Nutsfunctie
Er dient een strategie gevonden te worden die goed genoeg is om een waarde c te bereiken. Het heeft geen meerwaarde om hoger dan dit target te eindigen. Een nutsfunctie geeft een waardeoordeel over het bereikte kapitaal. De nutsfunctie u(f0 ) kan na het spelen van het laatste spel de volgende waarden aan nemen:
7
u(f0 ) :=
1 als f0 ≥ 1
0 als f0 < 1
Dus de investeerder hecht er geen waarde aan als we op een eindkapitaal van meer dan ´e´en uitkomen. Door de inzet groter te kiezen dan het verschil tussen je huidige kapitaal en het doel: si > 1−fi wordt er een onnodig risico genomen, de extra inzet kan wel worden verloren maar bij winst levert het geen extra nut op. Noteer verder U (ft , t) voor de verwachte nutsfunctie onder een optimale strategie, bij een huidig kapitaal ft en nog t spellen te gaan. Na het spelen van het laatste spel geldt: U (f0 , 0) = u(f0 ). Opmerking. U (ft , t) = u(f0 ≥ 1)P(f0 ≥ 1|ft , t) + u(f0 < 1)P(f0 < 1|ft , t) = 1 · P(f0 ≥ 1|ft , t) + 0 · P(f0 < 1|ft , t) = P(f0 ≥ 1|ft , t)
(2.1)
Dus de nutsverwachting onder een optimale strategie is gelijk aan de voorwaardelijke kans dat het doel bereikt wordt onder die strategie.
2.3
Gunstig spel
De winst die per spel gemaakt kan worden hangt naast de inzet ook van de winstkans w en de uitbetalingsfactor (1 − r)/r af, met r ∈ (0, 1). Beide waarden worden door het casino bepaald en liggen vast. Aangezien 0 < r < 1, neemt deze uitbetalingsfactor waarden tussen nul en oneindig aan: 0<
1−r <∞ r
Figuur 1 bevat de grafiek van (1 − r)/r als functie van r. We zoeken de optimale strategie bij een gunstig spel. Dat houdt in dat de kans op winst groter is dan de kans op verlies: w > 1/2. Verder moet ook de verwachte opbrengst per spel positief zijn. De opbrengst van een spel is gelijk aan ft−1 − ft : 1−r st (ft ) − (1 − w)st (ft ) r 1−r = st (ft ) w − (1 − w) r w − rw − r + rw = st (ft ) r w−r = st (ft ) r
E[ft−1 − ft ] = w
8
Figuur 1: grafiek (1 − r)/r Dus: E[ft−1 − ft ] > 0 ⇐⇒ w − r > 0 Voor een gunstig spel dient het casino dan altijd w > r te kiezen.
9
3
Binomiale kansverdelingen
We spelen steeds hetzelfde spel in het casino. Per spel zijn er twee mogelijke uitkomsten, winst of verlies, die onder een vaste kans voorkomen. Het gebruikte kansmodel met nog t spellen te gaan is dat van een rij onafhankelijke identiek verdeelde Bernoulli variabelen ξ1 , ξ2 , . . . zo dat P(ξi = 1) = p en P(ξi = 0) = 1 − p. Voor ons kansmodel zullen we dus veel gebruik maken van de binomiale verdeling die de kans geeft dat een uitkomst, winst of verlies, een bepaald aantal keer voorkomt. In dit hoofdstuk gaan we in op de eigenschappen van de binomiale verdeling en leiden we enkele combinatorische lemma’s af, die in het verdere verslag van pas zullen komen.
3.1
Eigenschappen van de binomiale verdeling
Zij p ∈ [0, 1], en laat t ∈ N het aantal te spelen spellen en k ∈ N het aantal keer dat een gebeurtenis zich voordoet zijn. Noteer de binomiale kansverdeling: t k k p 1 − p)t−k als k ∈ {0, 1, . . . , t}; P (k|t, p) := 0 als k < 0. en noteer: Pk i=0 P (i|t, p) als k ∈ {0, 1, . . . , t}; F (k|t, p) := 0 als k < 0; 1 als k > t. Dan beschouwen we de volgende eigenschappen van de binomiale verdeling: Lemma 3.1. Zij p ∈ [0, 1], t ∈ N en k ∈ {0, 1, . . . , t}. Dan geldt voor F (k|t, p): F (k|t, p) = p · F (k − 1|t − 1, p) + (1 − p) · F (k|t − 1, p)
(3.1)
Bewijs. Zij ξ1 , ξ2 , . . . een rij onafhankelijke identiek verdeelde Bernoulli variabelen zo dat P(ξi = 1) = p. Dan geldt: F (k|t, p) = P(ξ1 + . . . + ξt ≤ k) aangezien:
10
(3.2)
P(ξ1 + . . . + ξt ≤ k) = P(ξ1 + . . . + ξt ≤ k, ξt = 1) + P(ξ1 + . . . + ξt ≤ k, ξt = 0) = P(ξt = 1)P(ξ1 + . . . + ξt−1 ≤ k − 1) + P(ξt = 0)P(ξ1 + . . . + ξt−1 ≤ k) dan volgt voor F (k|t, p): F (k|t, p) = P(ξ1 + . . . + ξt ≤ k) = p · F (k − 1|t − 1, p) + (1 − p) · F (k|t − 1, p)
Lemma 3.2. Zij p ∈ [0, 1], t ∈ N en k ∈ {0, 1, . . . , t}. Dan geldt:
en
F (k − 1|t, p) ≤ F (k − 1|t − 1, p) ≤ F (k|t, p)
(3.3)
k F (k − 1|t − 1, p) = F (k − 1|t, p) + P (k|t, p) t
(3.4)
Bewijs. Zij ξ1 , ξ2 , . . . een rij onafhankelijke identiek verdeelde Bernoulli variabelen gedefinieerd zoals in (3.2). Ongelijkheid (3.3) volgt dan uit: {ξ1 + . . . + ξt−1 + ξt ≤ k − 1} ⊂ {ξ1 + . . . + ξt−1 ≤ k − 1} ⊂ {ξ1 + . . . + ξt−1 + ξt ≤ k}
Uit ongelijkheid (3.3) volgt dat F (k − 1|t − 1, p) geschreven kan worden als een convexe combinatie: (1 − q)F (k − 1|t, p) + qF (k|t, p) waar voor q ∈ [0, 1] geldt: F (k − 1|t − 1, p) − F (k − 1|t, p) F (k|t, p) − F (k − 1|t, p) F (k − 1|t − 1, p) − F (k − 1|t, p) = . P (k|t, p)
q=
Uit lemma 3.1 volgt: F (k − 1|t − 1, p) − F (k − 1|t, p) = F (k − 1|t − 1, p) − pF (k − 2|t − 1, p) − (1 − p)F (k − 1|t − 1, p) = pP (k − 1|t − 1, p) dus q=
p
t−1 k−1 (1 − p)t−k k−1 p t k t−k k p (1 − p)
11
=
k ∈ [0, 1]. t
(3.5)
Deze uitdrukking voor q invullen in vergelijking (3.5) geeft: k k F (k − 1|t, p) + F (k|t, p). F (k − 1|t − 1, p) = 1 − t t
(3.6)
Hieruit volgt: k F (k − 1|t − 1, p) = F (k − 1|t, p) + P (k|t, p). t
(3.7)
Opmerking. Uit vergelijkingen (3.1) en (3.6) volgt dat we recursies hebben gevonden voor F (k|t, p) die lijken op de driehoek van Pascal voor binomiaal co¨efficienten.
3.2
Verband tussen het kapitaal en de uitbetalingsfactor
De uitbetalingsfactor hangt af van de keuze voor r ∈ (0, 1). Stel nu p = (1 − r). Voor ieder kapitaal ft ∈ [0, 1] is er dan een getal k ∈ {0, 1, . . . , t} te vinden zodat: F (k − 1|t, 1 − r) ≤ ft < F (k|t, 1 − r). Het getal k is door ft uniek bepaald. Verder defini¨eren we q ∈ [0, 1) als de unieke oplossing van de vergelijking: ft = F (k − 1|t, 1 − r) + qP (k|t, 1 − r). Opmerking. De keuze voor p = (1 − r) en niet p = r heeft te maken met de manier waarop de winstkans en de uitbetalingsfactor gedefinieerd zijn. Later in het verslag zal blijken dat k aangeeft hoevaak er hoogstens verloren mag worden om hel doel nog te kunnen bereiken. Definitie 3.1. Zij r ∈ (0, 1) vast. Laat 0 ≤ q < 1 en k ∈ {0, 1, . . . , t} de unieke getallen zijn waarvoor geldt: ft = F (k − 1|t, 1 − r) + qP (k|t, 1 − r) Beschouw figuren 2 en 3 voor de grafieken van k en q uitgezet tegen ft bij r = 0.5 en t = 2. Lemma 3.3. Zij p ∈ [0, 1], t ∈ N en k ∈ {0, 1, . . . , t} en laat k en q zo gedefinieerd zijn als in definitie 3.1. Dan geldt voor ft ∈ [0, 1]: F (k − 1|t, 1 − r) ≤ ft ≤ F (k − 1|t − 1, 1 − r) ⇐⇒ 0 ≤ q ≤ en F (k − 1|t − 1, 1 − r) ≤ ft < F (k|t, 1 − r) ⇐⇒ 12
k ≤q<1 t
k t
Bewijs. Laat k en q zo gedefinieerd zijn als in definitie 3.1. Dan kan elk kapitaal ft ∈ [0, 1] geschreven worden als: ft = F (k − 1|t, 1 − r) + qP (k|t, 1 − r) Uit lemma 3.2 volgt dat q = k/t voor ft = F (k − 1|t − 1, 1 − r). Dus voor ft waarbij q < k/t geldt dat ft kleiner is dan F (k − 1|t − 1, 1 − r) en de kapitalen met q > k/t zijn groter dan F (k − 1|t − 1, 1 − r).
Lemma 3.3 zal later gebruikt worden bij het vinden van een ondergrens voor optimale inzetten.
Figuur 2: Grafiek van k voor r = 0.5 en t = 2
Figuur 3: Grafiek van q voor r = 0.5 en t = 2
13
Daarnaast leiden we nog het volgende combinatorische lemma af voor ft : Lemma 3.4. Laat k en q zo gedefinieerd zijn als in definitie 3.1. Dan geldt voor elke ft ∈ [0, 1]: t k (1 − r)k rt−k (3.8) ft = F (k − 1|t − 1, 1 − r) + q − t k Bewijs. Uit definitie 3.1 volgt: ft = F (k − 1|t, 1 − r) + qP (k|t, 1 − r) Verder zegt lemma 3.2: k F (k − 1|t, 1 − r) = F (k − 1, t − 1, 1 − r) − P (k|t, 1 − r) t Vergelijking (3.8) volgt hier direct uit.
14
(3.9)
4
Optimale inzetten met nog weing spellen te gaan
We beschouwen nu het speciale geval r = 1/2. Het verloop van het spel ziet er dan nu als volgt uit: ft + st (ft ) met kans w; ft−1 = ft − st (ft ) met kans (1 − w). Per spel kan de inzet gewonnen of verloren worden. Merk op dat de inzet maximaal even groot kan zijn als het kapitaal dus dat het kapitaal binnen ´e´en spel hoogstens verdubbeld kan worden. Om de verwachting U (ft , t) en de bijbehorende optimale inzetten st , . . . , s2 , s1 beter te kunnen begrijpen onderzoeken we eerst de situaties waarin er nog maar weinig spellen te gaan zijn. Maak hierbij gebruik van vergelijking (2.1) dat U (ft , t) gelijk is aan de voorwaardelijke kans op het bereiken van het doel: P(f0 ≥ 1|ft , t).
4.1
Nog ´ e´ en spel te gaan
Beschouw voor t = 1 de partitie intervallen: 0, 21 en 12 , 1 van het eenheidsinterval [0, 1). • Als f1 ∈ 0, 21 dan is het met nog maar ´e´en spel te gaan niet meer mogelijk om op ´e´en uit te komen, aangezien het kapitaal hoogstens verdubbeld kan worden en dat niet voldoende is. Dus U (f1 , 1) = 0 voor f1 ∈ 0, 12 ongeacht de inzet. • Als f1 ∈ 21 , 1 dan dient het spel bij een inzet van 1 − f1 gewonnen te worden om het doel te bereiken en zal bij verlies het doel niet gehaald zijn. Het verwachte nut is dan gelijk 1 aan de kans dat het spel gewonnen wordt: U (f1 , 1) = w voor f1 ∈ 2 , 1 , mits s1 (f1 ) ≥ 1 − f1 . • Als f1 = 1 is het doel al bereikt en wordt er niks gezet. Voor het verwachte nut geldt dan: U (f1 , 1) = 1. Op t = 1 voldoet een optimale inzet dus aan: als 0 ≤ f1 < 21 ;
0 ≤ s1 (f1 ) ≤ f1
1 − f1 ≤ s1 (f1 ) ≤ f1 als s1 (f1 ) = 0
1 2
≤ f1 < 1;
als f1 = 1.
Figuur 4 laat het optimale gebied voor s1 (f1 ) zien, waarbij de groene lijn een bovengrens is voor een optimale inzet en de blauwe lijn een ondergrens.
15
Figuur 4: Grafiek van s1 (f1 ). Voor het verwachte nut onder een optimale strategie geldt dan: 0 als 0 ≤ f1 < 21 ; w als 21 ≤ f1 < 1; U (f1 , 1) = 1 als f1 = 1. Het 1 verwachte nut onder een optimale inzet blijft dus binnen de intervallen 0, 2 en 21 , 1 constant, zie ook figuur 5 voor de grafiek van U (f1 , 1).
Figuur 5: Grafiek van U (f1 , 1) voor w = 0.6.
16
4.2
Nog twee spellen te gaan
Met nog t = 2 spellen te gaan delen we het eenheidsinterval nu op in 22 partitie intervallen. We onderzoeken weer de optimale inzetten en het verwachte nut. Merk op dat er voor een optimale strategie alleen maar gekeken hoeft te worden naar de eerste inzet s2 , omdat we eerder al voor elke f1 ∈ [0, 1] de optimale inzet hebben gevonden. • Als f2 ∈ 0, 41 dan is het niet meer mogelijk om op ´e´en uit te komen, aangezien het kapitaal hoogstens twee maal verdubbeld kan worden. Dus U (f2 , 2) = 0 voor f2 ∈ 0, 14 , ongeacht de inzet. • Als f2 ∈ 14 , 21 moet er twee keer gewonnen worden om het doel te bereiken. Dus U (f2 , 2) = w2 voor f2 ∈ 41 , 12 , mits de inzet s2 voldoende groot is om met tweemaal winst ´e´en te bereiken. Kies daarom: 1 2 − f2 ≤ s2 (f2 ) ≤ f2 . • Als f2 ∈ 12 , 43 kan het doel binnen ´e´en spel bereikt worden indien er een inzet: 1 − f2 gedaan wordt. De uitkomst van het tweede spel heeft dan geen invloed. 1 Als er verloren wordt komt het kapitaal terecht in het interval 0, 2 met nog maar ´e´en spel te gaan en kan het doel 2 niet meer 1 3 gehaald worden. Dus U (f2 , 2) = w + w(1 − w) = w voor f2 ∈ 2 , 4 , mits er gekozen wordt voor een voldoende grote inzet om het doel binnen ´e´en spel te halen: s2 : 1 − f2 ≤ s2 (f2 ) ≤ f2 . Maar voor t = 1 hadden we gezien dat een f1 ∈ 21 , 1 ook een kans w had om het doel te bereiken. Het doen van een inzet 0 ≤ s2 (f2 ) ≤ f2 − 21 is dus in dit geval even optimaal. Aangezien het kapitaal dan op t = 1 zich met zekerheid in het partitie interval 21 , 1 bevindt. • Als f2 ∈ 34 , 1 wordt met een eerste inzet 1 − f2 het doel bij winst bereikt, ongeacht de uitkomst van het tweede spel,en bij verlies is er 1 nog ´e´en spel te gaan, met een kapitaal 3 f1 ∈ 2 , 1 . Dus U (f2 , 2) = 2 w +w(1−w)+(1−w)w voor f2 ∈ 4 , 1 , onder een optimale inzet. Dus alle uitkomsten waarbij er niet twee keer verloren wordt: U (f2 , 2) = 1 − (1 − w)2 . Er moet voldoende ingezet worden om bij winst het 1 doel te bereiken, maar 1bijverlies mag er niet meer dan f2 − 2 verloren worden, zodat f1 ∈ 2 , 1 en er dus met het tweede spel alsnog ´e´en gehaald kan worden: 1 − f2 ≤ s2 (f2 ) ≤ f2 − 12 . • Als f2 = 1 is het doel al bereikt en wordt er niks gezet. Voor het verwachte nut geldt dan: U (f2 , 2) = 1. Dus met nog t = 2 spellen te gaan is een inzet s2 (f2 ) optimaal indien hij voldoet aan:
17
0 ≤ s2 (f2 ) ≤ f2
als 0 ≤ f2 < 41 ;
1 2
− f2 ≤ s2 (f2 ) ≤ f2
als
1 4
≤ f2 < 12 ;
1 − f2 ≤ s2 (f2 ) ≤ f2 of 0 ≤ s2 (f2 ) ≤ f2 − 12
als
1 2
≤ f2 < 34 ;
als
3 4
≤ f2 < 1;
1 − f2 ≤ s2 (f2 ) ≤ f2 −
1 2
s2 (f2 ) = 0 als f2 = 1, Waarbij er dus voor f2 ∈ 21 , 34 twee mogelijkheden zijn. Figuur 6 laat het optimale gebied van s2 (f2 ) zien, waarbij de groene lijn een bovengrens is voor een optimale inzet s2 en de blauwe lijn een ondergrens.
Figuur 6: Grafiek van s2 (f2 ). Onder een optimale strategie geldt dan dat er bij ieder partitie interval een uitkomst bij komt die tot het doel kan leiden. Figuur 7 bevat de grafiek van U (f2 , 2). De nutsfunctie U (f2 , 2) wordt gegeven door: 0 als 0 ≤ f2 < 41 ; w2 als 14 ≤ f2 < 21 ; w als 12 ≤ f2 < 43 ; U (f2 , 2) = 1 − (1 − w)2 als 34 ≤ f2 < 1; 1 als f2 = 1. 18
Figuur 7: Grafiek van U (f2 , 2) voor w = 0.6
4.3
Nog drie spellen te gaan
We kunnen dit op dezelfde manier uitbreiden voor t = 3. Figuur (8) bevat het gebied voor de optimale inzetten bij t = 3. Ook nu spelen de roosterpunten {0, 1/8, 2/8, . . . 7/8, 1} een belangrijke rol. Merk op dat er nu sprake is van 23 partitie intervallen waar binnen het verwachte nut onder een optimale inzet constant blijft. Voor de kapitalen tussen de roosterpunten zijn alle inzetten binnen het grijze gebied mogelijk, terwijl de roosterpunten zelf maar een eindig aantal optimale inzetten hebben, die precies groot genoeg zijn om op t = 2 weer op een roosterpunt uit te komen, ongeacht winst of verlies van het eerste spel. Voor het roosterpunt 21 zouden er misschien drie mogelijke inzetten verwacht worden, vanwege het patroon van de toegestane gebieden. Dit blijkt niet het geval te zijn, aangezien de inzetten s3 = 0 en s3 = 12 allebei een verwacht nut van w hebben, terwijl het verwachte nut onder een inzet s3 = 14 gelijk is aan w3 + 3w2 (1 − w).
19
Figuur 8: Grafiek van s3 (f3 )
Figuur 9: Grafiek van U (f3 , 3)
5
Binaire strategie¨ en
In dit hoofdstuk gaan we nog steeds uit van r = 1/2. Het verwachte nut onder een optimale strategie is dus voor nog een klein aantal spellen te gaan: t ∈ {0, 1, voor alle startkapitalen ft binnen een partitie 2, 3} constant met n = 0, 1, . . . , 2t − 1, aan het verwachte nut voor interval In = 2nt , n+1 2t het linkerroosterpunt: n U (ft , t) = U t , t 2 met n ≤ 2t ft < n + 1. De roosterpunten 2nt spelen een belangrijke rol bij het bepalen van een optimale strategie. In dit hoofdstuk laten we zien dat dit ook voor algemene t op gaat.
5.1
Binaire kapitalen
Elke ft kan volgens definitie 3.1 geschreven worden als: ft = F (k − 1|t, 1 − r) + qP (k|t, 1 − r). Waarbij k en 0 ≤ q < 1 uniek bepaald zijn. Vanwege r = 1/2 volgt: ft = =
k−1 t X t 1
i
i=0 Pk−1 t i=0 i 2t
2 +q
t t 1 +q k 2 t k
.
De roosterpunten van de partitite intervallen: 2nt , met n = 0, 1, . . . , 2t zijn dan de kapitalen waarvoor q · kt een geheel getal is, zodat geldt: t
2 ft =
k X t i=0
! t +q ∈ N. i k
Definitie 5.1 (Binair kapitaal). Een kapitaal ft heet een binair kapitaal met nog t spellen te gaan als q kt een geheel getal is, met q en k gedefinieerd als in definitie 3.1 zodat elke ft ∈ [0, 1] geschreven kan worden als: ft = F (k − 1|t, 1 − r) + qP (k|t, 1 − r). Met andere woorden, alle kapitalen ft = 2nt met n = 0, 1, 2, . . . , 2t zijn binair. Met nog t spellen te spelen zijn er dan (2t +1) verschillende binaire kapitalen te vinden die het eenheidsinterval in 2t partitie intervallen In = [ 2nt , n+1 2t ) opdelen.
21
Opmerking. Na het spelen van het laatste spel zijn alleen de waarden 0 en 1 binair, aangezien f0 een binair kapitaal is dan en slechts dan als: f0 = 2n0 , met n ∈ {0, 1}. De roosterpunten waar steeds over gesproken werd, worden vanaf nu dus binaire kapitalen genoemd. Het vermoeden is dat er een optimale strategie is die over de binaire kapitalen loopt. Niet voor elk kapitaal kan een inzet gevonden worden die ongeacht de uitkomst van het spel altijd op een binair kapitaal uit komt. Voorbeeld 5.1. Vind een binaire inzet met nog t = 1 spel te gaan. Maak onderscheidt tussen f1 is binair, dus f1 ∈ {0, 21 , 1}, en f1 is niet binair. Beschouw de verschillende gevallen: Binaire kapitalen: • Als f1 = 0 kan er geen inzet meer gedaan worden. Het kapitaal eindigt dan ook op nul: f0 = 0. • Als f1 = 21 dan is s1 (f1 ) = 12 een inzet die op een binair kapitaal uitkomt, ongeacht winst of verlies: 1 1 + = 1; 2 2 1 1 bij verlies f0 = f1 − s1 = − = 0. 2 2 bij winst f0 = f1 + s1 =
• Als f1 = 1 is het doel al bereikt en het is onnodig om nog een inzet te doen. Het kapitaal eindigt dan ook op ´e´en: f0 = 1 Niet-binaire kapitalen: • Als f1 ∈ / {0, 21 , 1}. Zoek een inzet s1 (f1 ) ∈ [0, f1 ] zodat beide uitkomsten voor het eindkapitaal: (f0 = f1 + s1 ) en (f0 = f1 − s1 ) in N liggen. We weten dat het eindkapitaal alleen binair is als: f0 = 0 of f0 = 1 Vanwege f1 > 0 en s1 (f1 ) ≥ 0, moet bij winst gelden: f1 + s1 (f1 ) > 0 dus f1 + s1 (f1 ) = 1 is de enige mogelijke binaire oplossing. Een zelfde redenatie geeft bij verlies f1 − s1 (f1 ) = 0 als enige mogelijke binaire oplossing. Het optellen van de vergelijkingen voor winst en verlies geeft: 2f1 = 1 Deze vergelijking kent allen de oplossing f1 = 21 en dit geeft een tegenspraak met de aanname dat f1 niet binair is. Er is dus geen inzet s1 (f1 ) te vinden die altijd op een binair kapitaal uitkomt als f1 niet binair is. 22
5.2
Binaire inzet
Definitie 5.2 (Binaire inzet). Een inzet st (ft ) die gegeven een startkapitaal ft na het spelen van het eerste spel altijd op een binair kapitaal uitkomt, ongeacht de uitkomst van het spel, heet een binaire inzet. Met andere woorden, een inzet is binair indien ft−1 geschreven kan worden in de vorm: n1 met n1 ∈ N; ft + st (ft ) = 2t−1 ft−1 = 2 ft − st (ft ) = 2nt−1 met n2 ∈ N. Uit voorbeeld 5.1 volgt dat er alleen voor de binaire kapitalen f1 ∈ {0, 21 , 1} een binaire inzet gevonden kan worden. Lemma 5.1. Gegeven een niet-binair beginkapitaal, dan bestaat er geen binaire inzet. Bewijs. Gegeven een niet-binair beginkapitaal met nog t spellen te gaan: 2t ft ∈ / N. Stel er bestaat wel een binaire inzet st (ft ) voor ft zodat het kapitaal na het spelen van het eerste spel geschreven kan worden als: m1 ; 2t−1 m2 = ft − st (ft ) = t−1 . 2
bij winst ft−1 = ft + st (ft ) = bij verlies ft−1
waarbij m1 en m2 postitieve gehele getallen zijn. +m2 2 Optellen van de vergelijking geeft: 2ft = m21t−1 . Dus: ft = m12+m , maar t t dat geeft een tegenspraak met 2 ft ∈ / N. Dus er bestaat geen binaire inzet st (ft ).
Lemma 5.2. Gegeven een binair beginkapitaal 2nt met nog t spellen te gaan, dan bestaat er altijd een binaire inzet. Deze binaire inzetten zijn van de vorm: n n o n n i n met i ∈ N en max 0, − 2t−1 ≤ i ≤ . (5.1) st t = t − t−1 2 2 2 2 2 Bewijs. Het beginkapitaal is binair, dus: ft = Vind een inzet st (ft ) ∈ [0, ft ] die voldoet aan:
n + st (ft ) = 2t n = t − st (ft ) = 2
bij winst ft−1 = bij verlies ft−1
n 2t
met n ∈ {0, 1, . . . , 2t }. m1 ; 2t−1 m2 . 2t−1
waarbij m1 en m2 postitieve gehele getallenzijn. Merk op dat m2 waarden n kan aannemen in 0, 2 en m1 waarden in n2 , n . Voor n > 2t−1 , dat wil 23
zeggen als ft > 1/2, kan m1 groter dan 2t−1 worden, in dat geval is binair op t − 1.
m1 2t−1
Optellen van de vergelijkingen voor de mogelijke uitkomsten geeft: 2 · m1 +m2 . Hieruit volgt: 2t−1 m1 = n − m2 . Elke inzet van de vorm: n n i st t = t − t−1 2 2 2
met i ∈ N en 0 ≤ i ≤
niet n 2t
=
n 2
is dan voor ft ≤ 1/2 een binaire inzet, maar voor ft > 1/2 dus als n > 2t−1 is het doen van een inzet groter dan 1 − ft niet meer binair. Hieruit volgt: i n n − ≤1− t 2t 2t−1 2 en dus geldt voor i ∈ N: n n o n max 0, − 2t−1 ≤ i ≤ . 2 2 Voor de kapitalen 2nt en 1 − 2nt zijn dan dezelfde binaire inzetten mogelijk. Onder een binaire inzet zijn de uitkomsten op t − 1: n−i ; 2t−1 i = t−1 . 2
bij winst ft−1 = bij verlies ft−1
5.3
Binaire strategie
Definitie 5.3 (Binaire strategie). Een strategie die uitsluitend binaire inzetten bevat wordt een binaire strategie genoemd. Gevolgen. • Voor een binair beginkapitaal is altijd een binaire inzet te vinden. Bij het spelen met deze binaire inzet neemt het kapitaal vervolgens per definitie alleen maar binaire waarden aan. Voor dit nieuwe binaire kapitaal bestaat er weer een binaire inzet. Voor een binair startkapitaal bestaat er dus altijd een binaire strategie. • Bij het toepassen van een binaire strategie eindigt het kapitaal na het spelen van het laatste spel altijd op waarde 0 of 1. • ls het beginkapitaal niet binair, dan kan er geen binaire inzet gevonden worden en bestaat er dus per definitie geen binaire strategie. 24
Nu kan het vermoeden dat het verwachte nut onder een optimale strategie voor alle kapitalen ft binnen een partitie interval In even groot is als U 2nt , t bewezen worden. Noteer n = b2t ft c voor het gehele getal n = 0, 1, . . . , 2t waarvoor geldt n ≤ 2t ft < n + 1. Propositie 5.3. Zij ft ∈ [0, 1] het kapitaal met nog t spellen te spelen. Dan geldt voor n = b2t ft c: n U (ft , t) = U t , t . (5.2) 2 Bewijs. Met behulp van inductie naar t. De bewering is waar voor t = 1 en t = 2. Neem aan waar is voor een willekeurige t, dus dat de bewering n t U (ft , t) = U 2t , t met n = b2 ft c voor elke ft ∈ [0, 1]. Laat zien dat het dan ook waar is met nog t + 1 spellen te gaan. Beschouw het geval met nog t + 1 spellen te gaan en een beginkapitaal ft+1 waarvoor geldt: m = b2t+1 ft+1 c. Volgens de inductieveronderstelling is het verwachte strategie binnen de partitie intervallen n n+1 nut onder een optimale t met n = 0, 1, . . . , 2 constant. Merk op dat U (ft+1 , t+1) geschreven 2t , 2t kan worden als: U (ft+1 , t + 1) =
max {(1 − w)U (ft+1 − s, t) + wU (ft+1 + s, t)} . (5.3)
0≤s≤ft+1
Vanwege de inductieveronderstelling met nog t spellen te gaan is vergelijking (5.3) gelijk aan: n n n o 2 1 U (ft+1 , t + 1) = max (1 − w)U , t + wU ,t , (5.4) 2t 2t waarbij het maximum genomen wordt over de natuurlijke getallen n1 en n2 , met n1 = b2t (ft+1 − s)c en n2 = b2t (ft+1 + s)c. Het is dus voldoende om te m laten zien dat ft+1 en 2t+1 onder een optimale eerste inzet, met nog t spellen te gaan in hetzelfde partitie interval terecht komen.
Het vervolg van het bewijs ziet er als volgt uit: eerst laten we zien dat het m voor een binair beginkapitaal 2t+1 optimaal is om een binaire inzet te doen. Vervolgens laten we zien dat elke ft+1 ∈ Im geldt: m U (ft+1 , t + 1) ≥ U t+1 , t + 1 . 2 De laatste stap is om te laten zien dat U (ft+1 , t + 1) ≤ U
m , t + 1 , 2t+1
door aan te tonen dat er voor elke geldige inzet st+1 (ft+1 ) voor ft+1 een m gevonden kan worden, die minstens inzet gevonden kan worden voor 2t+1 hetzelfde verwachte nut heeft. 25
We beginnen dus met het aantonen dat voor een binair startkapitaal een optimale inzet binair moet zijn. Uit lemma 5.2 volgt dat voor een binair m kapitaal 2t+1 de volgende binaire inzetten gedaan kunnen worden: m i − , 2t+1 2t
∀i ∈ A
(5.5)
waarbij A het gebied voor i tis zodat de inzet binair is: m A = i ∈ N : max 0, m − 2 ≤ i ≤ 2 2 . Het bijbehorende verwachte nut onder zo’n inzet wordt dan met nog t spellen te gaan gegeven door: m m i m−i bij winst U + − , t = U , t 2t+1 2t+1 2t 2t m m i i bij verlies U − + ,t = U ,t 2t+1 2t+1 2t 2t t De binaire inzetten op een afstand 1/2 van elkaar af. Voor elke inzet m liggen m 0 ≤ s ≤ min 2t+1 , 1 − 2t+1 geldt dan:
sB − s <
1 , 2t
waarbij sB nu de kleinste binaire inzet is met sB ≥ s. Elke geldige nietbinaire inzet s > 0 kan dan geschreven worden als: s = sB − δ
met 0 < δ <
1 . 2t
De uitkomsten na het eerste spel worden dan gegeven door: m−i m + sB − δ < ; 2t+1 2t m i+1 bij verlies t+1 − sB + δ < . 2 2t bij winst
Het verwachte nut onder een optimale strategie met nog t spellen te gaan is dan vanwege de inductieveronderstelling: m−i−1 bij winst U ,t ; 2t i bij verlies U ,t . 2t De waarde van U (ft , t) met nog t spellen te gaan is bij verlies gelijk gebleven, maar bij winst van het eerste spel gaan we er ten opzichte van de binaire inzet sB op achteruit. Een niet-binaire inzet s > 0 kan dus niet optimaal zijn, aangezien er altijd een betere inzet sB bestaat.
26
Rest alleen nog het geval s = 0. Voor even m voldoet het doen van geen inzet aan de eisen voor een binaire inzet. Dus beschouwen we alleen de oneven waarden van m. Het verschil met de kleinst mogelijke binaire inzet is dan: 1 sB = t+1 . 2 Als er geen inzet gedaan wordt is de nutsverwachting na het spelen van het eerste spel gelijk aan: ! 1 m 2m U t+1 , t = U ,t . 2 2t Aangezien m oneven is en 12 m dus geen geheel getal is wordt dit onder de inductieveronderstelling: ! 1 (m − 1) ,t . U 2 2t Terwijl onder de kleinst mogelijke binaire inzet het verwachte nut met nog t spellen te gaan gegeven wordt: ! 1 (m + 1) m 1 bij winst U + ,t = U 2 ,t ; 2t+1 2t+1 2t ! 1 (m − 1) 1 m − ,t = U 2 ,t . bij verlies U 2t+1 2t+1 2t Bij winst is de verwachting groter, terwijl het bij verlies hetzelfde blijft als bij s = 0. Voor oneven m is er dus altijd een betere binaire inzet sB te vinden dan s = 0. m Gegeven een binair startkapitaal 2t+1 metnog t + 1 spellen te gaan. Als voor elke ft ∈ [0, 1] geldt: U (ft , t) = U 2nt , t met n = b2t f c dan is voor elke m niet-binaire inzet s ∈ 0, 2t+1 een betere binaire inzet te vinden. Met andere woorden, elke optimale inzet is dan een binaire inzet.
Nu kunnen we terug naar een kapitaal ft+1 ∈ [0, 1] met m = b2t+1 ft+1 c en definieer: m 1 ft+1 = t+1 + , 0 ≤ < t+1 2 2 De te bewijzen bewering: m U (ft+1 , t + 1) = U t+1 , t + 1 , 2
27
is waar als een optimale eerste inzet voor ft+1 het in verwachting even goed m doet als dat 2t+1 het onder een optimale eerste inzet doet. Voor een binair kapitaal is elke optimale inzet binair. Dus: m i m−i U t+1 , t + 1 = max wU , t + (1 − w)U ,t . i∈A 2 2t−1 2t−1
(5.6)
Vanuit ft+1 kan hetzelfde verwachte nut met nog t spellen te gaan bereikt worden door het doen van de inzetten met dezelfde restricties als bij (5.5). De uitkomsten zijn dan namelijk: m i m−i m−i+1 m + + t+1 − t = +< t+1 t 2 2 2t 2 2 m−i =⇒ U ,t ; 2t m m i i i+1 bij verlies t+1 + − t+1 + t = t + < 2 2 2 2t 2 i ,t . =⇒ U 2t bij winst
m Dit zijn dezelfde waarden voor ft+1 als voor 2t+1 , dus met ft+1 is de kans op het bereiken van het doel minstens even groot: m U (ft+1 , t + 1) ≥ U t+1 , t + 1 . (5.7) 2
We laten nu zien dat de gelijkheid geldt, door aan te tonen dat er voor elke m m mogelijke s ∈ [0, ft+1 ] een binaire inzet voor 2t+1 in 0, 2t+1 gevonden kan worden die het even goed doet. Elke inzet 0 ≤ s ≤ min{ft+1 , 1 − ft+1 } ligt 1 op een maximale afstand van 2t+1 af van de dichtstbijzijnde binaire inzet: i m 1 min s − t+1 + t ≤ t+1 . i∈A 2 2 2 Noem sB de binaire inzet op de minimale afstand van s, dus: |s − sB | ≤
1 2t+1
,
dan geldt voor elke s met bijbehorende sB de volgende ongelijkheden: m (1 − w)U (ft+1 − s, t) ≤ (1 − w)U t+1 − sB , t ; (5.8) m 2 wU (ft+1 + s, t) ≤ wU t+1 + sB , t , 2 aangezien:
28
• Als s ≤ sB dan geldt dat s = sB − δ met 0 ≤ δ ≤ uitkomsten voor ft zijn dan:
1 . 2t+1
De mogelijke
m−i m−i+1 +−δ < ; t 2 2t i i+1 bij verlies t + + δ < . 2 2t bij winst
Onder de inductieveronderstelling geldt dan: m−i i U (ft+1 + s, t) ≤ U , t en U (ft+1 − s, t) = U ,t . 2t 2t • Als s ≥ sB dan geldt dat s = sB + δ met 0 ≤ δ ≤
1 . 2t+1
m−i m−i+1 ++δ < ; t 2 2t i i+1 bij verlies t + − δ < . 2 2t bij winst
Onder de inductieveronderstelling geldt dan: m−i i U (ft+1 + s, t) = U , t en U (ft+1 − s, t) ≤ U ,t . 2t 2t Dus voor elke inzet geldinge inzet s die gedaan kan worden voor ft+1 is er m m een binaire inzet sB voor 2t+1 te vinden die voor 2t+1 hetzelfde verwachte nut geeft. m U (ft+1 , t + 1) ≤ U t+1 , t + 1 . (5.9) 2 Uit ongelijkheden (5.7) en (5.9) volgt nu: m U (ft+1 , t + 1) = U t+1 , t + 1 . (5.10) 2
Opmerking. De optimale verwachte nutsfunctie is een stapfunctie op de bim naire kapitalen. Indien een kapitaal ft+1 geschreven kan worden als: 2t+1 + t+1 met m = b2 ft+1 c dan verhoogt , het verschil tussen het werkelijke ka1 pitaal en het binaire kapitaal, met 0 ≤ < 2t+1 , het verwachte nut van het kapitaal niet. Corollarium 5.4. Als het beginkapitaal binair is, dan is elke optimale strategie een binaire strategie. Bewijs. Gegeven een binair beginkapitaal ft , dan volgt uit het bewijs van propositie 5.3 dat elke optimale eerste inzet binair is. Vervolgens is het kapitaal met nog t − 1 spellen te gaan ook binair en dus moet elke optimale tweede inzet binair zijn, enzovoort. Een optimale strategie bestaat dan uitsluitend uit binaire inzetten. 29
5.4
Numeriek bepalen van U (ft , t) en st (ft )
Met nog maar weing spellen te gaan kan er nu voor binaire startkapitalen gemakkelijk U (ft , t) bepaald worden.. Met nog t spellen te gaan wordt het verwachte nut onder een optimale strategie gegeven door: U (ft , t) = max {(1 − w) · U (ft − s, t − 1) + w · U (ft + s, t − 1)} . 0≤s≤ft
Gebruik dat elke optimale strategie voor een binair startkapitaal uitsluitend gebruik maakt van binaire inzetten. Gegeven een startkapitaal 2nt , dan is i elke binaire inzet van de vorm: 2nt − 2t−1 zoals gedefinieerd in lemma 5.2. De mogelijke uitkomsten zijn dan: n−i ; 2t−1 i bij verlies ft − st (ft ) = t−1 . 2 bij winst ft + st (ft ) =
Dus voor een binair startkapitaal hoeft er alleen gemaximaliseerd te worden op de binaire inzetten: i n−i U t , t = maxn (1 − w) · U ,t − 1 + w · U ,t − 1 . 0≤i≤ 2 2 2t−1 2t−1 n
(5.11)
Op t = 0, na het spelen van het laatste spel, is de nutsverwachting gelijk aan het nut van het eindkapitaal: 0 als f0 < 1; U (f0 , 0) = u(f0 ) = 1 als f0 ≥ 1. Vanuit die waarden kan met vergelijking (5.11) voor t = 1, 2, . . . met behulp van Matlab voor elk binair kapitaal 2nt met n ∈ {0, 1, . . . , 2t } de maximale verwachting en de bijbehorende optimale waarden voor i en dus st (ft ) gevonden worden. In tabel 1 zijn deze berekende waarden voor U 2nt , t voor t = 0, 1, . . . , 4 en een winstkans per spel van w = 0.6 gegeven. Uit propositie 5.3 volgt dat de gevonden waarden voor alle ft binnen een interval In met n = b2t · ft c van toepassingen zijn. Dus niet alleen voor de binaire kapitalen maar voor elke ft ∈ [0, 1] kan U (ft , t) bepaald worden. De in tabel 1 gelden waarden voor alle ft binnen een partitie interval In = 2nt , n+1 . Figuur 10 bevat de t 2 grafiek van U (ft , t) als stapfunctie op de binaire kapitalen voor verschillende waarden van t. De bijbehorende gevonden optimale inzetten voor t = 4 zijn af te lezen in tabel 2. Voor een niet-binair kapitaal is een binaire inzet die optimaal is voor n 2t ook een optimale inzet. De berekende optimale inzetten uit tabel 2 zijn 30
Tabel 1: Waarden van U (ft , t) voor t = 0, 1, . . . , 4 en w = 0.6 I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 I12 I13 I14 I15 I16
U (f0 , 0) 0 1
U (f1 , 1) 0 0.6 1
U (f2 , 2) 0 0.36 0.6 0.84 1
U (f3 , 3) 0 0.216 0.36 0.504 0.648 0.744 0.84 0.936 1
U (f4 , 4) 0 0.1296 0.216 0.3024 0.3888 0.4752 0.5328 0, 5904 0.648 0.7056 0.7632 0.8208 0.8592 0.8976 0.936 0.9744 1
dus geldig voor alle ft ∈ In . Er hoeft niet ´e´en unieke binaire inzet te zijn die optimaal is. Een binair startkapitaal 1/2 heeft bijvoorbeeld drie mogelijke optimale inzetten. In hoofdstuk 4 zagen we dit ook bij t ∈ {1, 2, 3}. De gebruikte Matlab-code is te vinden in Bijlage A.2.
Figuur 10: Grafiek van U (ft , t) voor w = 0.6 en t = 1, 2, . . . 4.
31
Tabel 2: Optimale waarden van st (ft , t) voor t = 4 en w = 0.6 I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 I12 I13 I14 I15 I16
5.5
0 0.0625 0.125 0.1875 0.1250 0.1875 0.25 0.3125 0.375 0.3125 0.125 0.1875 0.25 0.0625 0.1250 0.0625 0
0.25 0.0625
0.125 0.0625 0.25 0.1875
0.5 0.0625
0.125
Verwachte nutsfunctie
Voor kleine waarden van t zijn de optimale strategie¨en te vinden door met behulp van Matlab alle mogelijke uitkomsten onder een binaire strategie na te gaan en daar het maximum van te nemen, maar naarmate t groter wordt moeten er steeds meer waarden uitgerekend worden. Om U (ft , t) te bepalen moeten namelijk eerst alle waarden voor het verwachte nut op t−1, t−2 . . . , 1 uitgerekend worden. Dit zijn 2t−1 +2t−2 +. . .+1 waarden. In deze paragraaf gaan we opzoek naar een expliciete uitdrukking voor U (ft , t). Uit de resulaten die met behulp van Matlab verkregen zijn lijkt het verband tussen U (ft , t) en w als volgt gegeven te zijn: voor kapitalen binnen het partitie interval I1 moeten alle t spellen gewonnen worden om op ´e´en uit te kunnen komen. Voor kapitalen in I2 wordt het doel bereikt als alle spellen gewonnen worden, maar ook in ´e´en situatie waarbij er een spel verloren wordt. Voor I3 zijn er drie mogelijke uitkomsten die het doel bereiken: als alles gewonnen wordt maar ook bij twee van de uitkomsten waar er ´e´en keer verloren wordt. Voor het partitie interval I2t −1 zijn er 2t − 1 uitkomsten die tot het bereiken van het doel kunnen leiden, alleen als alle t spellen verloren worden kan ´e´en niet bereikt worden: 1 2 t U ,t = w ,U = wt + wt−1 (1 − w), t 2 2t t 3 2 −1 t t−1 U = w + 2w (1 − w), . . . , U = 1 − (1 − w)t 2t 2t
32
Om dit te kunnen bewijzen moeten we eerst naar alle mogelijke uitkomsten bij t maal spelen van het spel kijken. Propositie 5.5. Gegeven een binair beginkapitaal ft = 2nt met n ∈ {0, 1 . . . , 2t } met nog t spellen te gaan en het gebruik van een optimale binaire strategie. Dan zijn er aan het einde van het laatste spel n mogelijkheden om op 1 uit te komen en 2t − n mogelijkheden om op 0 te eindigen. Bewijs. Bij t maal spelen zijn er 2t uitkomsten mogelijk. Gegeven een binair beginkapitaal en het gebruik van een binaire strategie, eindigt een speler na het spelen van het laatste spel altijd op een kapitaal 0 of 1. Stel w = 0.5 dan ontstaat er een martingaal voor het kapitaal, dat wil zeggen dat gegeven een kapitaal ft op tijdstip t, onder iedere mogelijke strategie het verwachte kapitaal op t − 1 gelijk is aan ft : Et [ft−1 ] =
1 1 (ft + st (ft )) + (ft − st (ft )) = ft . 2 2
De martingaal eigenschap en de zogenaamde tower property hebben tot gevolg dat het kapitaal in verwachting gelijk blijft aan het kapitaal op t: Et [f0 ] = . . . = Et [ft−2 ] = Et [ft−1 ] = ft =
n . 2t
Zie ook het boek van Shreve [1] voor meer informatie over martingalen. Onder een binaire strategie neemt het eindkapitaal f0 waarde nul of ´e´en aan, dus voor de verwachting van f0 geldt dan: Et [f0 ] = 1 · Pt (f0 = 1) + 0 · Pt (f0 = 0) = Pt (f0 = 1). Het verwachte nut onder een optimale strategie is gelijk aan de voorwaardelijke kans dat het doel bereikt wordt: U (ft , t) = Pt (f0 = 1). Hieruit volgt: n n = P (f = 1) = U ,t . t 0 2t 2t De kans op het bereiken van het doel Pt (f0 = 1) is de som van de kansen van alle mogelijke uitkomsten waarbij het kapitaal op ´e´en eindigt. Aangezien w = 0.5 is elk van deze uitkomsten even waarschijnlijk met kans 1/2t . Er moeten dus n uitkomsten zijn waarbij het doel bereikt wordt. Er blijven dan nog 2t − n uitkomsten over waarbij het doel niet bereikt wordt en die dus op nul uitkomen. De bewering is dus waar voor w = 0.5. Aangezien het resulterende kapitaal van een uitkomst niet afhankelijk is van de winstkans w is het ook waar voor alle w > 0.5.
33
Definitie 5.4. Beschouw alle 2t mogelijke uitkomsten en nummer de bijbehorende kansen W1 , W2 , . . . W2t zodanig dat: W1 ≥ W2 ≥ . . . ≥ W2t . Zij j = 1, 2, . . . , 2t met: t t t t t + ... + ≤j< + ... + + , 0 k 0 k k+1 dan geldt vanwege w > 0.5: Wj = (1 − w)k wt−k .
(5.12)
Bijvoorbeeld: W1 = wt , W2 = wt−1 (1 − w), . . . , W2t = (1 − w)t . Pn Dan is j=1 Wj de som van de n hoogste kansen. Hier kunnen we de volgende combinatorische uitdrukking voor vinden: Lemma 5.6. Laat k en q zo gedefinieerd zijn als in definitie 3.1 en W als in definitie 5.4 . Dan geldt: n X
Wj = F (k − 1|t, 1 − w) + q · P (k|t, 1 − w).
(5.13)
j=1
Bewijs. Uit definitie 5.4 volgt: Wj = (1 − w)k wt−k , met j = 1, 2, . . . , 2t en 0t + . . . + kt ≤ j < 0t + . . . +
t k
+
t k+1
.
Verder kon elke ft ∈ [0, 1] volgens definitie 3.1 geschreven worden als: ft = F (k − 1|t, 1 − r) + qP (k|t, 1 − r), waarbij k en q uniek bepaald zijn met 0 ≤ q < 1. In het speciale geval van de binaire kapitalen ft = 2nt , met n = 0, 1, . . . , 2t , kan n dan volgens definitie 5.1 geschreven worden als: k−1 X t t n= +q . i k i=0
Sommeren n kansen is dus gelijk aan het nemen van de P overtde hoogste t hoogste k−1 + q kansen. Dit zijn de kansen waar de term 1 − w het i=0 i k minst vaak voorkomt. n k−1 X X t t i t−i Wj = · (1 − w) w + q (1 − w)k wt−k i k j=1
i=0
= F (k − 1|t, (1 − w)) + qP (k|t, 1 − w).
34
(5.14)
Gegeven een binair startkapitaal 2nt dan zijn er volgens propositie 5.5 onder een binaire strategie n uitkomsten die succesvol blijken te zijn. De som van de n uitkomsten met de hoogste waarschijnlijkheid is dan dus een bovengrens voor de kans dat het doel bereikt wordt: U
n X ,t ≤ Wj . t
n 2
j=1
Aangezien w > 1−w zijn de n uitkomsten met de hoogste kans de uitkomsten waarin er het minst vaak verloren wordt en dit zijn dus precies de uitkomsten waar het doel bereikt wordt. Dus het verwachte nut moet gelijk zijn aan de bovengrens, want als geldt Wi < Wj dan impliceert dat dat er bij Wj vaker winst is opgetreden. Dus als dan bij de uitkomst die hoort bij Wi het doel bereikt wordt, dan wordt dat bij ´e´en keer vaker winnen ook bereikt. Dus stellen we: n n X Wj . (5.15) U t,t = 2 j=1
Met lemma 5.6 volgt dan: Stelling 5.7. Laat k en q zo gedefinieerd zijn als in definitie 3.1 en stel r = 1/2. Dan geldt voor een binair startkapitaal ft = 2nt met nog t spellen te gaan: n U t , t = F (k − 1|t, 1 − w) + qP (k|t, 1 − w). (5.16) 2 Bewijs. Volgt in hoofdstuk 6 voor algemene waarden van r.
5.6
Boven- en ondergens voor een optimale inzet
Gegeven een binair startkapitaal 2nt dan is volgens corrolarium 5.4 elke optimale inzet een binaire inzet. Verder is de kans dat het doel bereikt wordt volgens stelling 5.7 gelijk aan: n U t , t = F (k − 1|t, 1 − w) + qP (k|t, 1 − w), 2 waarbij k en q zo gedefinieerd zijn als in definitie 3.1. Al de uitkomsten waarbij er dus hoogstens k − 1 keer verloren wordt komen dus onder een optimale strategie op ´e´en uit, net als een q−de deel van de uitkomsten waar er in totaal k keer verloren wordt. • Stel we winnen het eerste spel. Dan zijn er nog t − 1 spellen te gaan waarvan er nog steeds k − 1 of minder keer mogen worden om het doel te bereiken. Dit P verloren t−1 kan op m = k−1 verschillende manieren. Als er in ieder geval i=0 i 35
m uitkomsten op ´e´en uit komen, dan moet volgens propositie 5.5 het kapitaal met nog t − 1 spellen te gaan minstens gelijk geweest zijn aan: Pk−1 t−1 m = i=0t−1 i = F (k − 1 |t − 1, 1/2 ) . 2t−1 2 Om bij winst van het eerste spel op een kapitaal dat minstens zo groot is als F (k − 1 |t − 1, 1/2 ) uit te komen moet er een minimale inzet: s ≥ F (k − 1 |t − 1, 1/2 ) −
n 2t
(5.17)
gedaan zijn. Verder kunnen er geen uitkomsten zijn waarbij er in de laatste t − 1 spellen meer dan k maal verloren wordt en het doel toch bereikt wordt. P succesvolle uitkomsten zijn. Het Dus kunnen er hoogstens ki=0 t−1 i kapitaal ft−1 kan dan niet groter zijn dan: Pk t−1 i=0 i 2t−1
= F (k |t − 1, 1/2 )
en wordt een bovengrens voor een optimale inzet: s ≤ F (k |t − 1, 1/2 ) −
n . 2t
(5.18)
• Stel we verliezen het eerste spel. Alle uitkomsten met hoogstens k − 2 maal verlies komen onder een optimale strategie nog op ´e´en uit. Dus moet het kapitaal op t − 1 minstens gelijk aan F (k − 2 |t − 1, 0.5 ) zijn: n − s ≥ F (k − 2 |t − 1, 1/2 ) 2t Voor de bijbehorende inzetten geldt dan: s≤
n − F (k − 2 |t − 1, 1/2 ) . 2t
(5.19)
Verder moet ook elke uitkomst waarbij er de komende t − 1 spellen meer dan k − 1 keer verloren wordt het doel niet bereiken. Dus kunPk−1 t−1 nen er hoogstens i=0 i succesvolle uitkomsten zijn en geldt als ondergrens voor een optimale inzet: s≥
n − F (k − 1 |t − 1, 1/2 ) . 2t
(5.20)
Samenvoegen van de gevonden grenzen (5.17), (5.18), (5.19) en (5.20) voor een optimale inzet geeft de volgende stelling: 36
Stelling 5.8. Laat P, F, k en q zo gedefinieerd zijn als in definitie 3.1 en r = 1/2. Als ft = 2nt een binair beginkapitaal is met nog t spellen te gaan, dan is st (ft ) een optimale inzet dan en slechts dan als: • st (ft ) een binaire inzet is; • st (ft ) ≤ min n/2t − F (k − 2 |t − 1, 1 − r ) , F (k |t − 1, 1 − r ) − n/2t ; • st (ft ) ≥ F (k − 1 |t − 1, 1 − r ) − n/2t . Bewijs. Volgt in hoofdstuk 6 voor algemene waarden van r. Het verloop van het spel onder een binaire strategie voor een startkapitaal 1/2 met nog t = 4 spellen te gaan is te zien in figuur 11. Op de knopen staat het kapitaal en de bijbehorende inzet: (ft , st (ft )). Er zijn 16 mogelijke uitkomsten waarvan er 8 het doel bereiken. De gebruikte strategie is niet de enige mogelijke binaire strategie die optimaal is, zie ook tabel 2. De gekozen inzetten hangen niet af van de winstkans w. Het bijbehorende verwachte nut wordt gegeven door: 1 U , 4 = F (k − 1|t, 1 − w) + qP (k|t, 1 − w) 2 = w4 + 4(1 − w)w3 + 3(1 − w)2 w2 = w2 (3 − 2w). Voor w = 0.6 geeft dit: U 12 , 4 = 0.6480. De Matlab codes die gebruikt worden om binaire strategi¨en na te gaan en het bijbehorende verwachte nut uit te rekenen zijn te vinden in Bijlage A.3, A.4, A.5 en A.6. De recusries die in hoofdstuk 3 voor F (k|t, p) zijn afgeleid worden hierbij gebruikt.
37
Figuur 11: Mogelijk spel verloop onder een binaire strategie.
6
Binomiale strategie¨ en
Vanaf nu wordt er weer gekeken naar een willekeurige waarde voor r ∈ (0, 1) waardoor het verloop van het spel weer terug gaat naar: ft + 1−r r st (ft ) met kans w; ft−1 = ft − st (ft ) met kans (1 − w). Voor r = 1/2 is beredeneerd wat het verwachte nut onder een optimale strategie is en zijn er voorwaarden gesteld aan de bijbehorende optimale inzetten. Deze beweringen zullen in dit hoofdstuk bewezen worden voor algemene waarden van r.
6.1
Binomiale kapitalen
Definitie 6.1. Zij k en q gedefinieerd als in defintie 3.1 zodat ft ∈ [0, 1] geschreven kan worden als: t ft = F (k − 1|t, 1 − r) + q · P (k|t, 1 − r). k Definieer dan Q(ft , t) als: t Q(ft , t) = F (k − 1|t, 1 − w) + q · P (k|t, 1 − w), k
(6.1)
waarbij k en 0 ≤ q < 1 dus op unieke wijze van ft afhangen. Merk op dat U (ft , t) voor r = 1/2 volgens stelling 5.7 hetzelfde gedefinieerd is als Q(ft , t) . Uit definitie 6.1 volgt: Q(ft , t) [ft − F (k − 1|t, 1 − r)] P (k|t, 1 − w) P (k|t, 1 − r) 1 − w k w t−k = F (k − 1|t, 1 − w) + [ft − F (k − 1|t, 1 − r)] . 1−r r = F (k − 1|t, 1 − w) +
(6.2)
Definitie 6.2. Zij k en q zo gedefinieerd als in definitie 3.1. • Een kapitaal ft is binomiaal op tijdstip t indien q kt een positief geheel getal is. • Een inzet st (ft ) op tijdstip t is binomiaal indien er op t − 1 uitgekomen wordt op een binomiaal kapitaal, ongeacht de uitkomst van het spel. Opmerking. De binomiale kapitalen zijn voor r = 1/2 gelijk aan de binaire kapitalen. 39
6.2
Nog ´ e´ en spel te gaan
Beschouw het geval t = 1. De binomiaal kapitalen ft ∈ [0, 1] zijn dan de t kapitalen waarvoor geldt: q k ∈ N. Voor t = 1 zijn dit ft ∈ {0, r, 1}. Voor 0 en 1 is het nut en de inzet triviaal, dus beschouwen we alleen ft = r. Een inzet s1 (r) = r, (6.3) is dan optimaal, aangezien we onder deze inzet het doel met kans w kunnen bereiken. De inzet is ook binomiaal aangezien we of op een kapitaal gelijk aan nul, of op een kapitaal gelijk aan ´e´en uit komen. We kunnen het eenheidsinterval nu opdelen in twee partitie intervallen: [0, r) en [r, 1). Binnen deze intervallen blijft het verwachte nut gelijk, aangezien er in ´e´en spel het kapitaal f1 hoogstens met f1 (1 − r)/r kan toenemen. Dus bij winst geldt voor het eindkapitaal f0 : f0 ≤ f1 +
1−r 1 f1 = f1 . r r
Dus voor f1 < r kan het doel nooit meer bereikt worden. Aangezien er voor kapitalen f1 ∈ [r, 1) onder een voldoende grote inzet ´e´en keer gewonnen moet worden om op 1 uit te komen geldt voor het verwachte nut: 0 als f1 < r; w als r ≤ f1 < 1; U (f1 , 1) = 1 als f1 = 1. Onder een optimale inzet s1 (f1 ): 0 ≤ s1 (f1 ) ≤ f1 als f1 < r; r ≤ s1 (f1 ) ≤ f1 als r ≤ f1 < 1; s1 (f1 ) = 0
6.3
als f1 = 1.
Nog twee spellen te gaan
Beschouw het geval t = 2. Dan zijn de binomiale kapitalen: 2 0, r , r, 1 − (1 − r)2 , 1 . Deel het eenheidsinterval op in half open partitie intervallen met de binomiale kapitalen als roosterpunten. Dan kan er op een zelfde manier als in hoofdstuk 4.2 afgeleid worden dat het verwachte nut ook hier binnen een partitie interval constant blijft. 40
Beschouw bijvoorbeeld het partitie interval r, 1 − (1 − r)2 . Als het startkapitaal f2 in dit interval ligt dan kan er binnen ´e´en spel het doel bereikt worden door voor een inzet s2 (f2 ) = r/(1 − r) · (1 − f2 ) te kiezen, aangezien we dan bij winst op een kapitaal uitkomen dat gelijk is aan ´e´en: f1 = f2 +
1−r r (1 − f2 ) = 1. r 1−r
Maar bij verlies komt f1 op een waarde kleiner dan r uit: f1 = f2 −
r · (1 − f2 ) < 1 − (1 − r)2 − r(1 − r) = r 1−r
(6.4)
En voor f1 < r kan het doel niet meer bereikt worden. Dus U (f2 , 2) = w als f2 ∈ r, 1 − (1 − r)2 onder een inzet: (1 − f2 )
r ≤ s ≤ f2 1−r
Maar er kan ook voor gekozen worden om niets in te zetten. Dan zit f1 met nog t = 1 spel te gaan in het interval [r, 1) en is het verwachte nut onder deze strategie ook gelijk aan U (f2 , 2) = w. Voor t = 2 geldt dan dat de volgende optimale inzetten mogelijk zijn: 0 ≤ s ≤ f2
als 0 ≤ f2 < r2 ;
r (r − f2 ) 1−r ≤ s ≤ f2
als r2 ≤ f2 < r;
0 ≤ s ≤ f2 − r of r (1 − f2 ) 1−r ≤ s ≤ f2
als r ≤ f2 < 1 − (1 − r)2 ;
r (1 − f2 ) 1−r ≤ s ≤ r − f2
als 1 − (1 − r)2 ≤ f2 < 1;
s=0
als f2 = 1.
Merk op dat voor de binomiale kapitalen geldt dat elke optimale inzet een binomiale inzet is. Figuur 12 bevat deze toegestande gebieden voor een optimale inzet s2 (f2 ) voor r = 1/3. Het verwachte nut onder deze inzetten wordt gegeven door:
41
Figuur 12: Optimale inzetten voor t = 2 en r = 1/3
0 als 0 ≤ f2 < 41 ; w2 als 14 ≤ f2 < 21 ; w als 12 ≤ f2 < 43 ; U (f2 , 2) = 1 − (1 − w)2 als 34 ≤ f2 < 1; 1 als f2 = 1. Dit is hetzelfde resultaat als dat van hoofdstuk 4.2 voor nog twee spellen te gaan met r = 1/2. Figuur 13 bevat de verwachte nutsfunctie voor t = 2 en r = 1/3. Het verwachte nut voor de binomiale kapitalen kan voor t = 2 dus weer in de vorm U (f2 , 2) = F (k − 1|2, 1 − w) + q · P (k|2, 1 − w) = Q(f2 , 2)
(6.5)
geschreven worden.
6.4
Nutsverwachting en optimale inzetten
Stelling 5.7 en 5.8 kunnen nu voor algemene waarden van r geformuleerd worden. Houdt bij het vinden van grenzen voor een optimale inzet rekening met de factor (1 − r)/r. Zoals ook bij de uitwerking van optimale inzetten bij t = 2 is gedaan. Ga daarnaast uit van w > r, zodat we een gunstig spel beschouwen.
42
Figuur 13: Optimale inzetten voor t = 2 en r = 1/3. Stelling 6.1. Laat w > r en Q(ft , t) gedefinieerd als in definitie 6.1. Voor ft binomiaal geldt dan met nog t spellen te gaan: 1. U (f, t) = Q(f, t) 2. st (ft ) is een optimale inzet dan en slechts dan als: (a) st (ft ) is binomiaal; o n r (F (k − 1|t − 1, 1 − r) − ft ) ; (b) st (ft ) ≥ max ft − F (k − 1|t − 1, 1 − r), 1−r n o r (c) st (ft ) ≤ min ft − F (k − 2|t − 1, 1 − r), 1−r (F (k|t − 1, 1 − r) − ft ) .
Bewijs. De stappen die in het bewijs worden gemaakt volgen de gemaakte stappen van het bewijs van Theorem 1 en Theorem 2 uit het artikel van Kulldorff [2]. De volledige uitwerking van het bewijs is te vinden in de bijlagen. Het bewijs volgt uit inductie naar t. De stelling is waar voor t = 1. Dus neem aan dat het waar is voor t − 1. De volgende stap in het bewijs is dan om te laten zien dat onder de inductieveronderstelling geldt: 1−r U (ft , t) ≥ (1 − w)Q(ft − s, t − 1) + wQ ft + s, t − 1 = Q(ft , t), r waarbij s de minimale inzet uit de stelling is. Deze inzet is binomiaal. Er wordt onderscheid gemaakt tussen de gevallen q < k/t en q ≥ k/t. Daarna laten we zien dat U (ft , t) ≤ Q(ft , t) geldt door de nutsfunctie u∗ (f0 ) = f0 te beschouwen, en de functie Es als volgt te defini¨eren: 1−r Es (ft , t) = (1 − w)U ∗ (ft − s, t − 1) + wU ∗ ft + s, t − 1 . r 43
Dan geldt voor het verwachte nut: U ∗ (ft , t) = max Es (ft , t). s
Onder een binomiale strategie eindig je na het spelen van het laatste spel altijd op nul of ´e´en, onder deze strategie geldt dan dus u(f0 ) = u∗ (f0 ). Hieruit volgt: U (ft , t) = U ∗ (ft , t) = max Es (ft , t). s
Door de afgeleide van Es gelijk te stellen aan nul blijkt dat Es maximaal is onder inzetten die voldoen aan de eisen uit de stelling. En dus: Es (ft , t) ≤ Q(ft , t). Hieruit volgt U (ft , t) ≤ Q(ft , t) en dus: U (ft , t) = Q(ft , t)
Nu hebben we voor elke r < w een expliciete uitdrukking voor U (ft , t) op de binomiale kapitalen. Het volgen van deze strategie voor binomiale kapitalen maximaliseert de kans op het bereiken van het doel. Figuur 14 bevat U (ft , t) als stapfunctie op de binomiale kapitalen. Merk op dat U (ft , t) dan gegeven wordt door: t U (ft , t) = F (k − 1|t, 1 − w) + q P (k|t, 1 − w), (6.6) k waarbij bxc het grootste gehele getal n geeft waarvoor geldt: n ≤ x. Het bewijs van bewering (6.6) zal niet meer in dit verslag gegeven worden. De Matlab-code die gebruikt is bij het genereren van U (ft , t) is te vinden in Bijlage A.7.
44
Figuur 14: U (ft , t) voor t = 1, 2, 3 en 4 met r = 1/3.
7
Conclusie
In het verslag is er gekeken naar een gunstig spel (w > r) in een eindig binomiaal model. We spelen steeds hetzelfde spel in het casino. Per spel zijn er twee mogelijke uitkomsten, winst of verlies, die onder een vaste kans voorkomen. De vraag is welke strategie er toegepast moet worden om gegeven een startkapitaal ft en nog t spellen te gaan de kans dat je portfolio uiteindelijk meer dan c waard is te maximaliseren. Het verloop van het spel wordt beschreven door: ft + 1−r r st (ft ) met kans w; ft−1 = ft − st (ft ) met kans (1 − w). We beschouwen hiervoor de verwachte nutsfunctie onder een optimale strategie: U (ft , t) en de bijbehorende inzetten st (ft ). Zonder verlies van algemeenheid kan er herschaald worden naar het eenheidsinterval [0, 1]. De binomiale verdeling geeft de kans dat een uitkomst, winst of verlies, een Pk t k bepaald aantal keer voorkomt. Voor F (k|t, p) = i=0 i p 1 − p)t−i zijn de volgende recursies gevonden: F (k|t, p) = p · F (k − 1|t − 1, p) + (1 − p) · F (k|t − 1, p); k k F (k − 1|t − 1, p) = 1 − F (k − 1|t, p) + F (k|t, p). t t Voor ieder kapitaal ft ∈ [0, 1] is er dan een getal k ∈ {0, 1, . . . , t} te vinden zodat: F (k − 1|t, 1 − r) ≤ ft < F (k|t, 1 − r). Het getal k is door ft uniek bepaald. Verder defini¨eren we q ∈ [0, 1) als de unieke oplossing van de vergelijking: t ft = F (k − 1|t, 1 − r) + q (1 − r)k rt−k . k We beschouwen eerst het geval r = 1/2. Door de situatie met nog een klein aantal spellen te spelen na te gaan is er in inzicht te verkrijgen in het spelverloop. Zo hoeft een optimale strategie niet uniek te zijn en spelen de partitie intervallen 2nt , n+1 een belangrijke rol. Binnen deze intervallen 2t blijft het verwachte nut onder een optimale strategie constant: n U (ft , t) = U t , t , 2 met n = b2t ft c. Deze roosterpunten noemen we de binaire kapitalen, dit zijn de kapitalen waarvoor geldt: q kt ∈ N. Het verwachte nut onder een 46
optimale strategie is dan een stapfunctie op de binaire kapitalen. Voor een binair kapitaal is er altijd een binaire inzet te vinden van de vorm: n n i st t = t − t−1 , 2 2 2 n met i ∈ N en max 0, 2 − 2t−1 ≤ i ≤ n2 . En mogelijke uitkomsten: n n−i + st (ft ) = t−1 ; 2t 2 i n bij verlies t − st (ft ) = t−1 . 2 2 bij winst
Gegeven een binair startkapitaal is elke optimale strategie een binaire strategie. Dan kan het verwachte nut en de bijbehorende optimale inzetten voor nog een klein aantal spellen te gaan, berekend worden door te maximaliseren over i: n i n−i U t , t = max (1 − w) · U ,t − 1 + w · U ,t − 1 . i 2 2t−1 2t−1 Voor een expliciete uitdrukking voor U (ft , t) is er eerst aangetoond dat gegeven een binair startkapitaal 2nt er n verschillende uitkomsten zijn die op ´e´en uitkomen en 2t − n uitkomsten die op nul uitkomen. Aangezien w > 0.5 hebben de uitkomsten waar er het vaakst gewonnen wordt de grootste kans om op te treden: W1 ≥ W2 ≥ . . . ≥ W2t , waarbij Wj = (1 − w)k wt−k voor j = 1, 2, . . . , 2t met t t t t t + ... + ≤j< + ... + + , k 0 k k+1 0 De uitkomsten waar het vaakst gewonnen wordt, zijn de uitkomsten waar het doel bereikt wordt. Sommeren over de hoogste n kansen geeft dan het verwachte nut onder een optimale strategie: U
n X , t = Wj = F (k − 1|t, 1 − w) + qP (k|t, 1 − w). t
n 2
j=1
Dit betekent dat gegeven een startkapitaal 2nt alle uitkomsten waar hoogstens k − 1 keer verloren wordt en een q-de deel van het uitkomsten waar k keer verloren wordt het doel bereiken. Hiermee kunnen we een boven- en ondergrens voor een optimale inzet afleiden, zodat met nog t spellen te gaan een inzet optimaal is dan en slechts dan als hij voldoet aan: • st (ft ) een binaire inzet is; • st (ft ) ≤ min n/2t − F (k − 2 |t − 1, 1 − r ) , F (k |t − 1, 1 − r ) − n/2t ; 47
• st (ft ) ≥ F (k − 1 |t − 1, 1 − r ) − n/2t . Bij het uitrekenen van de optimale inzetten en het verwachte nut worden de recursies die voor F (k|t, p) zijn afgeleid toegepast. De theorie voor een optimale inzet en het bijbehorende verwachte nut kan vervolgens uitgebreid worden voor algemene waarden van r ∈ (0, 1). We beschouwen dan nu de binomiale kapitalen, dit zijn de kapitalen waarvoor geldt q kt ∈ N. Onder willekeurige r gedraagt het spelverloop zich op eenzelfde manier als voor r = 1/2. Het verwachte nut onder een optimale strategie lijkt nu een stapfunctie op de binomiale kapitalen te zijn. Voor ft binomiaal geldt dan met nog t spellen te gaan en w > r: Zij k en q gedefinieerd als in defintie 3.1 zodat ft ∈ [0, 1] geschreven kan worden als: t ft = F (k − 1|t, 1 − r) + q · P (k|t, 1 − r). k Dan geldt voor het verwachte nut onder een optimale strategie: t U (ft , t) = F (k − 1|t, 1 − w) + q · P (k|t, 1 − w), k
(7.1)
waarbij k en 0 ≤ q < 1 dus op unieke wijze van ft afhangen. En st (ft ) is een optimale inzet dan en slechts dan als: • st (ft ) is binomiaal; n o r • st (ft ) ≥ max ft − F (k − 1|t − 1, 1 − r), 1−r (F (k − 1|t − 1, 1 − r) − ft ) ; n o r • st (ft ) ≤ min ft − F (k − 2|t − 1, 1 − r), 1−r (F (k|t − 1, 1 − r) − ft ) .
Het volgen van deze strategie maximaliseert de kans op het bereiken van het voorafgestelde doel.
48
Referenties [1] Shreve, S. (2004) Stochastic Calculus for Finance I, the binomial asset pricing model, Springer-Verlag New York. [2] Kulldorff, M. (1993), Optimal control of favorable games with a time limit, SIAM J. Control and Optimization, Vol. 31, blz. 52-59. [3] Breiman, L. (1961), Optimal gambling systems for favorable games, Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Vol. 1, blz. 65-78.
49
A
Bijlagen
A.1
Bewijs stelling 6.1
De stappen die in het bewijs worden gemaakt volgen die van het bewijs van Theorem 1 en Theorem 2 uit het artikel van Kulldorff [2]. Stelling 6.1 luidt als volgt: Laat w > r en Q(ft , t) gedefinieerd als in definitie 6.1. Voor ft binomiaal geldt dan met nog t spellen te gaan: 1. U (f, t) = Q(f, t) 2. st (ft ) is een optimale inzet dan en slechts dan als: (a) st (ft ) is binomiaal; n o r (b) st (ft ) ≥ max ft − F (k − 1|t − 1, 1 − r), 1−r (F (k − 1|t − 1, 1 − r) − ft ) ; n o r (c) st (ft ) ≤ min ft − F (k − 2|t − 1, 1 − r), 1−r (F (k|t − 1, 1 − r) − ft ) .
Bewijs. Het bewijs volgt uit inductie naar t. Beschouw t = 1. Dan geldt voor binomiaal kapitaal ft = r: U (ft , 1) = w onder optimale inzet st (ft ) = r.
(A.1)
Voor Q(ft , 1) geldt dan: t Q(ft , 1) = F (k − 1|t, 1 − w) + q P (k|t, 1 − w) k = F (0|1, 1 − w) = w, want uit ft = r volgt q = 0 en k = 1. Dus U (r, 1) = Q(r, 1). De inzet st (r) = r is binomiaal en voldoet ook aan de andere eisen aangezien: r min ft − F (k − 2|t − 1, 1 − r), (F (k|t − 1, 1 − r) − ft ) 1−r r = min r − 0, (1 − r) = r 1−r en q kt = 0 < kt dus ft < F (k − 1|t − 1, 1 − r). Merk op: F (0|0, 1 − r) = 1. r max ft − F (k − 1|t − 1, 1 − r), (F (k − 1|t − 1, 1 − r) − ft ) 1−r r = (1 − r) = r. 1−r
50
Dus de beweringen zijn waar voor t = 1. Neem aan dat de beweringen waar zijn voor t − 1. Laat zien dat het dan ook geldt voor t. We laten eerst zien dat geldt U (ft , t) ≥ Q(ft , t). Maak onderscheidt tussen de gevallen q ≥ k/t en q < k/t. We willen laten zien:
1−r U (ft , t) ≥ (1 − w)Q(ft − s, t − 1) + wQ ft + s, t − 1 = Q(ft , t), r
(A.2)
waarbij de inzet s voldoet aan de eisen van het tweede deel van stelling 6.1. Maak onderscheidt tussen de gevallen q ≥ k/t en q ≤ k/t. • Als q ≥ k/t. Uit lemma 3.2 volgt dan: ft ≥ F (k − 1|t − 1, 1 − r). Merk op dat in dit geval de minimale inzet uit de stelling: sm gelijk is aan: sm = f − F (k − 1|t − 1, 1 − r). Beschouw de mogelijke uitkomsten onder een inzet sm . 1. Bij winst van het eerste spel, is het nieuwe kapitaal gelijk aan het m startkapitaal plus (1 − r)/r maal de inzet: ft + 1−r r s . Noem f ∗ = ft +
1−r m r s .
f ∗ = ft + =
Dan geldt voor f ∗ :
1−r [ft − F (k − 1|t − 1, 1 − r)] r
1 [ft − (1 − r)F (k − 1|t − 1, 1 − r)] . r
(A.3)
Volgens lemma 3.4 kan elke ft ∈ [0, 1] geschreven worden als: k t ft = F (k − 1|t − 1, 1 − r) + q − (1 − r)k rt−k (A.4) t k Uitdrukking (A.4) invullen in (A.3) geeft: 1 k t ∗ k t−k f = rF (k − 1|t − 1, 1 − r) + q − (1 − r) r r t k k t = F (k − 1|t − 1, 1 − r) + q − (1 − r)k rt−k−1 . t k Merk op dat q − kt kt gelijk is aan: t k t−1 q− . (A.5) t−k t k Aangezien ft binomiaal is, geldt: q kt ∈ N en vanwege q ≥ k/t geldt dat (A.5) ook in N ligt. Het kapitaal f ∗ is dus binomiaal op t − 1 en k hangt nu af van f ∗ , maar blijft dezelfde waarde 51
houden als de oorspronkelijke k: k(f ∗ ) = k(ft ). Invullen van f ∗ in vergelijking (6.2) voor Q(ft−1 , t − 1) geeft dan: Q(f ∗ , t − 1) = F (k − 1|t − 1, 1 − w) (A.6) k t 1−w w t−k−1 k (1 − r)k rt−k−1 + q− t k 1−r r t k (1 − w)k wt−k−1 . = F (k − 1|t − 1, 1 − w) + q − t k (A.7) 2. Bij verlies van het eerste spel, is het nieuwe kapitaal gelijk aan het startkapitaal min de inzet: ft − sm . Noem f ∗∗ = ft − sm . Dan geldt voor f ∗∗ : f ∗∗ = ft − [ft − F (k − 1|t − 1, 1 − r)] = F (k − 1|t − 1, 1 − r).
(A.8)
Merk op dat ook f ∗∗ een binomiaal kapitaal is op t−1. Daarnaast hangt k nu af van f ∗∗ = F (k − 1|t − 1, 1 − r) en heeft dus dezelfde waarde: k(f ∗∗ ) = k(ft ) Invullen van f ∗∗ in vergelijking (6.2) voor Q(ft−1 , t − 1) geeft: Q(f ∗∗ , t − 1) = F (k − 1|t − 1, 1 − w).
(A.9)
Vergelijkingen (A.7) en (A.9) geven nu de twee mogelijke uitkomsten van Q(ft−1 , t − 1) onder de inzet sm . Voor ongelijkheid (A.2) voor U (ft , t): 1−r U (ft , t) ≥ (1 − w)Q(ft − s, t − 1) + wQ ft + s, t − 1 , r met ft ∈ {ft : q ≥ k/t} volgt dan: U (ft , t) ≥ (1 − w)Q(ft − sm , t − 1) + wQ(ft +
1−r m s , t − 1) r
= (1 − w)F (k − 1|t − 1, 1 − w) k t k t−k−1 + w F (k − 1|t − 1, 1 − w) + q − (1 − w) w t k t = F (k − 1|t, 1 − w) + q (1 − w)k−1 wt−k k = Q(ft , t). 52
De bewering U (ft , t) ≥ Q(ft , t) is dus waar voor q ≥ k/t. En de gegeven minimale inzet sm is een binomiale inzet, aangezien beide resulterende kapitalen f ∗ en f ∗∗ binomiaal zijn. • Als q < k/t. Uit lemma 3.2 volgt dan: ft ≤ F (k − 1|t − 1, 1 − r). Merk op dat in dit geval de minimale inzet sm uit de stelling gelijk is aan: r sm = (F (k − 1|t − 1, 1 − r) − ft ) 1−r Beschouw de mogelijke uitkomsten onder een inzet sm . 1. Bij winst van het eerste spel, is het nieuwe kapitaal gelijk aan het m startkapitaal plus (1 − r)/r maal de inzet: ft + 1−r r s . Noem f ∗ = ft +
1−r m r s ,
dan geldt voor f ∗ :
1−r r [F (k − 1|t − 1, 1 − r) − ft ] r 1−r = ft + F (k − 1|t − 1, 1 − r) − ft
f ∗ = ft +
= F (k − 1|t − 1, 1 − r).
(A.10)
Merk op dat f ∗ een binomiaal kapitaal is op t − 1. Daarnaast hangt k nu af van f ∗ = F (k − 1|t − 1, 1 − r) en heeft dus dezelfde waarde: k(f ∗ ) = k(ft ). Dit invullen in de vergelijking voor Q(ft−1 , t − 1) geeft: Q(f ∗ , t − 1) = F (k − 1|t − 1, 1 − w)
∗
+ [f − F (k − 1|t − 1, 1 − r)] = F (k − 1|t − 1, 1 − w).
1−w 1−r
k w t−k−1 r (A.11)
2. Bij verlies van het eerste spel, is het nieuwe kapitaal gelijk aan het startkapitaal min de inzet: ft − sm . Noem f ∗∗ = ft − sm , dan geldt voor f ∗∗ : r [F (k − 1|t − 1, 1 − r) − ft ] f ∗∗ = ft − 1 − r r r = 1+ ft + F (k − 1|t − 1, 1 − r) 1−r 1−r 1 = [ft − rF (k − 1|t − 1, 1 − r)] . 1−r
53
Het kapitaal ft ∈ [0, 1] kan met behulp van lemma 3.4 herschreven worden tot: k t ft = F (k − 1|t − 1, 1 − r) + q − · · (1 − r)k · rt−k t k = F (k − 1|t − 1, 1 − r) t−1 t k t−k − (1 − r) r +q· (1 − r)k rt−k . k−1 k Deze uitdrukking invullen in de vergelijking voor f ∗∗ geeft: t−1 ∗∗ f = F (k − 1|t − 1, 1 − r) − (1 − r)k−1 rt−k k−1 t +q (1 − r)k−1 rt−k k t = F (k − 2|t − 1, 1 − r) + q (1 − r)k−1 rt−k . (A.12) k Hieruit volgt: f
∗∗
t t−1 (1 − r)k−1 rt−k . = F (k − 2|t − 1, 1 − r) + q k k−1
Dus k(f ∗∗ ) = k(ft ) − 1 en q(f ∗∗ ) = q(ft ) kt . Vanwege q(ft ) < k/t, geldt: q(ft ) kt < 1, dus q(f ∗∗ ) ∈ [0, 1). Dus k en q voldoen aan definitie 3.1 en zijn uniek bepaald voor f ∗∗ . Daarnaast is f ∗∗ t t−1 binomiaal op t − 1, want q k ∈ N dus ook q kt k−1 ∈ N. Voor Q(ft − s, t − 1) = Q(f ∗∗ , t − 1) geldt dan nu: Q(f ∗∗ , t − 1) = F (k − 2|t − 1, 1 − w) + [f
∗∗
− F (k − 2|t − 1, 1 − r)]
1−w 1−r
k−1 w t−k . r
Herschrijf nu eerst het gedeelte tussen de vierkante haken met behulp van (A.12): f ∗∗ − F (k − 2|t − 1, 1 − r) = F (k − 2|t − 1, 1 − r) t +q (1 − r)k−1 rt−k − F (k − 2|t − 1, 1 − r) k t =q (1 − r)k−1 rt−k . (A.13) k 54
Vergelijking (A.13) invullen in de formule voor Q(f ∗∗ , t − 1) geeft nu: Q(f ∗∗ , t − 1) = F (k − 2|t − 1, 1 − w) k−1 w t−k t k−1 t−k 1 − w +q (1 − r) r 1−r r k t = F (k − 2|t − 1, 1 − w) + q (1 − w)k−1 wt−k . k
(A.14)
Vergelijkingen (A.11) en (A.14) geven dan de mogelijke uitkomsten van Q(ft−1 , t − 1) op tijdstip t − 1 onder de minimale inzet uit de stelling. Deze uitkomsten invullen in ongelijkheid (A.2) voor U (ft , t) geeft: U (ft , t) 1−r ≥ (1 − w)Q(ft − s, t − 1) + wQ(ft + s, t − 1) r t k−1 t−k = (1 − w) F (k − 2|t − 1, 1 − w) + q (1 − w) w k + wF (k − 1|t, 1 − w) t = F (k − 1|t, 1 − w) + q (1 − w)k−1 wt−k k = Q(ft , t). De bewering U (ft , t) ≥ Q(ft , t) is dus waar voor q < k/t. Daarnaast is sm een binomiale inzet, aangezien je ongeacht de uitkomst van het spel op een binomiaal kapitaal uitkomt. Er geldt dus voor alle binomiale ft ∈ [0, 1]: U (ft , t) ≥ Q(ft , t)
(A.15)
Laat nu zien dat ook U (ft , t) ≤ Q(ft , t) geldt. We beschouwen daarvoor eerst een andere nutsfunctie, namelijk: u∗ (f0 , 0) = f0
(A.16)
Noteer verder: 1−r Es (ft , t) = (1 − w)U ∗ (ft − s, t − 1) + wU ∗ ft + s, t − 1 , r zodat: U ∗ (ft , t) = max Es (ft , t). s
55
De functie Es∗ (ft , t) is continu en bijna overal differntieerbaar over s. Gegeven een binomiaal startkapitaal, onder een binomiale strategie kan het eindkapitaal de waarde nul of ´e´en aannemen. Onder deze strategie geldt dus: u(f0 , 0) = u∗ (f0 , 0), hieruit volgt ook: U (ft , t) = U ∗ (ft , t) = max Es (ft , t), s
onder een binomiale strategie. Vanwege de inductieveronderstelling geldt dan: 1−r Es (ft , t) = (1 − w)Q(ft − s, t − 1) + wQ ft + s, t − 1 . (A.17) r Het toepassen van uitdrukking (6.2) voor Q(ft−1 , t − 1) geeft: Q(ft − s, t − 1) = [ft − s − F (m − 1|t − 1, 1 − r)]
1−w 1−r
k w t−k−1 r
+ F (m − 1|t − 1, 1 − w);
(A.18)
1−r Q ft + s, t − 1 r 1−r = [ft + s − F (n − 1|t − 1, 1 − r)] r + F (n − 1|t − 1, 1 − w),
1−w 1−r
k w t−n−1 r (A.19)
waarbij m, n ∈ N zo dat: F (m − 1|t − 1, 1 − r) ≤ ft − s < F (m|t − 1, 1 − r); 1−r F (n − 1|t − 1, 1 − r) ≤ ft + s < F (n|t − 1, 1 − r). r Invullen van de vergelijkingen (A.18) en (A.19) in de uitdrukking voor Es (A.17) en vervolgens Es differenti¨eren over s, geeft: d (1 − w)m+1 w t−m−1 (1 − w)n w t−n Es = − + (A.20) ds (1 − r)m r (1 − r)n−1 r Vanwege w > r geldt: > 0 als m = n; d = 0 als m = n − 1; Es ds < 0 als m ≤ n − 2. 56
Beschouw voor een binomiaal kapitaal ft de volgende inzetten: 1. ft − F (k − 1|t − 1, 1 − r); 2.
r 1−r
(F (k − 1|t − 1, 1 − r) − ft );
3. ft − F (k − 2|t − 1, 1 − r); 4.
r 1−r
(F (k|t − 1, 1 − r) − ft ),
dit zijn de boven- en ondergrenzen uit de stelling. We onderzoeken de waarden die m en n aannemen onder deze inzetten. Dus de gehele getallen waarvoor geldt: F (m − 1|t − 1, 1 − r) ≤ ft − s < F (m|t − 1, 1 − r); 1−r s < F (n|t − 1, 1 − r). F (n − 1|t − 1, 1 − r) ≤ ft + r 1. Kies s1 = ft − F (k − 1|t − 1, 1 − r), de mogelijke uitkomsten onder deze inzet zijn in het eerste deel van het bewijs al uitgerekend en worden gegeven door: Bij winst: F (k − 1|t − 1, 1 − r) +
t t−k
k t−1 q− (1 − r)k rt−k−1 ; t k
bij verlies: F (k − 1|t − 1, 1 − r). Dus geldt n = m voor s ≤ s1 en > m voor s > s1 . r 2. Kies s2 = 1−r (F (k − 1|t − 1, 1 − r) − ft ), de mogelijke uitkomsten onder deze inzet zijn in het eerste deel van het bewijs al uitgerekend en worden gegeven door:
Bij winst: F (k − 1|t − 1, 1 − r); bij verlies: t t−1 F (k − 2|t − 1, 1 − r) + q (1 − r)k−1 rt−k . k k−1 Dus geldt n = m voor s < s2 en en n > m voor s ≥ s1 .
57
3. Kies s3 = ft − F (k − 2|t − 1, 1 − r). Onder deze inzet zijn de mogelijke uitkomsten: Bij winst: ft +
1−r [ft − F (k − 2|t − 1, 1 − r)] r
1 = [ft − (1 − r)F (k − 2|t − 1, 1 − r)] r k t−1 t q− (1 − r)k rt−k−1 ; = F (k − 1|t − 1, 1 − r) + t−k t k bij verlies: ft − ft − F (k − 2|t − 1, 1 − r) = F (k − 2|t − 1, 1 − r). Dus geldt n ≤ m + 1 als s ≤ s3 en n > m + 2 als s > s3 . r 4. Kies s4 = 1−r (F (k|t − 1, 1 − r) − ft ). Onder deze inzet zijn de mogelijke uitkomsten:
Bij winst: ft +
1−r r (F (k|t − 1, 1 − r) − ft ) = F (k|t, 1 − r); r 1−r
bij verlies: r (F (k|t − 1, 1 − r) − ft ) 1−r 1 = (f − rF (k|t − 1, 1 − r)) 1−r t−1 t = F (k − 2|t − 1, 1 − r) + q − 1 (1 − r)k rt−k . k k−1
ft −
Dus geldt n ≤ m + 1 als s ≤ s4 en n > m + 2 als s > s4 . Voor de afgeleide van Es geldt nu: > 0 als s < max{s1 , s2 }; d = 0 als max{s1 , s2 } < s < min{s3 , s4 }; Es ds < 0 als s > min{s3 , s4 }. Dus: Es (ft , t) ≤ Q(ft , t). En Es (ft , t) is maximaal dan en slechts dan als de inzet s voldoet aan de eisen die in het tweede deel van de stelling gesteld zijn: st (ft ) is een optimale inzet dan en slechts dan als: 58
1. st (ft ) is binomiaal; n o r 2. st (ft ) ≥ max ft − F (k − 1|t − 1, 1 − r), 1−r (F (k − 1|t − 1, 1 − r) − ft ) ; o n r (F (k|t − 1, 1 − r) − ft ) . 3. st (ft ) ≤ min ft − F (k − 2|t − 1, 1 − r), 1−r
Voor het verwachte nut onder een optimale strategie geldt dan: U (ft , t) = max Es (ft , t) ≤ Q(ft , t). s
We weten al uit het eerste deel van het bewijs: U (ft , t) ≤ Q(ft , t). Hieruit volgt dat voor elk binomiaal kapitaal ft met nog t spellen te gaan geldt: U (ft , t) = Q(ft , t).
59
A.2
Matlab code voor numeriek bepalen van U (ft , t) en st (ft )
T=4; % aantal spellen dat er gespeeld kan worden w = 0.6; % winstkans per spel U = ones(2^T+1,T+1); %verwachte nut U(1,1) = 0; % startwaarden: U(0,0) = 0 en U(1,0) = 1 U(2,1) = 1; for t = 1:T f(1,t+1) = 0; f(2^t +1, t+1) = 1; for n = 1:2^t-1 f(n+1,t+1) = n/2^t; x = floor(n/2); % alle mogelijke uitkomsten onder een binaire inzet: for i= 0:x X(i+1,t) = (1-w)*U(i+1,t) + w*U(n-i+1,t); end %verwachte nut onder een optimale strategie: U(n+1,t+1) = max(X(:,t)); for i= 0:x %bijbehorende optimale inzetten: if X(i+1,t) == U(n+1,t+1) I(n+1,i+1,t+1) = i; S(n+1,i+1,t+1) = n/(2^t) -i/2^(t-1); %optimale inzetten end end end U(1,t+1)= 0; U(2^t+1,t+1)=1; end % Plot U(f,t) voor t = 1, ...,T for l = 1:T xl = 0:1/(2^l):1; stairs(xl,U(1:2^l+1,l+1)) xlabel(’kapitaal f’); ylabel(’U(f,t)’); hold all end 60
A.3
Matlab code voor een binaire inzet
function S = inzetbin(f,T) r F n m
= = = =
0.5; ones(T+1,T); floor(f*(2^T)); n/(2^T);
% F(k|t,1-r) bepalen for t = 1:T if t == 1 F(1,1) = r; F(2,1) = 1; end if t ~= 1 F(1,t) = r*F(1,t-1); for i = 1:t F(i+1,t) = (1-r)*F(i,t-1) + r*F(i+1,t-1); end end end % k(f) bepalen for j = 0:T if f < F(1,T) k = 0; break; elseif f < F(j+1,T) k = j; break; end; if f == 1 k = T; end end if T == 1; if m <0.5 S = 0; end
61
if m>= 0.5 S = 1-m; end end if T ~= 1 if k == 0 F0 = F(k+1,T-1); F1 = 0; F2 = 0; end if k == 1 F0 = F(k+1,T-1); F1 = F(k,T-1); F2 = 0; end if k>1 F0 = F(k+1,T-1); %binocdf(k,t-1,1-r); F1 = F(k,T-1); %binocdf(k-1,t-1,1-r); F2 = F(k-1,T-1); %binocdf(k-2,t-1,1-r); end Up = min(m - F2, F0 - m); %bovengrens optimale inzet Low = abs(F1 - m); %ondergens optimale inzet d1 = floor(n/2); s = zeros(1,d1+1); %binaire inzetten for j = 0:d1 s(j+1) = (n - 2*j)/(2^T); end %Optimale inzetten: S = s(s>=Low & s<= Up); end
62
A.4
Matlab code voor een binaire strategie
function[Y] = Strategiebin(f,t,w) B = binornd(1,w,t,1); %uitkomsten van het spel S = zeros(t+1,1); %inzetten Y = zeros(t+1,1); %resulterende kapitalen Y(1) = f; for i = 1:t s = inzetbin(Y(i),t-i+1); %mogelijke optimale inzetten S(i) = max(s); %kies de grootste inzet if B(i) == 1 %spel gewonnen Y(i+1) = Y(i) + S(i); elseif B(i) == 0 %spel verloren Y(i+1) = Y(i) - S(i); end end end
A.5
Matlab code voor simulaties onder een binaire strategie
N = 10000; M = 1000; t = 1; w = 0.75; Uitkomst = ones(M+1,N); U = zeros(M+1,1); for j = 0:M f = j/M; for i = 1:N Y = Strategiebin(f,t,w); if Y(t+1)<1 Uitkomst(j+1,i) = 0; end end U(j+1) = mean(Uitkomst(j+1,:)); end x=0:1/M:1; plot(x,U) xlabel(’kapitaal f’); ylabel(’U(f)’);
63
A.6
Matlab code voor U (ft , t) binair
function U = Ubin(f,w,T) %In het binaire geval r = 0.5; %binair spel F = ones(T+1,T); %F(k|t,1-r) Fw = ones(T+1,T); %F(k|t,1-w) n = floor(f*(2^T)); m = n/(2^T); for t = 1:T %F(k|t,p) bepalen if t == 1 F(1,1) = r; F(2,1) = 1; Fw(1,1) = w; Fw(2,1) = 1; end if t ~= 1 F(1,t) = r*F(1,t-1); Fw(1,t) = w*Fw(1,t-1); for i = 1:t F(i+1,t) = (1-r)*F(i,t-1) + r*F(i+1,t-1); Fw(i+1,t) = (1-w)*Fw(i,t-1) + w*Fw(i+1,t-1); end end end %k bepalen for j = 0:T if m < F(1,T) k = 0; break; elseif m < F(j+1,T) k = j; break; end; if m == 1 k = T; 64
end end; %q en U(f,t) bepalen if k == 0 q = m/F(1,T); U = q * Fw(1,T); end if k ~= 0 && k ~= T+1 q = (m - F(k,T))/(F(k+1,T) - F(k,T)); U = Fw(k,T) + q * (Fw(k+1,T) - Fw(k,T)); end if k == T+1 q = 0; U = 1; end end
65
A.7
Matlab code voor U (ft , t) binomiaal
function U = Ubino(f,r,w,T) F = ones(T+1,T); Fw = ones(T+1,T);
%F(k|t,1-r) %F(k|t,1-w)
%Bepalen van F(k|t,p) for t = 1:T if t == 1 F(1,1) = r; F(2,1) = 1; Fw(1,1) = w; Fw(2,1) = 1; end if t ~= 1 F(1,t) = r*F(1,t-1); Fw(1,t) = w*Fw(1,t-1); for i = 1:t F(i+1,t) = (1-r)*F(i,t-1) + r*F(i+1,t-1); Fw(i+1,t) = (1-w)*Fw(i,t-1) + w*Fw(i+1,t-1); end end end %k bepalen for j = 0:T if f < F(1,T) k = 0; break; elseif f < F(j+1,T) k = j; break; end; if f == 1 k = T; end end; % U(f,t) bepalen 66
if k == 0 P = F(1,T) ; q = f/P ; R = r^T; X = round(P/R*10^8)*10^(-8); Q = floor(q*X); W = w^T; U = Q*W; end if k ~= 0 && k ~= T+1 P = (F(k+1,T) - F(k,T)); q = round((f - F(k,T))/P*10^8)*10^(-8); R = (1-r)^(k) * r^(T-k); X = round(P/R*10^8)*10^(-8); Q = floor(q*X); W = (1-w)^(k)*w^(T-k); U = Fw(k,T) + Q*W; end if k == T+1 q = 0; U = 1; end end
67