A.S.: Jep, tilsyneladende er singular af “terning” “die”. 😉
En vanskelig programmeringsopgave har været i omløb på internettet, der, som du måske har gættet ud fra mit forsøg på en pragmatisk titel, kan formaliseres på følgende måde:
Givet en funktion, der returnerer et ensartet tilfældigt tal mellem 1 og 5 (inklusive), design en funktion, der returnerer et ensartet tilfældigt tal mellem 1 og 7 (inklusive).
Hvis krydsfeltet mellem algoritmer og statistik er noget for dig, er du velkommen til at give den et forsøg! En ekstra udfordring er at gøre din algoritme afgrænset i tid. Jeg fandt dette som en sjov øvelse, blot for at indse, at der er fundamentale begrænsninger på spil her.
Selvfølgelig betyder en terning her en perfekt ensartet tilfældig generator, som kun eksisterer i teorien. Terninger i den virkelige verden er styret af naturlove og miljømæssige ufuldkommenheder på en sådan måde, at de kun er en tilnærmelse (om end en god en) af denne abstrakte model.
En ubegrænset løsning
Lad os se på en familie af ubegrænsede algoritmer. For at skabe en tilfældighedsgenerator, der har mindst 7 udfald, skal vi kaste den 5-sidede terning mindst to gange. Ved at kaste den to gange opstår der 5^2=25 mulige udfald, og selv om dette ikke er en faktor 7, kan vi tildele de første 21 udfald til 7 grupper af samme størrelse 3. Hvis vi ender med at få et af de resterende 4 resultater, må vi starte proceduren forfra. Vi kan ikke blot tildele en af disse 4 uheldige sluttilstande til et output, da dette vil ødelægge den ensartede tilfældighedsegenskab.
I ovenstående diagram repræsenterer cirklerne “tilstande” i vores program, og teksten indeni er den seneste værdi af den kastede terning. De grønne felter repræsenterer så det output, vi tildeler afhængigt af sluttilstanden (= efter at have kastet terningen to gange). I 84 % af tilfældene får vi et output efter to kast, og algoritmen afsluttes. Som du kan se, er der en løkke til stede, og den gør algoritmen ubegrænset. Det betyder, at der for hvert heltal, uanset hvor stort det er, er der en lille, men ikke-nul sandsynlighed for, at det samlede antal kast vil overstige dette antal for at beregne én udgangsværdi. Realtidsanvendelser med strenge tidskrav er derfor udelukket, medmindre man er villig til at gå på kompromis med algoritmens statistiske nøjagtighed.
En variant af denne løsning ruller i første omgang op til tre terninger, før den genstartes: Dette skaber 5^3=125 sluttilstande, og vi kan højst tildele 119 af dem til 7 grupper af samme størrelse 17. Nu er der 95,2 % sandsynlighed for at afslutte efter højst tre kast. Bemærk, at vi i gennemsnit skal kaste færre gange end tidligere (280/119 ≈ 2,35 mod 50/21 ≈ 2,38), fordi vi for det meste allerede efter de to første kast kan tage en genvej og direkte mappe disse mellemtilstande til et output. Dette gennemsnitlige antal kast bliver ved med at falde, efterhånden som vi fortsætter tendensen.
Hvis du er bekendt med informationsteori, så tænk på, at et kast med en 5-sidet terning (= rand5) genererer log2(5) ≈ 2,32 bits information, og et kast med en 7-sidet terning (= rand7) genererer log2(7) ≈ 2,81 bits information. Det viser sig, at vi i det begrænsende tilfælde kun har brug for log(7)/log(5) ≈ 1,21 opkald af rand5 for hver rand7-værdi, vi ønsker at få. Den nøjagtige implementering, der fungerer vilkårligt tæt på denne grænseværdi, er temmelig kompliceret og ligger uden for rammerne af denne artikel. Vi ville være nødt til at gemme tilstandsinformationer mellem flere kald af rand7, og den algoritme, jeg har i tankerne, er ikke kun stadig ubegrænset i tid, men også i hukommelse. Jeg inviterer dig gerne til at informere mig om en metode, der løser sidstnævnte problem!
En afgrænset løsning
Der findes ikke en afgrænset algoritme, der beregner en perfekt ensartet tilfældig værdi mellem 1 og 7, givet en tilfældighedsgenerator, der kun har en værdi mellem 1 og 5. Overvej familien af ubegrænsede løsninger ovenfor. Som jeg har antydet, vil der ved hvert punkt altid være en mængde “resttilstande” (fra 1 til 6), som får algoritmen til at starte forfra. Det skyldes, at 5 og 7 er primtal, og at ingen potens af 5 nogensinde kan være et multiplum af 7. Hvor fristende det end måtte være at bruge Fermats lille sætning, vil sådanne forsøg resultere i fejl af en til en, da grundlæggende talteori gør en afgrænset løsning i denne familie umulig.
Du kan med rette påpege, at antallet af sluttilstande ikke altid er en potens af 5, f.eks. i tilfældet med “op til tre ruller”, hvor vi kan tage genveje allerede efter to ruller. Måske kunne vi arrangere tilstandsdiagrammet således, at vi skaber en afgrænset algoritme med stier af variabel længde og 7n sluttilstande? Overvej dog følgende:
- Disse sluttilstande vil ikke være lige sandsynlige, fordi ikke alle stier har samme længde (= antal rand5-kald).
- Vi kan meget let udvide træet, så alle stier bliver lige lange, ved unødigt at kalde rand5 et passende antal gange, hver gang vi er ved en for tidlig sluttilstand. Nu bliver antallet af sluttilstande igen en potens af 5, og alle sluttilstande er lige sandsynlige.
Dette er naturligvis ikke et formelt bevis, men jeg håber at have givet dig en vis intuition om problemet. Som vi ser, kan et problem nogle gange virke meget realistisk, for så at snuble over matematiske kendsgerninger som disse. Kan du efter denne analyse regne ud, om det er muligt at simulere en 8-sidet terning med udgangspunkt i en 4-sidet terning?