Czy możemy generować liczby losowe przy użyciu liczb niewymiernych, takich jak π i e?

21

Liczby niewymierne, takie jak , i mają unikatową i niepowtarzalną sekwencję po przecinku. Jeśli wyodrębnimy cyfrę z takich liczb (gdzie jest liczbą wywołań metody) i utworzymy liczbę z cyframi takimi, jakimi są, to czy nie powinniśmy uzyskać idealnego generatora liczb losowych? Na przykład, jeśli używamy , i , pierwsza liczba to 123, druga to 471, następna to 184 i tak dalej. $\pi$ $e$ $\sqrt{2}$ $n$ $n$ $\sqrt{2}$ $e$ $\pi$

randomized-algorithms randomness random-number-generator

— Abhradeep Sarkar
źródło

30

Masz dziwną definicję „losowości” w twojej głowie. „Losowy” oznacza „nieprzewidywalny”. Jak twoja sekwencja jest nieprzewidywalna? Jaką masz na myśli definicję „losowego”? Być może to, co nazywacie „losowym”, ma inną nazwę.

— Eric Lippert

7

Uwaga: algorytmu czopka można użyć do wygenerowania dowolnej cyfry szesnastkowej w pi bez konieczności generowania wcześniejszych cyfr.

— rcgldr

10

@EricLippert Czy wszystkie generatory liczb pseudolosowych nie są przewidywalne?

— Federico Poloni

7

Termin pojawił się kilka razy: jest to „liczba losowa psuedo”, a nie „liczba losowa”. Jest to liczba generowana algorytmicznie (więc nie losowo), ale która ma wiele pożądanych właściwości, które mają liczby losowe. Kolejnym algorytmem jest algorytm „Książka telefoniczna NYC”, w którym alfabetycznie przeglądasz listę numerów telefonów i pobierasz z nich ostatnią cyfrę. Nie losowy, ale pseudolosowy z pewnymi ładnymi zachowaniami statystycznymi!

— Cort Ammon - Przywróć Monikę

5

„Pseudo” oznacza „podobny do ale nie”. Pseudolosowe liczby są więc podobne, ale nie losowe. Więc nie podążam tutaj za tobą. Teraz PRNG o sile kryptograficznej mają pożądaną właściwość, że jeśli atakujący nie zna stanu wewnętrznego, żaden test statystyczny, który posiadamy, nie byłby w stanie odróżnić kryptograficznego PRNG od prawdziwego RNG, co obejmuje ich brak przewidywalności. Ale cyfry pi nie mają tej właściwości; są wysoce przewidywalne.

— Eric Lippert

17

Najbardziej oczywistą wadą jest niepotrzebna złożoność algorytmów PRNG opartych na liczbach niewymiernych. Wymagają znacznie więcej obliczeń na wygenerowaną cyfrę niż, powiedzmy, LCG; i ta złożoność zwykle rośnie wraz z postępem w sekwencji. Obliczenie 256 bitów π w dwu kwadrylionowym bicie zajęło 23 dni na 1000 komputerach (w 2010 roku) - dość zaporowa złożoność dla RNG.

— Dmitrij Grigoriew
źródło

47

Dla każdej rozsądnej definicji ideału mechanizm, który opisujesz, nie jest doskonałym generatorem liczb losowych.

Niepowtarzanie nie wystarczy. Liczba dziesiętna $0.101001000100001\dots$ nie jest powtarzalna, ale jest strasznym generatorem losowych cyfr, ponieważ odpowiedź jest „zawsze” zero, czasami jedna i nigdy nic więcej.
W rzeczywistości nie wiemy, czy każda cyfra występuje równie często w rozwinięciu dziesiętnym $\pi$ lub $\mathrm{e}$ (choć podejrzewamy, że tak się dzieje).
W wielu sytuacjach wymagamy, aby losowe liczby były nieprzewidywalne (w rzeczywistości, gdyby zapytać przypadkową osobę, co oznacza „losowy”, prawdopodobnie powiedziałby coś o nieprzewidywalności). Cyfry znanych stałych są całkowicie przewidywalne.
Zwykle chcemy dość szybko generować liczby losowe, ale generowanie kolejnych cyfr stałych matematycznych bywa dość kosztowne.
Prawdą jest jednak, że cyfry $\pi$ i $\mathrm{e}$ wyglądają statystycznie losowo, w tym sensie, że każda możliwa sekwencja cyfr wydaje się występować tak często, jak powinna. Na przykład każda cyfra występuje bardzo blisko raz na dziesięć; każda dwucyfrowa sekwencja bardzo bliska jednej na sto i tak dalej.

— David Richerby
źródło

11

Po trzecie, musi być jakiś „tajny” wkład w proces generowania, aby był nieprzewidywalny (sam proces generowania powinien być deterministyczny, jeśli nie chcemy polegać na innym generatorze liczb losowych). Ten dodatkowy wkład jest często nazywany zalążkiem .

