Czym naprawdę jest przypadkowość

Jestem studentem informatyki i obecnie zapisuję się na kurs Symulacji Systemów i Modelowania. Obejmuje to radzenie sobie z codziennymi systemami wokół nas i symulowanie ich w różnych scenariuszach przez generowanie liczb losowych w różnych krzywych dystrybucyjnych, takich jak na przykład IID, Gaussa itp. Pracowałem nad projektem boids i właśnie uderzyło mnie pytanie, czym tak naprawdę jest „losowość”? Chodzi mi na przykład o to, że każda generowana przez nas liczba losowa, nawet w naszych językach programowania, takich jak Math.random()metoda w Javie, jest generowana zgodnie z „algorytmem”.

Skąd naprawdę wiemy, że ciąg liczb, który tworzymy, jest w rzeczywistości losowy i czy pomógłby nam symulować określony model tak dokładnie, jak to możliwe?

Krótka odpowiedź jest taka, że ​​nikt nie wie, czym jest prawdziwa przypadkowość, ani czy coś takiego istnieje. Jeśli chcesz skwantyfikować lub zmierzyć losowość dyskretnego obiektu, zwykle zwróciłbyś się do złożoności Kołmogorowa . Przed złożonością Kołmogorowa nie mieliśmy możliwości oszacowania losowości powiedzmy sekwencję liczb bez uwzględnienia procesu, który ją zrodził.

Oto intuicyjny przykład, który naprawdę wkurzał ludzi w ciągu dnia. Rozważ sekwencję rzutów monetą. Rezultatem jednego rzutu są albo głowy ( ), albo ogony ( T ). Powiedzmy, że wykonujemy dwa eksperymenty, w których rzucamy monetą 10 razy. Pierwszy eksperyment E 1 daje nam H , H , H , H , H , H , H , H , H , H . Drugi eksperyment E 2 daje nam T , T , H , T , H $H$$T$$E_1$$H,H,H,H,H,H,H,H,H,H$$E_2$ . Po zobaczeniu wyniku możesz pokusić się o stwierdzenie, że coś było nie tak z monetą w E 1 , a przynajmniej z jakiegoś dziwnego powodu to, co otrzymałeś, nie jest przypadkowe. Ale jeśli można zakładać zarówno H i T są prawdopodobne (moneta jest uczciwa), prawdopodobieństwo uzyskania albo E 1 lub E 2 jest równy ( 1 / 2 ) 10 . W rzeczywistości uzyskaniedowolnejokreślonej sekwencji jest tak samo prawdopodobne jak każde! Mimo to E 2 wydaje się$T,T,H,T,H,T,T,H,T,H$$E_1$$H$$T$$E_1$$E_2$$(1/2)^{10}$$E_2$ losowy, a nie.$E_1$

Ogólnie rzecz biorąc, ponieważ złożoności Kołmogorowa nie można obliczyć, nie można obliczyć, jak losowy jest ciąg sekwencji liczb, bez względu na to, jaki rodzaj roszczenia spowodował „całkowicie losowy” proces.

