\documentclass {article}
\usepackage [dutch] {babel}
\usepackage [T1] {fontenc}
\usepackage {palatino,a4}
\usepackage {amsmath}
\usepackage {amssymb}
\selectlanguage {dutch}
\newcommand \fbt[1] {\framebox {\smash[b] {#1 $\blacktriangleright$}}}
\newcommand \fb[1] {\framebox {\smash[b]{#1}}}
\newcommand \bon [1] {{\em #1}}
\newcommand \Opdrachten {{\medskip\mbox{}\par\noindent{\bf
Opdrachten}\mbox{}\nopagebreak}}
\newcounter {opdrachtctr}
\title {Winner takes all\\ {\small Simuleren en denken}}
\author {Jos van Kan \thanks {TU Delft, faculteit Informatietechnologie
en Systemen.}}
\date{18 januari 2000}
\hyphenation {uit-wen-di-ge ge-ko-zen ver-ge-le-ken si-mu-le-ren func-ti-o-neel 
wis-kun-di-ge}
\parindent 0pt
\begin {document}
\maketitle
\section {Inleiding}
In deze practische opdracht zullen wij een modelstudie verrichten met behulp 
van simulatie. Simulatie is een vaak gebruikt (misbruikt) middel om complexe 
processen te bestuderen. Deze worden vaak eerst vereenvoudigd tot een {model},
dat (hopelijk) nog steeds de wezenlijke kenmerken bevat van de complexe
werkelijkheid.  

Bij het simuleren komt men vaak niet verder dan wat data genereren en 
mooie plaatjes tekenen, maar dat is natuurlijk de kunst niet. De simulatie is
ook bedoeld om processen beter te {\em begrijpen}. 

In een modelstudie met simulatie kun je de volgende fasen onderscheiden:

\begin {description}
\item [Modelvorming] Van het proces wordt een model gemaakt. Zo'n model bevat
{\em modelparameters} en {\em modelvariabelen}. De modelparameters stellen
uitwendige omstandigheden  voor. Deze worden als gegeven beschouwd, maar kunnen
gevarieerd worden. Beleidsmakers spreken dan over verschillende {\em
scenario's}. Modelvariabelen zijn de grootheden waarvan we het gedrag willen
bekijken.
\item [Simulatie] Van een proces worden een aantal simulaties gedaan voor
verscheidene waarden van de parameters. Op grond hiervan kun je {\em voor de
gekozen waarden van de parameters} soms al een uitspraak doen over het gedrag
van de modelvariabelen.
\item [Analyse] De resultaten van verschillende simulaties worden met elkaar
vergeleken en geanalyseerd met algebra"ische, numerieke en grafische
hulpmiddelen. Vaak geeft de analyse aanleiding tot een
veronderstelling hoe het model zich gedraagt als je een modelparameter laat
vari"eren
\item [Scholium] De juistheid van zo'n veronderstelling moet je ook kunnen 
aantonen.  Dit is 
vaak het lastigste onderdeel, maar juist datgene wat het geheel
tot een {\em wiskundig} onderzoek maakt. Eventueel vereenvoudigt men het model
om formulematig iets aan te tonen.
\item [Conclusies] Tenslotte gaan we na in hoeverre we antwoord hebben gekregen
op de over het proces gestelde vragen.
\end {description}

\section {Two person freeze--out.}
Het proces, dat we gaan bekijken is een tweepersoons spel om geld. Dit spel wordt 
zolang
herhaald, totdat een van de twee spelers blut is. Per spel en per speler wordt
steeds eenzelfde bedrag ingezet. De gegevens (modelparameters) die bij dit
proces kunnen vari"eren  zijn de {\em behendigheid} van de spelers en de grootte
van hun {\em beginkapitaal}. Wij zijn ge"interesseerd in de volgende vragen.
\begin {itemize}
\item Als de spelers {\em even goed} zijn, hoe be"invloeden hun beginkapitalen
dan
hun kans op een succesvolle afloop? Hoe hangt het aantal spelletjes dat gespeeld
moet worden voordat een van de twee blut is af van de beginkapitalen?
\item En hoe zit het als een van de twee (beduidend) beter is?
\end {itemize}

\subsection {Modelvorming.}
Voor dit proces zou de fase {\em modelvorming} er als volgt uit kunnen zien. 
We doen alsof het spel dat gespeeld wordt een {\em kansspel} is en formuleren
daarmee een {\em stochastisch model}.
Wij (speler $W$) hebben een kans $p$ om elk afzonderlijk spel te winnen, en Zij
(speler $Z$) dus een kans $1-p$.
$W$ heeft een beginkapitaal in gehele guldens van
$G_w$ en $Z$ een beginkapitaal  $G_z$. Ieder
spel gaat om \'e\'en gulden: wint $W$, dan betaalt $Z$ \'e\'en gulden aan $W$,
en wint $Z$, dan betaalt $W$ een gulden aan $Z$. Het totale aantal guldens dat
in het spel is, is dus in iedere fase constant: $G_{tot} = G_w + G_z$.
\begin {quotation}
... and the total number of tears in the universe is a constant.\\
(Samuel Beckett, "`Waiting for Godot."')
\end {quotation}
 
\subsection {De fasen simulatie en analyse}
Voor het geval $p=\frac12$ doen we een aantal simulaties voor  verscheidene
waarden van $G_{tot}$. Voor een vaste waarde van $G_{tot}$ bekijken we {\em
alle} beginposities. 

De resultaten (winst als functie van beginkapitaal en sessielengtie als functie
van beginkapitaal) zetten we uit in een grafiek en we proberen een functioneel
verband hieruit te halen

Hetzelfde doen we voor het geval $p\neq\frac12.$

\subsection {Scholium fase}
Wij proberen de door ons uit de grafiek "`geraden"' verbanden ook met wiskundige
middelen af te leiden. In dit speciale geval kan dat (toevallig), maar het zal
ook blijken, dat het zeker voor het geval $p\neq\frac12$ niet zo eenvoudig is.


{\em We maken voor de simulatie gebruik van het programma WinStats. De commando's
worden beschreven in de vorm: \fbt {com1} \fbt{com2} ... \fb {com\#}. Dat
betekent klik menu-item com1, dan com2 in het pop-up menu enzovoorts tot com\#.
Start WinStats.}
 
\section {Beide spelers even goed: $p=\frac12$}
\subsection {Simulatie met $G_{tot} = 12$}
\fbt{Window} \fbt{Simulate} \fb{Gambler's Ruin} geeft een window met een regel
met W's en L's (wins \& losses). Dat is het resultaat van \'e\'en enkele
simulatie, maar dat is natuurlijk voor kinderen. Allereerst zetten we het
aantal op 10000. \fbt{Do} \fb{Number...}

Verder zetten we het beginkapitaal voor beide spelers op 6 gulden. \fb{Params}
Als alles goed is staat de \bon {probability of win} al op 0.5, anders moet je dat
ook nog doen.

Nu zijn we klaar om de simulatie te starten. \fbt{Do} \fb{Many} of F12.
In de titelbalk zie je hoeveel simulaties er al gedaan zijn. Als de simulatie
klaar is kun je het resultaat bekijken met \fbt{Do} \fbt{Data} \fb{Inspect}
Er verschijnt nu een venster met een rij uitkomsten, het \bon {games data}
venster. 
\begin {itemize}
\item \bon {leng} is het gemiddelde aantal spelletjes in een simulatierun. 
In \'e\'en simulatierun wordt net zolang gespeeld totdat een van de
twee partijen geen geld meer over heeft.
\item \bon {succ} is het aantal runs,
dat onze held won, gedeeld door het totale aantal simulatieruns. De nederlandse 
term hiervoor is {\em fractie
van successen.}
\item \bon {succ leng} is het gemiddelde aantal spelletjes in een door onze
held gewonnen simulatierun.
\item \bon {fail} is het aantal runs dat onze
held verloor, gedeeld door het totale aantal simulatieruns.
De nederlandse term hiervoor is {\em fractie van mislukkingen}.
\item \bon {fail leng} de gemiddelde lengte van een door onze held verloren 
simulatierun.
\item \bon {stake} (inzet) is het beginkapitaal van onze held.
\item \bon {total} (zou eigenlijk \bon {opponent's stake} moeten heten) is het
beginkapitaal van de tegenstander.
\item \bon {succ prob} De kans om \'e\'en spelletje te winnen.
\item \bon {trials} is het aantal simulatieruns. 
\end {itemize}

%\pagebreak
\Opdrachten
\begin {enumerate}
\item Welke uitkomsten van de simulatie zijn het belangrijkste voor de vragen
die wij over het proces willen beantwoorden?
\item Formuleer op grond van deze uitkomsten voorlopige antwoorden op deze twee
vragen. 
\item Gelden deze antwoorden ook voor andere instellingen van de
modelparameters?
\end {enumerate}

Wij herhalen dit voor $G_w=7$ en $G_z=5$. Dit geeft een nieuwe regel in het 
\bon {games data} venster. 

Zelfde voor $G_w=8$ en $G_z=4$, $G_w=9$ en $G_z=3$ ... enzovoort, totdat we
alle gevallen met totaal kapitaal 12 gehad hebben. Er staan nu 6 regels in het
\bon {games data} window. 
Als er per ongeluk te veel, of verkeerde regels in dit venster terecht gekomen
zijn is dat niet erg. Deze kunnen we later gemakkelijk verwijderen. (Zie
sectie~\ref{ana_hyp}).

We kunnen natuurlijk voor al deze gevallen afzonderlijk voorlopige antwoorden op
de vragen van bladzijde 2 formuleren, maar dat is niet zo interessant. Liever
proberen wij voor de instelling $p=\frac12$ en $G_{tot}=12$ een overzicht 
te krijgen hoe de {\em systeem variabelen} (kans op de overwinning, respectievelijk gemiddeld benodigd
aan tal spelletjes) vari"eren als functie van de {\em modelparameter} $G_w.$ 

\subsection {\label {ana_hyp} Analyse en hypothese voor $G_{tot}=12$}

Het \bon {games data} venster is door zijn breedte niet erg overzichtelijk. Om
de simulatiegegevens beter te kunnen bekijken en bewerken brengen we ze over naar
een ander deel van WinStats.
Hiertoe worden de gegevens eerst opgeborgen in een .fma file \fbt{Do} \fbt{Data}\fb{Save as
Matrix}. Berg deze gegevens op als {\tt geval1.fma}. Open het analyse deel voor twee variabelen van WinStats en
laad {\tt geval1.fma} (\fbt{Window} \fb{2-var}, daarna \fbt{File} \fb{Open}). 
Verwijder eventueel kolommen die voor onze analyse niet van belang
zijn. \fbt{Edit} \fbt{Remove} \fb{Columns...} en in het dialoogvenstertje het
nummer van de
eerste en laatste van {\em opeenvolgende} kolommen die moeten worden verwijderd.
Hoef je maar \'e\'en kolom te verwijderen, dan zijn deze nummers dus gelijk. 
(Op gelijke wijze verwijder je overtollige rijen:
\fbt{Edit} \fbt{Remove} \fb{Rows...}).

\Opdrachten
\begin {enumerate}
\item We hebben bij de simulaties alleen maar gevallen bekeken waarvoor 
$G_w \geq G_z$. Leg uit waarom je op grond van deze waarnemingen ook een
uitspraak kunt doen voor de andere gevallen.
\item Bekijk de uitkomsten van \bon{succ} en de bijbehorende waarden van \bon
{stake} en \bon {total}. Heb je een vermoeden over een verband tussen de kans
$u$ op uiteindelijk succes voor speler $W$ en zijn beginkapitaal $G_w$? Zo ja,
geef je vermoeden in de vorm van een formule waarin $u$ wordt uitgedrukt in
$G_w$ en $G_{tot}.$
\item Kun je ook een verband vinden voor \bon {leng},  $G_w$ en $G_z$?
\setcounter {opdrachtctr} {\value {enumi}}
\end {enumerate}

Als je uit de tabel de gevraagde verbanden niet hebt kunnen vinden, lukt dat
waarschijnlijk beter met behulp van grafieken. Heb je wel formules gevonden, dan
kun je deze controleren aan de hand van de grafiek.


Om \bon {succ} te plotten tegen \bon {stake} \fbt{Scatter} \fb{Plot} en in de dialoogbox
in het vakje \bon {horiz} het kolomnummer van  \bon {stake} invullen. In het eerste
\bon {vert} het kolomnummer van \bon {succ} invullen.

Maak het grafiekvenster zo groot mogelijk. Kies het zichtvenster:\\
\fbt{View} \fb{Set Corners...}\\ 
en nu
in het dialoogvenstertje als uiterste waarden voor de horizontale as 0 en 12
invullen en voor de uiterste waarden van de verticale as 0 en 1.

{\Opdrachten}
\begin {enumerate}
\setcounter {enumi}{\value {opdrachtctr}}
\item Bedenk hoe de figuur voor waarden van \bon{stake} tussen 0 en 6 zou kunnen
worden voortgezet. Welk type verband wordt door de stippen gesuggereerd?
(lineair, kwadratisch, exponentieel, logarithmisch, sinuso"ide)
\item Welke formule hoort daarbij? (Aanwijzing: Wat is \bon{succ} voor een
\bon{stake}-waarde van 0? Wat is \bon {succ} voor een \bon {stake}-waarde van
12?) Kijk of je gevonden formule klopt met de data. (\fbt {Graph} \fb{Other} en
in het vakje $Y=$ de formule voor $x$ invullen.
\setcounter {opdrachtctr} {\value {enumi}}
\end {enumerate}

Plot \bon{leng} tegen \bon{stake} en pas de verticale schaal van het 
assenstelsel aan, zodat de hele figuur in beeld komt.

\pagebreak
\Opdrachten
\begin  {enumerate}
\setcounter {enumi}{\value {opdrachtctr}}
\item Bedenk hoe de figuur voor waarden van \bon {stake} tussen 0 en 6 zou
kunnen worden voortgezet. Van welk type is het verband dat door de stippen wordt
gesuggereerd? (lineair, kwadratisch, derde- of hogere-graads, exponentieel,
logaritmisch, sinuso"idaal)
\item Wat is de symmetrie--as? Wat zijn de nulpunten? Wat is de bijbehorende
formule? Kijk ook hier of je gevonden formule klopt met de data.   
\end {enumerate}

\subsection {Simulatie met $G_{tot}=18$}
Maak eerst de vensters in het simulatie-deel van WinStats schoon:
\fbt{Do} \fbt{Data} \fb{Reset}

Herhaal de simulaties van sectie 3.1 voor $G_{tot}=18.$ Dit geeft dus 9
regels in het \bon {games data} venster.
Berg deze gegevens op in {\tt geval2.fma}.

\subsection {Analyse en hypothese voor $G_{tot} = 18$}
Analyseer de nieuwe simulatiegegevens op de manier van sectie~\ref{ana_hyp}  en formuleer
weer hypothese over $u$ en $L$. Zijn de formules die je nu hebt bedacht anders
dan in sectie~\ref{ana_hyp}? Probeer de formules z\'o te schrijven, dat ze niet afhankelijk zijn
van de {\em specifieke} waarde van $G_{tot},$ maar voor elke waarde van
$G_{tot}$ bruikbaar zijn. (Aanwijzing: de modelparameter $G_{tot}$ zal dus
moeten voorkomen in een dergelijke formule.)

\subsection {Scholium} 
In dit gedeelte zullen we proberen de gevonden zaken wiskundig te onderbouwen.
Allereerst proberen we aan te tonen, dat bij $p=\frac12$ het verband tussen $u$
en $G_w$ lineair is.

In onze dataset {\tt geval1.fma} hebben we een compleet overzicht van de kans op
succes bij {\em alle} mogelijke verdelingen van het beginkapitaal. Maar je zou
ook kunnen zeggen, dat we gedurende het spel eigenlijk steeds opnieuw beginnen,
alleen na een herverdeling van het kapitaal! Bekijk
eens de situatie dat wij f 8 hebben en de tegenstander (dus) f 4. Het
resultaat van eenmaal spelen kan resulteren in twee mogelijke situaties:
\begin {enumerate} 
\item We winnen. Wij hebben dan f 9, de tegenstander f3.
\item We verliezen. Wij hebben dan f 7, de tegenstander f5.
\end {enumerate}
Elk van deze gebeurtenissen kunnen plaats vinden met kans $p=\frac12$. Hoe zit
het nu met de kans op succes als we f 8 hebben? Laten we de kans op succes
met f 8 $u_{8}$ noemen, of in het algemeen, de kans op succes met $n$ gulden
$u_n$.

\Opdrachten
\begin {enumerate}
\item Leg met behulp van bovenstaande redenering uit, dat moet gelden
$$ u_{8} = \frac12 u_{7} + \frac12 u_{9} $$
of in het algemeen
$$ u_n = \frac12 u_{n-1} + \frac12 u_{n+1}$$

\item Verifieer of voor de gesimuleerde waarden deze betrekking ongeveer
klopt. 

\item Vervang in de laatste betrekking $u_n$ door $\frac12 u_n + \frac12 u_n$ en
leg uit, dat geldt:
$$u_{n+1} - u_n = u_n - u_{n-1}$$
ofwel
$$\Delta u_n = \Delta u_{n-1}$$
\setcounter {opdrachtctr} {\value {enumi}}
\item Het resultaat van opdracht~\arabic{opdrachtctr} betekent, dat van de rij $u_0,
u_1,\dots,u_n$ de {\em verschilrij} een {\em constante} rij is. Van welk type is
(dus) de rij $u_0, u_1, \dots, u_n$ zelf? 
Leg aan de hand van de formule die je voor de $n$-e term van zo'n rij kent uit,
dat $u_n$ een eerstegraads functie van $n$ is. 
\item Leg uit, dat hiermee is aangetoond, dat voor $p=\frac12$ en $G_{tot} = 12$
het verband tussen $u$ en $G_w$ lineair is.
\item Ga na, dat dezelfde redenering opgaat voor {\em iedere} waarde van
$G_{tot}$.
\setcounter {opdrachtctr} {\value {enumi}}
\end {enumerate}
\newcommand \pushctr {\setcounter {opdrachtctr} {\value {enumi}}}
\newcommand \popctr  {\setcounter {enumi}{\value {opdrachtctr}}} 
Voor de gemiddelde sessielengte $L$ is de redenering iets ingewikkelder, maar
gaat in wezen op dezelfde manier.

\Opdrachten
\begin {enumerate}
\popctr
\item Laat de gemiddelde spellengte bij het bezit van $n$ gulden $L_n$ zijn.
Leg met behulp van bovenstaande redenering uit dat moet gelden
$$ L_{8} =  \frac12 L_{7} +  \frac12 L_{9} + 1 $$
of algemeen
$$ L_n = \frac12 L_{n-1} + \frac12 L_{n+1} + 1$$
\pushctr
\item Verifieer of voor de gesimuleerde waarden deze betrekking ongeveer klopt.
\item Leid uit het resultaat van opdracht~\arabic {opdrachtctr} een betrekking
af tussen twee opeenvolgende termen $\Delta L_n$ en $\Delta 
L_{n-1}$ van de
verschilrij van $L_0, L_1, \dots$
\item Leg uit, dat uit dit resultaat volgt dat de {\em verschilrij van de
verschilrij} een {\em constante} rij is. Wat weet je in zo'n geval van de $n$-e
term van  $L_0, L_1, \dots$ zelf?
\item Wat voor soort functie is $L_n$ van $n$? (lineair, kwadratisch, derde of
hogeregraads, exponentieel, logaritmisch, sinuso"idaal)
Het is in zo'n onderzoek niet ongebruikelijk, dat je in de loop van de tijd op
dezelfde vragen verschillende antwoorden geeft. Men spreekt dan van
{\em voortschrijdend inzicht.} 
\end {enumerate} 

\subsection {Conclusies}

Nu we de hypothesen over het model ook met algebra"ische middelen hebben weten
te verifi"eren kunnen we met een gerust hart antwoord geven op de vragen, die we
aan het begin over ons proces hebben gesteld. Wel moeten we ons er rekenschap
van geven, dat wij een {\em model} hebben bekeken. Onze antwoorden zullen dus
altijd een {\em benadering} zijn. De keten is zo sterk als zijn zwakste schakel:
onze antwoorden zijn nooit beter dan ons model.

Onze conclusies luiden als volgt. Onder de gegeven spelregels geldt voor {\em even
goede} spelers:
\begin {itemize}
\item De kans op een goede afloop voor een speler is {\em op elk moment} gelijk
aan de {\em fractie} die zijn kapitaal uitmaakt van het totale kapitaal.
\item Het aantal spellen dat gemiddeld nog gespeeld moet worden is {\em op elk
moment} gelijk aan het product van de kapitalen van beide spelers. Een klein
puntje: deze kapitalen moeten worden uitgedrukt in de inzet per spel en per
speler.
\end {itemize}

{\Opdrachten}
\begin {enumerate}
\item Als we met $f$ 30,= beginnen en onze tegenstander met $f$ 10,=, wat is dan
onze kans om te winnen? Wat is de gemiddelde sessielengte $L$?
\item We spelen twaalf sessies, waarbij wij steeds met $f$ 30,= beginnen en onze
tegenstander steeds met $f$ 10,=. Hoeveel denk je dat wij na die twaalf sessies
gewonnen hebben?
\end {enumerate}



\section {Een speler beduidend beter, $p>\frac12$}

We herhalen de eerste simulatieset voor het geval dat een der twee spelers
beduidend beter speelt dan de ander.  Als voorbeeld nemen we $p=0.55.$

We simuleren weer met $G_{tot}=12$. Deze keer laten we $G_w$ lopen van 1 tot
11 en er moeten nu 11 regels in het \bon {games data} venster komen.
Ook deze gegevens opbergen ({\tt geval3.fma}). 

Laad {\tt geval3.fma} binnen (\fbt{Window} \fb{2-var...}) en plot \bon {succ}
resp \bon {leng} tegen \bon {stake}.
Geldt het voor $p=0.5$ gevonden functie verband voor \bon {succ} ook hier?
En dat van \bon {leng}?

Het is in dit geval niet zo gemakkelijk om uit de grafische gegevens een
functieverband te "`raden"'. Maar de gevolgde methodiek uit het scholium van de
vorige sectie kan ons wel helpen.

\Opdrachten
\begin {enumerate}
\item Probeer met eenzelfde soort redenering als in de vorige paragraaf $u_n$ 
uit te drukken in $u_{n+1}$ en $u_{n-1}$. Kijk of de waarden van de simulatie 
een beetje kloppen met de gevonden betrekking.
\item Vervang in deze uitdrukking nu $u_n$ door $0.55u_n + 0.45u_n$ en laat
zien, dat geldt:
$$ 0.55 \Delta u_n = 0.45 \Delta u_{n-1}$$
ofwel
$$ \Delta u_n = \frac 9{11} \Delta u_{n-1}$$
Wat voor soort rij is deze verschilrij?
\item Ga na, dat de uitdrukking
$$u_n = a + br^n$$
voor een geschikte keuze van $r$ eenzelfde verschilrij oplevert. Hoe kies je
$r$?
\item Bereken ook de constanten $a$ en $b$ in deze uitdrukking. (Aanwijzing:
$u_0=0$ en $u_{12}=1$.)
\item Controleer de gevonden uitdrukking door deze te plotten in de figuur,
waarin \bon{succ} is uitgezet tegen \bon {stake}.
\item Druk $L_n$ uit in $L_{n-1}$ en $L_{n+1}.$ Verifieer het gevonden verband
aan de simulatiedata. Een uitdrukking vinden voor $L_n$ hoeft niet.
\item (Voor een bonuspunt) Druk {\em voor algemene waarden van $p$} $u_n$ uit in
$u_{n-1}$ en $u_{n+1}$ en bereken de formule voor $u_n$. Hier komt $p$ dus als
{\em modelparameter} nog in voor! Verifieer je resultaat door simulaties met
verscheidene waarden van $p$. 
\end {enumerate}

\section {Toepassing}
(Dit is voor het tweede bonuspunt.) 
Mr. Thorvald heeft een weddenschap aangegaan om een freeze-out te spelen tegen
Mr. Gates. Mr. Gates is weliswaar niet zo'n goede speler (T heeft p=0.55, G
p=0.45), maar is dermate puissant rijk, dat zijn kapitaal gemakshalve op
oneindig gesteld kan worden. Hoe kun je dat simuleren? 

Hoeveel geld moet T meenemen om deze confrontatie met 90\% zekerheid te winnen 
(of liever gezegd, niet te verliezen...)?

Succes!
\end {document}
