Paradoks urodzinowy - losowanie liczb jedna po drugiej i generatory PRNG

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Paradoks urodzinowy - losowanie liczb jedna po drugiej i generatory PRNG

Post autor: matemix »

W Internecie ludzie piszą, że, jeśli używamy generatorów liczb pseudolosowych o długości cyklu \(\displaystyle{ 2^{n}}\), to do praktycznych zastosowań np. symulacji powinniśmy używać tylko \(\displaystyle{ 2^{\frac {n}{2}}}\) z tych liczb ze względu na paradoks urodzinowy. Większość generatorów działa bowiem jak permutacje zawierające jeden cykl - przebiegają po wszystkich liczbach w zakresie od \(\displaystyle{ 0}\) do \(\displaystyle{ 2^{n}-1}\) i nie ma tam powtórzeń, jak gdybyśmy te liczby faktycznie losowali (dlatego po pewnym czasie zaczną wykazywać systematyczne błędy, bo powtórzenia, które powinny się pojawić, nie będą się pojawiać).

Ale rozważmy faktyczne losowanie liczb z zakresu \(\displaystyle{ 0}\) do \(\displaystyle{ 2^{n}-1}\). Podobno możemy zacząć się spodziewać powtórzeń już po około \(\displaystyle{ 2^{\frac {n}{2}}}\) liczb. Rozumiem to tak, że wylosujemy jakąkolwiek liczbę, która została wcześniej wygenerowana kolejny raz właśnie średnio po \(\displaystyle{ 2^{\frac {n}{2}}}\) losowaniach. Czy to prawda? Nie wiem jak to policzyć, ale też nie zastanawiałem się za długo jak to zrobić. Trudno znaleźć naukowe, czy merytoryczne źródła tej informacji. Nie wiem, czy Knuth lub L'Ecuyer gdzieś o tym nie pisał i tego nie liczył, ale nie jestem sobie w stanie przypomnieć.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Paradoks urodzinowy - losowanie liczb jedna po drugiej i generatory PRNG

Post autor: Dasio11 »

Paradoks urodzin stwierdza, że dla dużych liczb naturalnych \(\displaystyle{ N}\) wystarczy wylosować około \(\displaystyle{ \sqrt{N}}\) liczb ze zbioru \(\displaystyle{ \{ 1, \ldots, N \}}\), by prawdopodobieństwo, że pewna liczba się powtórzy, przekroczyło \(\displaystyle{ \frac{1}{2}}\). Idea dowodu jest prosta - jeśli losujemy \(\displaystyle{ k}\) liczb, to szansa na brak powtórzeń wynosi

\(\displaystyle{ p = 1 \cdot \left(1-\frac{1}{N}\right) \cdot \ldots \cdot \left(1-\frac{k-1}{N}\right)}\).

Jeśli \(\displaystyle{ k}\) jest małe w stosunku do \(\displaystyle{ N}\), to \(\displaystyle{ p}\) jest w przybliżeniu równe

\(\displaystyle{ 1 - \frac{1}{N} - \frac{2}{N} - \ldots - \frac{k-1}{N} = 1 - \frac{k(k-1)}{2N} \approx 1 - \frac{k^2}{2N}}\).

Zatem w przybliżeniu

\(\displaystyle{ 1-p > \frac{1}{2} \iff k^2 > N \iff k > \sqrt{N}}\).
ODPOWIEDZ