Dlaczego nie można stworzyć prawdziwie losowych liczb?

47

Próbowałem rozwiązać problem hobby, który wymagał wygenerowania miliona losowych liczb. Ale szybko zdałem sobie sprawę, że trudno jest uczynić je wyjątkowymi. Wziąłem instrukcję projektowania algorytmów, aby przeczytać o generowaniu liczb losowych.

Ma następujący akapit, którego w pełni nie rozumiem.

Niestety generowanie liczb losowych wygląda o wiele łatwiej niż jest w rzeczywistości. Rzeczywiście, generowanie liczb losowych na dowolnym urządzeniu deterministycznym jest zasadniczo niemożliwe. Von Neumann [Neu63] powiedział to najlepiej: „Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu.” Najlepsze, na co możemy liczyć, to liczby pseudolosowe, strumień liczb, które wyglądają jak jeśli zostały wygenerowane losowo.

Dlaczego niemożliwe jest uzyskanie prawdziwie losowych liczb w jakimkolwiek deterministycznym urządzeniu? Co oznacza to zdanie?

Vinoth Kumar CM
źródło
86
Czy naprawdę pytasz, dlaczego nie możesz wygenerować prawdziwie losowej liczby na urządzeniu deterministycznym ? Czy pytanie nie zawiera już odpowiedzi?
herby
37
Jeśli wszystkie liczby, które generujesz, muszą być unikalne, nie są tak naprawdę losowe. Jest całkiem możliwe, że prawdziwy generator liczb losowych da ten sam wynik dziesięć razy z rzędu.
TMN,
28
Wadą jest wyszukiwanie liczb losowych, które są unikalne . Jeśli starasz się, aby liczby były unikalne , to nie są one losowe, ponieważ losowe wymaga możliwości powtórzenia, bez względu na to, jak nieprawdopodobne.
Mark Booth,
13
Czy poza komputerem, czy jakakolwiek liczba losowa jest naprawdę losowa? Rzuć kostką, to fizyka z wieloma wektorami.
MPelletier,
9
@MPelletier: Niezupełnie. Mechanika kwantowa może (gdy naukowcy odkryją ją więcej) sugerować istnienie prawdziwej przypadkowości, w zależności od twojej definicji losowości.
Brian,

Odpowiedzi:

65

Należy szukać kryptograficznie bezpiecznego generatora liczb pseudolosowych . Większość PRNG to liniowe generatory zgodności (więc next numberjest to funkcja liniowa previous number), więc jeśli narysujesz wykres next numbervs previous numberotrzymasz wykres równoległych linii. CSPRNG tego nie zrobi. Kompromis polega na tym, że są one powolne.

Generatory liczb losowych dzielę na 3 kategorie :

  1. Wystarczająco dobry do odrabiania lekcji.
  2. Wystarczająco dobry, aby postawić na swoją firmę.
  3. Wystarczająco dobry, aby postawić swój kraj.

Dlaczego niemożliwe jest uzyskanie prawdziwie losowych liczb w jakimkolwiek deterministycznym urządzeniu?

Deterministyczne urządzenie zawsze będzie wytwarzało tę samą moc wyjściową, jeśli otrzyma takie same warunki początkowe i dane wejściowe - tak właśnie powinno być deterministic. „Prawdziwie losowa liczba” jest bardziej filozoficznym punktem widzenia, ponieważ to, co oznacza być, randomstanowi sedno filozoficznego patrzenia na pępek (ludzie nie są nawet pewni, czy rozpad atomowy jest losowy lub przebiega według jakiegoś wzoru, którego po prostu nie możemy zrozumieć jeszcze). Kryptograficznie bezpieczny generator liczb losowych pobierze jakieś zewnętrzne źródło entropii, aby urządzenie nie było deterministyczne.

