Conway s algoritme. Roelof Kuipers 7 juli Bachelorscriptie Begeleiding: dr. Sonja Cox

Conway’s algoritme Roelof Kuipers 7 juli 2015 Bachelorscriptie Begeleiding: dr. Sonja Cox

Korteweg-de Vries Instituut voor Wiskunde Faculteit der Natuurwetenschappen, Wiskunde en Informatica Universiteit van Amsterdam

Samenvatting Iedereen wil gratis geld. Veel mensen proberen dit te krijgen door te gokken in het casino, maar gaan uiteindelijk altijd blut naar huis. Toch heeft wiskundige John Conway een algoritme bedacht waarmee je er in sommige spellen toch voor kan zorgen dat je zonder veel moeite met een grote kans wint. Spellen waarbij dit kan zijn nontransitief, maar Conway’s algoritme is slechts van toepassing op ´e´en spel in het bijzonder: Penney’s spel. Conway’s algoritme werkt alleen op een nogal rare manier: je gebruikt binaire getallen, trekt wat van elkaar af en zo kan je de kans berekenen waarmee je wint van je tegenspeler. In deze scriptie wordt onderzocht waarom het werkt. Li [3] heeft in zijn artikel A Martingale Approach to the Study of Occurence of Sequence Patterns in Repeated Experiments met behulp van martingalen en verwachte stoptijden aangetoond dat Conway’s algoritme werkt. Daarvoor is eerst veel voorkennis op het gebied van maattheorie en martingalen nodig. Eerst zal daarover worden uitgeweid in deze scriptie waarna dit als een opstap wordt gebruikt voor het bewijs van Conway’s algoritme door Li [3].

Titel: Conway’s algoritme Auteur: Roelof Kuipers, [email protected], 10220321 Begeleiding: dr. Sonja Cox Einddatum: 7 juli 2015 Korteweg-de Vries Instituut voor Wiskunde Universiteit van Amsterdam Science Park 904, 1098 XH Amsterdam http://www.science.uva.nl/math

2

Inhoudsopgave 1. Inleiding

4

2. Nontransitiviteit in de kansrekening 2.1. Nontransitieve dobbelstenen . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Penney’s spel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Conway’s algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 8 9

3. Voorwaardelijke verwachting 3.1. Voorwaardelijke verwachting van L2 - & L1 -integreerbare stochasten 3.2. Convergentie en uniforme integreerbaarheid . . . . . . . . . . . . . 3.2.1. Convergentie . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2. Uniforme integreerbaarheid . . . . . . . . . . . . . . . . . . 3.2.3. Limietstellingen . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Convergentie van de voorwaardelijke verwachting . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

13 13 16 17 17 18 19

4. Martingalen 4.1. Definitie martingaal . . . . . . . . . . . 4.2. Sub- en supermartingalen . . . . . . . 4.3. Martingaaltransformaties en stoptijden 4.4. De stelling van Doob . . . . . . . . . .

. . . .

. . . .

. . . .

21 21 23 24 26

. . . . . . A . .

. . . . .

. . . . .

27 27 30 30 34 37

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

5. Bewijs van Conway’s algoritme 5.1. Terminologie voor het bewijs . . . . . . . . . . . . . 5.2. Bewijs van Conway’s algoritme . . . . . . . . . . . 5.2.1. Verwachte stoptijd voor sequentie B na A . 5.2.2. Afleiding van de kans dat sequentie B eerder 5.2.3. Afleiding van Conway’s algoritme . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . . . . . . . . . voorkomt dan . . . . . . . .

. . . .

6. Discussie

40

7. Populaire samenvatting

41

Bibliografie

42

A. Bijlage

43

3

1. Inleiding Heel veel geld verdienen, zonder daar veel moeite voor te hoeven doen. Wie wil dat nou niet? Je zou dan eindelijk een gouden Lamborghini kunnen kopen, kunnen baden in champagne of een villa kunnen kopen op een afgelegen tropisch eiland. Zelf zou ik een wasmaschine en een droger kopen zodat ik niet elke keer weer met tassen vol was naar de waserette hoef te gaan. Veel mensen proberen dit voor elkaar te krijgen door te gokken in het casino en zo te hopen dat ze daar met het winnen van spelletjes bakken met geld verdienen. Wij wiskundigen weten dat de kans dat dit ook daadwerkelijk gebeurd ongelofelijk klein is, terwijl de kans dat je blut naar huis gaat juist weer heel groot is. Maar kunnen wij onze wiskundige kennis en inzichten in de kansrekening niet gebruiken om ervoor te zorgen dat deze kans aanzienlijk groter wordt en dat wij zo dankzij de wiskunde toch moeiteloos veel geld kunnen verdienen? In mijn scriptie zal worden aangetoond dat dit bij sommige spellen kan. Deze spellen hebben een bepaalde eigenschap die nontransitiviteit heet. E´en spel in het bijzonder ga ik bekijken, genaamd Penney’s spel. Dit is een spel voor twee spelers bedacht door Walter Penney waarbij herhaaldelijk een munt op wordt gegooid en waarbij spelers na elkaar een bepaalde strategie kiezen. Hoewel het lijkt dat bij dit spel de kans op winst en verlies gelijk is, heeft wiskundige John Conway een algoritme bedacht waarmee de tweede speler met eenvoudige wiskunde kan zorgen dat hij het spel altijd met een grote kans wint. Het algoritme is alleen nogal raar: je zet dingen om naar binaire getallen, trekt dan weer een paar van deze binaire getallen van elkaar af en als je dat op een bepaalde manier van krijg je daaruit de verhouding waarmee speler twee wint van speler een. De grote vraag is daarom ook: waarom werkt dit Conways algoritme? Dit ga ik in mijn scriptie onderzoeken en aantonen. Het bewijs van Conways algoritme dat ik hiervoor gebruik is van Li [3] en maakt gebruik van martingalen en vele maattheoretische onderwerpen. Ik ben het meeste hiervan nog niet eerder in mijn bachelor tegengekomen. Het is daarom nodig om ons eerst wat meer in deze voor het bewijs vereiste voorkennis te verdiepen voordat we kunnen bewijzen dat Conways algoritme werkt. Als we hiermee eenmaal hebben bewezen dat Conways algoritme klopt, kunnen we het gebruiken om voor geld Penney’s spel te spelen en zo eindelijk moeiteloos bakken met geld te verdienen! Allereerst zal ik het hebben over wat deze nontransitieve spellen nou precies zijn, uitleggen hoe het Penney’s spel werkt en bespreken hoe Conways algoritme gaat. Vervolgens zal ik in twee hoofdstukken bezig zijn met de opmaat voor het bewijs: we kijken naar de voorwaardelijke verwachting van L1 −integreerbare stochasten. Dit gebruiken we in het hoofdstuk daarna om te kijken naar wat martingalen zijn en een belangrijke stelling af te leiden: de stelling van Doob. Tenslotte zullen we dit allemaal gebruiken om Conways algoritme bewijzen.

4

Deze scriptie is gebaseerd op twee primaire bronnen: allereerst de syllabus Measure Theoretic Probabilty van Spreij [8] die ons de voorkennis geeft en ten tweede het artikel A Martingale Approach to the Study of Occurence of Sequence Patterns in Repeated Experiments van Li [3] dat Conways algoritme bewijst.

5

2. Nontransitiviteit in de kansrekening Als we willen onderzoeken hoe Conway’s algoritme werkt moeten we eerst kijken naar nontransitiviteit in de kansrekening. Maar wat was transitiviteit ook alweer? Transitiviteit is een relatie die wanneer hij geldt tussen A en B en tussen B en C, hij ook moet gelden tussen A en C. Als jij zwaarder bent dan Raymond van Barneveld en Raymond van Barneveld zwaarder is dan Frans Bauer, dan ben jij ook automatisch zwaarder dan Frans Bauer. Of, omdat het getal 1 kleiner is dan 2 en het getal 2 weer kleiner is dan 4, moet 1 ook wel kleiner zijn dan 4. In de kansrekening zijn er echter veel voorbeelden te vinden van gebeurtenissen die op het eerste gezicht transitief lijken, maar dat niet blijken te zijn. Ik zal hier twee voorbeeld van geven die besproken worden in Martin Gardner’s The Colossal Book of Mathematics [2001]. Eerst zal ik het hebben over een voorbeeld van een nontransitief spel en vervolgens zal ik bespreken hoe je de nontransitiviteit hierbij kan gebruiken om er altijd met een grote kans voor te zorgen dat je het spel wint. Daarna zal ik het tweede voorbeeld van een nontransitief spel geven: het spel van Penney. Dit is een spel waarbij je een munt herhaaldelijk opgooit en waarbij je Conway’s algoritme nodig hebt om gebruik te maken van de nontransitiviteit en er zo voor te zorgen dat je ook hier altijd met een grote kans het spel wint.

2.1. Nontransitieve dobbelstenen Een illustratief voorbeeld van nontranstiviteit in de kansrekening is het volgende spel met oneerlijke dobbelstenen: we hebben vier oneerlijke dobbelstenen die weergegeven zijn in Figuur 2.1. Je speelt met twee personen een spel waarbij je na elkaar een dobbelsteen kiest. Je gooit daarna allebei je dobbelsteen en degene die het hoogste cijfer heeft wint. Als deze dobbelstenen transitief zouden zijn, dan zou er een dobbelsteen zijn die het beste is van de vier (denk hierbij aan de voorbeelden die in de vorige alinea zijn benoemd). Speler ´e´en zou dan altijd de dobbelsteen kunnen kiezen die met de grootste kans hoger gooit dan alle andere dobbelstenen en speler twee zou dan altijd benadeeld zijn. Maar dit blijkt niet het geval te zijn. We zullen zien dat bij deze dobbelstenen, ongeacht welke dobbelsteen de eerste persoon kiest, de tweede speler altijd een dobbelsteen kan kiezen zodat hij met kans 2/3 van de eerste speler wint. Dit, omdat de dobbelstenen nontransitief zijn. Laten we de eerste speler ‘speler A’ noemen en de tweede speler ‘speler B’. Het is handig om eerst even wat notaties in te voeren. Stel speler A heeft de eerste dobbelsteen uit Figuur 2.1. Als we de kans willen weten dat speler A een 4 gooit dan zullen we dit

6

Figuur 2.1.: Nontransitieve dobbelstenen [2, p. 287] . schrijven als P(4A ). Als speler B de tweede dobbelsteen heeft en we de kans willen weten dat A een 4 gooit en B een 3 dan zullen we dit noteren als P(4A ∩ 3B ). Nu, stel A kiest dus de eerste dobbelsteen en B de tweede, dan wint speler A als hij een 4 gooit en speler B een 3 gooit. Dit is dus met kans: P(4A ∩ 3B ) = P(4A ) · P(3B ) = 4/6 · 1 = 2/3. A wint dan dus met kans 2/3 van B. Analoog, als A de tweede dobbelsteen kiest en B de derde, wint A met kans: P(3A ∩ 2B ) = P(3A ) · P(2B ) = 1 · 4/6 = 2/3. Nu, als A de derde dobbelsteen kiest en B de vierde, dan wint A als hij een 2 gooit en speler B een 1 o´f als A een 6 gooit. Dit is dus met kans: P((2A ∩ 1B ) ∪ 6A ) = P(2A ∩ 1B ) + P(6A ) = P(2A ) · P(1B ) + P(6A ) = 4/6 · 3/6 + 2/6 = 12/36 + 1/3 = 2/3. Dit lijkt dus een transitief spel te zijn. Dobbelsteen ´e´en gooit met kans 2/3 hoger dan de tweede dobbelsteen, maar de tweede dobbelsteen gooit weer met dezelfde kans hoger dan de derde en ook de derde gooit weer met kans 2/3 hoger dan de vierde dobbelsteen. Maar laten we nu kijken naar de kans waarmee speler A wint van speler B als speler A de vierde dobbelsteen kiest en speler B de eerste. Speler A moet dan een 5 gooien o´f speler A moet een 1 gooien en speler B een 0. Dit is dus met kans: P(5A ∪ (1A ∩ 0B )) = P(5A ) + P(1A ) · P(0B ) = 3/6 + 3/6 · 2/6 = 3/6 + 6/36 = 2/3. De dobbelstenen zijn dus nontransitief en we krijgen de kansen waarmee de ene dobbelsteen hoger gooit dan de ander zoals je kan zien in Figuur 2.1. Gemiddeld genomen

7

wint dobbelsteen 1 van dobbelsteen 2, wint dobbelsteen 2 van 3, dobbelsteen 3 weer van 4, maar 4 wint weer van dobbelsteen 1. Als spelers A en B om de beurt een dobbelsteen kiezen, kan speler B vanwege de nontransitiviteit van de dobbelstenen dus altijd na A een dobbelsteen kiezen waarmee hij met kans 2/3 van A wint. Oftewel bij deze nontransitieve dobbelstenen wint B twee keer zo vaak als A. We kunnen dus in het algemeen zeggen dat bij een dergelijk nontransitief spel de tweede speler altijd in het voordeel is.

