Algorytm generowania liczb losowych dla ludzkich mózgów? [Zamknięte]

Czy znasz lub opracowałeś jakieś praktyczne, łatwe do nauczenia się algorytmy „w głowie”, które pozwalają ludziom generować (nieco „prawdziwe”) liczby losowe? Przez „w głowie” rozumiem… najlepiej bez żadnych zewnętrznych narzędzi i urządzeń. Ponadto pożądana jest wysoka wydajność (wiele liczb losowych na minutę).

Zapytałem o to na SO, ale nie spotkało się to z dużym zainteresowaniem. Może to lepiej nadaje się dla programistów.

Oto algorytm George'a Marsaglii :

Wybierz 2-cyfrowy numer, powiedzmy 23, „twoje ziarno”.

Utwórz nową 2-cyfrową liczbę: cyfra 10 plus 6-krotna cyfra jednostek.

Przykładowa sekwencja to 23 -> 20 -> 02 -> 12 -> 13 -> 19 -> 55 -> 35 -> ...

a jego okres jest rzędu mnożnika 6 w grupie reszt względnie pierwszych względem modułu 10. (59 w tym przypadku).

„Losowe cyfry” to cyfry jednostek liczb dwucyfrowych, tj. 3,0,2,2,3,9,5, ... sekwencja mod 10. Arytmetyka jest na tyle prosta, że ​​można ją wykonać w twoim głowa.

Sprawdź ten artykuł na temat Geomancji . W szczególności sekcja na temat generowania map geomantycznych . Obejmuje technikę generowania liczb pseudolosowych z wykorzystaniem cyfr binarnych i prostych obliczeń rekurencyjnych. Wygląda na to, że dość łatwo można to zrobić w głowie (choć kawałek papieru by to pomógł).

Oświadczenie: sam tego nie próbowałem; kiedy potrzebuję wystarczająco losowej liczby, albo otrzymuję dane wyjściowe /dev/random, używam randw dowolnym języku, który mam pod ręką, lub rzucam moim zaufanym d20.

Jeśli jesteś cudownym matematykiem, metoda na środku kwadratu jest dość lekką obliczeniowo, choć zauważalnie niewiarygodną metodą.

Myślę, że rozsądnym założeniem jest to, że musisz polegać na ogromnej ilości informacji werbalnych przechowywanych w twoim mózgu. Źródłem może być wszystko, teksty piosenek, wiersze, szkice Monty Python, ale musi to być coś, co znasz na pamięć.

Następnie musisz wybrać dość losową jego część, eliminując w jak największym stopniu nieświadome uprzedzenie. Przykładem tego może być wybranie utworu, wybranie numeru kod 10 do 20, a następnie znalezienie klitery w jej tekście.

Oczywiście nie zapewni to jednolitego rozkładu, ponieważ częstotliwość liter jest inna, ale mimo to jest to losowa litera lub przynajmniej tak blisko niej, jak uważam, jest możliwe bez zewnętrznego źródła.

Aktualizacja: Nawiasem mówiąc, gdy ludzie są proszeni o napisanie losowej sekwencji rzutów monetą, najczęstszym błędem jest zdecydowanie uczynienie sekwencji „zbyt losową”: serie identycznych wyników będą zbyt krótkie, co zwykła długość serii analiza ujawni. Ta metoda ma głównie na celu uniknięcie tej pułapki. Oczywiście inne anomalie mogą wynikać z cienia tej tendencyjności, ale by je znaleźć, potrzebne są odpowiednie eksperymenty. Jak na ironię, algorytmu generowania liczb losowych przez samo myślenie nie można znaleźć samemu myśląc.

Próbkuj swój zegarek.

Robię to, jeśli potrzebuję liczby losowej o wartości 60 (sekund). Weź odpowiedni modulo o dowolnej porze. 16:17:23, symulując rzut kostką, staje się 5.

Doskonałe pytanie. Obawiam się, że dobra odpowiedź może okazać się bardzo trudna.