Tangurena
źródło
1
Dlatego niemożliwe jest uzyskanie naprawdę losowej liczby. Nawet jeśli sekwencja nigdy się nie powtarza, co nie jest gwarantowane dla liczb losowych , kolejne uruchomienie programu z tymi samymi danymi wejściowymi da te same wyniki. Więc ktoś inny może odtworzyć twoje losowe liczby w późniejszym czasie, co oznacza, że ​​tak naprawdę wcale nie był losowy.
Spencer Rathbun,
2
@ user973810 Problem z tą definicją z teorii informacji polega na tym, że nie można pokazać rzeczywistego wystąpienia losowej sekwencji. Możemy udowodnić, dla każdego rozsądnego języka definicji, że prawie każda nieskończona sekwencja (w sensie technicznym) jest losowa, ponieważ nie można jej w ogóle opisać w tym języku. Bardziej użyteczna jest koncepcja generatora losowej sekwencji: nie takiej, która generuje losową sekwencję, ale takiej, która generuje losową sekwencję.
Gilles: „Przestańcie być źli”,
13
Nieznaczne nitpick: niektórzy ludzie, a mianowicie fizycy jądrowi i cząsteczkowi, są całkiem pewni, że procesy takie jak rozpad atomowy naprawdę losowe.
David Z
9
@David: Możemy pójść nawet dalej. Różne eksperymenty dotyczące nierówności Bella pokazują, że pewne procesy kwantowe są definitywnie nieprzewidywalne . Mogą być losowe w pewnym sensie filozoficznym lub mogą zależeć od nielokalnych zmiennych ukrytych, ale w obu przypadkach uniemożliwia wiarygodne przewidywanie.
dmckee,
7
@dmckee: tak, właśnie pomyślałem, że łatwiej będzie trzymać się z dala od prób wyjaśnienia związku między nierównością Bella a załamaniem funkcji falowych w komentarzach do prog.SE. Ludzie zawsze mogą przyjść na naszą stronę, jeśli są ciekawi ;-) Tangurena: to prawda, Einstein tak powiedział, ale to tylko oznaczało, że naprawdę chciał, aby wszechświat był deterministyczny. Ale tak nie jest. Eksperymenty przeprowadzone po śmierci Einsteina wykazały to dość jednoznacznie (z wyjątkiem nielokalnych zmiennych ukrytych, czyli dziwności ). To, że jest Einsteinem, nie oznacza, że ​​miał rację we wszystkim.
David Z
22

Prawdziwa przypadkowość implikuje niedeterminizm. Jeśli jest deterministyczny, można go dokładnie przewidzieć (to właśnie oznacza determinizm); jeśli można to przewidzieć, nie jest losowy.

Najlepszą rzeczą, jaką można uzyskać od deterministycznego generatora liczb pseudolosowych, jest strumień liczb, który ma bardzo długi cykl (niepowtarzanie się jest niemożliwe, chyba że urządzenie RNG ma nieograniczoną pamięć), które przez cały cykl daje liczby strumieni spełniające wszystkie pozostałe właściwości losowej sekwencji (najbardziej interesujący jest jednolity rozkład wartości).

Aby rozwiązać ten problem, wiele współczesnych uniksów i systemów uniksowych ma RNG jądra, które wykorzystują fizyczne źródła hałasu do generowania prawdziwej losowości.

Innym powszechnym podejściem jest przyjmowanie bieżącego czasu jako zalążka deterministycznego RNG ( srand(time(NULL));w C); kryptograficznie rzecz biorąc, jest to bezwartościowe, ponieważ obecny czas nie jest tajemnicą, ale w przypadku takich rzeczy, jak symulacje fizyczne lub gry wideo, jest wystarczająco dobry.

