Monte-Carlo simulaties

In dit artikel worden enkele eenvoudige voorbeelden van Monte-Carlo simulaties behandeld, beginnend met het klassieke voorbeeld van het berekenen van de waarde van $\pi$ door middel van het gooien van pijltjes.

Het schatten van pi

Stel dat we een vierkant bord hebben waarin een kwart cirkel is getekend. We gooien vervolgens pijltjes naar het bord en houden bij of elk pijltje binnen of buiten de kwart cirkel valt. Na veel worpen berekenen we de verhouding tussen de pijltjes binnen de cirkel en het totale aantal worpen.

Uitgaande van het feit dat onze pijltjes uniform over het vierkant zijn verdeeld, zou deze verhouding volgens de wet van de grote getallen moeten convergeren naar de verhouding tussen de oppervlakte van de kwart cirkel $A{circ}$ en het volledige vierkant $A{square}$.

Bij een vierkant met een zijde van 1 is dit:

$$\frac{A{circ}}{A{square}}=\frac{\pi/4}{1}=\frac{\pi}{4}$$

Hieruit volgt:

$$\pi \approx 4 \times \frac{\text{hits binnen}}{\text{totaal aantal worpen}}$$

De code hiervoor is zeer eenvoudig:

const total = Number(samples.value);
let inside = 0;
for (let i = 0; i < total; i++) {
  const x = Math.random();
  const y = Math.random();
  const inCircle = x * x + y * y <= 1;
  if (inCircle) inside++;
}
estimateValue = 4 * inside / total;

Men zal merken dat de schatting relatief onnauwkeurig is, zelfs bij 1000 samples. Om $\pi$ met redelijke betrouwbaarheid tot vier decimalen achter de komma te schatten, zijn ongeveer 10 miljard samples nodig.

In het algemeen neemt bij onafhankelijke pogingen zoals deze de typische steekproeffout af in proportie tot $1/\sqrt{N}$, waarbij $N$ het aantal pogingen is. Dit betekent dat om de fout te halveren, vier keer zoveel samples nodig zijn.

Hoewel het schatten van $\pi$ triviaal lijkt, is het een voorbeeld van een belangrijke klasse problemen waarvoor Monte-Carlo simulaties worden gebruikt: numerieke integratie. Onze simulatie schat de oppervlakte onder de curve van de kwart cirkel, wat een bepaalde integraal is.

Veel integralen zijn analytisch zeer moeilijk op te lossen. Monte-Carlo methoden zijn bijzonder nuttig voor hoogdimensionale integralen, waarbij andere numerieke methoden prohibitief duur kunnen worden.

Combinatorische simulatie - het spel SET

Een veelvoorkomend gebruik van Monte-Carlo methoden is het schatten van complexe combinatorische berekeningen. Deze hebben vaak geen analytische oplossingen, en het opsommen van alle opties is ondoenlijk vanwege de omvang van de getallen. Als voorbeeld nemen we het spel SET. Elke SET-kaart heeft vier eigenschappen:

  • Aantal vormen (1, 2 of 3)
  • Kleur (Rood, Groen of Paars)
  • Vormtype (Ovaal, Ruit of Kronkel)
  • Arcering (Leeg, Gestreept of Massief)

Het doel is om een "set" te vinden: drie kaarten die voor elke eigenschap afzonderlijk ofwel allemaal hetzelfde, ofwel allemaal verschillend zijn.

Een interessante vraag is: gegeven een vers geschud SET-dek, wat is de kans dat de eerste 12 getrokken kaarten geen enkele set bevatten? Deze vraag is moeilijk te beantwoorden zonder computer.

Het is eenvoudig om het aantal manieren te berekenen om een hand van 12 kaarten te delen uit een dek van 81:

$$\binom{81}{12}=70.724.320.184.700$$

Maar hoeveel van deze handen bevatten geen sets? Het controleren van 70 biljoen SET-handen zou zeer lang duren en er is geen eenvoudige telformule. Donald Knuth heeft aan dit probleem gewerkt en een programma ontwikkeld (setset-all) dat vaststelde dat er 2.284.535.476.080 van zulke handen zijn. Daarom is het antwoord:

$$\frac{2.284.535.476.080}{70.724.320.184.700} \approx 0,0323$$

Er is dus een kans van 3,23% dat een willekeurig getrokken hand van 12 kaarten geen set bevat.

Met een Monte-Carlo simulatie kunnen we dit beantwoorden met relatief weinig inspanning, zonder diepgaande kennis van de wiskundige eigenschappen van SET. We kunnen de volgende pseudocode gebruiken:

  1. Stel $C = 0$
  2. Voer $N$ keer uit:
  • Trek een willekeurige hand van 12 kaarten uit een nieuw dek.
  • Tel het aantal sets in de hand.
  • Als er geen sets zijn: $C = C + 1$
  1. Geschatte kans $= C / N$

