Przykład z kostką
Masz zwykłą sześcienną kostkę do gry, oznaczaną w grach jako K6, a potrzebujesz liczby od 1 do 4. Nasuwa się prosty przepis. Odejmij 1 od liczby oczek, policz resztę z dzielenia przez 4 i na koniec znów dodaj 1. Odjęcie i dodanie jedynki sprawiają tylko, że wyniki idą od 1 do 4, a nie od 0 do 3.
Jeśli wypadnie od jednego do czterech oczek, dostajesz dokładnie tyle samo: wynik od 1 do 4. Gdy wypadnie pięć oczek, po odjęciu jedynki zostaje 4. Reszta z dzielenia 4 przez 4 to 0, więc wynik wynosi 1. W ten sam sposób sześć oczek daje wynik 2.
Policzmy teraz, ile ścianek kostki prowadzi do każdego wyniku. Do wyniku 1 prowadzą dwie ścianki: jedno i pięć oczek. Do wyniku 2 też dwie: dwa i sześć oczek. Wynikom 3 i 4 odpowiada tylko po jednej ściance. Jedynka wypada więc z prawdopodobieństwem 2/6, czyli w 33,3% rzutów. Trójka wypada z prawdopodobieństwem 1/6, czyli w 16,7% rzutów. Przepis wygląda niewinnie, a jednak niskie wyniki są dwa razy bardziej prawdopodobne.
Skąd się bierze nierówność
Kostka to tylko przykład ogólnej reguły, którą matematycy nazywają zasadą szufladkową. Mówi ona, że jeśli rozkładasz przedmioty do szufladek, a przedmiotów nie da się rozdzielić po równo, to w niektórych szufladkach będzie ich więcej niż w innych.
W losowaniu przedmiotami są wszystkie wartości, które może dać źródło losowości, na przykład kostka albo generator w komputerze. Oznaczmy ich liczbę przez S. Szufladkami są potrzebne wyniki, których jest n. Kiedy liczymy resztę z dzielenia przez n, przypisujemy kolejne wartości do kolejnych wyników tak, jak rozdaje się karty graczom: po kolei, jedną za drugą.
Jeśli S nie dzieli się przez n bez reszty, ostatnie rozdanie jest niepełne. Kilku pierwszych graczy dostaje wtedy o jedną kartę więcej. Przy kostce wartości jest 6, a wyników 4. Po jednym pełnym rozdaniu zostają dwie nadprogramowe ścianki i trafiają do wyników 1 i 2.
Dokładnie ten sam mechanizm działa w programach. Klasyczny przykład to losowy bajt, czyli liczba od 0 do 255, zamieniony na liczbę od 0 do 99 działaniem bajt % 100. Znak % oznacza tu resztę z dzielenia. Wśród 256 wartości bajtu mieszczą się dwa pełne rozdania po 100 liczb, od 0 do 99 i od 100 do 199. Zostaje jeszcze niepełna końcówka: 56 wartości od 200 do 255.
Dlatego do każdego wyniku od 0 do 55 prowadzą trzy wartości bajtu. Każdy z tych wyników wypada z prawdopodobieństwem 3/256, czyli 1,17%. Do wyników od 56 do 99 prowadzą tylko dwie wartości, więc każdy z nich ma 0,78% szans. Wynik 7 wypada zatem półtora raza częściej niż 77. Sprawdź to w symulacji:
Modulo kontra odrzucanie
Źródło losowości
Liczba wyników4 (0–3)
Wynik = wartość źródła mod 4. Liczymy od zera, jak w kodzie.
Modulo: Wyniki 0–1 dostają po 2 z 6 wartości źródła (33,33%), a wyniki 2–3 po 1 (16,67%). Najczęstszy wynik jest 2 razy bardziej prawdopodobny niż najrzadszy.
Odrzucanie: wartości od 4 do 5 są odrzucane i losowane od nowa (33,3% losowań), więc każdy wynik ma dokładnie 25%.
Czy przy dużych liczbach to ma znaczenie?
Kostka i bajt mają mało wartości, więc nierówność widać od razu. Generatory w komputerach dają jednak zwykle liczby 32-bitowe, czyli zapisane za pomocą 32 zer i jedynek. Takich liczb jest ponad 4,29 mld.
Przy zakresie od 1 do 100 po wszystkich pełnych rozdaniach zostaje nadwyżka 96 wartości. Wyniki od 1 do 96 dostają więc po jednej wartości więcej niż wyniki od 97 do 100. Ta przewaga jest jednak znikoma. Uprzywilejowane wyniki wypadają częściej mniej więcej o jedną 43-milionową. Takiej różnicy nie widać w jednym losowaniu ani nawet w miliardach losowań.
Problem rośnie, gdy zakres zbliża się do wielkości całej puli generatora. Weźmy zakres 3 mld i liczby 32-bitowe. Do pierwszych ok. 1,29 mld wyników prowadzą wtedy po dwie wartości generatora, a do pozostałych tylko po jednej. Część wyników jest więc dwa razy częstsza, tak samo jak w przykładzie z kostką.
Podobny kłopot pojawia się w popularnym w języku JavaScript zapisie Math.floor(Math.random() * n). Funkcja Math.random() losuje ułamek od 0 do 1, zapis mnoży go przez n, a Math.floor zaokrągla wynik w dół. Komputer zapisuje ułamki ze skończoną dokładnością, więc Math.random() może zwrócić tylko skończoną liczbę różnych wartości. Zasada szufladkowa działa więc i tu. Do tego Math.random() nie jest generatorem kryptograficznym, czyli takim, którego wyników nie da się przewidzieć. Nie nadaje się więc do losowań, w których coś jest do wygrania.
Rozwiązanie: odrzucanie
Skoro kłopot bierze się z niepełnego rozdania, wystarczy je usunąć. Tak działa metoda odrzucania (ang. rejection sampling). Bierzemy tylko te wartości z generatora, które mieszczą się w pełnych rozdaniach po n. Jeśli wypadnie wartość z niepełnej końcówki, odrzucamy ją i losujemy od nowa.
Przy kostce oznacza to prostą regułę: gdy wypadnie pięć albo sześć oczek, rzuć jeszcze raz. Wtedy do każdego wyniku od 1 do 4 prowadzi dokładnie jedna ścianka, więc każdy ma 25% szans. Koszt jest niewielki. Po odrzuconym rzucie trzeba losować ponownie, ale średnio wystarcza mniej niż dwa losowania na wynik. Przy 32-bitowym generatorze i małym zakresie powtórka prawie się nie zdarza.
Jak to robi losowaliczba.pl
W naszych narzędziach stosujemy odrzucanie w obu trybach losowania:
- Tryb szybki korzysta z generatora kryptograficznego wbudowanego w przeglądarkę (
crypto.getRandomValues). Program bierze z niego liczby 32-bitowe, a gdy zakres przekracza 2³², czyli ponad 4,29 mld, liczby 53-bitowe. W obu przypadkach odrzuca niepełną końcówkę. - Tryb weryfikowalny korzysta z drand, publicznej sieci, która w kolejnych rundach ogłasza nowe losowe wartości. Program zamienia wartość wybranej rundy funkcją SHA-256 na 256-bitowe bloki i do nich też stosuje odrzucanie. Bloki mają kolejne numery, a odrzucone też są liczone. Dlatego każdy, kto powtórzy losowanie dla tej samej rundy, przejdzie te same kroki i dostanie ten sam wynik. Więcej piszemy o tym w artykule o weryfikowalnym losowaniu.
Dzięki temu każdy wynik w generatorze liczb losowych, generatorze Lotto czy przy rzucie kostką ma dokładnie taką samą szansę wypaść.