tdammers
źródło
Zauważ, że powtarzanie nie jest również możliwe dla żadnego generatora z ograniczoną wartością wyjściową (ograniczona liczba bitów). Ale oczywiście długość cyklu deterministycznego generatora jest najprawdopodobniej znacznie krótsza niż teoretyczne maksimum, czyli wszystkie możliwe permutacje.
9000
@ 9000: Oczywiście to nie jest prawda. Weź nieracjonalną liczbę cyfr (dowolną bazę) jako „losową” sekwencję. Bum! niepowtarzalna sekwencja (z definicji) i wciąż ograniczona (do twojej bazy).
ThePopMachine
@ThePopMachine: możesz wygenerować niepowtarzalną sekwencję bitów o dowolnej długości, równoważną niepowtarzalnej sekwencji liczb o nieograniczonej długości. Nie można wygenerować powtarzającej się sekwencji liczb całkowitych o ograniczonej wielkości (np. 32-bit); po wygenerowaniu wszystkich permutacji wartości 32-bitowych sekwencja musi się powtórzyć. Masz rację; mówimy tylko o różnych rzeczach.
9000
@ 9000: Bez łasicy. Złożyłeś ogólne oświadczenie, które jest fałszywe. Jeśli naprawdę próbujesz po prostu mieć nie więcej niż n ^ k różnych sekwencji długości k dla n różnych wartości, i dlatego musi się powtarzać, to jest to dość oczywiste i nie interesujące.
ThePopMachine
2
@ThePopMachine: Byłbym wdzięczny, gdybyś trochę stonował. Cytując, „powtarzanie jest również niemożliwe dla dowolnego generatora z ograniczoną wartością wyjściową (ograniczona liczba bitów)”. To, o czym wyraźnie mówisz, to nieograniczona liczba bitów, jako ciąg cyfr [binarnych] liczby niewymiernej. Twoje stwierdzenie, choć prawdziwe, nie ma związku z problemem.
9000
10

Drugi rozdział książki Discrete-Event Simulation: A First Course autorstwa Lawrence'a Leemisa stanowi fantastyczne wprowadzenie do generatorów liczb losowych (a ściślej - generatorów liczb losowych psuedo).

Fragment jego książki wyjaśnia to dobrze moim zdaniem:

W przeszłości do zastosowań obliczeniowych zalecano trzy typy generatorów liczb losowych: (a) generatory przeglądające tablice w stylu lat 50. XX wieku, jak na przykład tablica korporacyjna RAND z milionem losowych cyfr; (b) generatory sprzętowe, takie jak na przykład termiczne urządzenia „białego szumu”; oraz (c) generatory algorytmiczne (programowe). Z tych trzech typów tylko generatory algorytmiczne uzyskały szeroką akceptację. Powodem tego jest to, że tylko generatory algorytmiczne mają potencjał do spełnienia wszystkich następujących ogólnie ogólnie przyjętych kryteriów generowania liczb losowych. Generator powinien być:

  • random - zdolny do wytworzenia wyniku, który przejdzie wszystkie rozsądne statystyczne testy losowości;
  • sterowalny - w razie potrzeby zdolny do odtworzenia swoich wyników;
  • przenośny - zdolny do wytworzenia tej samej mocy wyjściowej w wielu różnych systemach komputerowych;
  • wydajny - szybki, przy minimalnych wymaganiach dotyczących zasobów komputerowych;
  • udokumentowane - teoretycznie przeanalizowane i szeroko przetestowane.

Tak więc chociaż możliwe byłoby użycie generatora szumów białych w celu uzyskania „lepszych” liczb losowych, nie zyskały one akceptacji, ponieważ nie spełniają większości powyższych kryteriów.

Radziłbym, abyś dostał kopię tej książki (lub czegoś podobnego). Zrozumienie, w jaki sposób praca PRNG z pewnością pomoże ci w twoich wysiłkach.

riwalk
źródło
7

Ponieważ musisz napisać kod, aby wygenerować losowe liczby, a kod NIE jest losowy. (To deterministyczne)

Więc zaczynasz od „Wartości początkowych”, które są wybierane jako „Losowo” (zwykle aktualny znacznik czasu), a następnie używasz go w algorytmie, aby zacząć generować liczby. Ale cały zestaw oparty jest na oryginalnej wartości Seed!

Więc jeśli ponownie uruchomisz kod z dokładnie tymi samymi wartościami nasion, otrzymasz DOKŁADNY ten sam ZESTAW liczb! Jak każda rozsądna osoba może nazwać to przypadkiem? Ale to na pewno nie LOOK losowy.


