Paradoks urodzin, czyli dlaczego PRNG produkują duplikaty częściej, niż mogłoby się wydawać.
Istnieje kilka problemów związanych z problemem PO. Jeden to paradoks urodzin, jak wspomniano powyżej, a drugi to natura tego, co generujesz, co nie gwarantuje, że dana liczba się nie powtórzy.
Paradoks urodzin ma zastosowanie, gdy dana wartość może wystąpić więcej niż raz w okresie działania generatora - a zatem w próbce wartości mogą wystąpić duplikaty. Efekt Paradoksu Urodzinowego jest taki, że rzeczywiste prawdopodobieństwo otrzymania takich duplikatów jest dość znaczące, a średni okres między nimi jest krótszy, niż można by sądzić. Ten dysonans między prawdopodobieństwami postrzeganymi i rzeczywistymi sprawia, że Paradoks urodzinowy jest dobrym przykładem błędu poznawczego , w którym naiwne, intuicyjne oszacowanie może być szalenie błędne.
Krótkie wprowadzenie na temat generatorów liczb pseudolosowych (PRNG)
Pierwsza część twojego problemu polega na tym, że bierzesz ujawnioną wartość generatora liczb losowych i konwertujesz ją na znacznie mniejszą liczbę, więc przestrzeń możliwych wartości jest zmniejszona. Chociaż niektóre generatory liczb pseudolosowych nie powtarzają wartości w swoim okresie, ta transformacja zmienia dziedzinę na znacznie mniejszą. Mniejsza domena unieważnia warunek „brak powtórzeń”, więc można spodziewać się znacznego prawdopodobieństwa powtórzeń.
Niektóre algorytmy, takie jak liniowa przystająca PRNG ( A'=AX|M) , gwarantują unikalność przez cały okres. W LCG wygenerowana wartość zawiera cały stan akumulatora i nie jest utrzymywany żaden dodatkowy stan. Generator jest deterministyczny i nie może powtórzyć liczby w okresie - każda podana wartość akumulatora może implikować tylko jedną możliwą kolejną wartość. Dlatego każda wartość może wystąpić tylko raz w okresie generatora. Jednak okres takiego PRNG jest stosunkowo mały - około 2 ^ 30 dla typowych implementacji algorytmu LCG - i nie może być większy niż liczba różnych wartości.
Nie wszystkie algorytmy PRNG mają tę cechę; niektóre mogą powtórzyć daną wartość w okresie. W problemie OP algorytm Mersenne Twister (używany w module losowym Pythona ) ma bardzo długi okres - znacznie większy niż 2 ^ 32. W przeciwieństwie do liniowego kongruentnego PRNG, wynik nie jest wyłącznie funkcją poprzedniej wartości wyjściowej, ponieważ akumulator zawiera dodatkowy stan. Z 32-bitową liczbą całkowitą i okresem ~ 2 ^ 19937, nie może zapewnić takiej gwarancji.
Mersenne Twister jest popularnym algorytmem dla PRNG, ponieważ ma dobre właściwości statystyczne i geometryczne oraz bardzo długi okres - pożądane cechy dla PRNG używanego w modelach symulacyjnych.
Dobre właściwości statystyczne oznaczają, że liczby generowane przez algorytm są równomiernie rozłożone i żadna z liczb nie ma znacznie większego prawdopodobieństwa wystąpienia niż inne. Słabe właściwości statystyczne mogą powodować niepożądane odchylenia w wynikach.
Dobre właściwości geometryczne oznaczają, że zbiory liczb N nie leżą na hiperpłaszczyźnie w N-wymiarowej przestrzeni. Słabe właściwości geometryczne mogą generować fałszywe korelacje w modelu symulacyjnym i zniekształcać wyniki.
Długi okres oznacza, że możesz wygenerować wiele liczb, zanim sekwencja zakończy się na początku. Jeśli model wymaga dużej liczby iteracji lub musi być uruchamiany z kilku początków, wówczas około 2 ^ 30 dyskretnych liczb dostępnych w typowej implementacji LCG może nie być wystarczające. Algorytm MT19337 ma bardzo długi okres - 2 ^ 19337-1 lub około 10 ^ 5821. Dla porównania, całkowitą liczbę atomów we wszechświecie szacuje się na około 10 ^ 80.
32-bitowa liczba całkowita utworzona przez MT19337 PRNG nie może prawdopodobnie reprezentować wystarczającej liczby dyskretnych wartości, aby uniknąć powtarzania w tak dużym okresie. W takim przypadku prawdopodobne jest wystąpienie zduplikowanych wartości i nieuniknione przy wystarczająco dużej próbce.
Paradoks urodzin w pigułce
Ten problem został pierwotnie zdefiniowany jako prawdopodobieństwo, że dowolne dwie osoby w pokoju będą obchodzić urodziny tego samego dnia. Najważniejsze jest to, że dowolne dwie osoby w pokoju mogą dzielić urodziny. Ludzie mają naiwną tendencję do błędnego interpretowania problemu jako prawdopodobieństwa, że ktoś w pokoju będzie miał urodziny z określoną osobą, co jest źródłem błędu poznawczego, który często powoduje, że ludzie nie doceniają tego prawdopodobieństwa. Jest to błędne założenie - nie ma wymogu, aby dopasowanie dotyczyło konkretnej osoby, a dowolne dwie osoby mogą pasować.
Prawdopodobieństwo dopasowania dwóch dowolnych osób jest znacznie wyższe niż prawdopodobieństwo dopasowania do określonej osoby, ponieważ dopasowanie nie musi dotyczyć określonej daty. Zamiast tego musisz znaleźć tylko dwie osoby, które mają te same urodziny. Z tego wykresu (który można znaleźć na stronie Wikipedii na ten temat) widzimy, że potrzebujemy tylko 23 osób w pokoju, aby istniało 50% szans na znalezienie dwóch pasujących w ten sposób.
Z wpisu w Wikipedii na ten temat możemy uzyskać ładne podsumowanie. W zadaniu PO mamy 4500 możliwych „urodzin” zamiast 365. Dla danej liczby generowanych losowo wartości (równych „ludziom”) chcemy poznać prawdopodobieństwo pojawienia się dowolnych dwóch identycznych wartości w ciągu.
Obliczanie prawdopodobnego wpływu paradoksu urodzinowego na problem PO
W przypadku sekwencji 100 liczb mamy 
pary (patrz Zrozumienie problemu ), które mogą potencjalnie pasować (tj. Pierwsza może pasować do drugiej, trzeciej itd., Druga może pasować do trzeciej, czwartej itp. Itd.), Więc liczba kombinacji, które mogą potencjalnie pasować, jest większa niż tylko 100.
Z Obliczenia prawdopodobieństwa otrzymujemy wyrażenie 
. Poniższy fragment kodu Pythona poniżej dokonuje naiwnej oceny prawdopodobieństwa wystąpienia pasującej pary.
from math import log10, factorial
PV=4500
SS=100
numerator = factorial (PV)
denominator = (PV ** SS) * factorial (PV - SS)
log_prob_no_pair = log10 (numerator) - log10 (denominator)
print 1.0 - (10 ** log_prob_no_pair)
Daje to rozsądnie wyglądający wynik p = 0,669 dla dopasowania występującego w 100 liczbach wybranych z populacji 4500 możliwych wartości. (Może ktoś mógłby to zweryfikować i zamieścić komentarz, jeśli jest zły). Z tego widać, że długości przebiegów między dopasowanymi liczbami zaobserwowane w PO wydają się całkiem rozsądne.
Przypis: używanie tasowania w celu uzyskania unikalnej sekwencji liczb pseudolosowych
Zobacz poniższą odpowiedź od S. Marka, aby dowiedzieć się, jak uzyskać gwarantowany unikalny zestaw liczb losowych. Technika, do której odnosi się plakat, pobiera szereg liczb (które podajesz, aby były unikalne) i tasuje je w losowej kolejności. Narysowanie sekwencji liczb z tasowanej tablicy da ci sekwencję liczb pseudolosowych, które na pewno się nie powtórzą.
Przypis: PRNG zabezpieczone kryptograficznie
Algorytm MT nie jest bezpieczny pod względem kryptograficznym, ponieważ stosunkowo łatwo jest wywnioskować o stanie wewnętrznym generatora na podstawie sekwencji liczb. Inne algorytmy, takie jak Blum Blum Shub, są używane w aplikacjach kryptograficznych, ale mogą być nieodpowiednie do symulacji lub ogólnych aplikacji z liczbami losowymi. PRNG zabezpieczone kryptograficznie mogą być drogie (być może wymagające obliczeń bignum) lub mogą nie mieć dobrych właściwości geometrycznych. W przypadku tego typu algorytmu podstawowym wymaganiem jest, aby wyprowadzenie stanu wewnętrznego generatora na podstawie sekwencji wartości było niemożliwe obliczeniowo.