— Dyskretna jaszczurka

6

@Discretelizard To prawda, ale nie ma zbyt wiele miejsca na rozsiewanie poza „zwracaj kolejne cyfry, zaczynając od pozycji

”. Do czasu, kiedy widziałem

cyfr, że sekwencja występuje tylko kilka razy w ciągu pierwszych

cyfry

, więc jest to unikalny w ciągu pierwszych

cyfr z dużym prawdopodobieństwem i wiesz nasienie.

s

$s$

2 \log s

$2\log s$

s^{2}

$s^2$

π

$\pi$

s

$s$

— David Richerby

2

@Barmar: W tym momencie musisz zapytać, czy ta technika jest naprawdę bardziej wydajna (i zajmuje więcej miejsca) niż „standardowy” PRNG.

— Kevin

2

Cyfry pi lub e są całkowicie nieprzewidywalne, zwłaszcza że przeglądający / odbiorca / łamacz kodów itp. Nie ma pojęcia, jak daleko jesteś w sekwencji. Jeśli zaczniesz od cyfry 237423 sekwencji, ustalenie losowości zajmie tak dużo czasu.

— Odwrócony inżynier

10

@DaveBoltman Jeśli nie robimy czegoś takiego jak kryptografia, nikt nie będzie na tyle dbał o to, aby sobie z tym poradzić. Jeśli wykonujemy kryptografię, to standardowe założenie, że twój przeciwnik wie, jakiego algorytmu używasz, w tym przypadku obejmuje liczbę nieracjonalną, z której pochodzi sekwencja i sposób wybierania cyfr, z wyjątkiem dowolnego parametru, takiego jak „zacznij od cyfry

”. Jeśli przeciwnik nie wie, jakiej liczby używasz, to następna cyfra może być dosłownie czymkolwiek, ale wtedy zgadują, że to

s

$s$

i gra skończona.

\sqrt{my birthday}

$\sqrt{\text{my birthday}}$

— David Richerby

29

Jest kryptograficznie bezużyteczny, ponieważ przeciwnik może przewidzieć każdą cyfrę. Jest to również bardzo czasochłonne.

— gnasher729
źródło

11

OP nigdy nie wspomina o kryptografii ...

— AnoE

13

@AnoE Więc? To, że proces ten byłby kryptograficznie bezużyteczny, jest nadal istotne, ponieważ crypto jest zapalonym użytkownikiem losowości. Jeśli uruchomisz urządzenia, /dev/randoma /dev/urandomktoś niezmiennie wywoła kryptografię.

— Greg Schmit - Przywróć Monikę

6

Byłbyś zaskoczony, jak bezużyteczne zabezpieczenia kryptograficzne są w czasie rzeczywistym generowaniem PRNG. liczby niewymierne są często używane w PRNG GPU. Istnieje wiele aplikacji, w których „bezpieczeństwo” PRNG jest po prostu nieistotne. W czymś takim jak spójne generowanie hałasu jest jakość dystrybucji i częstotliwość powtarzania okresu oraz efekty korelacji z powodu sąsiednich ziaren (które wymagałyby naprawy mikserów lawinowych). Szczerze mówiąc, twoja odpowiedź jest zła, nie należy tutaj i prawdopodobnie powinna zostać usunięta.

— kiedy

6

To nie jest odpowiedź na pytanie. Uwaga: OP w połączonym pytaniu używa liczb losowych do zaszczepienia analizy Monte Carlo. Należy rozważyć aktualizację w celu rozwiązania zadanego pytania. mathoverflow.net/questions/26942/…

— CramerTV

8

Z pewnością istnieje wiele aplikacji, w których PRNG nie muszą być zabezpieczone kryptograficznie. Ale OP nie zapytał, czy przydałby się w niektórych celach, zapytali, czy ta metoda jest „idealną RNG”. Chociaż nie wyjaśnili, co rozumieją przez „doskonały”, fakt, że nie nadaje się do jednego z głównych zastosowań RNG, wydaje się bardzo istotny dla odpowiedzi na to pytanie.

— Geoffrey Brent

7

( zaktualizowane po tym, jak wiele osób zauważyło, że generator liczb losowych to nie to samo, co pojedyncza normalna sekwencja)

$\pi$

$\pi$

Dane dotyczące dystrybucji cyfr znajdują się np. Http://www.eveandersson.com/pi/precalculated-frequencies lub https://thestarman.pcministry.com/math/pi/RandPI.html (pierwsze 1000 cyfr):

Na stronie mathoverflow znajdują się również ładne odpowiedzi na:

— Ayrat
źródło

3

Jeśli uważasz, że pytanie jest duplikatem, to dlaczego na nie odpowiadasz? Powinieneś go po prostu oflagować, a nie wzmacniać niepożądane zachowania związane z publikowaniem.

— dkaeae

8