Jeśli chodzi o uczynienie ich wyjątkowymi, po wygenerowaniu numeru po prostu sprawdź, czy już go masz, jeśli tak, wyrzuć go i wygeneruj nowy.

Kretynowie
źródło
13
Z drugiej strony powtarzalne liczby pseudolosowe mogą być świetne do debugowania.
David Thornley,
5

Ponieważ generujesz liczby losowe, należy oczekiwać, że wygenerowane wartości będą niejednoznaczne. Jest to właściwość losowości - nie można powiedzieć, że sekwencja liczb prawdziwie losowych (lub nawet pseudolosowych) jest unikalna, ponieważ wymaganie to pozwoliłoby przewidzieć końcową wartość w zakresie, a także zmienić prawdopodobieństwo wszystkie niezaznaczone liczby za każdym razem, gdy wybierany jest nowy.

James McLeod
źródło
1
To naprawdę jest komentarz, a nie odpowiedź, ponieważ tak naprawdę nie odpowiada na pytanie .
Mark Booth,
5

Mam bardzo prostą definicję Pseudo Random :

Zbyt wiele nieznanych zmiennych do przewidzenia.

Mam również prostą definicję True Random :

Nieskończone nieznane zmienne.

Problem z komputerem polega na tym, że zawsze zna WSZYSTKIE zmienne. Liczba losowa jest po prostu funkcją matematyczną o pewnej wartości początkowej .
Najlepsze, co możemy zrobić, to podać komputerowi pseudolosową wartość początkową, która zwykle opiera się na zmiennej, której nie jesteśmy w stanie przewidzieć (takiej jak dokładny czas).

Mimo że komputer absolutnie nie jest w stanie utworzyć liczby losowej, dobrze jest wprowadzić zbyt wiele zmiennych, aby można było przewidzieć!

Scott Rippey
źródło
1
Cóż, „czas” jest złym przykładem czegoś, czego nie można przewidzieć. Z drugiej strony ruch myszy, wejście mikrofonu itp. Są danymi nieprzewidywalnymi.
HoLyVieR,
3

Generowanie prawdziwie losowych liczb w oprogramowaniu nie jest w rzeczywistości możliwe, jak zauważyli inni, jednak możliwe jest zbudowanie przez sprzęt urządzenia, które może generować prawdziwie losowe liczby *. Istnieje wiele takich przykładów w Internecie i istnieje wiele różnych metod, od odczytu czasu pomiędzy tyknięciami na liczniku Geigera do próbkowania białego szumu (głównie promieniowania tła z wszechświata) nieregulowanego odbiornika. Sam zbudowałem kilka przy użyciu kilku dostępnych metod.

* Każdy dobry maniak fizyki zwróci uwagę, że biorąc pod uwagę sposób działania wszechświata, żaden z nich nie jest naprawdę technicznie losowy, ale nie ma rozsądnego sposobu przewidzenia wyników, więc ze względu na tę dyskusję są wystarczające.

Unkwntech
źródło
5
Jako maniak fizyki pracujący w niepełnym wymiarze godzin, generatory oparte na zdarzeniach kwantowych są (o ile jesteśmy w stanie powiedzieć) naprawdę losowe. Ludzie, którzy nie lubią przypadkowości, od początku starali się usunąć losowość z mechaniki kwantowej, a wszystko, co zrobiono, to zgromadzić więcej dowodów na to, że jest naprawdę losowa.
David Thornley,
@DavidThornley, ... dopóki ktoś nie wymyśli formuły.
CaffGeek
1
@Chad: Nie ma formuły w zwykłym znaczeniu; co zostało wykluczone z eksperymentów EPR. Z pewnością można sobie wyobrazić, że wszystko jest deterministyczne, ale nie w żaden łatwo zrozumiały sposób.
David Thornley,
@DavidThornley, wiedziałem, że to niewłaściwe słowo do użycia. Chyba wiemy, co chciałem powiedzieć. Prawie zawsze, gdy ktoś mówi, że coś jest niemożliwe, ktoś inny ostatecznie dowodzi, że się mylą. To ludzka natura.
CaffGeek,
2
To tak, jakby powiedzieć, że w końcu ktoś stworzy maszynę, która rozwiąże problem zatrzymania, ponieważ ktoś powiedział, że to niemożliwe. To nie jest kwestia znalezienia równania, w rzeczywistości jest losowe według wszystkich przeprowadzonych eksperymentów i matematyki, która je popiera.
Alex
2