2.2. Penney’s spel Een ander spel dat ook door Gardner [2001] besproken wordt is een spel dat je speelt door herhaaldelijk een munt op te gooien en dat bedacht is door Walter Penney (een nogal toepasselijke naam). Als je een munt opgooit krijg je met kans 1/2 kop en met kans 1/2 munt. We zullen vanaf nu ‘kop’ noteren met een ‘H’ (van ‘heads’) en ‘munt’ met een ‘T’ (van ‘tails’). Als we deze munt drie keer gooien dan hebben we 23 = 8 mogelijk uitkomsten. Dit zijn namelijk: HHH, HHT, HT H, T HH, T HT, T T H en T T T . Penney’s spel gaat als volgt: we spelen een spel met twee spelers waarbij de eerste speler ´e´en van deze acht mogelijke uitkomsten kiest en de tweede speler daarna ´e´en van de overgebleven zeven. We blijven dan herhaaldelijk een munt opgooien tot ´e´en van de door de twee spelers gekozen uitkomsten achter elkaar verschijnt. Degene bij wie dit als eerst gebeurt wint. Het lijkt alsof dit een eerlijk spel is. De kans op kop is namelijk altijd even groot als de kans op munt. Maar toch is dit niet zo. We noemen speler ´e´en weer ‘speler A’ en speler twee weer ‘speler B’. Stel speler A kiest HHT en B kiest daarna T HH. Als we een T hebben gegooid, dan hoeft B alleen nog maar HH te krijgen. Dit, terwijl A nog steeds HHT moet krijgen. Er is dus een grotere kans dat de keuze van B eerder verschijnt dan die van A. Hoewel dit spel dus eerlijk lijkt is het dat helemaal niet. Het is daarom van belang dat beide spelers spelen met een bepaalde strategie: ze moeten de mogelijke rij van drie opeenvolgende uitkomsten z´o kiezen dat ze met een grote kans het spel winnen. Dus stel de strategie van A is om T HH te kiezen, en die van B is HHH. Als we achtereenvolgens T T HT HH gooien, dan wint A, speler ´e´en. We kunnen zelfs de precieze kansen uitrekenen waarmee de strategie van B, speler twee, wint van de strategie van A, speler ´e´en. Het uitrekenen van deze kansen zal ik hier niet doen, maar deze zijn weergegeven in Figuur 2.2. Hieruit blijkt dat ook dit een nontransitief spel is. Het maakt niet uit welke strategie A als eerste kiest, B kan altijd na A een strategie kiezen zodat hij met minimaal kans 2/3 en maximaal 7/8 van A wint. Kiest speler A strategie T HH dan wint speler B met kans 2/3 als hij strategie T T H kiest. Als dit spel transitief zou zijn dan zou speler A een strategie kunnen kiezen waarmee hij gegarandeerd met een grote kans wint van B, maar dit is dus niet het geval. De tweede speler is ook hier dus altijd in het voordeel. In Bijlage A is de Python code voor een programma dat Penney’s spel voor twee strategie¨en 100.000 keer simuleert te vinden. Dit heb ik geschreven voor de flitspresentatie voor mijn scriptie om te laten zien dat dit, hoewel het een eerlijk spel lijkt te zijn, vanwege de nontransitiviteit een oneerlijk spel is.

8

Figuur 2.2.: De kansen dat B wint van A [2, p. 303] . Het blijkt dat voor alle strategi¨en van sequenties van lengte n groter dan 2 deze nontransitiviteit geldt. Voor elke lengte n > 2 geldt dus dat als beide spelers een strategie van lengte n kiezen, dat B, de tweede speler, altijd een strategie kan kiezen waarmee hij met een grote kans wint van A, de eerste speler. Het enige probleem is dat als we willen bepalen welke strategie B moet kiezen, we eerst de kansen moeten uitrekenen waarmee elke strategie wint van A, zoals te zien was bij het strategie¨en van lengte 3 in Figuur 2.2. Bij strategie¨en van lengte 3 is dat zelfs al veel werk, maar dat is nog te doen. We hebben dan immers slechts 23 = 8 mogelijke strategie¨en. Maar als we naar strategie¨en kijken van lengte 10 dan zijn er al 210 = 1024 mogelijkheden. Dit is dus bijna niet te doen! Maar betekent dit dat we in dit spel dus toch niet makkelijk kunnen winnen van speler A als we speler B zijn? Gelukkig kunnen we dat alsnog. John Conway heeft namelijk een algoritme bedacht waarmee ongeacht de lengte van de strategie¨en gemakkelijk de kans kunnen uitrekenen dat speler B van speler A wint.

2.3. Conway’s algoritme So I do some serious mathematics, but I also do games. And for me, they are very similar. −John Conway In Penney’s spel kan het lastig zijn om uit te rekenen wat te kans is waarmee de

9

ene strategie van een ander wint, en al helemaal als de strategie¨en nogal lang zijn. Dit kan worden opgelost door Conway’s algoritme te gebruiken, dat besproken wordt door Gardner [2001]. Als we Penney’s spel spelen voor geld en zorgen dat we de tweede speler, oftewel speler B, zijn (dit zou overigens wel makkelijk te regelen zijn, omdat de tegenspeler toch denkt dat het een eerlijk spel is, dus wie er als eerste begint zou dan niet uitmaken), dan kunnen we er met dit algoritme voor zorgen dat we gemakkelijk met grote kans van de eerste speler winnen. Zo kunnen we dus moeiteloos veel geld verdienen en dat is natuurlijk precies wat we willen. Maar hoe werkt dit algoritme precies? Laten we naar een voorbeeld kijken met strategi¨een van lengte 7. Stel bijvoorbeeld dat speler A de sequentie (oftewel strategie) T HHT T T H kiest en speler B de sequentie (oftewel stragie) T T T HT HT . We willen de kans weten dat de strategie van B eerder voorkomt dan die van A als we herhaaldelijk een munt opgooien. Wat we dan volgens Conway’s algoritme moeten doen is het volgende: we schrijven de strategie van A boven A, die B boven B, A boven B en van B boven A (zie Figuur 2.3). Vervolgens maken we een binair getal van elk paar strategie¨en, beginnend met het paar AA van A boven A, door delen van de bovenste sequentie te vergelijken met de onderste sequentie. Dit werkt alsvolgt: we kijken dus eerst naar het paar AA en gaan kijken of de eerste zeven letters T HHT T T H van de bovenste sequentie A overeenkomen met de eerste zeven letters T HHT T T H van de onderste sequentie. Komen ze overeen dan zetten we een 1 onder de eerste letters van beide sequenties neer en zo niet, dan zetten we er een 0 niet. Zoals je in Figuur 2.3 kan zien, als je naar het paar AA, kijkt is dat het geval. We krijgen dus een 1 onder de eerste letters. Vervolgens kijken we naar de laatste zes letters van de bovenste strategie T HHT T T H van A. Dit is dus de (deel)sequentie HHT T T H. Deze vergelijken we met de eerste zes van de sequentie A daaronder: T HHT T T . Komen ze overeen dan zetten we een 1 onder de tweede letter van beide sequenties. We zien dat HHT T T H niet gelijk is aan T HHT T T , dus we zetten een 0 onder de tweede letters. Dit is ook weer te zien in Figuur 2.3. Daarna gaan we de laatste vijf letters van de bovenste sequentie met de eerste vijf van de onderste sequentie van het paar AA vergelijken. We zien dat HT T T H niet gelijk is aan T HHT T dus we zetten ook onder de derde letter een 0 neer. Daarna vergelijken we T T T H met T HHT en we krijgen weer een 0. Hetzelfde geldt voor T T H en T HH, maar als we de laatste twee letters T H van de bovenste sequentie vergelijken met de eerste twee letters T H van de sequentie daaronder dan zien we dat ze gelijk zijn. Dus onder de zesde letter zetten we een 1. Tenslotte vergelijken we de laatste letter H met de eerste letter T daaronder en die komen niet overeen dus we zetten onder de zevende letter een 0. Zo hebben we uiteindelijk voor het paar AA het binaire getal 1000010 geconstrueerd. Dit komt overeen met het decimale getal 68. We noemen dit getal het kengetal AA van A over A. Op dezelfde manier gaan we door de strategie A met B vergelijken een binair getal construeren en dat doen we ook als we B met B vergelijken en B met A (merk op dat B met A vergelijken niet hetzelfde binaire getal geeft als wanneer we A met B vergelijken, je kan dit zelf nagaan en zien in Figuur 2.3). Zo krijgen we dus het kengetal AA van A over A, het kengetal AB van A over B, het kengetal BB van B over B en het kengetal BA van B over A. Deze zijn te zien in Figuur 2.3. Vervolgens bepalen we alsvolgt de verhouding waarmee de strategie B eerder voorkomt dan A als we herhaaldelijk een

10

Figuur 2.3.: Conway’s algoritme waarmee we de kans dat B wint van A kunen berekenen [2, p. 307]. munt opgooien: (AA − AB) : (BB − BA) = (68 − 8) : (65 − 1) = 60 : 64 = 15 : 16. Dit is wederom ook te zien in Figuur 2.3. De verhouding waarmee B eerder voorkomt dan A is dus 15 : 16. Per 16 keer dat B voorkomt komt A maar 15 keer voor. De kans 16 dat B wint is dan 15+16 = 16 ≈ 0.52. 31 We willen nu even controleren of de kans 2/3 waarmee de strategie T T H van speler B eerder voorkomt dan de strategie T HH van A uit Figuur 2.2 klopt door Conway’s algoritme te grbuiken. Als we A en B zo gaan vergelijken als in Conway’s algoritme dan krijgen we de volgende kengetallen: AA = 4, AB = 0, BB = 4 en BA = 2. Nu is de verhouding waarmee B eerder voorkomt dan A: (AA − AB) : (BB − BA) = (4 − 2) : (4 − 0) =2:4 = 1 : 2. 2 = 23 . Dit komt overeen met wat we zien Dus B komt eerder voor dan A met kans 1+2 in Figuur 2.2. We kunnen dus met Conway’s algoritme gemakkelijk de kansen uitrekenen waarmee een strategie van speler twee eerder voorkomt dan de strategie van speler ´e´en. En hoewel het op het eerste opzicht niet zo lijkt, is Penney’s spel dus een nontransitief spel waarbij dus de tweede speler met grotere kans wint. We kunnen daarom Conway’s algoritme gebruiken om zo bakken met geld te verdienen. Alleen is de manier waarop dit algoritme werkt dus nogal raar: we moeten alle strategie¨en met elkaar vergelijken (ook de strategie van speler A met zichzelf), op een rare manier omzetten naar binaire getallen, wat van elkaar aftrekken en dan krijgen we de verhouding waarmee B wint van A. Zoals Gardner [2] erover zegt:

11

I have no idea why it works. It just cranks out the answer as if by magic, like so many of Conway’s other algorithms. Dus waarom werkt Conway’s algoritme? Dat is wat ik ga onderzoeken en bewijzen in deze scriptie. Het uiteindelijke bewijs komt van Li [3], maar voordat we daaraan kunnen beginnen moeten we eerst naar martingalen en andere maattheoretische onderwerpen bekijken. Deze zijn nodig, omdat Li’s bewijs is gebaseerd op martingalen alsmede een voor het bewijs belangrijke stelling die we ook eerst moeten bewijzen: de stelling van Doob. Allereerst moeten we beginnen bij de basis voor dit allemaal: we zullen kijken naar de voorwaardelijke verwachting van L2 - & L1 -integreerbare stochasten. We zullen in hetvolgende hoofdstuk meteen in het diepe duiken en daarmee beginnen.

12

3. Voorwaardelijke verwachting Voor Li’s bewijs van Conway’s algoritme is dus flink wat voorkennis nodig. We beginnen met het defini¨eren van de voorwaardelijke verwachting van stochasten. Dit hebben we vervolgens nodig als we kijken naar martingalen, die weer belangrijk zijn voor het bewijs van Li. Zij (Ω, F, P) een kansruimte. Dan zeggen we, zoals dat in Rynne and Youngson [6] gedefineerd is, dat een stochast X ∈ Lp (Ω, F, P) als X een Lp −integreerbare functie is. ¯ is meetbaar, ∀α ∈ R geldt {ω ∈ Ω : X(ω) > α} ∈ F en Dat wil zeggen: X : Ω → R
R 1/p |X|p dP < ∞. Ω

3.1. Voorwaardelijke verwachting van L2- & L1-integreerbare stochasten Eigen versie van H8 van Peter Spreij’s Measure Theoretic Probability [2014] en addendum Sonja Cox. Definitie 3.1. Laat (Ω, F, P) een kansruimte zijn en G ⊆ F een sub-σ-algebra op F. Beschouw de stochast X ∈ L2 (Ω, F, P). We zijn geinteresseerd in het zo goed mogelijk benaderen van X met een stochast als we maar beperkte informatie over X hebben, namelijk informatie uit G ⊆ F. Deze stochast die X benaderd noteren we als E(X|G) en is het unieke element van L2 (Ω, G, P) zodat kX − E(X|G)kL2 (Ω,F ,P) ≤

inf

Y ∈L2 (Ω,G,P)

kX − Y kL2 (Ω,F ,P) .

Oftewel E(X|G) is de stochast die het dichtst bij X in de buurt ligt van alle mogelijke stochasten in L2 (Ω, G, P). We noemen E(X|G) de voorwaardelijke verwachting van X gegeven G. De voorwaardelijke verwachting E(X|G) van X ∈ L2 (Ω, F, P) gegeven G bestaat altijd. Omdat L2 (Ω, F, P) een Hilbertruimte is en L2 (Ω, G, P) een gesloten (want volledige) deelruimte is, volgt uit Stelling 4.50 uit Spreij [8] de existentie en de uniciteit van een E(X|G). Lemma 3.2. Beschouw kansruimte (Ω, F, P), sub-σ-algebra G ⊆ F en stochast X ∈ L2 (Ω, F, P). Voor alle gebeurtenissen G ∈ G geldt dat Z Z E(X|G) dP = X dP. G

G

13

Bewijs. Omdat X − E(X|G) orthogonaal staat op L2 (Ω, G, P) geldt (zie stelling 4.50 uit Spreij [8]) voor alle Z ∈ L2 (Ω, G, P) dat (X − E(X|G), Z)L2 (Ω,F ,P) = 0. Hierbij gebruiken we het standaardinproduct op L2 (Ω, F, P) gedefinieerd in Rynne and Youngson [6]. Nemen we nu Z = 1G , merk op dat 1G ∈ L2 (Ω, G, P), dan krijgen we: Z (X − E(X|G), 1G )L2 (Ω,F ,P) = (X − E(X|G))1G dP = 0. Ω

Oftewel, Z

Z E(X|G) dP =

G

X dP. G