Ale na początek dość łatwo jest wygenerować „prawdziwą” przypadkowość, gdy zaangażowane są dwie osoby: po prostu pozwól jednej z nich liczyć cicho w module głowy pewną liczbę, a druga powie „zatrzymać” po dowolnym odstępie czasu. Następnie liczbę tę można przekształcić w inne dystrybucje przy użyciu standardowych metod.

Aby ta metoda była niezawodna, moduł nie może być zbyt duży, w przeciwnym razie wystąpi silne odchylenie od małych liczb. Naprawdę chciałbym sprawdzić, czy istnieją prace analizujące stochastyczne właściwości tej metody.

To złożone pytanie; Spróbuję wyjaśnić trochę, nie wędrując zbyt daleko w stronę chwastów.

Najpierw musimy zapytać „czym jest prawdziwa przypadkowość”? Takie dyskusje szybko przeradzają się w wody filozoficzne, ale sedno jest takie: „czy wszechświat jest naprawdę przypadkowy”? Innymi słowy, jeśli kwantyzujesz czas i materię, czy możesz obliczyć następny stan wszechświata na podstawie obecnego? Jeśli tak, to wszechświat jest deterministyczny i nie ma prawdziwej przypadkowości (zobacz, co mam na myśli mówiąc o „filozofii”?)

Ponieważ „prawdziwa losowość” jest trudna do zdefiniowania, często zadowalamy się „pseudolosowością”. Jest to oczywiście wymagane przy generowaniu „losowych” liczb na komputerze.

Najprostszym generatorem liczb pseudolosowych byłby coś w rodzaju słynnego algorytmu Dilberta „9… 9… 9…”. Ale intuicyjnie nie wydaje się to zbyt dobre (co oczywiście jest żartem). Statystycy opracowali cały szereg testów, aby stwierdzić, czy sekwencja rzekomo losowych wyników jest „dobra”. Zacznij od strony wikipedii dla „chi kwadrat test” i możesz spędzić popołudnie po prostu czytając o tych testach.

Prosty algorytm komputerowy, taki jak „liniowy kongruencjalny generator”, generuje liczby wystarczająco dobre do testu chi-kwadrat (jednak nadal trzeba „wysiać” ten algorytm z czegoś).

Następnym krokiem w „dobroci” jest „kryptograficznie silna losowość”, co oznacza, że ​​biorąc pod uwagę sekwencję a1, a2,… nie można przewidzieć kolejnej liczby w sekwencji z „rozsądnym prawdopodobieństwem”, chyba że zastosuje się dużo obliczeń. Liczby te są czasami nazywane „pseudolosowymi obliczeniowo”. Jednym z powszechnych sposobów uzyskania takiej sekwencji jest „łańcuch mieszania”, taki jak: a1 = SHA512 (a2), a2 = SHA512 (a3), ... Ponieważ wierzymy (na podstawie doświadczenia, a nie matematycznego dowodu), że SHA512 jest trudno jest odwrócić obliczeniowo, uważamy, że a2 jest „niemożliwe” do przewidzenia, biorąc pod uwagę tylko a1.

Teraz pojawia się pytanie, co najlepiej zrobić ludzie zgodnie z zasadami określonymi w twoim pytaniu? Ludzie są znani z generowania przypadkowości; kiedyś istniała strona internetowa, w której próbowałbyś generować rzuty monetą przez „losowe” wpisywanie H, T, T, H, H, T, T itp. tak jakbyś rzucił monetą (ale robisz to w Twoja głowa). Po chwili strona internetowa zacznie przewidywać twoje przewroty lepiej niż w 50% przypadków (przy użyciu ukrytego modelu Markowa). Jesteśmy w tym po prostu źli.

