Losowość w ogóle nie jest przypadkowa?

Zrobiłem to, aby przetestować losowość randinta:

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

Próbowałem około 10 razy więcej, a najlepszy wynik jaki uzyskałem to 121 iteracji przed repeaterem. Czy to najlepszy wynik, jaki można uzyskać z biblioteki standardowej?

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.

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
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.

Zanim obwinisz Pythona, powinieneś naprawdę odświeżyć trochę teorii prawdopodobieństwa i statystyki. Zacznij od przeczytania o paradoksie urodzin

Nawiasem mówiąc, randommoduł w Pythonie wykorzystuje twister Mersenne PRNG, który jest uważany za bardzo dobry, ma ogromny okres i został szeroko przetestowany. Możesz więc mieć pewność, że jesteś w dobrych rękach.

Jeśli nie chcesz, aby powtarzał się, wygeneruj tablicę sekwencyjną i użyj random.shuffle

W odpowiedzi na odpowiedź Nimbuz:

http://xkcd.com/221/

Prawdziwa losowość z pewnością obejmuje powtarzanie się wartości, zanim cały zestaw możliwych wartości zostanie wyczerpany. W przeciwnym razie nie byłoby to przypadkowe, ponieważ byłbyś w stanie przewidzieć, jak długo wartość nie będzie się powtarzać.

Jeśli kiedykolwiek rzuciłeś kostką, na pewno dość często trafiałeś 3 szóstki z rzędu ...

Losowa implementacja Pythona jest właściwie najnowocześniejsza:

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

To nie jest repeater. Repeater jest wtedy, gdy powtarzasz tę samą sekwencję . Nie tylko jedna liczba.

Jesteś generowanie 4500liczb losowych z zakresu 500 <= x <= 5000. Następnie sprawdzasz, dla każdego numeru, czy został on wcześniej wygenerowany. Problemem urodziny mówi nam co jest prawdopodobieństwo dla dwóch z tych numerów, aby dopasować podane nwypróbowuje się z szeregu d.

Możesz także odwrócić wzór, aby obliczyć, ile liczb musisz wygenerować, zanim szansa na wygenerowanie duplikatu będzie większa niż 50%. W takim przypadku masz >50%szansę znaleźć zduplikowaną liczbę po 79iteracjach.

Zdefiniowałeś losową przestrzeń 4501 wartości (500-5000) i wykonujesz iterację 4500 razy. Zasadniczo masz gwarancję kolizji w napisanym teście.

Pomyśl o tym w inny sposób:

• Gdy tablica wyników jest pusta P (dupe) = 0
• 1 wartość w tablicy P (dupe) = 1/4500
• 2 wartości w tablicy P (dupe) = 2/4500
• itp.

Więc zanim dojdziesz do 45/4500, ta wkładka ma 1% szansy na bycie duplikatem, a to prawdopodobieństwo rośnie z każdym kolejnym wkładem.

Aby stworzyć test, który naprawdę przetestuje możliwości funkcji losowej, zwiększ wszechświat możliwych wartości losowych (np .: 500-500000). Możesz uzyskać duplikat lub nie. Ale średnio otrzymasz znacznie więcej iteracji.

Dla każdego, kto ma ten problem, użyłem uuid.uuid4 () i działa to jak urok.

Jest paradoks urodzinowy. Biorąc to pod uwagę, zdajesz sobie sprawę, że mówisz, że znalezienie „764, 3875, 4290, 4378, 764” lub czegoś podobnego nie jest zbyt przypadkowe, ponieważ liczba w tej sekwencji się powtarza. Prawdziwym sposobem na to jest porównanie sekwencji. Napisałem skrypt w Pythonie, aby to zrobić.

from random import randint
y = 21533456
uniques = []
for i in range(y):  
    x1 = str(randint(500, 5000))
    x2 = str(randint(500, 5000))
    x3 = str(randint(500, 5000))
    x4 = str(randint(500, 5000))
    x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
    raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
    raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)