Opmerking. De voorwaardelijke verwachting E(X|G) is de orthogonale projectie van X ∈ L2 (Ω, F, P) op L2 (Ω, G, P) en een orthogonale projectie is een lineaire operator. Vervang in Lemma 3.2 de stochast X ∈ L2 (Ω, F, P) voor Y + Z met Y, Z ∈ L2 (Ω, F, P) en er volgt dat E(Y +Z|G) = E(Y |G)+E(Z|G). Ook geldt zo voor α ∈ R dat E(αX|G) = αE(X|G). Lemma 3.3. Beschouw kansruimte (Ω, F, P), sub-σ-algebra G ⊆ F en stochast X ∈ L2 (Ω, F, P). Als Y ∈ L2 (Ω, G, P) voldoet aan Z Z Y dP = X dP. G

G

voor alle G ∈ G, dan moet gelden Y = E(X|G). Bewijs. Stel Y ∈ L2 (Ω, G, P) voldoet aan Z Z Y dP = X dP G

G

voor alle G ∈ G. We gaan laten zien dat hieruit volgt dat P({Y > E(X|G)}) = 0 en P({Y < E(X|G)}) = 0, oftewel Y = E(X|G). Zowel Y als E(X|G) zijn G-meetbaar, en dus is de verzameling {Y > E(X|G)} ook G-meetbaar. Immers, Y − E(X|G) is meetbaar dus ook {Y − E(X|G) > 0} ∈ G. Uit Lemma 3.2 volgt nu Z Z Z Y dP = X dP = E(X|G) dP. {Y >E(X|G)}

En dus

{Y >E(X|G)}

{Y >E(X|G)}

Z (E(X|G) − Y ) dP = 0. {Y >E(X|G)}

14

(3.1)

Stel dat P({Y > E(X|G)}) > 0, dan Z (E(X|G) − Y ) dP < 0. {Y >E(X|G)}

Maar dit is in tegenspraak met (3.1), dus P({Y > E(X|G)}) = 0. Analoog geldt voor {Y < E(X|G)} dat P({Y < E(X|G)}) = 0. Dus P({Y = E(X|G)}) = 1 en Y = E(X|G) in L2 (Ω, G, P). We slaan voor Gevolg 3.4 en Gevolg 3.5 het bewijs over, omdat het bewijs analoog gaat aan het bewijs van Lemma 3.3. We zullen deze gevolgen nodig hebben voor het bewijs van Lemma 3.7. Vervolgens gebruiken we Lemma 3.7 om existentie aan te tonen in Definitie 3.8. Gevolg 3.4. Beschouw kansruimte (Ω, F, P), sub-σ-algebra G ⊆ F en stochast X ∈ L2 (Ω, F, P). Als X ≥ 0, dan geldt Z Z E(X|G) dP = X dP ≥ 0 {E(X|G)<0}

{E(X|G)<0}

en dus E(X|G) ≥ 0. Gevolg 3.5. Analoog hebben we onder dezelfde voorwaarden als in Gevolg 3.4 dat als voor stochast Y ∈ L2 (Ω, F, P) geldt dat X ≥ Y , dan ook E(X|G) ≥ E(Y |G). Gevolg 3.6. Beschouw kansruimte (Ω, F, P), sub-σ-algebra G ⊆ F en stochast X ∈ L2 (Ω, F, P). Dan geldt Z E(X|G) dP = E(X). E(E(X|G)) = Ω

De eerste gelijkheid geldt per definitie van de verwachting van een stochast X (zie §4.4 in Spreij [8]) en hetzelfde geldt voor de tweede gelijkheid, omdat we integreren over de hele ruimte Ω. Lemma 3.7. Voor alle X ∈ L2 (Ω, F, P) geldt dat E|E(X|G)| ≤ E|X|. Bewijs. Zoals we eerder zagen is de voorwaardelijke verwachting E(X|G) van X gegeven G een lineaire operator. We hebben daarom |E(X|G)| = |E(X + |G) + E(X − |G)| ≤ E(X + |G) + E(X − |G) = E(|X||G).

(driehoeksongelijkheid)

Passen we nu Gevolg 3.6 toe dan krijgen we E|E(X|G)| ≤ E|X|. We willen nu bekijken wat de voorwaardelijke verwachting is van X als X ∈ L1 (Ω, F, P).

15

Definitie 3.8. Laat (Ω, F, P) een kansruimte zijn, G ⊆ F een σ-algebra en X ∈ L1 (Ω, F, P). De voorwaardelijke verwachting E(X|G) van X gegeven G is het unieke element van L1 (Ω, G, P) zodat voor alle G ∈ G geldt dat Z Z E(X|G) dP = X dP. G

G

We moeten de existentie en de uniciteit van de voorwaardelijke verwachting E(X|G) van X gegeven G aantonen. Eerst de existentie. De verzameling van alle simpele functies ligt overal dicht in elke ruimte Lp (Ω, F, P), met 1 ≤ p < ∞. (zie Bogachev [1]). Dus zij X ∈ L1 (Ω, F, P), dan kan X benaderd worden met een rij simpele functies (Xn )n≥0 in L2 (Ω, F, P) zodat limn→∞ kXn − XkL1 (Ω,F ,P) = 0. Nu volgt uit Lemma 3.7 en uit Jensen’s ongelijkheid (Stelling 8.7 (iii) uit Spreij [8]) dat: E|E(Xn |G) − E(Xm |G)| ≤ E(E(|Xn − Xm |G)) ≤ E|Xn − Xm |. Omdat (Xn )n≥0 convergent is in L1 (Ω, F, P) is het ook een Cauchyrij. Dus (E(Xn |G))n≥0 is ook een Cauchyrij in L1 (Ω, F, P). We weten dat L1 (Ω, F, P) een volledige ruimte is dus de Cauchyrij (E(Xn |G))n≥0 convergeert naar een element van L1 (Ω, F, P). Dit element noemen we de voorwaardelijke verwachting E(X|G) van X gegeven G. De uniciteit van E(X|G) wordt aangetoond op een zelfde manier als in Lemma 3.3. We hebben in deze paragraaf gekeken naar het zo goed mogelijk benaderen van stochasten X ∈ L2 (Ω, F, P) en X ∈ L1 (Ω, F, P) als we maar beperkte informatie G ⊂ F hebben. Deze unieke benadering heet de voorwaardelijke verwachting E(X|G) van X gegeven G. We zullen later kijken naar rijen van stochasten waarvan de voorwaardelijke verwachting aan een bepaalde eigenschap voldoet. Deze rijen van stochasten heten martingalen en zijn van groot belang voor het bewijs van Conway’s algoritme. Om met deze martingalen te kunnen werken moeten we eerst nog wat meer eigenschappen van de voorwaardelijke verwachting kennen.

3.2. Convergentie en uniforme integreerbaarheid Eigen versie van H4 en H7 van Peter Spreij’s Measure Theoretic Probability [2014]. We zullen in de volgende paragraaf kijken naar de convergentie van een rij voorwaardelijke verwachtingen, omdat we hier een aantal eigenschappen van de voorwaardelijke verwachting mee afleiden die we nodig hebben voor het bewijs van Conway’s algoritme. Voordat we dat doen moeten we eerst kijken naar de convergentie en uniforme integreerbaarheid van (collecties van) stochasten in L1 (Ω, F, P). We zullen in deze paragraaf bovendien een aantal stellingen bewijzen die we nodig hebben voor het bewijs van de stelling van Doob (Stelling 4.14) in het volgende hoofdstuk. Deze stelling is ook heel belangrijk voor het bewijs van Conway’s algoritme.

16

3.2.1. Convergentie Definitie 3.9. Zij X, X1 , X2 , . . . een rij stochasten. We hebben de volgende drie soorten van convergentie. Hierbij laten we n steeds naar oneinding gaan. (i) Als P(ω : Xn (ω) → X(ω)) = 1, dan convergeert Xn ‘bijna zeker’ (b.z.) naar X. b.z. Notatie: Xn −−→ X. (ii) Als P(|Xn − X| > ) → 0 voor alle  > 0, dan convergeert Xn in kans naar X. P Notatie: Xn − → X. (iii) Als E|Xn − X|p → 0 (oftewel kXn − Xkp → 0) voor p ≥ 1, dan convergeert Xn Lp naar X in Lp . Notatie: Xn −→ X.

3.2.2. Uniforme integreerbaarheid We gaan nu een collectie stochasten in kansruimte (Ω, F, P) bekijken en willen weten of die collectie uniform integreerbaar is. We geven eerst twee lemma’s waarvan we het bewijs achterwege laten Lemma 3.10. Stel X ∈ L1 (Ω, F, P). Dan is er voor alle F ∈ F en voor elke  > 0 een δ > 0, zodat als P(F ) < δ, dan E|X|1F < . Dit wil zeggen: als de kans op F kleiner wordt, dan wordt de verwachting van X gegeven gebeurtenis F ook kleiner. Lemma 3.11. Zij X een stochast, dan geldt X ∈ L1 (Ω, F, P) dan en slechts dan als lim E|X|1{|X|≥K} = 0.

K→∞

Definitie 3.12. Beschouw een collectie C van stochasten gedefinieerd op kansruimte (Ω, F, P). Deze collectie is uniform integreerbaar als lim sup{E|X|1{|X|>K} } = 0.

K→∞ X∈C

We geven nu twee voorbeelden van uniforme integreerbare collecties C. Voorbeeld 3.13. Beschouw C een collectie stochasten die begrensd is in Lp (Ω, F, P) R voor p > 1. Dan is er dus een M > 0 zodat E|X|p = Ω |X|p dP ≤ M, voor alle X ∈ C. Er geldt dan dat |X|p 1{|X|>K} |X|p−1 |X|p ≤ E p−1 1{|X|>K} K M ≤ p−1 . K

E|X|1{|X|>K} = E

Hieruit volgt dat C uniform integreerbaar is.

17

Voorbeeld 3.14. Zij Y een niet-negatieve stochast met EY < ∞ en C een collectie stochasten zodanig dat |X| ≤ Y b.z. voor alle X ∈ C. Omdat |X| ≤ Y b.z. geldt dat E|X|1{|X|>K} ≤ EY 1{Y >K} . Dus, lim sup{E|X|1{|X|>K} } ≤ EY 1{Y >K} .

K→∞ X∈C

Nu volgt uit Lemma 3.11 dat C uniform integreerbaar is. Gevolg 3.15. Er geldt (i) als C een eindige collectie stochasten is in L1 (Ω, F, P), dan is C uniform integreerbaar. (ii) de vereniging van twee uniform integreerbare collecties is uniform integreerbaar. Het belang van uniforme integreerbaarheid zien we in de volgende stelling waarbij het nodig is voor convergentie van een rij stochasten (Xn )n≥0 in L1 (Ω, F, P). Het bewijs hiervan wordt achterwege gelaten. Stelling 3.16. Laat (Xn )n≥0 een rij zijn in L1 (Ω, F, P) en X ∈ L1 (Ω, F, P). Dan L1

Xn −→ X (oftewel E|Xn − X| → 0) dan en slechts dan als P 1. Xn − → X, en 2. (Xn )n≥0 is uniform integreerbaar.

3.2.3. Limietstellingen We willen in de volgende paragraaf kijken naar convergentie van een rij van voorwaardelijke verwachtingen, maar daarvoor hebben we aantal limietstellingen nodig. In deze drie limietstellingen koppelen we het begrip convergentie aan integreerbaarheid. Het bewijs van de stellingen wordt achterwege gelaten. Stelling 3.17 (Monotone convergentiestelling). Beschouw een rij niet-negatieve stochasten (Xn )n≥0 gedefinieerd op (Ω, F, P), zodanig dat Xn+1 ≥ Xn b.z. voor alle n. Laat X = lim supn→∞ Xn . Dan geldt Z Z Xn dP ↑ X dP ≤ ∞. Ω

Ω

Lemma 3.18 (Fatou’s Lemma). Beschouw een willekeurige rij niet-negatieve stochasten (Xn )n≥0 gedefinieerd op (Ω, F, P). Dan geldt Z Z lim inf Xn dP ≥ (lim inf Xn ) dP. n→∞

Ω

Ω

n→∞

Als R er een niet-negatieve stochast Y is gedefinieerd op (Ω, F, P) zodat Xn ≤ Y a.e., en Y dP < ∞, dan geldt Ω Z Z lim sup Xn dP ≤ (lim sup Xn ) dP. n→∞

Ω

Ω

18

n→∞

Stelling 3.19 (Gedomineerde convergentiestelling). Beschouw een rij stochasten (Xn )n≥0 en de stochast X gedefinieerd op (Ω, F, P). Stel Xn (ω) → X(ω) voor alle ω die buiten een verzameling met kans nul zitten. Stel ook dat er een R niet-negatieve stochast Y is ook gedefineerd op (Ω, F, P), zodat supn |Xn | ≤ Y b.z. en Ω Y dP < ∞. Dan geldt Z |Xn − X| dP → 0, Ω

en dus

Z

Z Xn dP →

Ω

X dP. Ω