Istnieją sposoby na poprawę sytuacji za pomocą różnych technik miksowania, które prawdopodobnie są możliwe do wykonania w twojej głowie. Są nawet aplikacje, o których mógłbym wymyślić, dlaczego możesz tego chcieć (więzień polityczny chce zaszyfrować wiadomość do zewnętrznych sojuszników). Ale myślę, że ten post jest wystarczająco długi. :)

Głównym powodem rozprzestrzeniania się RNG opartych na narzędziach jest to, że należy opracować dobry algorytm generowania liczb losowych .

Na szczęście przenośne generatory liczb losowych - w tym monety do flopowania, kości (z różną liczbą faset) do toczenia, karty do zbierania i słomki do losowania - są stosunkowo łatwe do uzyskania przy niskich kosztach. Co więcej, dla technofilów wśród nas istnieją pewne dość dobre symulacje tych narzędzi dostępne dla większości platform mobilnych.

Serdecznie poleciłbym którykolwiek z nich zamiast jakiejkolwiek alternatywy dla wyrobów mięsnych.

Wysoce losowa, duża ilość na minutę i generowana przez ludzi? Nie wydarzy się

Główne problemy, z którymi będziesz się borykać to:

• Ludzie szybko się nudzą, więc wzory pojawią się szybko
• Ludzki mózg ma wiele struktur poświęconych rozpoznawaniu / tworzeniu wzorców, więc będziesz musiał to pokonać
• Prawdziwie losowe liczby zawierają powtórzenia, których ludzie starają się unikać
• Ludzie nie są dobrzy w przypadku dużych liczb

Doprowadziło to wielu kryptografów do porzucenia technik „in-head” na rzecz losowych procesów zewnętrznych, ponieważ zbyt proste było wypracowanie wzorców opartych na liczbach „in-head”.

Nie na temat, ale interesujące

Chociaż nie jest to mechanizm generowania liczb losowych w twojej głowie, algorytm Solitaire (przedstawiony w Cryptonomicon Neala Stephensona ) pokazuje, jak trudno jest używać liczb losowych do celów kryptograficznych. Wymaga tylko paczki zwykłych kart do gry, aby stworzyć dość bezpieczne wyjście, ale metoda jest dość skomplikowana.

Jestem naprawdę ciekawy wszystkiego, co ludzie mogliby wymyślić w związku z tym problemem.

Odsuń się od biurka i jedź do Las Vegas.

Ludzkość ma dziesiątki losowych procedur. Możesz zobaczyć je wszystkie w Las Vegas.

Masz wirujące kręgi. Masz walące się kostki. I tasowałeś tokeny. Wszystkie działają cudownie dobrze.

Kostki są chyba najstarsze. Najwyraźniej w jednym punkcie zastosowano wydłużone 4-stronne drążki. Symetryczne kostki kostkowe owiec były popularne od tysiącleci. Używamy tego rodzaju randomizatorów od - prawdopodobnie - mniej więcej w tym samym czasie, gdy opracowaliśmy język.

http://itunes.apple.com/us/app/motionx-dice/id287509231?mt=8

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

--- John von Neumann

Nie mogę wymyślić żadnego. W rzeczywistości spodziewałbym się, że wszystko, co wymyślisz, miałoby w sobie tyle stronniczości, że byłoby bezwartościowe.

Jeśli potrzebuję liczb losowych, generalnie rzucam kośćmi.

Czy prosisz o LCM, który możesz zrobić w swojej głowie? Zauważ, że pomysł, że jest to lepsze niż kostka, pozostaje absurdalny.

Jest to jednak tak losowe, jak to tylko możliwe, każdy algorytm skończony, określony i skuteczny.

http://www.vias.org/simulations/simusoft_lincong.html

http://www1.i2r.a-star.edu.sg/~knandakumar/nrg/Tms/Probability/Probgenerator.htm

U_ {k + 1} = (a \ razy U_k + b) mod (m + 1).

Łatwiej jest zobaczyć, co to robi, jeśli wybieramy małe wartości a = 5, b = 1 i m = 7. Powinieneś być w stanie to zrobić w swojej głowie.