W przypadku Javy (lub podobnych języków) znamy algorytm używany do tworzenia liczb losowych. Jeśli zaczyna się od pojedynczego materiału siewnego, numery nie są przypadkowe w ogóle, to znaczy, jeśli wiemy, w sekwencji 0 , ... , n , wiemy jak I + 1 , lub określona jako prawdopodobieństwa warunkowego: ∀ k , l , i : P ( a i + 1 = k ∣ a i = l ) ∈ { 0 $a_i$$a_0,\dots,a_n$$a_{i+1}$

Niemniej jednak te serie mogą spełniać właściwości (patrz np. WP: autokorelacja ), które spełniają liczby losowe i te właściwości często wystarczają do wykonania zadań, w których chcielibyśmy użyć „rzeczywistych” (np. Wygenerowanych przez jakiś proces fizyczny) liczb losowych, ale mogą „ wysilam się.

Nie ma pewności, czy dana sekwencja jest losowa, czy nie. Możesz jednak spojrzeć na cechy (lub parametry) sekwencji i obliczyć prawdopodobieństwo takiej sekwencji, biorąc pod uwagę rozkład zainteresowania.

Jeśli możesz wygenerować nieskończenie długą sekwencję za pomocą generatora losowego, powinien on mieć takie same parametry jak rozkład losowy. Na przykład, jeśli używasz standardowego rozkładu Gaussa , to twoja sekwencja powinna zbliżać się do średniej 0 i standardowego odchylenia 1 . Tak więc jednym wstępnym sposobem sprawdzenia generatora jest wygenerowanie naprawdę długiej sekwencji i sprawdzenie, czy jest ona zbliżona do pożądanego rozkładu losowego.$(\mu=0,\sigma=1)$$1$

Możesz dodać dodatkowe momenty interesującego rozkładu (takie jak skośność) w celu dalszej weryfikacji. W przypadku liczb IID można również spróbować wyszkolić algorytm uczenia maszynowego w celu przewidywania nadchodzących elementów sekwencji, a następnie przetestować hipotezę zerową, że historia poprawia wydajność. Żadna z tych metod nie może jednak udowodnić, że sekwencja jest naprawdę losowa, aw najlepszym przypadku może rozpoznać, kiedy sekwencje NIE są losowe (do pewnego stopnia pewności).

Współczesna teoria odpowiedzi komputerowej brzmi: „źródło losowe jest źródłem losowym dla ulubionej klasy algorytmów”. Jest to utylitarna perspektywa: jeśli źródło przypadkowości wygląda jak prawdziwa przypadkowość dla wszystkich algorytmów, na których Ci zależy, nic innego się nie liczy. Możesz analizować swoje algorytmy, jakby otrzymywały naprawdę losowe rzuty monetami, a Twoja analiza da prawidłowe odpowiedzi.

$\mathcal{A}$$\mathcal{A}$

• wszystkie maszyny Turinga, które zawsze się zatrzymują
• wszystkie rodziny obwodów wielomianowych
• maszyny Turinga z wielomianowym czasem
• wszystkie maszyny logistyczne Turinga

$\mathcal{A}$$(X_n)$$X_n$$\{0, 1\}^n$$\epsilon$$\mathcal{A}$$A \in \mathcal{A}$

Pomysł ten kryje się za każdym nowoczesnym formalnym pojęciem pseudolosowości.

Oto dwa kolejne centy.

Jednym ze sposobów myślenia o algorytmach losowych jest zobrazowanie ramki, która pobiera dane wejściowe, robi z nimi tajemnicze rzeczy i wytwarza pewne („nieprzewidywalne”) dane wyjściowe.

Zamiast tego pomocne może być myślenie o nich jako o deterministycznych algorytmach, które pobierają dwa dane wejściowe: „prawdziwy” sygnał wejściowy i niektóre „losowe” dane wejściowe, które otrzymujemy z funkcji takich jak Math.Random().

$[0,1]$$n \log n$

$[0,1]$$n \log n$

Jak wspominają Jonathan i Frafl, istnieją sposoby na sprawdzenie, czy przypadkowe źródło zachowuje się „losowo”. Ale wszystko, co zrobią, to wpływ na to, co wierzysz o przyszłe informacje pochodzące z tego losowego źródła. Jeśli uważasz, że każdy bit może być równy zero lub jeden, niezależnie od poprzednich bitów, to zgodnie z Twoją najlepszą wiedzą i przekonaniami, to źródło jest jednolicie i niezależnie losowe, a zatem, zgodnie z Twoją najlepszą wiedzą i przekonaniami, będzie działał szybko, będzie poprawny itp. To zresztą moje filozoficzne podejście.

Nie możemy wygenerować liczb naprawdę losowych. Istnieją różne metody generowania liczb pseudolosowych przy użyciu określonego równania i określonej wartości początkowej. Tak więc losowa sekwencja liczb zależy od wartości początkowej. Po poznaniu wartości początkowej możemy przewidzieć, jaka będzie sekwencja. Oprócz tego istnieją inne metody generowania liczb losowych. Ludzie używają teraz niektórych metod do generowania prawdziwych liczb losowych, takich jak wykorzystanie czasu ruchu głowicy dysku i inne metody fizyczne, które można włączyć do komputera. Patrz: http://en.wikipedia.org/wiki/Random_number_generation#Generation_methods

podaną metodą, tak jak powiedziałeś
Math.random () w Java
Randomize; Losowo (n); w Delfach

możesz zaimplementować własną strukturę i logikę do generowania liczb losowych, przy
czym taki „algorytm” może działać zgodnie z podanymi specyfikacjami w celu uzyskania lepszych wyników losowych.
i budować na tym logikę.

Dzięki.

inne odpowiedzi są dobre, oto inne punkty widzenia na to bardzo ważne / mimowolnie głębokie pytanie. informatycy badają losowość od dziesięcioleci i prawdopodobnie nadal ją badają. ma wiele głębokich powiązań i przede wszystkim otwarte pytania pozostające w terenie. oto kilka wskazówek.

• „prawdziwa / rzeczywista losowość” występuje w procesach fizycznych niskiego poziomu i „szumach”, takich jak diody Zenera, mechanika kwantowa itp., które można wykorzystać w sprzętowych RNG

• inne liczby generowane w sferze komputerowej to tak zwane „pseudolosowe” które jest symulowane i nigdy nie może się równać z „prawdziwą przypadkowością”. są to tak zwane PRNG

• istnieje ważne poczucie „twardości kryptograficznej generatorów liczb losowych”, które w pewnym sensie mierzy ich „jakość” lub „bezpieczeństwo”, patrz np. kryptograficznie bezpieczny PRNG . w zasadzie „słaby” generator nie ma tyle złożoności obliczeniowej, co „twardy” generator, a „słaby” generator jest łatwiejszy do złamania.

• Innym dość pokrewnym poczuciem, jakie się pojawia, jest „twardość dowodów”. wyobraź sobie dowód na to, że RNG jest czasem liniowym$O(n)$. dowód ten wydaje się prostszy niż wymagany do udowodnienia, że ​​jest kwadratowy$O(n^2)$i tak dalej. koncepcja ta jest wciąż formalizowana / badana, ale w rzeczywistości wpływa na głębokie pytania, takie jak P.$\stackrel{?}{=}$NP w słynnej pracy o nazwie Natural Proofs . z grubsza autorzy pokazują P$\neq$Dowód NP musi mieć pewną „złożoność”, w przeciwnym razie można zastosować tę samą technikę analizy, aby rozbić PRNG, a ponadto, co nieco zaskakujące, większość lub może wszystkie separacje / techniki klas złożoności znane w tym dniu (lub nawet później, do tej pory ) nie mają wystarczającej złożoności.

• ważnym tematem badawczym w TCS są algorytmy randomizowane i derandomizowane . z grubsza chodzi o zbadanie, jak bardzo algorytm jest zmieniany przez zastąpienie „prawdziwej przypadkowości” PRNG, a na ten temat istnieją różne głębokie twierdzenia. oto wysoko postawione pytanie cstheory.se, które nadaje posmak badań w tej dziedzinie: wydajne i proste randomizowane algorytmy, w których determinizm jest trudny

• innym kluczowym tematem związanym z TCS jest entropia informacji - pierwotnie wprowadzona w fizyce dawno temu - która bada ściśle powiązaną koncepcję „rozrzucenia informacji” i podobnie jak niektóre inne ważne pojęcia w (T) CS wydaje się być jedną z kluczowych idei, które przecinają granica między zastosowaną a teoretyczną analizą, nawet niektóre formuły są takie same .

• ponownie potwierdzając status aktywnych badań, istnieją inne wysoko postawione pytania na cstheory.se, które dotyczą tego pytania. tutaj jest jeden blisko, prawie taki sam: jest naprawdę losowym generatorem liczb obliczalnym przez Turinga