Je leest:

Apen, typemachines en abracadabra

Apen, typemachines en abracadabra

Auteurs: en | 16 november 2005

Stel dat we een aap achter een typemachine zetten en dat de aap lukraak op de toetsen begint te slaan. De aap zwaait flink met zijn armen en elke letter heeft daardoor dezelfde kans om geraakt te worden. Hoe lang duurt het gemiddeld tot de aap ABRACADABRA typt? En duurt dat langer dan ABCDEFGHIJK of misschien juist korter?

Intuïtief denk je waarschijnlijk dat dit niks uit maakt, ABRACADABRA en ABCDEFGHIJK bestaan allebei uit elf letters en elke letter heeft dezelfde kans, dus het zal vast even lang duren om deze woorden te maken. Maar in ABRACADABRA zit herhalingen: *ABRA*CAD*ABRA* en *A*BRACADABR*A*. In het woord ABCDEFGHIJK zit zo’n herhaling niet. Dat is een belangrijk verschil. De wiskundige oplossing van dit probleem komt uit de theorie van eerlijke kansspelen, ofwel de martingalen.

Martingalen en gokkers

De martingaal is een begrip uit de kansrekening: het is een proces waarbij de verwachte uitkomst op een bepaald tijdstip niet afhangt van wat er daarvoor allemaal is gebeurd. Het nieuwe verwachte resultaat is de huidige waarde van het proces; wat er daarvoor allemaal is gebeurd doet er niet toe. Klinkt dit lastig? Denk dan maar aan het gooien van een muntje, ook al gooi je tien keer achter elkaar kop, bij de elfde keer gooien is de kans op munt nog steeds 50%. Martingalen komen ook voor in het dagelijks leven: beurskoersen en het weer zijn te zien als voorbeelden. Omdat martingalen niet te voorspellen zijn met voorkennis, is de beste schatting voor morgen bij een martingaal dan ook de waarde van vandaag.

‘Martingaal’ was oorspronkelijk de naam voor een populaire gokstrategie in het 18de eeuwse Frankrijk. De eenvoudige strategie was bedoeld voor een gokspel waarbij steeds een munt wordt gegooid. De gokker verliest als het kop is, en wint zijn inzet dubbel terug als het munt is. De martingaal-strategie van de gokker was om elke keer als hij verloor, zijn inzet te verdubbelen. Zodra er dan een keer munt werd gegooid, had hij in een klap al zijn verliezen terug plus als extra winst zijn eigen inzet. Met deze methode win je uiteindelijk altijd, maar het enige nadeel is dat je naar verwachting zowel oneindig veel tijd als oneindig veel geld nodig hebt. En als de gokker een paar keer achter elkaar pech heeft, dan is zijn geld toch zo op. Inzetten op zwart of rood bij een roulettetafel is eigenlijk hetzelfde als op een muntje gokken. Ook hier kan je dus alleen maar winnen van de bank als je héél veel geld en tijd hebt…

Stoppen!

Om te weten of die aap nu eerst ABRACADABRA of ABCDEFGHIJK zal typen, hebben we nog iets nodig: stoptijden. De stoptijd is, zoals de naam al zegt, de tijd waarop je stopt met je experiment. De stoptijd mag alleen afhangen van het verleden en het heden. Dat betekent dat je een beslissing moet maken met de informatie die je op dat moment hebt en dat je geen informatie uit de toekomst hoeft te gebruiken. Denk maar aan een gokspel met een munt: je kunt besluiten om te stoppen als er drie keer kop gegooid is. Je keuze kan alleen afhangen van wat er tot dan toe is gebeurd: je kunt niet besluiten om weg te gaan vóór je verliest.

Er bestaat een wiskundige stelling, die zegt dat er iets speciaals aan de hand is voor martingalen en stoptijden. Onder bepaalde voorwaarden geldt dat de verwachte uitkomst van een martingaal op een stoptijd gelijk is aan de verwachte waarde van deze martingaal op tijdstip 0. Deze stelling kan gebruikt worden om te bewijzen dat een gokker met een eindige hoeveelheid geld en tijd nooit kan winnen van het casino bij een kop-munt-spel.

Abracadabra