Nie ma możliwości wyprodukowania losowej liczby bez specjalnego sprzętu. W pierwszym roku studiów, z kilkoma kolegami z klasy, zaproponowaliśmy generator liczb losowych, który ma w zasadzie odbiornik AM i dostroił się do 4 różnych kanałów, dostał dane wejściowe do konwertera A na D i dodał je wszystkie (modulo do maksymalnej liczby). Ponieważ kombinacja wejścia analogowego z dowolnej dowolnej liczby stacji jest losowa i moglibyśmy wygenerować dużą liczbę liczb losowych z konwertera A2D, zaproponowaliśmy, że może to być dobry generator. Oczywiście nawet to nie jest przypadkowe w sensie filozoficznym, choć dla większości praktycznych celów może to zadziałać.

Balaji Viswanathan
źródło
2

Determinizm jest zasadniczo funkcją. Pamiętaj z Algebry, że funkcja jest zgodnością między domeną i zakresem, że każdy członek domeny odpowiada dokładnie jednemu członkowi zakresu.

Więc jeśli f (x) = z, f (x)! = Y, chyba że y jest z. To jest funkcja. Wyobraź sobie JavaScript:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

Bez względu na to, ile razy wywołasz Add(2,3), zawsze zwróci 5. Innymi słowy, Add () jest funkcją deterministyczną.

Czynniki zewnętrzne mogą powodować, że Add zachowuje się w sposób niedeterministyczny. Na przykład, jeśli wprowadzisz wielowątkowość do równania. Wkład człowieka powoduje również niedeterminizm.

Teraz rzeczy stają się interesujące.

„Każdy, kto rozważa arytmetyczne metody tworzenia losowych cyfr, jest oczywiście w stanie grzechu”.

Uwaga Von Neumann stwierdza: „arytmetyczne metody wytwarzania [...]”. Nie chodzi tu o wkład człowieka, współbieżność, przykładowe prędkości wiatru odczytane z precyzyjnego przyrządu lub inne nie algorytmiczne sposoby generowania losowego sygnału wejściowego do funkcji deterministycznej.

To po prostu stwierdza, że ​​funkcja lub system funkcji nie stanie się nagle niedeterministyczny. Innymi słowy, Add (2,3) nie zwróci w żaden sposób 6 ani niczego innego niż 5 przy tych samych danych wejściowych . To jest niemożliwe.

Cytujący autor idzie o krok dalej.

Najlepsze, na co możemy liczyć, to liczby pseudolosowe, strumień liczb, które wyglądają tak, jakby zostały wygenerowane losowo.

Kontekst został wcześniej zdefiniowany jako „na dowolnym deterministycznym urządzeniu”. Mógłbym zakończyć tę dyskusję tutaj. Ale co, jeśli zmienimy kontekst, wprowadzając nowy element do systemu? Element niedeterministyczny dodany jako dane wejściowe czyni system systemem niedeterministycznym. Jednak poprzez usunięcie elementu niedeterministycznego sprowadzamy się z powrotem do systemu deterministycznego. Jeśli potrafimy w jakiś sposób prześledzić lub w inny sposób odtworzyć dane wejściowe, możemy odtworzyć wynik. Cały ten akapit jest jednak ściśle związany z tym, co mówi autor. Zapamiętaj kontekst.

Można spierać się o znaczenie niedeterminizmu. Jeszcze raz tangetenial. Zapamiętaj kontekst.

Więc ma rację. Na żadnym deterministycznym urządzeniu układ deterministyczny nie może wygenerować prawdziwego losowego wyniku.

P.Brian.Mackey
źródło