Matematyka.pl

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ć.

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}}\).