Dlaczego dzielenie z resztą zawyża niektóre wyniki
Najprostszy przepis na losową liczbę z zakresu to wziąć losową wartość i policzyć resztę z dzielenia. Ten przepis po cichu faworyzuje niskie wyniki. Pokazujemy dlaczego, o ile i jak tego uniknąć.
Przykład z kostką
Masz zwykłą kostkę K6, a potrzebujesz liczby od 1 do 4. Nasuwa się prosty przepis: odejmij 1 od liczby oczek, weź resztę z dzielenia przez 4 i dodaj 1. Oczka 1–4 dają wyniki 1–4, oczko 5 daje 1, a oczko 6 daje 2.
Wyniki 1 i 2 mają więc po dwie ścianki, a wyniki 3 i 4 – tylko po jednej. Jedynka wypada z prawdopodobieństwem 2/6 (33,3%), a trójka 1/6 (16,7%). Niskie wyniki są dwa razy bardziej prawdopodobne, choć przepis wygląda niewinnie.
Skąd się bierze nierówność
To zasada szufladkowa. Źródło ma S równie prawdopodobnych wartości, a chcesz n wyników. Reszta z dzielenia przez n rozkłada wartości źródła po wynikach jak karty rozdawane po kolei graczom. Jeśli S nie dzieli się przez n bez reszty, ostatnie rozdanie jest niepełne i kilku pierwszych graczy dostaje o jedną kartę więcej.
Klasyczny przykład z programowania: losowy bajt (256 wartości, 0–255) zamieniony na liczbę 0–99 przez bajt % 100. Wyniki 0–55 dostają po trzy wartości bajtu (1,17%), a 56–99 tylko po dwie (0,78%). Wynik 7 wypada półtora raza częściej niż 77.
Sprawdź sam
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?
Generatory zwykle dają 32-bitowe liczby: ponad 4,29 mld wartości. Przy zakresie 1–100 nadwyżka to 96 wartości na ponad 4 mld, więc uprzywilejowane wyniki są częstsze o ok. 1 na 43 mln. W jednym losowaniu nie do zauważenia, w milionach losowań już mierzalne.
Problem rośnie, gdy zakres zbliża się do rozmiaru źródła. Losując z zakresu 3 mld za pomocą 32-bitowej liczby, pierwsze ok. 1,29 mld wyników dostaje po dwie wartości źródła, a reszta po jednej. Część wyników jest wtedy dwa razy częstsza – tak samo jak w przykładzie z kostką.
Podobny kłopot ma popularny przepis Math.floor(Math.random() * n). Math.random() zwraca skończoną liczbę możliwych wartości, więc zasada szufladkowa działa i tu, a do tego nie jest generatorem kryptograficznym: nie nadaje się do losowań, w których coś jest do wygrania.
Rozwiązanie: odrzucanie
Metoda odrzucania (ang. rejection sampling) usuwa niepełne rozdanie. Bierzemy tylko wartości poniżej największej wielokrotności n, która mieści się w źródle. Wartość z niepełnej końcówki odrzucamy i losujemy od nowa.
W przykładzie z kostką oznacza to: przy oczku 5 lub 6 rzuć jeszcze raz. Każdy z wyników 1–4 ma wtedy dokładnie jedną ściankę, czyli 25%. Koszt jest niewielki: odrzucona wartość wymaga kolejnego losowania, ale średnio potrzeba mniej niż dwóch losowań na wynik, a przy 32-bitowym źródle i małym zakresie odrzucenie prawie się nie zdarza.
Jak to robi losowaliczba.pl
- Tryb szybki bierze 32-bitowe liczby z generatora kryptograficznego przeglądarki (
crypto.getRandomValues), a dla zakresów większych niż 2³² – 53-bitowe, i zawsze stosuje odrzucanie. - Tryb weryfikowalny zamienia losowość rundy drand na 256-bitowe bloki (SHA-256) i też stosuje odrzucanie. Odrzucone bloki są liczone, więc każdy, kto powtarza losowanie, dostaje ten sam wynik. Więcej w artykule o weryfikowalnym losowaniu.
Dzięki temu każdy wynik w generatorze liczb losowych, generatorze Lotto czy przy rzucie kostką ma dokładnie takie samo prawdopodobieństwo.
Wypróbuj w praktyce
Generator liczb losowych