3.3. Convergentie van de voorwaardelijke verwachting Eigen versie van H8 van Peter Spreij’s Measure Theoretic Probability [2014]. Tot dusver hebben we gekeken naar de convergentie en uniforme integreerbaarheid van stochasten. Voor X ∈ L1 (Ω, F, P) en sub-σ-algebra G ∈ F zullen we nu kijken naar convergentie van de voorwaardelijke verwachting E(X|G) van X gegeven G. Stelling 3.20. De volgende eigenschappen gelden als we kijken naar de convergentie van de voorwaardelijke verwachting E(Xn |G) van Xn gegeven sub-σ-algebra G ∈ F. (i) Als (Xn )n≥0 een b.z. stijgende rij is van niet-negatieve stochasten, dan geldt hetzelfde voor de rij van voorwaardelijke verwachtingen (E(Xn |G))n≥0 . Als bovendien Xn ↑ X, dan ook E(Xn |G) ↑ E(X|G). (monotone convergentie van de voorwaardelijke verwachting) (ii) Als (Xn )n≥0 een rij b.z. niet-negatieve stochasten is met bijbehorende voorwaardelijke verwachtingen (E(Xn |G))n≥0 , dan geldt lim inf n→∞ E(Xn |G) ≥ E(lim inf n→∞ Xn |G) b.z.. (Fatou’s lemma voor de voorwaardelijke verwachting) (iii) Als (Xn )n≥0 een rij stochasten is zodat er voor een X geldt dat Xn → X b.z. en als er stochast Y is zodat EY < ∞ en |Xn | ≤ Y b.z. voor alle n. Dan geldt (E(Xn |G))n≥0 → E(X|G) b.z.. (gedomineerde convergentie voor voorwaardelijke verwachtingen) Bewijs. (i) Uit Gevolg 3.5 volgt dat de voorwaardelijke verwachtingen (E(Xn |G))n≥0 van X gegeven G ook een b.z. stijgende rij is. Laat E(X|G) := lim supn→∞ E(Xn |G), dan is E(X|G) G-meetbaar en E(Xn |G) ↑ E(X|G) b.z.. We moet nu alleen nog nagaan dat E(X|G) de voorwaardelijke verwachting is van X gegeven G. Uit Definitie 3.8 volgt dat voor alle G ∈ G geldt Z Z E(Xn 1G ) = Xn dP = E(Xn |G) dP = E(E(Xn |G)1G ). G

G

Passen we nu links en rechts de monotone convergentiestelling toe dan krijgen we dat E(X|G) de voorwaardelijke verwachting is van X gegeven G.

19

(ii) We gebruiken het bewijs van de gewone versie van Fatou’s lemma uit Spreij [8], maar passen het toe op voorwaardelijke verwachtingen. Definieer Yn = inf m≥n Xm . Voor alle m ≥ n is Yn ≤ Xm . Vanwege Gevolg 3.5 geldt nu E(Yn |G) ≤ E(Xm |G) voor alle m ≥ n en zelfs dat E(Yn |G) ≤ inf m≥n E(Xm |G). We gaan nu aan beide kanten van deze ongelijkheid de limiet nemen. Rechts krijgen we lim inf n→∞ E(Xn |G). De rij (Yn )n≥0 is stijgend en heeft limiet Y = lim inf n→∞ Xn . Vanwege Stelling 3.20 (i) krijgen we aan de linkerkant van de ongelijkheid nu dat E(Yn |G) ↑ E(Y |G) b.z.. Dus E(Y |G) ≤ lim inf n→∞ E(Xn |G). (iii) Bewijs gaat op een zelfde manier als (ii), maar dan passen we nu het bewijs van de gedomineerde convergentiestelling uit Spreij [8] toe op voorwaardelijke verwachtingen. Stelling 3.21. We geven nog een aantal eigenschappen van de voorwaardelijke verwachting waarvan we de eerste eigenschap zullen bewijzen. (i) Als H ⊂ G een sub-σ-algebra is van G, dan is de voorwaardelijke verwachting E(E(X|G)|H) van E(X|G) gegeven H gelijk aan de voorwaardelijke verwachting E(X|H) van X gegeven H. (tower property) (ii) Als Z G-meetbaar is zodanig dat ZX ∈ L1 (Ω, F, P), dan is E(ZX|G) = ZE(X|G). (iii) Voor sub-σ-algebra H ⊂ G geldt dat E(X) = E(X|H) als σ(X) en H onafhankelijk zijn van elkaar. Bewijs. (i) Beschouw voorwaardelijke verwachting E(E(X|G)|H) van E(X|G) gegeven H. Dan geldt er E1H [E(E(X|G)|H)] = E1H [E(X|G)] voor alle H ∈ H, zie Definitie 3.8. Maar, omdat H ⊂ G geldt dus ook dat E1H [E(X|G)] = E1H X. Dus E(E(X|G)|H) is de voorwaardelijke verwachting van E(X|H). We hebben in dit hoofdstuk gekeken naar de voorwaardelijke verwachting van stochasten en we hebben daar vele eigenschappen van bekeken en stellingen mee bewezen. Deze kennis hebben we nodig als we in het volgende hoofdstuk gaan kijken naar martingalen. Dit zijn dus rijen van stochasten waarvan de voorwaardelijke verwachting aan bepaalde eigenschappen voldoet. Martingalen en de stellingen die in het volgend hoofdstuk besproken worden spelen een cruciale rol in het bewijs van Conway’s algoritme van Li.

20

4. Martingalen Eigen versie van H9: §9.1 en §9.2 van Peter Spreij’s Measure Theoretic Probability [2014] en aantekeningen van Sonja Cox. We zullen in de eerste paragraaf van dit hoofdstuk martingalen defini¨eren om vervolgens in de volgende paragraaf van dit hoofdstuk te kijken naar gestopte martingalen, martingaaltransformaties en de stelling van Doob, waar we martingalen voor nodig hebben. Met name de stelling van Doob is een essentieel onderdeel van het bewijs van Conway’s algoritme.

4.1. Definitie martingaal Een martingaal is een stochastisch proces met bepaalde eigenschappen. Een stochastisch proces (of gewoon een proces, zoals we het vanaf nu zullen noemen) is een rij stochasten X0 , X1 , X2 , . . . gedefinieerd op kansruimte (Ω, F, P). We noteren deze rij stochasten (dit proces) als geheel met X. Dus X = (Xn )n≥0 . Voordat we een martingaal kunnen defini¨eren hebben we een filtratie F nodig. Een filtratie F is een rij sub-σ-algebras F = (Fn )n≥0 van F, waarbij voor elke n ≥ 0 geldt dat Fn ⊂ F en Fn ⊂ Fn+1 . De filtratie F is dus een rij steeds groter wordende sub-σ-algebras van F die in elkaar bevat zitten. Omdat een vereniging van σ-algebras in het algemeen geen σ-algebra hoeft te zijn defini¨eren we F∞ := σ(∪∞ n=0 Fn ). Dit is de kleinste σ-algebra die alle σ-algebras bevat, dus Fn ∈ F∞ voor alle n ≥ 0. Nu, als X = (Xn )n≥0 een proces is, dan defini¨eren we FnX := σ(X0 , . . . , Xn ), de kleinste σ−algebra die X0 , . . . , Xn bevat. Het is duidelijk dat FX := (FnX )n≥0 dan een filtratie is. Gegeven filtratie F kijken we vaak naar processen die F-aangepast zijn. Een proces Y = (Yn )n≥0 is F-aangepast (of aangepast voor F of gewoon aangepast) als voor alle n de de stochast Yn Fn -meetbaar is (dat wil zeggen: Yn ∈ Fn ). Als we filtratie F = FX hebben dan is proces X duidelijk FX −aangepast, omdat elke Xn ∈ FnX . Een filtratie kunnen we zien als een informatiestroom waarbij elke Fn de beschikbare informatie tot aan tijdstip n weergeeft. Voor F = FX komt de informatie uit proces X en op tijdstip n is de informatie die we hebben dat we weten wat de gebeurtenissen X0 , . . . , Xn zijn. Nu we dit allemaal weten kunnen we martingalen defini¨eren. Definitie 4.1. Een stochastisch proces X = (Xn )n≥0 noemen we een martingaal als het aangepast is voor filtratie F, als Xn ∈ L1 (Ω, F, P) voor alle n ≥ 0 en als E(Xn+1 |Fn ) = Xn .

21

(4.1)

We noemen deze laatste eigenschap, die geldig moet zijn voor alle n ≥ 0, ook wel de martingaaleigenschap van X. Wat (4.1) zegt is dat we verwachten dat er in een rij stochasten X telkens niks veranderd. We verwachten dat stochast Xn+1 gelijk is aan Xn als we Fn weten. Bovendien geldt, hoewel we de martingalen hebben gedefinieerd in termen van voorwaardelijke verwachtingen die ´e´en stap vooruit kijken, iets soortgelijks voor martingalen waarbij we meer dan ´e´en stap vooruit kijken. Zo zien we als we in (4.1) de term Xn+1 vervangen door Xn+2 dat: E(Xn+2 |Fn ) = E(E(Xn+2 |Fn+1 )|Fn ) = E(Xn+1 |Fn ) = Xn . Waarbij de eerste gelijheid geldt vanwege de tower property (omdat Fn ⊂ Fn+1 , zie Stelling 3.21 (i)) en waarbij we bij de tweede en derde gelijkheid tweemaal de martingaaleigenschap toepassen. Analoog geldt voor Xn+3 vanwege de tower property en omdat Fn ⊂ Fn+2 dat: E(Xn+3 |Fn ) = E(E(Xn+3 |Fn+2 )|Fn ) = E(Xn+2 |Fn ) = Xn . Dus in het algemeen geldt voor alle n ≥ 0 en m ≥ n + 1 E(Xm |Fn ) = Xn . Ook zien we dat uit (4.1), uit Gevolg 3.6 en uit het bovenstaande volgt dat de voorwaardelijke verwachting van een martingaal X = (Xn )n≥0 is voor alle n gelijk aan de verwachting van X0 . Er geldt namelijk dat: Z E(Xn+1 |Fn ) = E(Xn+1 ). E(Xn ) = E(E(Xn+1 |Fn )) = Ω

Dus krijgen we uiteindelijk dat voor alle n ≥ 0 geldt dat: E(X0 ) = E(Xn ). We geven nu twee voorbeelden van martingalen. Voorbeeld 4.2. Zij X een proces bestaande uit onafhankelijke P stochasten XP n, n ≥ 1 en stel dat Xn ∈ L1 (Ω, F, P) voor alle n. Stel X0 = 0 en Sn = nk=0 Xk = kn=1 Xk . Neem F = FX . Dan is S aangepast voor F en Sn ∈ L1 (Ω, F, P) voor alle n. We willen kijken of S een martingaal is en moeten dus nagaan wanneer de martingaaleigenschap geldt. We bekijken de voorwaardelijke verwachting van Sn+1 en zien E(Sn+1 |FnX ) = E(Sn + Xn+1 |FnX ) = E(Sn |FnX ) + E(Xn+1 |FnX ) = Sn + E(Xn+1 ). Waarbij de laatste stap geldt vanwege Stelling 3.21 (iii). Dus S is een martingaal (voldoet aan de martingaaleigenschap) als E(Xn ) = 0 voor alle n.

22

Voorbeeld 4.3. Zij X een stochast met E|X| < ∞ en zij F een filtratie. Definieer Mn = E(X|Fn ), n ≥ 0. Vanwege de tower property geldt E(Mn+1 |Fn ) = E(E(X|Fn+1 )|Fn ) = E(X|Fn ) = Mn . Dus het proces M is een martingaal.

4.2. Sub- en supermartingalen Behalve naar martingalen kijken we ook naar sub- en supermartingalen en naar martingalen die gebaseerd zijn op een ander proces. Namelijk het proces ∆X. Definitie 4.4. Een stochastisch proces X = (Xn )n≥0 heet een submartingaal (of Fsubmartingaal), als het aangepast is voor filtratie F, als Xn ∈ L1 (Ω, F, P) voor alle n ≥ 0 en als E(Xn+1 |Fn ) ≥ Xn . (4.2) Analoog is een stochastisch proces X = (Xn )n≥0 een supermartingaal als onder dezelfde voorwaarden geldt dat E(Xn+1 |Fn ) ≤ Xn . (4.3) Hoe we hier naar moeten kijken is dat we een submartingaal kunnen zien als een steeds toenemende ‘trend’. Bij een martingaal verwachten we dat er niks veranderd, maar bij een submartingaal verwachten we een toename. Analoog voor een supermartingaal een afname. Voorbeeld 4.5. We bekijken nu nogmaals Voorbeeld 4.2 voor sub- en supermartingalen. Het proces S in Voorbeeld 4.2 is een submartingaal als Xn een positieve verwachting heeft voor alle n ≥ 0. Analoog is S een supermartingaal als Xn voor alle n ≥ 0 een negatieve verwachting heeft. Laten we nu kijken naar een ander proces dan X, namelijk het proces ∆X waarbij we kijken naar de verschillen tussen twee opeenvolgende stochaten. Definitie 4.6. Als X een proces is dan definieren we het proces ∆X door ∆Xn = Xn − Xn−1 , n ≥ 1. P We zien dan vervolgens dat Xn =PX0 + nk=1 ∆Xk . Of als we ∆X0 definieren als ∆X0 := X0 dan zeggen we ook wel Xn = nk=0 ∆Xk . De martingaaleigenschap van een aangepast (voor filtratie F) L1 -integreerbaar proces X is dan E(∆Xn+1 |Fn ) = 0, voor n ≥ 0. Voor submartingalen geldt dan voor n ≥ 0 dat E(∆Xn+1 |Fn ) ≥ 0. Stel nu dat de stochast Pn ξn de uitbetaling weergeeft van de n-de keer dat je een spel speelt. Dan is Sn = k=1 ξk je totale opbrengst na n keer spelen. We hebben dan ∆Sn = ξn . Als S een martingaal is, dan speel je een eerlijk spel en als S een submartingaal is dan speel je een spel waarbij je waarschijnlijk winst maakt. We zullen hiermee in de volgende paragraaf aantonen dat je, als een spel oneerlijk is, ongeacht alle informatie en voorkennis die je hebt altijd verwacht geld te verliezen.

23

