Czym dokładnie jest ziarno w generatorze liczb losowych?

Próbowałem użyć zwykłego wyszukiwania w Google itp., Ale większość odpowiedzi, które znalazłem, są albo niejasne, albo specyficzne dla języka / biblioteki, takie jak Python lub C ++ stdlib.hitp. Szukam agnostycznej, matematycznej odpowiedzi na język, a nie specyfiki biblioteki.

Na przykład wielu twierdzi, że ziarno jest punktem początkowym generatora liczb losowych, a to samo ziarno zawsze wytwarza tę samą liczbę losową. Co to znaczy? Czy to oznacza, że ​​liczba wyjściowa jest funkcją deterministyczną określonego ziarna, a losowość wynika z wartości ziarna? Ale jeśli tak jest, to dostarczając ziarno, czyż my, programiści, nie tworzymy losowości, zamiast pozwolić maszynie to zrobić?

Co również oznacza punkt początkowy w tym kontekście? Czy to nie jest rygorystyczny sposób wypowiadania elementu domeny mapy ? A może coś nie tak? f : X → $x\in\mathfrak{X}$$f:\mathfrak{X}\rightarrow\mathfrak{Y}$

Większość generatorów liczb pseudolosowych (PRNG) opiera się na algorytmach wykorzystujących pewien rodzaj metody rekurencyjnej, zaczynając od wartości bazowej określonej przez dane wejściowe o nazwie „seed”. Domyślnym PRNG w większości programów statystycznych (R, Python, Stata itp.) Jest algorytm Mersenne Twister MT19937, który jest przedstawiony w Matsumoto i Nishimura (1998) . Jest to skomplikowany algorytm, więc najlepiej przeczytać na nim papier, jeśli chcesz wiedzieć, jak to działa szczegółowo. W tym konkretnym algorytmie istnieje relacja powtarzalności stopnia , a twoje ziarno wejściowe jest początkowym zbiorem wektorów . Algorytm wykorzystuje liniową relację powtarzalności, która generuje:x 0 , x 1 , . . . , x n - $n$$\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}$

gdzie i a są przedmioty, które mogą być określone jako parametry w algorytm. Ponieważ ziarno daje początkowy zestaw wektorów (i dane inne stałe parametry algorytmu), szereg liczb pseudolosowych wygenerowanych przez algorytm jest stały. Jeśli zmienisz ziarno, zmienisz początkowe wektory, które zmienią pseudolosowe liczby wygenerowane przez algorytm. Jest to oczywiście funkcja nasion.r $1 \leqslant m \leqslant n$$r$$\mathbf{A}$

Należy teraz zauważyć, że jest to tylko jeden przykład, wykorzystujący algorytm MT19937. Istnieje wiele programów PRNG, które można wykorzystać w oprogramowaniu statystycznym, i każdy z nich obejmuje różne metody rekurencyjne, więc ziarno oznacza w każdym z nich inną rzecz (pod względem technicznym). Można znaleźć bibliotekę PRNGs dla Rw tej dokumentacji , która zawiera listę dostępnych algorytmów i dokumenty, które opisują te algorytmy.

Celem materiału siewnego jest umożliwienie użytkownikowi „zablokowania” generatora liczb pseudolosowych w celu umożliwienia powtarzalnej analizy. Niektórzy analitycy lubią ustawiać ziarno za pomocą prawdziwego generatora liczb losowych (TRNG), który wykorzystuje dane wejściowe do generowania początkowego numeru nasion, a następnie zgłasza to jako liczbę zablokowaną. Jeśli ziarno jest ustawione i zgłoszone przez pierwotnego użytkownika, wówczas audytor może powtórzyć analizę i uzyskać taką samą sekwencję liczb pseudolosowych jak pierwotny użytkownik. Jeśli parametr początkowy nie jest ustawiony, algorytm zwykle użyje pewnego rodzaju domyślnego parametru początkowego (np. Z zegara systemowego) i generalnie nie będzie można powtórzyć randomizacji.

Po pierwsze, nie ma prawdziwej przypadkowości w dzisiejszych generowanych komputerowo „liczbach losowych”. Wszystkie generatory pseudolosowe używają metod deterministycznych. (Być może komputery kwantowe to zmienią).

Trudnym zadaniem jest opracowanie algorytmów, które wytwarzają dane wyjściowe, których nie można znacząco odróżnić od danych pochodzących z prawdziwie losowego źródła.

Masz rację, że ustawienie nasienia rozpoczyna cię w konkretnym znanym punkcie początkowym na długiej liście liczb pseudolosowych. W przypadku generatorów zaimplementowanych w języku R, Python i tak dalej lista jest bardzo długa. Wystarczająco długo, aby nawet największy wykonalny projekt symulacyjny nie przekroczył „okresu” generatora, aby wartości zaczęły się cyklicznie zmieniać.

W wielu zwykłych aplikacjach ludzie nie ustawiają nasion. Następnie nieprzewidywalne ziarno jest wybierane automatycznie (na przykład z mikrosekund na zegarze systemu operacyjnego). Generatory pseudolosowe w powszechnym użyciu zostały poddane szeregowi testów, w większości składających się z problemów, które okazały się trudne do symulacji z wcześniejszymi niezadowalającymi generatorami.