@dkaeae Nie ma wsparcia dla duplikatów pytań na innych stronach. Co więcej, to samo pytanie na różnych stronach może uzyskać różne odpowiedzi. W takim przypadku witryna taka jak matematyka może nie zwracać uwagi na kwestie bezpieczeństwa. Zobacz także tę odpowiedź . Pamiętaj, że odradzamy zadawanie tego samego pytania na wielu stronach jednocześnie, ponieważ prowadzi to do zmarnowanych wysiłków. Ale to samo pytanie różnych osób w różnych momentach na różnych stronach jest zwykle w porządku.

— Dyskretna jaszczurka

6

Niestety, tylko dlatego, że liczba jest normalna, nie oznacza, że wyprowadzenie jej cyfr daje dobre RNG. Wyniki takiego RNG są nadal całkowicie przewidywalne. To, czy jest to dopuszczalne, może zależeć od aplikacji. Nie sądzę więc, żeby to było tak proste, jak powiedzenie „pi jest normalne, sprawa zamknięta”.

— DW

2

Czy to tylko obserwacja cesarska dla pierwszych kilku cyfr? Co to ma znaczyć?

— marszałkowiec

1

@DW Wspomniałem, że zamierzam użyć kombinacji liczb takich jak π i e. I proszę powiedzieć, w jaki sposób wyjście będzie przewidywalne, jeśli nie będziemy wiedzieć, jak daleko w dół sekwencji poszedł generator?

— Abhradeep Sarkar

1

Ogólnie rzecz biorąc, to podejście nie działa: „losowość” nie oznacza, że otrzymujesz wiele różnych cyfr, ale są też inne aspekty. Na przykład klasyczny test polega na sprawdzeniu, czy wszystkie dwucyfrowe lub trzycyfrowe kombinacje itp. Występują z tą samą częstotliwością. Byłby to bardzo prosty test, który może wykluczyć oczywiste nieprzypadkowe wyniki, ale wciąż jest zdecydowanie zbyt uproszczony, aby sprawdzić, czy zachowuje się naprawdę losowo.

Zobacz stronę Wikipedii na temat testów losowości jako zbiór linków do głównych źródeł na ten temat. Wspominają o dość skomplikowanych koncepcjach; nie jest tak ważne, aby zagłębiać się w to szczegółowo - ale jasne jest, że intuicyjnie nie można zadeklarować określonej liczby jako dobrego źródła dla takich cyfr.

Pozytywnie: w przypadku konkretnej liczby niewymiernej możesz oczywiście po prostu spróbować; tzn. oblicz liczbę w dostatecznie dużym stopniu cyfr i przeprowadź ją przez wszystkie znane testy (istnieją do tego narzędzia, patrz powyższy link). Jeśli miara jest wystarczająca dla twojego przypadku użycia i jeśli masz świadomość, że jest to oczywiście bezużyteczne w przypadku aplikacji kryptograficznych, i zawsze otrzymuj te same liczby, jeśli powinieneś zacząć od nowa, i że jakość może się pogorszyć, jeśli przejdziesz przez nwybrany do testowania losowości można użyć tych liczb. Ale znacznie lepiej będzie użyć dedykowanego (pseudo-) generatora liczb losowych; i nic nie przebije dobrego fizycznego źródła losowości.

— AnoE
źródło

4

π

$\pi$

e

$\mathrm{e}$

3

Odpowiedź Ayrata prowadzi do innych stron, na których matematycy przeprowadzili te testy. Uważają, ale nie udowodnili, że π spełnia testy statystyczne.

— Barmar

Tak, o to mi chodziło w moim ostatnim akapicie - warto spróbować tylko empirycznie; ale rygorystycznie nie zostało to udowodnione (lub nie można po prostu założyć, że jest to prawda) dla dowolnych „irracjonalnie wyglądających” irracjonalności. @DavidRicherby, @ Barmar

— AnoE

1

Zapewnia dobrą liczbę losową, dopóki nie zdasz sobie sprawy, jak została wytworzona, podobnie jak wiele pseudolosowych liczb. Wybrane przez ciebie irracjonalne (niealgebraiczne i nie transcendentalne) liczby są wspólne i dlatego łatwiej je zgadnąć niż inne. Nie widzę żadnego problemu z tą metodą, pod warunkiem, że wybierzesz mniej popularne generatory.

— rzemiosło marszałkowskie
źródło

4

Nie ma problemu poza rażącą nieefektywnością, faktem, że polegasz na przeciwniku, który nie zna twojego algorytmu, fakt, że zły wybór generatora może prowadzić do bardzo złej sekwencji, ...

— David Richerby

4

\sqrt{2}

$\sqrt{2}$

π

$\pi$

e

$\mathrm{e}$

Liczba transcendentalna jest liczbą rzeczywistą, która nie jest algebraiczna. Nie jest możliwe, aby liczba rzeczywista była jednocześnie niealgebraiczna i transcendentalna.

— Brady Gilg,