4.3. Martingaaltransformaties en stoptijden Als iemand op tijdstip n − 1 weet wat de uitkomst wordt van een willekeurig experiment op tijdstip n, dan kan hij deze uitkomst correct voorspellen. Dit is wat we bedoelen met een voorspelbaar proces. Definitie 4.7. Gegeven een filtratie F, is een proces Y = (Yn )n≥1 F-voorspelbaar (of gewoon voorspelbaar ) als Yn ∈ Fn−1 . Hierbij doen we de aanname dat Y0 = 0. Een voorspelbaar proces Y kan je zien als een strategie: het zegt wat je op tijdstip n moet doen gegeven de informatie van tijdstip n − 1. Stel dat een rij stochasten ξn (met ξ0 = 0) de uitbetaling van een spel op tijdstip n weergeeft voor alle n ≥ 0 als je ´e´en unit (hiermee bedoelen we bijvoorbeeld geld of een fiche) inzet. Yn Xn is dan de uitbetaling als je Yn units inzit op tijdstip n. Het aantal units Yn dat je inzet op tijdstip n kan afhangen van wat je uitbetaling was voor tijdstip n. Oftewel, van ξm met m < n.PHierom is het proces Y dus Fξ −voorspelbaar. = nk=1 Yk ξk (met Pn Je totale winst op tijdstip n is Sn P n S0 = 0). Definieer nu XP n = k=1 ξk , dan is ∆Sn = Yn ∆Xn en Sn = k=1 Yk ∆Xk . n Merk op dat Sn = k=1 Yk ∆Xk de discrete variant is van de (continue) integraal Rt St = 0 Ys dXs , die we een stochastische integraal noemen. Als X een martingaal is dan noemen we de discrete variant S = (Sn )n≥0 een discrete stochastische integraal. Zo’n proces S heet ook wel een martingaaltransformatie en dit noteren we met S = Y · X. We geven twee eigenschappen van martingaaltransformaties. Lemma 4.8. Zij X een aangepast proces en Y een voorspelbaar proces. Neem aan dat voor alle n zowel Xn als Yn ∆Xn elementen zijn van L1 (Ω, F, P) en stel dat S = Y · X een martingaaltransformatie is. Dan geldt (i) Als X een martingaal is, dan is ook S een martingaal. (ii) Als X een submartingaal (supermartingaal) is en Y is niet-negatief, dan is S ook een submartingaal (supermartingaal). Bewijs. Omdat voor alle n de stochast Xn ∈ Fn en Fn−1 ⊂ Fn zit dus ook ∆X ∈ Fn . En, omdat voor alle n de stochast Yn ∈ Fn−1 en Fn−1 ⊂ Fn zit ook Yn ∈ Fn . Dus voor alle n geldt Sn ∈ Fn en dus is S aangepast. Gegeven is dat voor alle n geldt dat Yn ∆Xn ∈ L1 (Ω, F, P). Dus we moeten alleen nog de martingaaleigenschap controleren. Vanwege Stelling 3.21 (ii) geldt dat E(∆Sn |Fn−1 ) = Yn E(∆Xn |Fn−1 ) = 0. Dus, analoog aan Definitie 4.6, is S een martingaal. Op dezelfde wijze is ook S een submartingaal (supermartingaal) als X een submartingaal (supermartingaal) is en Y niet-negatief is. Wat betekent dit lemma nu als we een spel spelen waarbij we geld inzetten? Als P je een ongunstig spel speelt dan is het proces X, waarbij voor alle n geldt dat Xn = nk=1 ξk , (je totale uitbetaling op tijdstip n) een supermartingaal. Een (voorspelbare) strategie Y waarbij elke Yn weergeeft hoeveel je het beste in kan zetten op tijdstip n, gegeven wat er tot tijdstip n − 1 is gebeurd, is niet-negatief. Dus uit Lemma 4.8 volgt dat het proces S = Y ·X dat je totale winst weergeeft, ongeacht je strategie Y ook een supermartingaal, oftewel een ongunstig spel, is. Je verwacht dus altijd geld te verliezen. Dit is wat we

24

willen omzeilen met Conway’s algoritme. We hebben nu bijna alle voorkennis die we nodig hebben voor het bewijs. We moeten alleen nog kijken naar stoptijden en daarna de stelling dan Doob bewijzen.. Definitie 4.9. Zij F een filtratie. een afbeelding T : Ω → N heet een stoptijd als voor alle n ∈ N geldt {T = n} ∈ Fn . Opmerking. T is een stoptijd dan en slechts dan als voor Sn alle n geldt dat {T ≤ n} ∈ Fn . Immers, stel T is een stoptijd. Dan geldt {T ≤ n} = k=0 {T = k} ∈ Fn . en de andere kant op geldt vanwege {T = n} = {T ≤ n}\{T ≤ n − 1}. Maar wat betekent een stoptijd precies? Stel dat je aan het wedden bent en wilt stoppen als je minimaal 1000 euro hebt verdiend. Als S weer het proces is dat je winst weergeeft stop je met spelen op tijdstip T , waarbij T = inf{n ≥ 0 : Sn ≥ 1000}. Deze T is dus de stoptijd en hangt alleen af van wat er tot tijdstip T gebeurd is. Dus de gebeurtenis {T = n} ∈ Fn . In het volgende lemma zullen we zien dat T een stoptijd is als X een aangepast proces is. Lemma 4.10. Zij F een filtratie en X een aangepast proces. Stel B ∈ B is een Borel set in R en stel T = inf{n ≥ 0 : Xn ∈ B}, dat wil zeggen: we stoppen op het eerste moment n waarop Xn ∈ B. Dan is T een stoptijd. S Bewijs. We kunnen {T ≤ n} schrijven als nk=0 {Xk ∈ B}. Omdat X aangepast is geldt voor elke k dat {Xk ∈ B} ∈ Fk ⊂ Fn . Dus {T ≤ n} ∈ Fn en T is een stoptijd. Definitie 4.11. We bekijken nu stoptijd T en n ∈ {0, 1, 2, . . .}. We defini¨eren Tn (ω) := T (ω) ∧ n. Het minimum van stoptijd T (ω) en n voor alle ω ∈ Ω. Vaak schrijven we ook wel Tn = T ∧ n. De functie Tn is ook een stoptijd. We gaan gevallen onderscheiden om dit aan te tonen. Voor k < n geldt {Tn ≤ k} = {T ≤ k} ∈ Fk , want T is een stoptijd. Voor k ≥ n geldt dat {Tn ≤ k} = Ω, omdat n dus altijd kleiner gelijk is aan k. We weten dat voor alle n geldt dat Ω ∈ Fn , dus Tn is een stoptijd. Definitie 4.12. Als X een aangepast proces is en T een stoptijd, dan defini¨eren we het gestopte proces X T met XnT (ω) := XT (ω)∧n (ω), waarbij n ≥ 0. Merk op dat X0T = X0 , want het minimum van T (ω) en 0 is 0. En als T (ω) ≤ n, dan geldt XnT (ω) = XT (ω) (ω), oftewel XnT = XT voor {T ≤ n}. Lemma 4.13. Er geldt het volgende (i) Als X een aangepast proces is en T een stoptijd, dan is X T ook aangepast. (ii) Als X een supermartingaal is, dan is X T dat ook en dan is EXnT ≤ EX0 . (iii) Als X een martingaal is, dan is X T dat ook en dan is EXnT = EX0 . hoi hoi hoi

25

Bewijs. hoi (i) Stel X is een aangepast proces. We hebben gezien dat voor {T ≤ n} geldt XnT = T X nu XnT schrijven als XnT = PTn en voor {T > n} is Xn = Xn . Dus we kunnen T T is k=0 Xk 1{T =k} + Xn 1{T >n} . We zien nu dat Xn ∈ Fn voor alle n. Dus X aangepast. (ii) We defini¨eren nu het proces Yn = 1T ≥n met n ≥ 1. Merk op dat {Yn = 0} = {1T ≥n = 0} = {T ≤ n − 1} ∈ Fn−1 . Dus Y is voorspelbaar. We bekijken nu ∆XkT T ∆XkT = XkT − Xk−1

=

k X

Xj 1{T =j} + Xk 1{T >k} −

j=0

k−1 X

Xj 1{T =j} + Xk−1 1{T >k−1}

(vanwege (i))

j=0

= 1{T =k} Xk + 1{T >k} Xk − 1{T >k−1} Xk−1 = 1{T ≥k} Xk − 1{T >k−1} Xk−1 = 1{T ≥k} (Xk − Xk−1 ) = Yk ∆Xk P Dus X T = X0 + nk=1 Yk ∆Xk = X0 + Y · X. Nu volgt (ii) uit Lemma 4.8. (iii) Ook dit volgt analoog aan (ii) nu uit Lemma 4.8.

4.4. De stelling van Doob Nu we dit allemaal hebben gedefinieerd en bewezen kunnen we dit voor de stelling van Doob. Als we deze stelling hebben bewezen hebben we alle voorkennis die we nodig hebben en dan kunnen we in het volgende hoofdstuk Conway’s algoritme gaan bewijzen. Stelling 4.14 (Stelling van Doob). Zij (Ω, F, P) een kansruimte, F een filtratie, X een F-aangepaste martingaal en T een stoptijd. Neem bovendien aan dat T b.z. eindig is, P(T < ∞) = 1, dat EXT < ∞ en dat Z |Xk | dP = 0. lim k→∞

