Simulating a 7-sided die from a 5-sided die

A.S.: Yep, apparently the singular of 'dice’ is 'die’. 😉

Po Internecie krążyło podchwytliwe zadanie programistyczne, które, jak można się domyślić po mojej próbie pragmatycznego tytułu, można sformalizować w następujący sposób:

Given a function that returns a uniformly random number between 1 and 5 (inclusive), design a function that returns a uniformly random number between 1 and 7 (inclusive).

Jeśli skrzyżowanie algorytmów i statystyki to twój rodzaj rzeczy, nie krępuj się i spróbuj! Dodatkowym wyzwaniem jest sprawienie, by twój algorytm był ograniczony w czasie. Uważam to za zabawne ćwiczenie, ale zdałem sobie sprawę, że istnieją tu fundamentalne ograniczenia.

Oczywiście, kość oznacza tu idealnie jednolity generator losowy, który istnieje tylko w teorii. Kości rzeczywistego świata są rządzone przez naturalne prawa i niedoskonałości środowiska w taki sposób, że są tylko przybliżeniem (choć dobrym) tego abstrakcyjnego modelu.

Nieograniczone rozwiązanie

Przyjrzyjrzyjmy się rodzinie nieograniczonych algorytmów. Aby stworzyć generator losowy, który ma co najmniej 7 wyników, będziemy musieli rzucić pięcioboczną kością co najmniej dwa razy. Rzucenie jej dwa razy daje 5^2=25 możliwych wyników, i chociaż nie jest to współczynnik 7, możemy przypisać pierwsze 21 wyników do 7 grup o równej wielkości 3. Jeśli skończymy na jednym z pozostałych 4 wyników jednak, a następnie procedura musi rozpocząć się od nowa. Nie możemy po prostu przypisać żadnego z tych 4 pechowych stanów końcowych do wyjścia, ponieważ to zepsuje własność jednorodnej losowości.

Na powyższym wykresie kółka reprezentują „stany” naszego programu, a tekst w środku jest ostatnią wartością rzutu kością. Zielone pola reprezentują wyjście, które przypisujemy w zależności od stanu końcowego (= po dwukrotnym potoczeniu kością). W 84% przypadków po dwóch rzutach otrzymujemy wyjście i algorytm się kończy. Jak widać, obecna jest pętla, która powoduje, że algorytm jest niezwiązany. Oznacza to, że dla każdej liczby całkowitej, niezależnie od tego, jak dużej, istnieje małe, ale niezerowe prawdopodobieństwo, że całkowita liczba zwojów przekroczy tę liczbę w celu obliczenia jednej wartości wyjściowej. Aplikacje czasu rzeczywistego o ścisłych wymaganiach czasowych nie wchodzą więc w rachubę, chyba że jesteś skłonny pójść na kompromis w kwestii statystycznej dokładności algorytmu.

Odmiana tego rozwiązania początkowo toczy do trzech kości przed ponownym uruchomieniem: tworzy to 5^3=125 stanów końcowych, a my możemy przypisać co najwyżej 119 z nich do 7 grup o równym rozmiarze 17. Teraz istnieje 95,2% prawdopodobieństwo, że skończymy po maksymalnie trzech rzutach. Zauważmy, że średnio musimy turlać się mniej razy niż poprzednio (280/119 ≈ 2.35 w porównaniu z 50/21 ≈ 2.38), ponieważ przez większość czasu możemy już po pierwszych dwóch turlać się na skróty i bezpośrednio mapować stany pośrednie na wyjście. Ta średnia liczba zwojów spada, gdy kontynuujemy ten trend.

Jeśli jesteś zaznajomiony z teorią informacji, to rozważ fakt, że jeden rzut pięcioboczną kością (= rand5) generuje log2(5) ≈ 2.32 bitów informacji, a jeden rzut siedmioboczną kością (= rand7) generuje log2(7) ≈ 2.81 bitów informacji. Okazuje się, że w ograniczonym przypadku potrzebujemy tylko log(7)/log(5) ≈ 1.21 wywołania rand5 dla każdej wartości rand7, którą chcemy uzyskać. Dokładna implementacja, która działa arbitralnie blisko tej granicy jest dość skomplikowana i wykracza poza zakres tego artykułu. Musielibyśmy przechowywać informacje o stanie pomiędzy kolejnymi wywołaniami rand7, a algorytm, który mam na myśli, jest nie tylko wciąż nieograniczony w czasie, ale i w pamięci. Z przyjemnością zapraszam do poinformowania mnie o metodzie, która rozwiązuje ten ostatni problem!

Związane rozwiązanie

Nie istnieje coś takiego jak związany algorytm, który oblicza idealnie jednolitą wartość losową między 1 a 7, biorąc pod uwagę generator losowy tylko między 1 a 5. Rozważ rodzinę niezwiązanych rozwiązań powyżej. Jak już wspomniałem, w każdym punkcie zawsze będzie pewna ilość „pozostawionych” stanów (w zakresie od 1 do 6), które powodują ponowne uruchomienie algorytmu. Dzieje się tak dlatego, że 5 i 7 są liczbami pierwszymi, a żadna potęga 5 nie może być wielokrotnością 7. Jakkolwiek kuszące może być użycie małego twierdzenia Fermata, takie próby będą skutkowały błędami typu off-by-one, ponieważ podstawowa teoria liczb sprawia, że ograniczone rozwiązanie w tej rodzinie jest niemożliwe.

Możesz słusznie zauważyć, że liczba stanów końcowych nie zawsze jest potęgą 5, na przykład w przypadku „do trzech rolek”, gdzie możemy iść na skróty już po dwóch rolkach. Może dałoby się ułożyć diagram stanów tak, aby powstał algorytm związany o zmiennej długości ścieżek i 7n stanach końcowych? Rozważ jednak następujące kwestie:

  1. Te stany końcowe nie będą jednakowo prawdopodobne, ponieważ nie każda ścieżka ma taką samą długość (= ilość wywołań rand5).
  2. Możemy bardzo łatwo rozszerzyć drzewo, aby każda ścieżka była równie długa, przez bezużyteczne wywołanie rand5 odpowiednią ilość razy, ilekroć jesteśmy w przedwczesnym stanie końcowym. Teraz ilość stanów końcowych znów staje się potęgą 5, a wszystkie stany końcowe są równie prawdopodobne.

Oczywiście nie jest to formalny dowód, ale mam nadzieję, że dałem Ci jakąś intuicję na temat problemu. Jak widzimy, czasami problem może wydawać się bardzo realistyczny, tylko po to, aby natknąć się na fakty matematyczne, takie jak te. Czy po tej analizie jesteś w stanie stwierdzić, czy można symulować ośmioboczną kostkę zaczynając od czterobocznej?

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.