Na 10 miljoen gesimuleerde trekkingen kwam ik uit op 0,0323, wat zeer dicht bij het werkelijke antwoord ligt. De Monte-Carlo benadering stelt ons in staat om complexe problemen eenvoudig op te lossen. Voor een hand van 15 kaarten zou de zoekruimte enorm toenemen (ongeveer 100x groter dan bij 12 kaarten), maar voor een Monte-Carlo simulatie passen we slechts één parameter aan om een betrouwbaar antwoord te krijgen (ongeveer 0,00037) [3].

Pensioenprognoses

Monte-Carlo simulaties zijn alomtegenwoordig bij projecties voor pensioenportefeuilles. Stel dat iemand met een totaalbedrag van 1 miljoen dollar wil pensioneren en jaarlijks 30.000 dollar wil opnemen voor levensonderhoud. Zou dat werken?

Voor eenvoud kijken we naar twee factoren: portfolio-rendement en inflatie. Bij een naïvme schatting met gemiddelde waarden gaan we uit van een gemiddeld jaarlijks rendement van 4% en een gemiddelde jaarlijkse inflatie van 2% [4].

Als we het rendement aanduiden als $r=0,04$ en de inflatie als $q=0,02$, dan is het reële rendement per jaar:

$$r^{\mathrm{real}}=\frac{1+r}{1+q}-1 \approx 0,0196$$

Beginnend met \$1.000.000, hebben we aan het einde van het jaar \$1.019.600, waarna we \$30.000 opnemen [5], waardoor we eindigen met \$989.600. Op deze manier raakt het geld na ongeveer 55 jaar op, wat suggereert dat iemand die op 65-jarige leeftijd met pensioen gaat, veilig is.

Dit is echter zeer simplistisch. Alleen uitgaan van gemiddelde rendementen is riskant omdat ze de realiteit slecht weergeven. De volgorde van rendementen is cruciaal; een slecht jaar (-10%) gevolgd door een geweldig jaar (+18%) resulteert in een gemiddelde van 4%, maar levert aanzienlijk minder geld op dan twee opeenvolgende jaren van +4%.

Ook inflatie is onvoorspelbaar en soms gecorreleerd met portfolio-rendementen. Naarmate we meer factoren toevoegen (variantie in jaarlijkse opnames, diverse portfolio's van aandelen, obligaties, vastgoed, levensverwachting, onvoorziene gebeurtenissen, wijzigingen in belastingwetgeving etc.), wordt een enkele gemiddelde schatting steeds onbetrouwbaarder.

Dit is waarom Monte-Carlo simulaties populair zijn in dit domein: door te putten uit redelijke distributies op basis van historische data, kan een simulatie een miljoen verschillende scenario's doorlopen. Men kan dan bijvoorbeeld bepalen wat de kans is dat het geld opraakt vóór het overlijden.

Uit simulaties blijkt vaak dat een plan risicovoller is dan een gemiddelde aanname doet vermoeden. Bijvoorbeeld, als iemand plant voor 25 jaar pensioen, kan een kans van ~30% dat de fondsen onvoldoende zijn, een reden zijn om de plannen aan te passen (zoals een soberdere levensstijl of het veiligstellen van extra middelen).

Pensioenprognoses zijn slechts één van de vele financiële en economische toepassingen. Bedrijfsomzetprognoses, groeiprognoses en beursintroductieprijzen maken ook gebruik van Monte-Carlo simulaties om schattingen met redelijke foutmarges te verkrijgen.

***

Code Alle code voor de exploraties in dit artikel is beschikbaar op GitHub.

Voetnoten [1] Hoewel deze technieken conceptueel veel eerder begrepen werden, is het niet verrassend dat hun eerste echte toepassingen samenvielen met de ontwikkeling van de eerste digitale computers, aangezien Monte-Carlo simulaties profiteren van een groot aantal pogingen voor een redelijke nauwkeurigheid.

[2] Het antwoord is: drie lege rode ruiten, drie massieve paarse ovalen, drie gestreepte groene kronkels. Let op dat deze drie kaarten voor elk van de 4 SET-eigenschappen ofwel allemaal hetzelfde, ofwel allemaal verschillend zijn.

[3] Voor hetzelfde aantal pogingen heeft deze schatting een grotere relatieve onzekerheid dan de schatting voor 12 kaarten, omdat we veel minder vaak een hand zonder set tegenkomen.

[4] Voor de voorbeelden in dit artikel gebruiken we reële dollars (de waarde van het geld van vandaag). We nemen aan dat de jaarlijkse opname van \$30.000 niet verandert en passen de inflatie in plaats daarvan toe op de portfolio zelf.

[5] Geavanceerdere simulaties zouden ons in staat stellen deze parameters te beheren; bijvoorbeeld of de onttrekkingsfondsen aan het begin of einde van elk jaar worden opgenomen, of op maandelijkse basis worden verdeeld.