{T
Dan geldt: EXT = EX0 . Bewijs. Omdat X een martingaal is volgt uit Lemma 4.13 dat EXT ∧k = EX0 voor alle k ∈ N. Er geldt dus: |EXT − EX0 | = |E(XT ∧k + (XT − Xk )1{T >k} ) − EX0 | = |E((XT − Xk )1{T >k} )| ≤ E(|XT |1{T >k} ) + E(|Xk |1{T >k} ). Nu volgt uit Lemma 3.10 dat limk→∞ E(|XT |1{T >k} ) = 0. En limk→∞ E(|Xk |1{T >k} ) = 0, want dat hebben we aangenomen. Dus, EXT = EX0 .

26

5. Bewijs van Conway’s algoritme Dit hoofdstuk en het bewijs van Conway’s algoritme is gebaseerd op het artikel A Martingale Approach to the Study of Occurence of Sequence Patterns in Repeated Experiments van Li [3]. Nu we alles over martingalen, voorwaardelijke verwachtingen et cetera weten, kunnen we eindelijk beginnen aan het bewijs van Conway’s algoritme. Wat we dus willen bewijzen is: waarom is de verhouding waarmee een strategie van B, speler twee, eerder voorkomt als we herhaaldelijke een munt opgooien dan een strategie van A, speler ´e´en, gelijk aan (AA − AB) : (BB − BA)? Hierbij is AA het kengetal behorende bij het paar AA zoals beschreven staat in Hoofdstuk 2. Li [3] heeft dit bewezen in zijn artikel A Martingale Approach to the Study of Occurence of Sequence Patterns in Repeated Experiments en dat bewijs zullen we in dit hoofdstuk ook (zij het wat uitgebreider) gebruiken. Het bestaat uit een aantal stellingen waaruit het bewijs van Conway’s algoritme volgt. We zullen eerst een aantal definities en notaties geven voordat we aan het bewijs beginnen.

5.1. Terminologie voor het bewijs Zij Z een discrete stochast die zijn waarden aanneemt in Σ = {a1 , . . . , an } en kansverdeling {p1 , . . . , pn } heeft. Hierbij is pj = P(Z = aj ), met 1 ≤ j ≤ n. Beschouw nu de rij Z1 , Z2 , . . . van i.i.d. stochasten die allemaal dezelfde verdeling hebben als Z. Definitie 5.1. Als B = (b1 , . . . , bn ) een eindige sequentie is die zijn waarden aanneemt in Σ. Dan noemen we NB de tijd die we moeten wachten tot B een samenhangende deelverzameling is van het proces Z1 , Z2 , . . .. Het is duidelijk dat NB een stoptijd is. Definitie 5.2. Stel nu dat we al weten dat we beginnen met een bepaalde eindige sequentie A = (a1 , a2 , . . . , am ) die zijn waarden aanneemt in Σ. Het proces ziet er dan dus alsvolgt uit: a1 , a2 , . . . , am , Z1 , Z2 , . . .. En stel dat de eindige sequentie B geen samenhangende deelrij is van (a1 , a2 , . . . , am−1 ). Dan defini¨eren we NAB als de tijd (of, zoals we later zullen zien, het aantal keer dat we een munt opgooien) tot we rij B hebben krijgen in het proces a1 , a2 , . . . , am , Z1 , Z2 , . . . als we met rij A begonnen zijn. Hierbij nemen we aan dat B geen samenhangende deelverzameling (oftewel geen aangesloten deelrij) is van A. Iets meer wiskundig gedefinieerd krijgen we: NAB = min{k|B is een samenhangende deelverzameling van (a1 , . . . , am , Z1 , . . . , Zk )}. Merk op: we beginnen dus pas met tellen n´a sequentie A. Ook is NAB gelijk aan NB als A = ∅. Bovendien is ook deze NAB een stoptijd. Immers, stel dat Fk = σ(Z1 , . . . , Zk ).

27

Dan geldt {NAB > k} ∈ Fk en dus ook dat {NAB ≤ k} ∈ Fk . Dus NAB is een stoptijd. We zullen een illustratie geven van wat deze stoptijd NAB nu precies is aan de hand van twee voorbeelden. Voorbeeld 5.3. Stel dat we herhaaldelijk een munt opgooien. Dan stelt Z een munt voor die we opgooien. Z neemt zijn waarden dus aan in Σ = {H, T }. Hierbij is H =‘Heads’ (kop) en T =‘Tails’ (munt). We hebben dan natuurlijk kansverdeling P(Z = H) = P(Z = T ) = 1/2 . Het proces Z1 , Z2 , . . . staat dus voor de uitkomsten van de munt die we herhaaldelijk achter elkaar opgooien. Stel we hebben sequenties A = (a1 , a2 , a3 ) = (H, T, H) en B = (b1 , b2 , b3 , b4 ) = (T, H, H, T ) en we willen weten hoe lang het duurt tot we B krijgen in het proces a1 , a2 , a3 , Z1 , Z2 , . . .. Oftewel we zijn benieuwd naar NAB = min{k|B is een samenhangende deelrij van (a1 , a2 , a3 , Z1 , . . . , Zk )}. Als we nu herhaaldelijk een ‘munt opgooien’ en als we als eerste acht uitkomsten van het proces Z1 , Z2 , . . . het volgende krijgen: Z1 , . . . , Z8 = H, H, T, T, H, H, T, H. Dan is dus de stoptijd NAB , oftewel het aantal keer dat we moeten gooien zodat B = (T, H, H, T ) een samenhangende deelrij is van (H, T, H, H, H, T, T, H, H, T, H), gelijk aan 7. Immers, als we 7 keer hebben gegooid dan hebben we (H, T, H, H, H, T, T, H, H, T) en daarin is B een samenhangende deelrij. Voorbeeld 5.4. Stel nu dat we weer hebben dat A = (H, T, H) en B = (T, H, H, T ), maar dat we een andere uitkomst krijgen in het proces Z1 , Z2 , . . .. Namelijk dat deze eerste twee uitkomsten hebben: Z1 , Z2 = H, T. Dan is dus de stoptijd NAB , oftewel het aantal keer dat we moeten gooien zodat B = (T, H, H, T ) een deelrij is van (H, T, H, H, T ), gelijk aan 2. Omdat de laatste twee waarden van A gelijk zijn aan de eerste twee van B en we toevallig de eerste keer H en de tweede keer T gooien, krijgen we al na 2 keer gooien dat B = (T, H, H, T ) een deelrij is van (H, T, H, H, T ). In het bovenstaande voorbeeld zien we dat de verwachte stoptijd NAB als we beginnen met A niet alleen afhangt van sequentie B maar dus ook van de sequentie A. Dit idee is belangrijk voor het bewijs van Conway’s algoritme. We hebben dus nu de stoptijd NAB tot B als we beginnen met A gedefinieerd, maar we weten normaal niet wat dit is, omdat Z1 , Z2 , . . . een stochastisch proces is. Daarom zijn we meer ge¨ınteresseerd in de verwachte stoptijd. Hier kunnen we uitspraken over doen en dit is daarom ook waar we in de volgende paragraaf mee werken. Voordat we dat kunnen doen moeten we kijken naar twee dingen. We zullen nog nog een definitie geven die we nodig hebben als we gaan bepalen en bewijzen hoe groot de verwachte stoptijd precies is. En daarna zullen we nog bewijzen dat de verwachte stoptijd, ongeacht de sequentie die we bekijken, eindig is. Definitie 5.5. Zij A = (a1 , a2 , . . . , am ) en B = (b1 , b2 , . . . , bn ) twee sequenties die allebei hun waarden aannemen in Σ. We schrijven voor alle paren (i, j) met 1 ≤ i ≤ max{n, m} en 1 ≤ j ≤ max{n, m}: ( P(Z = bj )−1 als ai = bj δij = 0 anders.

28

Vervolgens defini¨eren we: A ∗ B = δ11 δ22 · · · δmm + δ21 δ32 · · · δm,m−1 + δ31 δ42 . . . δm,m−2 + · · · + δm−1,1 δm,2 + δm1 . Opmerking. Bij de groep ‘anders’ horen niet alleen de ai en bj waarbij ai 6= bj . Als bijvoorbeeld m > n dan geldt dat δmm = 0, omdat bm niet gedefini¨eerd is en dus ook niet geldt dat am = bm . Oftewel als voor het paar (i, j) geldt dat ai wel gedefini¨eerd is, maar bj niet (of andersom) dan is δij = 0. We geven een voorbeeld om te illustreren hoe je A ∗ B nou precies bepaald. Voorbeeld 5.6. Stel dat Σ = {H, T }, A = (T, T, H, T ) en B = (T, H, H). We zien dat a1 = b1 = H en dus ook dat a2 = b1 en a4 = b1 . Verder is a3 = b2 en a3 = b3 . Dus δ11 = δ21 = δ41 = δ32 = δ33 = 2. Als ai = bj dan is δij = 2, omdat P (Z = bj ) = 21 voor alle j. Dit, omdat bj ∈ {H, T } en de kans op H is gelijk aan de kans op T . Deze kans is namelijk 12 . Voor alle overige (i, j) geldt δij = 0. We gaan nu A ∗ B bepalen: A ∗ B = δ11 δ22 δ33 δ44 + δ21 δ32 δ43 + δ31 δ42 + δ41 =2·0·2·0+2·2·0+0·0+2 = 2. Nu we dit hebben gedefinieerd bewijzen we nog dat de verwachte stoptijd ongeacht de sequentie eindig is. Stelling 5.7. Gegeven sequentie B = (b1 , . . . , bn ) die zijn waarden aanneemt in Σ. Voor de verwachte stoptijd ENB totdat B voorkomt in het proces Z1 , Z2 , . . . geldt dat ENB < ∞. P eren Bewijs. Zij B = (b1 , . . . , bn ), dan geldt dat ENB = ∞ k=1 kP(NB = k). We defini¨ ˜B := min{k : (Znk+1 , Znk+2 , . . . , Znk+n ) = B}. N ˜B dus het proces Z1 , Z2 , . . . in stappen van lengte n (de lengte van B) We bekijken bij N en stoppen pas als een van deze stappen van lengte n gelijk is aan de sequentie B. Merk ˜B . Vervolgens defini¨eren we op dat er geldt dat NB ≤ nN ˜B = 1) = P(Z1 = b1 ) · P(Z2 = b2 ) · · · P(Zn = bn ). p := P(N ˜B = k) = P(N ˜B = 1) = p geldt er dat Omdat voor elke k ≥ 1 geldt dat P(N ˜B = EN

∞ X

˜B = k) kP(N

k=1

= =

∞ X

k(1 − p)k−1 p

k=1 ∞ X

1 p

k(1 − p)k−1 .

k=1

29

Omdat p < 1 zien we dat ∞ X

k(1 − p)k−1 =

k=1

∞ X (1 − p)k

!0

k=0

1 0 ) 1−p 1 = . (1 − p)2 =(

Dus hieruit volgt dat ˜B = EN

1 < ∞. p(1 − p)2

˜B geldt dus ook dat ENB < ∞. Nu, omdat NB ≤ nN Opmerking. De claim in het bewijs dat kans p 6= 1 is realistisch om te maken. Het proces Z1 , Z2 , . . . stelt in deze scriptie immers een munt voor die herhaaldelijk wordt opgegooid. De kans op ‘kop’ en de kans op ‘munt’ is steeds 12 dus de kans dat je in ´e´en keer bijvoorbeeld kop-kop-kop gooit is niet gelijk aan 1 Hiermee hebben we alle terminologie geintroduceerd waardoor we nu eindelijk aan het bewijs van Conway’s algoritme kunnen beginnen!

5.2. Bewijs van Conway’s algoritme We zullen in deze paragraaf het bewijs geven van Conway’s algoritme. Wat dus willen aantonen is dat gegeven strategie A = (a1 , a2 , . . . , am ) van speler ´e´en (speler A) en strategie B = (b1 , b2 , . . . , bm ) van speler twee (speler B) de verhouding waarmee de strategie van B eerder voorkomt dan de strategie van A als we herhaaldelijk een munt opgooien gelijk is aan (AA − AB) : (BB − BA). Hierbij zijn AA, AB, BB en BA de kengetallen die we construeren met Conway’s algoritme. Het bewijs is opgebouwd uit een aantal stellingen van Li [3] waaruit het bewijs van Conway’s algoritme volgt. In deze stellingen gebruiken we de definities uit de vorige paragraaf en de voorkennis uit de vorige hoofdstukken. We zullen het bewijs in drie delen geven.

5.2.1. Verwachte stoptijd voor sequentie B na A Stelling 5.8 (Li). Gegeven beginsequentie A = (a1 , a2 , . . . , am ) is de verwachte tijd nodig tot sequentie B = (b1 , b2 , . . . , bn ) voorkomt in het proces Z1 , Z2 , . . . gelijk aan ENAB = B ∗ B − A ∗ B. Hierbij nemen we aan dat B geen samenhangende deelrij is van A. In het bijzonder is de wachttijd tot een sequentie B voorkomt ENB = B ∗ B (dit is dus in de situatie waarin we geen beginsequentie A hebben).

30

Bewijs. Zij A = (a1 , a2 , . . . , am ) en B = (b1 , b2 , . . . , bn ). We defini¨eren voor k ≥ 0 de rij ωk = (Z1 , . . . , Zk ) waarbij elke Zi , i = 1, . . . , n, een stochast is die zijn waarden aanneemt in de verzameling Σ. We zeggen dat ω0 = ∅. We zullen eerst de volgende stochast gebruiken en willen uiteindelijk de stelling van Doob (Stelling 4.14) gebruiken voor deze stochast: Xk = Aωk ∗ B − k, waarbij Aωk de rij A gevolgd door ωk is: Aωk = (a1 , a2 , . . . , am , Z1 , . . . , Zk ). We willen laten zien dat het proces {Xk∧NAB }k≥0 een martingaal is. Om dit te doen defini¨eren we eerst voor k ≥ 0 en j ≥ 1 − m,  0 als k < j       als de laatste k − j + 1  1 (j) − 1 termen van de rij Aωk Mk = P(Z = b1 ) · · · P(Z = bk−j+1 )   gelijk zijn aan b1 , . . . , bk−j+1      -1 anders. (j)

We zullen aantonen dat voor elke vaste j het proces {Mk∧NAB }k≥0 een martingaal is en daaruit zullen we afleiden dat ook {Xk∧NAB }k≥0 een martingaal is. Merk op dat (j) uit Lemma 4.13 volgt dat het volstaat om aan te tonen dat {Mk }k≥0 en {Xk }k≥0 (j) martingalen zijn. We nemen filtratie Fk = σ(Z1 , . . . , Zk ). Merk hierbij op dat Mk Fk −meetbaar is. We willen nu de martingaaleigenschap nagaan: (j)

(j)

E(Mk |σ(Z1 , . . . , Zk−1 )) = Mk−1 . Voor alle A ∈ Fk−1 geldt: Z

(j) Mk

Z dP =

A

(j)

Mk−1 dP.

(5.1)

A

Het is daarom voldoende om A van de vorm A = {(Z1 , . . . , Zk−1 ) = (z1 , . . . , zk−1 )} te bekijken, waarbij zj ∈ Σ voor j = 1, . . . , k − 1, en te onderzoeken of voor alle k ≥ 1 de gelijkheid 5.1 voor deze A geldt. Als we dit gedaan hebben volgt uit Lemma 3.3 de martingaaleigenschap. Dus stel vanaf nu dat A = {(Z1 , . . . , Zk−1 ) = (z1 , . . . , zk−1 )} en (j) laten we nu nog eens kijken naar Mk−1 :  0 als k − 1 < j     1 (j) − 1 als (Zk−j , . . . , Zk−1 ) = (b1 , . . . , bk−j ) Mk−1 = P(Z = b1 ) · · · P(Z = bk−j )     −1 anders. (j)

We gaan voor alle drie de mogelijke waarden van Mk−1 controleren of de gelijkheid 5.1 voor alle k ≥ 1 geldt:

31

(j)

(i) Stel k − 1 < j dan geldt dat Mk−1 = 0. Als dan voor k ook geldt dat k < j dan is (j) Mk = 0. En dus geldt er dat Z Z 0 dP = 0 dP. A

A

Oftewel, we hebben gelijkheid 5.1. Stel nu dat k = j, dan geldt:  1  − 1 als Zk = b1 (j) P(Z = b1 ) Mk =  −1 anders. We zien nu dat er geldt dat   Z (j) Mk dP = P(A) · P(Zk = b1 ) · A

  1 − 1 + P(Zk 6= b1 ) · −1 P(Z = b1 )

= 0.

(j)

Merk op dat dit voor alle k > j analoog gaat. Dus als Mk−1 = 0 dan klopt gelijkheid 5.1. (ii) Stel dat k − 1 ≥ j en dat (Zk−j , . . . , Zk−1 ) = (b1 , . . . , bk−j ). Dan hebben we (j)

Mk−1 =

1 − 1. P(Z = b1 ) · · · P(Z = bk−j )

(j)

Voor Mk geldt dan dat  1  − 1 als Zk = bk−j+1 (j) P(Z = b1 ) · · · P(Z = bk−j )P(Z = bk−j+1 ) Mk =  −1 anders. Nu zien we dat  Z (j) Mk dP = P(A) · P(Zk = bk−j+1 ) · A

 1 −1 P(Z = b1 ) · · · P(Z = bk−j+1 ) hoi + P(A) · P(Zk 6= bk−j+1 ) · −1   1 = P(A) · −1 P(Z = b1 ) · · · P(Z = bk−j ) Z (j) = Mk−1 dP. A

Dit is wederom gelijkheid 5.1.

32

(j)

(iii) Stel tenslotte dat Mk−1 = −1. Dan geldt dus dat k−1 ≥ j en dat (Zk−j , . . . , Zk−1 ) 6= (j) (b1 , . . . , bk−j ). Dan geldt dus voor Mk dat k > j, maar (Zk−j , . . . , Zk ) kan dan niet gelijk zijn aan (b1 , . . . , bk−j+1 ), omdat (Zk−j , . . . , Zk−1 ) 6= (b1 , . . . , bk−j ). Dus (j) ook Mk = −1. En dus geldt Z Z −1 dP = −1 dP. A

A

Oftewel, we hebben weer gelijkheid 5.1. Hiermee hebben we dus aangetoond dat gelijkheid 5.1 voor alle k ≥ 1 geldt. Uit Lemma 3.3 volgt nu dus dat (j)

(j)

E(Mk |σ(Z1 , . . . , Zk−1 )) = Mk−1 . (j)

Dus {Mk∧NAB }k≥0 is een martingaal. P (j) We willen nu laten zien dat { ∞ j=1−m Mk }k≥0 een martingaal is. Neem hierbij filtratie (j)

Fk = σ(Mi : 1 ≤ i < k, j ≥ 1 − m). Omdat we weten dat voor alle j ≥ 1 − m het (j) proces {Mk }k≥0 een martingaal is volgt er direct dat ! ∞ ∞ X X (j) (j) E E(Mk+1 |Fk ) Mk+1 Fk = j=1−m

=

j=1−m ∞ X

(j)

E(Mk ).

j=1−m

P (j) Dus { ∞ j=1−m Mk }k≥0 is een martingaal. Nu kunnen we deze martingaal omschrijven tot ∞ k X X (j) (j) Mk = Mk = Aωk ∗ B − k − m = Xk − m. j=1−m

j=1−m

P∞

P (j) (j) Maar, omdat { j=1−m Mk }k≥0 een martingaal is, is { ∞ j=1−m Mk +m}k≥0 = {Xk }k≥0 met m ∈ N ook een martingaal. Hieruit volgt dus dat {Xk∧NAB }k≥0 ook een martingaal is. Deze eigenschap hebben we nodig als we hieronder de stelling van Doob (Stelling 4.14) willen gebruiken. Laten we nu kijken naar het gestopte proces XNAB . We kunnen dit omschrijven tot XNAB = AωNAB ∗ B − NAB = B ∗ B − NAB . In Stelling 5.7 hebben we gezien dat voor elke sequentie B geldt dat ENB < ∞. Omdat ENAB ≤ ENB geldt dus ook dat ENAB < ∞. Hieruit volgt dat E|XNAB | = E|B ∗ B − NAB | ≤ B ∗ B + ENAB < ∞.

33

Op de verzameling {NAB > k} krijgen we vervolgens |Xk | = |Aωk ∗ B − k| ≤ Aωk ∗ B + k ≤ Aωk ∗ B + NAB ≤ B ∗ B + NAB . Hierbij krijgen we de laatste ongelijkheid, omdat het aantal keer dat je moet gooien om B te krijgen als je begint met A alleen maar minder of even groot kan zijn als het aantal keer dat je in totaal moet gooien om B te krijgen. Een stuk van het begin van de sequentie B kan immers voorkomen aan het eind van de sequentie A. Hierdoor zien we dat Z Z lim |Xk | dP ≤ lim (B ∗ B + NAB ) dP = 0. k→∞

{NAB >k}

k→∞

{NAB >k}

Waarbij de laatste gelijkheid geldt vanwege Lemma 3.11 en omdat B ∗ B een constante is. Dan krijgen we namelijk dat Z B ∗ B dP = B ∗ B · lim P(NAB > k) = 0. k→∞

{NAB >k}

Dus, omdat voor R k ≤ NAB {Xk∧NAB }k≥0 een martingaal is, omdat E|XNAB | < ∞ en omdat limk→∞ {NAB >k} |Xk | dP = 0 mogen we nu de stelling van Doob (Stelling 4.14) gebruiken. We zien dus dat EXNAB = EX0 = A ∗ B. Dus, omdat NAB = B ∗ B − XNAB , geldt dat ENAB = B ∗ B − A ∗ B. Merk hierbij op dat als we geen beginsequentie A hebben, EX0 = 0. Dan geldt dus ENB = B ∗ B.

5.2.2. Afleiding van de kans dat sequentie B eerder voorkomt dan A Laten we weer even terugkeren naar het spel waarmee we beginnen. Spelers kiezen allebei een strategie (een rij) van mogelijke opeenvolgende uitkomsten van een munt die herhaaldelijk opgegooid wordt. Degene van wie de strategie als eerst voorkomt als we de munt achtereenvolgens blijven opgooien wint. Wat we nu zouden willen weten is wat de kans is dat speler twee (speler B) met een bepaalde strategie van speler ´e´en (speler

34

A) wint. We bekijken daarvoor twee rijen A en B die de strategie¨en van speler ´e´en en speler twee weergeven en die alletwee hun waarden aannemen in Σ = {H, T }. Hierbij is H =‘Heads’ (kop) en T =‘Tails’ (munt). Stel dat de stochast Z wederom de munt voorstelt die we opgooien. Z neemt zijn waarden dus aan in Σ = {H, T }. We hebben de kansverdeling P(Z = H) = P(Z = T ) = 1 /2 . Het proces Z1 , Z2 , . . . staat dan voor de uitkomsten van de munt die we herhaaldelijk achter elkaar opgooien. Elke stochast hierin i.i.d. en heeft dezelfde verdeling als Z. We willen nu de kans weten dat de ene strategie eerder voorkomt dan de ander in het proces Z1 , Z2 , . . . . De strategie¨en A en B hebben elk hun stoptijd NA en NB en we defini¨eren N = min{NA , NB } als het minimum van deze twee. We zijn benieuwd naar de kansen pA = P (N = NA ), dat wil zeggen de kans dat A als eerste voorkomt, en pB = P (N = NB ), de kans dat B het eerst voorkomt. Stelling 5.9 (Li). Laat Z, Z1 , Z2 , . . . onafhankelijke discrete stochasten met dezelfde verdeling en A en B eindige sequenties van mogelijke waarden van Z (namelijk H of T ). Laat pA = P(N = NA ) de kans dat sequentie A als eerste voorkomt in het proces Z1 , Z2 , . . . en pB = P(N = NB ) de kans dat sequentie B als eerste voorkomt in het proces Z1 , Z2 , . . .. Dan geldt voor A dat, pA A ∗ A + pB B ∗ A = EN. Analoog geldt dan ook voor B dat, pA A ∗ B + pB B ∗ B = EN. Hierbij is EN de verwachte stoptijd tot A of B voorkomt. Bewijs. We defini¨eren N := min{NA , NB }. Omdat het bewijs voor sequentie A en B praktisch hetzelfde gaat, laten we alleen het bewijs voor A zien. We zien ENA = EN + E(NA − N ) Hierbij weten we vanwege Stelling 5.8 dat ENA = A ∗ A. Voor de verwachting E(NA − N ) geldt bovendien dat E(NA − N ) = pA E(NA − N |N = NA ) + pB E(NA − N |N = NB ). Nu zien we dat E(NA − N |N = NB ) het verwachte aantal stappen is dat we moeten doen na B om A te krijgen. Oftewel E(NA − N |N = NB ) = A ∗ A − B ∗ A = ENBA . En daarom volgt dus ook dat E(NA − N |N = NA ) = A ∗ A − A ∗ A(= 0).

35

Dus vullen we dit allemaal in in de eerste vergelijking dan krijgen we: A ∗ A = EN + pA (A ∗ A − A ∗ A) + pB (A ∗ A − B ∗ A) = EN + (pA + pB )A ∗ A − pA A ∗ A − pB B ∗ A = EN + A ∗ A − pA A ∗ A − pB B ∗ A. Oftewel, pA A ∗ A + pB B ∗ A = EN. En dit is de vergelijking die we wilden krijgen. Het bewijs voor de vergelijking bij sequentie B gaat op analoge wijze. Als we deze twee vergelijkingen uit Stelling 5.9 nu in een matrix zetten samen met de vergelijking pA + pB = 1, die zegt dat de som van de twee kansen 1 moet zijn, dan kunnen we daarmee verwachte stoptijd, EN , en de kans dat de ene sequentie eerder voorkomt dan de ander, pA en pB , bepalen De vergelijkingen uit Stelling 5.9 worden in matrixvorm:      0 1 1 EN 1 −1 A ∗ A B ∗ A   pA  = 0 . −1 A ∗ B B ∗ B pB 0 Laten we de eerste matrix hierboven M noemen. Li and Gerber [4] hebben in hun artikel The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain aangetoond dat deze matrix nietsingulier is en daarom kan de regel van Cramer worden toegepast om EN , pA en pB te bepalen. We zullen nu eerst zonder bewijs de regel van Cramer uit Poole [5] geven. Stelling 5.10 (Regel van Cramer). Stel M is een nonsinguliere n × n matrix en b = (b1 , . . . , bn )T . Dan is de unieke oplossing x = (x1 , . . . , xn )T van de vergelijking M x = b gedefinieerd door: det(Mi ) i = 1, . . . , n xi = det(M ) Hierbij is Mi de matrix verkregen uit matrix M door kolom i van M te vervangen door de kolomvector b. We kunnen nu hiermee EN, pA en pB bepalen. Zo zien we dat EN gelijk is aan: EN · det(M ) = det(M1 ) = (A ∗ A) · (B ∗ B) − (A ∗ B) · (B ∗ A). En voor pA en pB : pA · det(M ) = det(M2 ) = B ∗ B − B ∗ A pB · det(M ) = det(M3 ) = A ∗ A − A ∗ B. Dit geeft ons het volgende gevolg:

36

Gevolg 5.11. Als A en B twee elkaar niet bevattende sequenties zijn, dan is de verhouding waarmee B eerder voorkomt dan A in het proces Z1 , Z2 , . . . gelijk aan (A ∗ A − A ∗ B) : (B ∗ B − B ∗ A). Laten we controleren of dit klopt door twee strategie¨en van lengte drie te bekijken en die te vergelijken met de kans die we zien in Figuur 2.2. Voorbeeld 5.12. Stel de eerste speler heeft strategie A = (H, H, H) en de tweede B = (T, H, T ). In Figuur 2.2 zien we dat de kans pB , dat B eerder voorkomt dan A als 7 we he herhaaldelijk een munt opgooien, gelijk aan pB = 12 . We gaan na of dit ook volgt uit Gevolg 5.11. We zien analoog aan Voorbeeld 5.6 dat als ai = bj dat dan δij = 2. Eerst bepalen we A ∗ A = δ11 δ22 δ33 + δ21 δ32 + δ31 = 23 + 22 + 2 = 14. Zo zien we ook dat A ∗ B = 0, B ∗ B = 10 en dat B ∗ A = 0. We krijgen dus de verhouding 14 : 10 oftewel 7 14 = 12 . Dit is dezelfde kans als in Figuur 2.2. kans 10+14

5.2.3. Afleiding van Conway’s algoritme We hebben inmiddels iets bewezen dat sterkt lijkt op Conway’s algoritme. Het enige verschil is dat we het nu bewezen hebben voor A ∗ A, A ∗ B, et cetera. Terwijl Conway’s algoritme geldt voor het kengetal AA van A over A, het kengetal AB van A over B, et cetera. Deze kengetallen construeer je met Conway’s algoritme door de mogelijke combinaties van de strategie¨en A en B om te zetten naar binaire getallen zoals beschreven in het algoritme in Hoofdstuk 2. Daarmee kunnen we de kans berekenen dat een rij eerder voorkwam dan de ander. Als we nu aan kunnen tonen dat A∗A gelijk is aan het kengetal AA van A over A, dat A ∗ B gelijk is aan het kengetal AB van A over B enzovoorts, dan volgt uit Gevolg 5.11 het bewijs van Conway’s algoritme. Herinner hoe we in Hoofdstuk 2 het kengetal van twee strategie¨en bepaalden. We willen nu eerst de constructie van deze kengetallen wat wiskundiger defini¨eren. Hierna zullen we A ∗ B afleiden uit het kengetal AB. Tenslotte zullen we Conway’s algoritme bewijzen door aan te tonen dat (AA − AB) : (BB − BA) gelijk is aan (A ∗ A − A ∗ B) : (B ∗ B − B ∗ A). Definitie 5.13 (Conway’s kengetallen). Gegeven twee sequenties A = (a1 , . . . , am ) en B = (b1 , . . . , bn ) defini¨eren we het kengetal AB van A over B als het binaire getal n n−1 . . . 1 waarbij voor 1 ≤ i ≤ n geldt:  1 als 1 ≤ i ≤ min{m, n} en de twee     sequenties (am−i+1 , . . . , am ) en (b1 , . . . , bi ) i = gelijk zijn,     0 anders. We maken dit wat duidelijker aan de hand van een voorbeeld. Voorbeeld 5.14. Zij A = (a1 , a2 , a3 ) en B = (b1 , b2 , b3 ). We willen het kengetal AB bepalen. We zien: ( 1 als (a3 ) = (b1 ) 1 = 0 anders.

37

Nu, ( 2 =

1

als (a2 , a3 ) = (b1 , b2 )

0

anders.

En, ( 3 =

1

als (a1 , a2 , a3 ) = (b1 , b2 , b3 )

0

anders.

Stel we hebben A = (H, T, H) en B = (T, H, H) dan zien we het volgende: omdat (a3 ) = (H) en (b1 ) = (T ) krijgen we 1 = 0, omdat (a2 , a3 ) = (T, H) en (b1 , b2 ) = (T, H) krijgen we 2 = 1 en zo vinden we ook dat 3 = 0. Voor alle n > 3 geldt n = 0. Het kengetal is dus in dit geval het binaire getal 010, oftewel het decimale getal 2. Laten we nu Conway’s kengetal AB van A over B vergelijken met A ∗ B. We doen dit alleen voor kengetal AB, omdat de vergelijking voor BB, BA en AA analoog gaat (ze zijn immers van dezelfde vorm als AB). Stel A = (a1 , . . . , am ) en B = (b1 , . . . , bn ). We kunnen zonder verlies van algemeenheid zeggen dat min{n, m} = n. We krijgen dan het kengetal n n−1 . . . 1 van A over B. Dit is dan gelijk aan het decimale getal 2n−1 n + 2n−2 n−1 + · · · + 20 1 . In Voorbeeld 5.14 zien we zo dat het binaire getal 010 gelijk is aan 22 · 0 + 21 · 1 + 20 · 0 = 2. We gaan dit vergelijken met A ∗ B. Laten we eerst nog een keer naar Definitie 5.5 van δij teruggaan. Omdat we het hier hebben over Penney’s spel waarbij we herhaaldelijk een munt opgooien kunnen we deze definitie van δij versimpelen. Herinner je hierbij dat Z de stochast is die waarden aanneemt in Σ = {H, T } en een munt voorstelt die we opgooien. In het algemeen kunnen we zeggen dat voor elke twee sequenties A = (a1 , a2 , . . . , am ) en B = (b1 , b2 , . . . , bn ) het volgende geldt: omdat voor alle 1 ≤ j ≤ n geldt dat bj ∈ {H, T } en P(Z = H) = P(Z = T ) = 1/2 zien we dat voor alle bj : P(Z = bj )−1 =

1 1 = 1 = 2. P(Z = bj ) /2

We kunnen δij met 1 ≤ i ≤ max{n, m} en 1 ≤ j ≤ max{n, m} daarom herschrijven tot: ( P(Z = bj )−1 = 2 als ai = bj δij = 0 anders. Hierbij moeten we opmerken dat als m > n dan δmm = 0, omdat bm dan niet gedefinieerd is dus ook niet geldt dat bm = am . Als we nu wederom kijken naar de definitie van A ∗ B: A ∗ B = δ11 δ22 · · · δmm + δ21 δ32 · · · δm,m−1 + · · · + δm1 en we vergelijken dit met het kengetal AB, dan zien we dat: A ∗ B = 2n · n + 2n−1 · n−1 + · · · + 21 · 1 = 2 · (2n−1 n + 2n−2 n−1 + · · · + 20 1 ) = 2AB.

38

Dit is misschien allemaal een beetje veel om te verwerken dus laten we nogmaals kijken naar Voorbeeld 5.14, maar dan A ∗ B maken en dit vergelijken met het kengetal AB. Voorbeeld 5.15. Zij A = (H, T, H) en B = (T, H, H). We willen A ∗ B = δ11 δ22 δ33 + δ21 δ32 +δ31 bepalen. We zijn daarom alleen ge¨ınteresseerd in de δij ’s die we nodig hebben voor A ∗ B. Nu zien we dat δ33 = δ21 = δ32 = 2 en δ11 = δ22 = δ31 = 0. We krijgen dus: A ∗ B = δ11 δ22 δ33 + δ21 δ32 + δ31 =0·0·2+2·2+0 =0+4+0 = 2 · (22 · 0 + 21 · 1 + 20 · 0) = 2AB. Dus er geldt voor strategi¨en A van speler ´e´en en B voor speler twee dat A ∗ B = 2AB, waarbij AB het kengetal van A over B is. Het bewijs van Conway’s algoritme is nu makkelijk. Stelling 5.16 (Conway). Zij A = (a1 , . . . , am ) en B = (b1 , . . . , bm ). Als AB het kengetal van A over B is, dan is de verhouding waarmee B eerder voorkomt dan A in het proces Z1 , Z2 , . . . (oftewel als we herhaaldelijk een munt opgooien) gelijk aan (AA − AB) : (BB − BA). Bewijs. We weten uit Gevolg 5.11 dat de verhouding waarmee B eerder voorkomt dan A gelijk is aan (A ∗ A − A ∗ B) : (B ∗ B − B ∗ A). Ook weten we dat A ∗ A = 2AA, A ∗ B = 2AB, B ∗ B = 2BB en B ∗ A = 2BA. Hiervolgt dus dat (2AA − 2AB) : (2BB − 2BA) De twee¨en vallen weg, omdat ze voor de verhouding niks uitmaken aangezien ze voor alle kengetallen staan. Dit geeft dus de verhouding (AA − AB) : (BB − BA). Conway’s algoritme is hiermee dus eigenlijk gewoon een gevolg van Gevolg 5.11. Merk op dat de kans waarmee B eerder voorkomt dan A dus gelijk is aan BB − BA . AA − AB + BB − BA We hebben nu dus met het artikel van Li [3] bewezen dat Conway’s algoritme klopt. Dit kunnen we dus gebruik als we Penney’s spel spelen en gemakkelijk geld willen verdienen. Het enige waar we voor moeten zorgen is dat we als tweede een strategie kiezen zodat we gebruik kunnen maken van de nontransitiviteit van dit spel (waardoor de tweede speler altijd met een grote kans het spel wint). Omdat het een eerlijk spel is zal de andere speler denken dat het niet uitmaakt wie er als eerste kiest dus dat zou geen probleem moeten zijn. We moeten dan alleen met behulp van Conway’s algoritme de kansen uitrekenen waarmee de andere strategie¨en eerder voorkomen dan de strategie van speler ´e´en als we herhaaldelijk een munt opgooien en dan kunnen we eindelijk genieten van ons gratis geld!

39

6. Discussie We weten nu hoe we met Conways algoritme gemakkelijk de kansen kunnen berekenen waarmee een bepaalde strategie eerder voorkomt dan een ander als we een herhaaldelijk een munt opgooien. Dit spel is nontransitief dus de tweede speler is altijd in het voordeel. Maar als de tweede speler nu de strategie wil kiezen waarmee hij met een zo’n groot mogelijk kans wint van speler ´e´en, dan moet hij eerst uitrekenen met welke kans elke strategie wint van de strategie van speler ´e´en. Daarna pas kan hij de strategie kiezen waarmee hij met een zo groot mogelijke kans wint. Als we strategie¨en van lengte drie hebben is dit nog te doen. Je hebt dan 23 = 8 mogelijke strategie¨en dus dan moet je 7 keer Conway’s algoritme gebruiken (alleen niet voor de strategie die speler ´e´en kiest). Maar als we strategie¨en van lengte 20 hebben zijn er 220 = 1048576 mogelijke strategie¨en. Conways algoritme kan weliswaar voor elke strategie gemakkelijk uitrekenen met welke kans hij eerder voorkomt dan de strategie van speler ´e´en, maar dat neemt niet weg dat als we willen bepalen wat de beste strategie is we dit algoritme 1048576 − 1 keer moeten toepassen. Mijn voorstel voor een vervolgonderzoek luidt dan ook: hoe kunnen we gemakkelijk bepalen wat de beste strategie is waarmee speler twee van speler ´e´en kan winnen? Bovendien moeten het spel altijd nontransitief zijn. Voor strategie¨en van lengte drie weten we dat dit het geval is en volgens Gardner [2] is dat ook het geval voor langere lengtes, maar waarom is dat zo? En hoe kan je dat nagaan? Voor strategie¨en van lengte drie heb ik op Youtube [7] een filmpje gevonden dat laat zien hoe je in een keer de beste strategie kan kiezen. Speler twee, die wederom na speler ´e´en zijn strategie kiest, neemt het middelste element van de strategie van speler ´e´en, spiegelt dat element (dat wil zeggen als dat element H is maakt speler twee er een T van), plaats hem voor de strategie van speler ´e´en en neemt de eerste drie elementen als zijn eigen strategie. We lichten dit toe met een voorbeeld: stel speler ´e´en heeft strategie HT T , dan moet speler twee die middelste T spiegelen en voraan zetten. We krijgen dan HHT T . De eerste drie elementen zijn dan HHT . Dit is de strategie waarmee speler twee met de grootste kans van speler ´e´en wint. Dit komt ook overeen met de tabel op pagina 303 van Gardner [2], maar waarom het klopt en hoe dit werkt voor strategie¨en van langere lengtes, is een mooie uitdaging voor een vervolgonderzoek.

40

7. Populaire samenvatting We willen veel geld krijgen en daar weinig moeite voor doen. Naar het casino gaan maakt ons over het algemeen alleen maar armer. Of zouden we misschien onze wiskundige kennis kunnen gebruiken om toch moeiteloos geld te verdienen? Bij sommige spellen kan dat. Dit zijn nontransitieve spellen: spellen waarbij speler twee in het voordeel is. Een voorbeeld daarvan is het Penney’s spel. Twee spelers kiezen na elkaar een strategie van lengte n, dat wil zeggen een opeenvolging van n mogelijke uitkomsten als we herhaaldelijk een munt opgooien, en we gaan vervolgens een munt opgooien net zo lang tot de strategie van een van beide spelers voorbij is gekomen. Als wij speler twee zijn zijn we benieuwd naar de strategie die we moeten kiezen zodat we dus met een grote kans winnen. Daarvoor moeten we wel kunnen bepalen wat de kans is dat we met een strategie winnen van speler ´e´en. Dit kan heel lastig zijn, maar John Conway heeft daar een algoritme voor bedacht. Om te bewijzen dat Conway’s algoritme werkt is alleen veel moeilijke wiskunde nodig. Maar waar het bewijs op neerkomt is het volgende. We noemen hierbij speler ´e´en ‘A’ en speler twee ‘B’. We kijken eerst naar de verwachte tijd tot we de strategie van A krijgen, nadat we de strategie van B hebben. We beginnen dus met de strategie van B en gaan dan net zo lang een munt opgooien tot we strategie A hebben. Dit is gelijk aan het verwachtte aantal keer gooien tot we strategie A hebben min een correctiefactor. We moeten er namelijk een correctiefactor vanaf halen, omdat het zou kunnen dat we het begin van strategie A aan het eind van strategie B hebben. Stel bijvoorbeeld dat A = HT T en B = HHT , hierbij staat H voor ‘kop’ en T voor ‘munt’. Als we beginnen met B dan beginnen we dus met HHT . We moeten dan eigenlijk alleen nog T gooien om strategie A te krijgen. We hebben dan immers HHTT. Dus de verwachte tijd tot we strategie A hebben na B kan korter zijn dan de verwachte tijd tot we strategie A hebben gegooid. Hetzelfde geldt voor de verwachte tijd tot we B krijgen als we beginnen met A. Als we nu de verhouding van de verwachte tijd tot A na B met de verwachte tijd tot B na A nemen, dan weten we dus de verhouding waarmee de strategie B van speler twee eerder voorkomt dan de strategie A van speler ´e´en. Stel namelijk dat we verwachten dat we 4 keer moeiten gooien tot B na A en 6 keer tot A nadat we B hebben. Dan is de verhouding dat B eerder voorkomt dan A : 6 : 4. Hiermee kunnen we ook de kans dat B eerder voorkomt dan A uitrekenen en dat is 6 = 0.6. Dit is hoe het bewijs van Conways algoritme intu¨ıtief werkt en dit namelijk 6+4 toont dus aan dat je als speler twee in dit spel altijd veel geld kan verdienen!

41

Bibliografie [1] Vladimir Bogachev. Measure Theory, volume 2. Springer, 2007. [2] Martin Gardner. The colossal book of mathematics: Classic puzzles, paradoxes, and problems : Number theory, algebra, geometry, probability, topology, game theory, infinity, and other topics of recreational mathematics. W. W. Norton & Company, New York, 2001. [3] Shuo-Yen Robert Li. A martingale approach to the study of occurence of sequence patterns in repeated experiments. The Annals of Probability, 8(6):1171–1176, 1980. [4] Shuo-Yen Robert Li and Hans U. Gerber. The occurrence of sequence patterns in repeated experiments and hitting times in a markov chain. Stochastic Processes and their Applications, 11:101–108, 1981. [5] David Poole. Linear Algebra: A Modern Introduction. 4th edition, 2014. [6] Bryan P. Rynne and Martin A. Youngson. Linear Functional Analysis. 2nd edition, 2008. [7] singingbanana (Youtube-account). Coin Game Magic Trick Maths: The Penney Ante Part 1 (Re: Derren Brown: How to Win the Lottery). [Video file]. September 2009. URL http://www.youtube.com/watch?v=OcYnlSenF04. [8] P. J. C. Spreij. Measure Theoretic Probability. [Lecture Notes], Retrieved from https://staff.fnwi.uva.nl/p.j.c.spreij/onderwijs/TI/mtsp.html, 2014.

42

A. Bijlage In deze bijlage de Pythoncode waarmee ik Penney’s spel voor strategie¨en van lengte drie geprogrammeerd heb. Ik gebruikte dit in mijn flitspresentatie waarbij ik mensen uit de klas uitdaagde om Penney’s spel tegen mij te spelen. Eerst liet ik zien dat het een eerlijk spel lijkt (de kans om kop-kop-kop te gooien is even groot als de kans om munt-kop-munt te gooien bijvoorbeeld). De tegenstander koos vervolgens eerst een strategie en daarna ik. Vervolgens speelden we het spel 100.000 keer. Pas als ik 60% of meer van de gespeelde spellen won mocht ik een broodje houden. Anders won mijn tegenstander een broodje. Het spel leek eerlijk, maar dat is niet het geval. Ik mocht het broodje uiteindelijk zelf opeten. Vervolgens legde ik uit dat dit het onderwerp is van mijn scriptie, waarom dit spel dus toch niet eerlijk is (onder andere vanwege de nontransitiviteit) en hoe ik ervoor zorg dat ik win: door Conway’s algoritme. import random from math import* from decimal import * #Afronden op aantal decimalen achter de komma getcontext().prec = 2 #strategie wordt binair getal #M/T wordt 1 en H/K wordt 0 def binstrat(x): P=list(x) L=[] for i in range(0,len(P)): if P[i]==’H’: L.append(0) elif P[i]==’T’: L.append(1) elif P[i]==’K’: L.append(0) elif P[i]==’M’: L.append(1) return L #binair getal wordt strategie def stratbin(x):

43

L=[] for i in range(0,len(x)): if x[i]==0: L.append(’K’) elif x[i]==1: L.append(’M’) g = ’’ for f in L: g = g + f return g

def spel(A,B,q):

# invoer strategie A, strategie B en #aantal keer dat we spelen # strategie omzetten naar binair getal: K=0, M=1

a=binstrat(A) b=binstrat(B) awin=0 # bijhouden wie er wint bwin=0 i=0 while i
44

print ’Als we’,q,’keer spelen, waarbij Roelof strategie’,B,’heeft en’ ’zijn tegenstander strategie’,A if i==1: print ’en we gooien achtereenvolgens in’,n+2,’keer’, stratbin(r) if awin==1: print ’dan wint de tegenstander het broodje!’ if bwin==1: print ’dan wint Roelof en mag hij het broodje houden :D.’ if i>1: print ’Wint Roelof’,bwin,’keer en wint zijn tegenstander’,awin,’keer’ print ’Oftewel Roelof wint’, ’{0:.0%}’.format(Decimal(bwin) / Decimal(q)), ’van de spellen.’ if Decimal(bwin) / Decimal(q)>Decimal(6)/Decimal(10): print ’Dit is groter dan 60% dus Roelof mag het broodje houden :D’ else: print ’Dit is kleiner dan 60% dus je hebt het broodje gewonnen!!!’ spel(’MKK’,’KMK’,1)

spel(’strategie tegenstander’,’strategie roelof’,100000)

45