Terug naar de apen: we gaan om de dierentuin spannender te maken een gokspel organiseren bij de typende aap. Precies voordat de aap een nieuwe toets aanslaat, komt een gokker binnen. Hij zet 1 euro in op de volgende letter die de aap zal typen. Hij verliest als de aap GEEN A typt en hij wint maar liefst 26 euro (gelijk aan het aantal letters in het alfabet) als de aap wel een A typt. Als de gokker wint, dan gaat hij door naar de volgende ronde. Als de aap daarna als volgende letter een B typt, dan wint de gokker maar liefst 262 euro. Als de aap GEEN B typt, dan verliest de gokker nu 26 euro. De gokker gaat weer door als hij gewonnen heeft. Nu verliest hij 262 euro als de aap GEEN R typt en wint hij 263 euro als de aap wel een R typt. Zo gaat het spel door tot de aap ABRACADABRA heeft getypt, of tot de gokker een keer verliest. Vanaf het moment dat de eerste gokker begint, komt er bij elke aanslag een nieuwe gokker bij, die precies ditzelfde gokspel speelt.

De aap achter de typemachine: hier heeft hij pas een blaadje of drie volgetypt…

Het tijdstip waarop de aap ABRACADABRA heeft getypt is precies zo’n stoptijd die we eerder beschreven. Wat eenvoudig rekenwerk laat zien, dat elke speler die verloren heeft voor deze stoptijd T, precies 1 euro heeft moeten betalen. De winst die de bank nu heeft na n rondes noemen we Wn. Je kunt laten zien dat deze winst Wn precies een martingaal is. Dit betekent dat we de stelling met de martingaal en de stoptijd kunnen gebruiken voor ABRACADABRA! Met andere woorden: de verwachte winst voor de bank op tijdstip T is gelijk aan de verwachte winst op tijdstip 0.

Een eenvoudig voorbeeld laat het verschil zien tussen woorden mét en zonder herhaling. Stel dat je een typemachine hebt met alleen de letters A en B. Hoe lang duurt het dan voor je AAA, ABA of AAB typt?

Je wilt AAA:

Je typt AB: helemaal opnieuw beginnen Je typt AAB: helemaal opnieuw beginnen

Je wilt ABA:

Je typt AA: A bewaren en hopen op een B Je typt ABB: helemaal opnieuw beginnen

Je wilt AAB:

Je typt AB: helemaal opnieuw beginnen Je typt AAA: bewaren en hopen op een B

Het is het makkelijkste om AAB – het woord zonder herhalingen – te typen, dit duurt naar verwachting 8 aanslagen. ABA is iets moeilijker en zal 9 aanslagen duren. AAA kost meer moeite en zal gemiddeld pas na 13 aanslagen komen.

Laten we eens kijken welke spelers er nog in het spel zijn op stoptijd T: het moment dat de aap het magische woord ABRACADABRA heeft getypt. De grote winnaar is de speler die ABRACADABRA helemaal heeft volbracht. Hij krijgt maar liefst 2611 euro van de bank! Dan is er de speler die op dat moment het woord ABRA heeft gemaakt, hij krijgt van de bank 264 euro. Dan is er nog een speler die op tijdstip T alleen A heeft gemaakt en die van de bank 26 euro krijgt. Alle andere spelers hebben verloren en leveren de bank elk 1 euro op. Er zijn T aanslagen geweest, dus de bank heeft in totaal T euro van de gokkers gekregen.

We weten dat de verwachte winst van de bank op tijdstip T gelijk is aan de winst aan het begin. Aan het begin heeft de bank niks, dus op tijdstip T verwachten dat de bank precies 0 euro heeft. De bank heeft T euro gekregen als inzet van de gokkers en de bank moet 2611 + 264 + 26 euro uitbetalen. Dus de verwachte waarde van T – 2611 – 264 – 26 is gelijk aan 0. Dus de verwachte waarde van T is 2611 + 264 + 26. Dus we verwachten dat de aap 2611 + 264 + 26 letters zal aanslaan voordat hij ABRACADABRA typt.

Op dezelfde manier kunnen we berekenen dat het naar verwachting 2611 aanslagen zal duren tot de aap ABCDEFGHIJK zal typen, omdat daarbij aan het einde maar één winnende speler over is. Dus, gemiddeld genomen, duurt ABRACADABRA langer om te typen dan ABCDEFHIJK en dat komt niet doordat het een magisch woord is! De moraal: intuïtie kan een slechte raadgever zijn en zelfs een aap achter een typemachine kan interessante wiskunde opleveren!

Dit artikel is gebaseerd op een opgave uit het boek ‘Probability with martingales’ van David Williams.

Zie ook:

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 16 november 2005

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.