Handout Gambler’s ruin
Een gokker heeft een startkapitaal van ie. Hij speelt herhaaldelijk een gokspel waarbij hij telkens 1e inlegt. Met kans p wint hij en wordt zijn inleg verdubbeld en met kans 1 − p verliest hij zijn inleg. Als zijn vermogen 0e bereikt is hij natuurlijk niet meer in staat verder te spelen, en als hij een vermogen van N e bijelkaar heeft, dan gaat hij tevreden naar huis (en betaalt de volgende dag zijn collegegeld ter hoogte van N e). Wat is de kans dat de gokker uiteindelijk tevreden naar huis gaat? Om deze vraag op te lossen defini¨eren we de eventualiteiten T := {de gokker gaat uiteindelijk tevreden naar huis}, W := {de gokker wint het eerste spel}, en we zetten: pi := Pi (T )
(i = 0, . . . , N ).
Hier betekent het subscript i dat de gokker begint met een startkapitaal van ie. We zien direct dat p0 = 0,
pN = 1.
Verder merken we op dat, voor alle 0 < i < N : Pi (T |W c ) = Pi−1 (T ).
Pi (T |W ) = Pi+1 (T ),
(Als hij het eerste spel wint dan is de situatie hetzelfde als aan het begin van het spel met startkapitaal i + 1e, en als hij het eerste spel verliest dan is de situatie hetzelfde als aan het begin van het spel met startkapitaal i − 1e.) Met de wet van de totale kans vinden we, voor alle 0 < i < N : Pi (T ) = Pi (T |W )Pi (W ) + Pi (T |W c )Pi (W c ). We hebben dus de volgende relatie afgeleid voor the pi -tjes: pi = (1 − p) · pi−1 + p · pi+1 ,
voor i = 1, . . . , N − 1.
Herschrijven geeft: (1 − p) · pi − (1 − p) · pi−1 = p · pi+1 − p · pi , oftewel: 1
(1)
pi+1 − pi =
1−p p
(pi − pi−1 ).
(2)
Herhaaldelijk toepassen van (2) geeft:
pi+1 − pi =
1−p p
(pi − pi−1 ) 2 1−p (pi−1 − pi−2 ) p 3 1−p (pi−2 − pi−3 ) p .. . i 1−p (p1 − p0 ) p i 1−p p1 p
= =
= =
(in de laatste stap gebruiken we dat p0 = 0.) Aan de andere kant hebben we pi+1 = pi+1 − p0 = (pi+1 − pi ) + (pi − pi−1 ) + · · · + (p1 − p0 ) i i−1 1−p 1−p 1−p = p + p + · · · + p1 + p1 . 1 1 p p p In het speciale geval dat p =
1 2
hebben we (1 − p)/p = 1 en dan staat hier dus gewoon: pi+1 = (i + 1)p1 .
Omdat moet gelden dan pN = 1 = N p1 volgt nu dat p1 = 1/N en dus in het algemeen is: pi =
i N
voor i = 0, . . . , N .
(als p = 12 .) Maar wat nu als p 6= 12 ? In dat geval volgt met de formule voor de som van een geometrische reeks dat: 1− pi+1 =
1−
1−p p
i+1
1−p p
· p1 .
(Merk op dat je de formule voor de som van een geometrische reeks niet kunt toepassen als p = 12 omdat de noemer dan nul wordt.) Door middel van 1− 1 = pN =
1−
2
1−p p
N
1−p p
· p1 ,
vinden we dat p1 = 1 −
1−p p
N 1−p . Dus voor algemene 0 ≤ i ≤ N geldt: / 1− p 1−
1−
pi =
1−p p
1−p p
i
N .
(als p 6= 12 )
Het verwachte totale aantal spellen. Laat nu X het totaal aantal spellen zijn dat de gokker doet voordat hij ofwel een vermogen van 0e ofwel een vermogen van N e heeft bereikt. We zijn ge¨ınteresseerd in de verwachting Ei X. (Hier betekent het subscript i weer dat het startkapitaal gelijk is aan ie.) Merk op dat geldt E0 X = EN X = 0, en voor 0 < i < N : Ei (X|W c ) = 1 + Ei−1 X.
Ei (X|W ) = 1 + Ei+1 X,
(Als de gokker het eerste spel wint dan is de situatie als bij het begin van het proces met startkapitaal van i + 1e, behalve dat er al een spel is gespeeld. Idem als hij het eerste spel verliest.) We kunnen dus schrijven: Ei X = Ei (X|W )P(W ) + Ei (X|W c )P(W c ) = p(1 + Ei+1 X) + (1 − p)(1 + Ei−1 X) = 1 + pEi+1 X + (1 − p)Ei−1 X. Als we schrijven ei := Ei X dan hebben we het stelsel e0 = eN = 0,
ei = 1 + (1 − p)ei−1 + pei+1 .
Herschrijven van die laatste vergelijking geeft p(ei+1 − ei ) = (1 − p)(ei − ei−1 ) − 1,
(i = 1, . . . , N − 1).
Stel nu eerst weer dat p = 21 . Dan kunnen we schrijven: ei+1 − ei = ei − ei−1 − 2,
(i = 1, . . . , N − 1).
Herhaaldelijkt toepassen geeft: ei+1 − ei = e1 − e0 − 2i = e1 − 2i,
(i = 1, . . . , N − 1).
En dus: ei+1 = = = =
ei+1 − e0 (ei+1 − ei ) + (ei − ei−1 ) + · · · + (e1 − e0 ) (i + 1)e1 − 2(i + · · · + 1) (i + 1)e1 − i(i + 1). 3
(3)
Of ook: ei = ie1 − i(i − 1). Invullen van i = N geeft: 0 = eN = N e1 − N (N − 1), oftewel e1 = N − 1. De oplossing voor algemene 1 ≤ i ≤ N is dus: ei := i(N − 1) − i(i − 1) = i(N − i). Wat nu als p 6= 12 ? Je kunt laten zien dat ei dan de volgende vorm heeft:
ei :=
1−p p
i
−1 i N . − · N 1 − 2p 1 − 2p 1−p − 1 p
(4)
(Zie de opgaven.)
Opgaven Opgave 1. In de nabije toekomst gaat het collegeld omhoog naar 10000e. De nieuwe directeur van de SNS bank is bereid om je telkens 1e te laten inzetten op kop bij een worp met een zuivere munt (bij kop verdubbelt hij de inzet, bij munt verlies je je inzet). Hoeveel startkapitaal moet je hebben om met kans 0.9 met 10000e naar huis te gaan in plaats van met lege handen? Opgave 2. Bacchus, de god van de wijn, houdt niet alleen van wijn maar ook van gokken. Hij speelt roulette in het casino van de goden en heeft een beginkapitaal van 1000e. Hij zet telkens 1e in op “rood” (bij winst verdubbelt de inzet, bij verlies ben je je inzet kwijt). Anders dan in de casino’s voor sterfelingen, is in het casino van de goden de kans op “rood” gelijk aan maar liefst 32 . Bacchus is onsterfelijk en zou dus in principe oneindig lang door kunnen spelen. Stel dat hij naar huis gaat zodra hij ofwel 0e heeft ofwel 1010 e. Wat is de kans dat hij nooit naar huis gaat? Opgave 3. Bacchus uit de vorige opgave besluit alleen naar huis te gaan als zijn geld helemaal op is. Wat is de kans dat hij oneindig lang kan doorspelen (zijn vermogen nooit 0e bereikt)? Opgave 4. Zelfde vraag als de kans op rood gelijk is aan
1 3
en als p = 12 .
Z.O.Z
4
Opgave 5. Een muis bevindt zich in een appartement met 9 kamers, 2 katten en 2 stukken kaas als in de plattegrond hieronder.
Als de muis een kamer met een kat binnen gaat, wordt hij meteen opgegeten. De katten zijn nogal lui en blijven altijd in dezelfde kamer. De arme muis is nogal vergeetachtig en kiest telkens een willekeurige kamer uit alle kamers die grenzen aan de kamer waar hij zich op het moment bevindt, elk met gelijke kans. (Dus op het moment kiest hij elk van de 4 aangrenzende kamers met kans 1/4.) Wat is de kans dat de muis ´e´en van de kazen vindt voordat hij door een kat wordt opgegeten? Wat is de kans dat de muis beide kazen vindt voordat hij wordt opgegeten? Opgave 6. Wat is het verwachte aantal kamers dat de muis uit de vorige opgave bezoekt voordat hij/zij wordt opgegeten door een kat? (Na het vinden/opeten van een kaas gaat het beestje gewoon door met steeds een willekeurige kamer kiezen.) Opgave 7. Wat is het verwachte aantal kazen dat de muis uit de opgave 5 opeet voordat hij/zij zelf wordt opgegeten? Opgave 8. Laat zien dat (4) de unieke oplossing van het stelsel (3) is (als p 6= 12 ).
5
