A.S.: Japp, tydligen är singularis av ”dice” ”die”. 😉
En knepig programmeringsuppgift har cirkulerat på Internet som, som ni kanske har gissat av mitt försök till en pragmatisk titel, kan formaliseras på följande sätt:
Genom en funktion som returnerar ett enhetligt slumpmässigt tal mellan 1 och 5 (inklusive), konstruera en funktion som returnerar ett enhetligt slumpmässigt tal mellan 1 och 7 (inklusive).
Om skärningspunkten mellan algoritmer och statistik är något för dig är du välkommen att prova! En extra utmaning är att göra din algoritm bunden i tid. Jag tyckte att detta var en rolig övning, bara för att inse att det finns grundläggande begränsningar som spelar in här.
En tärning här betyder naturligtvis en perfekt enhetlig slumpgenerator som bara existerar i teorin. Tärningar i den verkliga världen styrs av naturlagar och miljöimperfektioner på ett sådant sätt att de bara är en approximation (om än en bra sådan) av denna abstrakta modell.
En obegränsad lösning
Låt oss titta på en familj av obegränsade algoritmer. För att skapa en slumpgenerator som har minst 7 utfall måste vi kasta den femsidiga tärningen minst två gånger. Genom att kasta den två gånger skapas 5^2=25 möjliga utfall, och även om detta inte är en faktor 7 kan vi tilldela de första 21 utfallen till 7 grupper av samma storlek 3. Om vi hamnar på ett av de återstående 4 utfallen måste vi dock börja om på nytt. Vi kan inte helt enkelt tilldela något av dessa 4 olyckliga sluttillstånd till ett utfall, eftersom detta kommer att förstöra den enhetliga slumpmässiga egenskapen.
I diagrammet ovan representerar cirklarna ”tillstånd” i vårt program, och texten inom dem är det senaste värdet av den kastade tärningen. De gröna rutorna representerar sedan det utdata vi tilldelar beroende på sluttillståndet (= efter att tärningen kastats två gånger). I 84 % av fallen får vi ett resultat efter två kast och algoritmen avslutas. Som du kan se finns det en slinga som gör algoritmen obegränsad. Detta innebär att för varje heltal, oavsett hur stort det är, finns det en liten men inte noll sannolikhet för att det totala antalet kast kommer att överstiga detta antal för att beräkna ett utdatavärde. Tillämpningar i realtid med strikta tidskrav är därför uteslutna, om man inte är villig att kompromissa med algoritmens statistiska noggrannhet.
En variant av den här lösningen rullar inledningsvis upp till tre tärningar innan den startar om: detta skapar 5^3=125 sluttillstånd, och vi kan tilldela högst 119 av dem till 7 grupper av samma storlek 17. Nu finns det en sannolikhet på 95,2 % att man kommer att sluta efter högst tre kast. Observera att vi måste kasta färre gånger i genomsnitt än tidigare (280/119 ≈ 2,35 jämfört med 50/21 ≈ 2,38), eftersom vi för det mesta redan efter de två första kasten kan ta en genväg och direkt mappa dessa mellanliggande tillstånd till en utgång. Detta genomsnittliga antal kast fortsätter att sjunka när vi fortsätter trenden.
Om du är bekant med informationsteori, tänk då på det faktum att ett kast med en 5-sidig tärning (= rand5) genererar log2(5) ≈ 2,32 bitar information, och ett kast med en 7-sidig tärning (= rand7) genererar log2(7) ≈ 2,81 bitar information. Det visar sig att i gränsfallet behöver vi bara log(7)/log(5) ≈ 1,21 ringar av rand5 för varje rand7-värde som vi vill få fram. Den exakta implementeringen som fungerar godtyckligt nära denna gräns är ganska komplicerad och ligger utanför ramen för denna artikel. Vi skulle behöva lagra tillståndsinformation mellan flera anrop av rand7, och den algoritm jag har i åtanke är inte bara fortfarande obegränsad i tid utan också i minne. Jag bjuder gärna in dig att informera mig om en metod som löser det sistnämnda problemet!
En begränsad lösning
Det finns ingen begränsad algoritm som beräknar ett perfekt enhetligt slumpmässigt värde mellan 1 och 7, givet en slumpgenerator som endast har ett värde mellan 1 och 5. Betrakta familjen av obundna lösningar ovan. Som jag har antytt kommer det vid varje punkt alltid att finnas en mängd ”överblivna” tillstånd (som varierar mellan 1 och 6) som gör att algoritmen måste starta om. Detta beror på att 5 och 7 är primtal, och ingen potens av 5 kan någonsin vara en multipel av 7. Hur frestande det än kan vara att använda Fermats lilla sats kommer sådana försök att resultera i fel av en till en, eftersom grundläggande talteori omöjliggör en avgränsad lösning i denna familj.
Du kan med rätta påpeka att antalet sluttillstånd inte alltid är en potens av 5, t.ex. i fallet med ”upp till tre ruljangningar” där vi kan ta genvägar redan efter två ruljangningar. Kanske kan vi ordna tillståndsdiagrammet så att vi skapar en avgränsad algoritm med vägar av varierande längd och 7n sluttillstånd? Tänk dock på följande:
- Dessa sluttillstånd kommer inte att vara lika sannolika eftersom inte varje väg har samma längd (= antal rand5-anrop).
- Vi kan mycket enkelt utvidga trädet så att varje väg blir lika lång, genom att i onödan anropa rand5 ett lämpligt antal gånger närhelst vi befinner oss i ett för tidigt sluttillstånd. Nu blir antalet sluttillstånd en potens av 5 igen, och alla sluttillstånd är lika sannolika.
Det här är naturligtvis inget formellt bevis, men jag hoppas att jag har gett dig en viss intuition om problemet. Som vi ser kan ett problem ibland verka mycket realistiskt, bara för att snubbla över matematiska fakta som dessa. Kan du efter denna analys räkna ut om det är möjligt att simulera en 8-sidig tärning med utgångspunkt från en 4-sidig tärning?