A.S.: Yep, blijkbaar is het enkelvoud van ‘dobbelsteen’ ‘dobbelsteen’. 😉
Er circuleert een lastige programmeeropdracht op het internet die, zoals je misschien al had kunnen raden uit mijn poging tot een pragmatische titel, als volgt kan worden geformaliseerd:
Geef een functie die een uniform willekeurig getal tussen 1 en 5 (inclusief) teruggeeft, ontwerp een functie die een uniform willekeurig getal tussen 1 en 7 (inclusief) teruggeeft.
Als het snijvlak van algoritmen en statistiek uw ding is, ga dan gerust uw gang! Een extra uitdaging is om je algoritme begrensd in tijd te maken. Ik vond dit een leuke oefening, alleen realiseerde ik me dat hier fundamentele beperkingen in het spel zijn.
Natuurlijk wordt hier met een dobbelsteen een perfect uniforme toevalsgenerator bedoeld, die alleen in theorie bestaat. Dobbelstenen in de echte wereld worden zodanig beheerst door natuurwetten en onvolkomenheden in de omgeving, dat zij slechts een benadering (zij het een goede) zijn van dit abstracte model.
Een onbegrensde oplossing
Laten we eens kijken naar een familie van onbegrensde algoritmen. Om een toevalsgenerator te maken die minstens 7 uitkomsten heeft, moeten we de 5-zijdige dobbelsteen minstens tweemaal gooien. Twee keer gooien geeft 5^2=25 mogelijke uitkomsten, en hoewel dit geen factor 7 is, kunnen we de eerste 21 uitkomsten toewijzen aan 7 groepen van gelijke grootte 3. Als we echter op een van de resterende 4 uitkomsten uitkomen, dan moet de procedure opnieuw beginnen. We kunnen niet eenvoudigweg één van deze 4 ongelukkige eindtoestanden aan een uitgang toekennen, omdat dit de uniforme willekeurigheid in het gedrang brengt.
In de bovenstaande grafiek stellen de cirkels “toestanden” van ons programma voor, en de tekst erbinnen is de meest recente waarde van de gegooide dobbelsteen. De groene vakjes geven dan de uitvoer weer die we toewijzen afhankelijk van de eindtoestand (= nadat de dobbelsteen twee keer is gegooid). 84% van de tijd krijgen we een uitgang na twee worpen en eindigt het algoritme. Zoals je ziet, is er een lus aanwezig en is het algoritme onbegrensd. Dit betekent dat voor elk geheel getal, hoe groot ook, er een kleine maar niet nul kans is dat het totaal aantal worpen dat aantal zal overschrijden om één uitvoerwaarde te berekenen. Real-time toepassingen met strikte tijdseisen zijn dus uit den boze, tenzij je bereid bent compromissen te sluiten op de statistische nauwkeurigheid van het algoritme.
Een variant van deze oplossing gooit aanvankelijk tot drie dobbelstenen alvorens opnieuw te beginnen: dit levert 5^3=125 eindtoestanden op, en we kunnen maximaal 119 daarvan toewijzen aan 7 groepen van gelijke grootte 17. Nu is er een kans van 95,2% om te eindigen na maximaal drie worpen. Merk op dat we gemiddeld minder keren moeten rollen dan voorheen (280/119 ≈ 2.35 versus 50/21 ≈ 2.38), omdat we meestal na de eerste twee rollen al een shortcut kunnen nemen, en deze tussenliggende toestanden direct kunnen mappen naar een uitgang. Dit gemiddelde aantal worpen blijft dalen naarmate we de trend voortzetten.
Als u bekend bent met informatietheorie, bedenk dan dat één worp met een 5-zijdige dobbelsteen (= rand5) log2(5) ≈ 2,32 bits aan informatie oplevert, en één worp met een 7-zijdige dobbelsteen (= rand7) log2(7) ≈ 2,81 bits aan informatie oplevert. Het blijkt dat we in het limietgeval slechts log(7)/log(5) ≈ 1.21 oproepen van rand5 nodig hebben voor elke rand7 waarde die we willen verkrijgen. De exacte implementatie die willekeurig dicht bij deze limiet werkt is nogal ingewikkeld en valt buiten het bereik van dit artikel. We zouden toestandsinformatie moeten opslaan tussen meerdere aanroepen van rand7, en het algoritme dat ik in gedachten heb is niet alleen nog steeds onbegrensd in tijd, maar ook in geheugen. Ik nodig u van harte uit mij te informeren over een methode die dit laatste probleem oplost!
Een begrensde oplossing
Er bestaat niet zoiets als een begrensd algoritme dat een volkomen uniforme willekeurige waarde tussen 1 en 7 berekent, gegeven een willekeurige generator tussen 1 en 5 alleen. Beschouw de familie van onbegrensde oplossingen hierboven. Zoals ik al aangaf, zal er op elk punt altijd een aantal “overgebleven” toestanden zijn (variërend van 1 tot 6) waardoor het algoritme opnieuw moet beginnen. Dit komt omdat 5 en 7 priemgetallen zijn, en geen macht van 5 ooit een veelvoud kan zijn van 7. Hoe verleidelijk het ook is om de kleine stelling van Fermat te gebruiken, dergelijke pogingen zullen resulteren in off-by-one fouten, omdat de fundamentele getaltheorie een begrensde oplossing in deze familie onmogelijk maakt.
Je zou er terecht op kunnen wijzen dat het aantal eindtoestanden niet altijd een macht van 5 is, bijvoorbeeld in het geval van ’tot drie worpen’ waar we na twee worpen al een shortcuts kunnen nemen. Misschien kunnen we het toestandsdiagram zo inrichten dat er een begrensd algoritme ontstaat met paden van variabele lengte en 7n eindtoestanden? Maar overweeg het volgende:
- Deze eindtoestanden zullen niet even waarschijnlijk zijn omdat niet elk pad even lang is (= het aantal aanroepen van rand5).
- We kunnen de boom heel gemakkelijk uitbreiden om elk pad even lang te maken, door rand5 nutteloos een passend aantal keren aan te roepen telkens als we in een voorbarige eindtoestand zijn. Nu wordt het aantal eindtoestanden weer een macht van 5, en alle eindtoestanden zijn even waarschijnlijk.
Natuurlijk is dit geen formeel bewijs, maar ik hoop u enige intuïtie over het probleem te hebben gegeven. Zoals we zien, kan een probleem soms heel realistisch lijken, om dan op wiskundige feiten als deze te stuiten. Kun je na deze analyse nagaan of het mogelijk is een 8-zijdige dobbelsteen te simuleren uitgaande van een 4-zijdige dobbelsteen?