Zwykle wyjście generatora składa się z wartości, które ze względów praktycznych nie są możliwe do odróżnienia od liczb wybranych naprawdę losowo z jednolitego rozkładu na Następnie manipuluje się tymi liczbami pseudolosowymi, aby dopasować to, co można pobrać losowo z innych rozkładów, takich jak dwumianowy, Poissona, normalny, wykładniczy itp.$(0,1).$

$\mathsf{Unif}(0,1)$

set.seed(1776);  m = 50000
par(mfrow=c(1,2))
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
par(mfrow=c(1,1))

Czasem przydaje się ustawienie nasionka. Niektóre z takich zastosowań są następujące:

1. Podczas programowania i debugowania wygodnie jest mieć przewidywalne wyjście. Tak wielu programistów umieszcza set.seedinstrukcję na początku programu, dopóki nie zakończy się pisanie i debugowanie.

2. Podczas nauczania o symulacji. Jeśli chcę pokazać uczniom, że mogę symulować rzuty rzetelnej kości za pomocą samplefunkcji w R, mógłbym oszukiwać, przeprowadzać wiele symulacji i wybierać tę, która jest najbliższa docelowej wartości teoretycznej. Ale to dałoby nierealistyczne wrażenie, jak naprawdę działa symulacja.

   Jeśli ustawię ziarno na początku, symulacja przyniesie ten sam wynik za każdym razem. Studenci mogą dokonać korekty kopii mojego programu, aby upewnić się, że daje on zamierzone wyniki. Następnie mogą przeprowadzać własne symulacje, albo z własnymi nasionami, albo pozwalając programowi wybrać własne miejsce początkowe.

   $$3/36 = 1/12 = 0.08333333.$$ $$2\sqrt{(1/12)(11/12)/10^6} = 0.00055.$$

   set.seed(703);  m = 10^6
   s = replicate( m, sum(sample(1:6, 2, rep=T)) )
   mean(s == 10)
   [1] 0.083456         # aprx 1/12 = 0.0833
   2*sd(s == 10)/sqrt(m)
   [1] 0.0005531408     # aprx 95% marg of sim err.
   

3. Podczas udostępniania analiz statystycznych obejmujących symulację. Obecnie wiele analiz statystycznych wymaga pewnej symulacji, na przykład testu permutacji lub próbnika Gibbsa. Pokazując ziarno, umożliwiasz osobom, które czytają analizę, dokładne odtworzenie wyników, jeśli chcą.

4. Pisząc artykuły naukowe dotyczące randomizacji. Artykuły akademickie zwykle przechodzą wiele rund recenzowania. Działka może wykorzystywać np. Losowo roztrzęsione punkty w celu ograniczenia nadmiernego rysowania. Jeśli analizy wymagają nieznacznej zmiany w odpowiedzi na komentarze recenzentów, dobrze jest, jeśli konkretne niepowiązane drgania nie zmieniają się między rundami recenzji, co może być niepokojące dla szczególnie podejrzanych recenzentów, więc ustawiasz ziarno przed wstrząsami.

TL; DR;

Ziarno zwykle umożliwia odtworzenie sekwencji liczb losowych. W tym sensie nie są to prawdziwe liczby losowe, ale „pseudolosowe liczby”, stąd Generator PNR (PNRG). To prawdziwa pomoc w prawdziwym życiu!

Trochę więcej szczegółów:

Praktycznie wszystkie generatory liczb losowych zaimplementowane w językach komputerowych są pseudolosowymi generatorami liczb. Wynika to z faktu, że biorąc pod uwagę wartość początkową (===> ziarno), zawsze będą zapewniać tę samą sekwencję pseudolosowych wyników. Dobry generator wygeneruje sekwencję, której nie da się odróżnić - w kategoriach statystycznych - od prawdziwej losowej sekwencji (rzuć prawdziwą kostką, prawdziwą monetą itp.).

W wielu przypadkach symulacji chcesz mieć prawdziwe „losowe” doświadczenie. Jednak chcesz także być w stanie odtworzyć swoje wyniki. Czemu? Cóż, przynajmniej regulatorzy są zainteresowani tą szczególną rzeczą.

Jest wiele do nurkowania. Ludzie analizują nawet „najlepsze” losowe nasiona. Moim zdaniem unieważnia to ich model, ponieważ nie radzą sobie z „prawdziwym” przypadkowym zachowaniem - lub ich PRNG nie nadaje się do ich implementacji. Przez większość czasu po prostu nie wykonują wystarczającej liczby symulacji - ale wymagają czasu.

Teraz wyobraź sobie „prawdziwą” RNG. Można to zaimplementować na podstawie pewnego rodzaju losowości w maszynie. Jeśli weźmiesz tylko losowe ziarno (np. Czas), utworzysz rodzaj losowego punktu początkowego, ale losowość sekwencji nadal zależy od algorytmu w celu ustalenia kolejnych liczb. W większości przypadków jest to ważniejsze niż punkt początkowy, ponieważ rozkład wyników określa rzeczywisty „wynik”. Jeśli Twoja sekwencja powinna być naprawdę losowa, jak byś to zaimplementował? Tiki zegara komputera można uznać za deterministyczne, w przeciwnym razie prawdopodobnie wykażą wiele autokorelacji. Więc co możesz zrobić? Jak dotąd najlepszym rozwiązaniem jest wdrożenie solidnego PNRG.

Obliczenia kwantowe? Nie jestem pewien, czy to naprawi.