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

37

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.

Magnus Wolffelt
źródło
7
@ S.Lott Nie wydaje mi się, żeby to było absurdalne. Niepraktyczny? Ależ oczywiście. Absurd? Zdecydowanie nie. I nawet gdyby tak było, absurdalność może utorować drogę dla nowych, przydatnych myśli.
biziclop
21
9 .... 9 .... 9 .... 9 - Nie możesz udowodnić, że nie jest przypadkowy.
13
S.Lott: Pomysł easzy do obliczenia generatora liczb pseudolosowych wcale nie jest absurdalny. Myślę, że OP chce tutaj uniknąć sposobu na uprzedzenia ludzi ...
Jens
8
Zabawne (i jednocześnie nieco przygnębiające) jest dla mnie to, jak wielu ludzi docenia argument niewiedzy. „Nie mogę sobie tego wyobrazić, dlatego nie może istnieć” lub odpowiedzi, które zupełnie nie mają sensu.
biziclop
4
To pytanie wydaje się być nie na temat, ponieważ dotyczy zdolności poznawczych jednostki, a nie programowania.

Odpowiedzi:

36

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.

Davo
źródło
To brzmi naprawdę dobrze.
biziclop
4
Może to nie stanowić problemu dla potrzeb konkretnej osoby, ale daje to tylko 90 różnych strumieni.
compman
5
79, 79, 79, 79, 79, 79, 79, 79, 79, 79, och nie! Zakładam, że powinieneś pozostać <= 60, co działa dobrze, ponieważ możesz użyć zegara dla nasion, jeśli go nie masz.
red.
4
@eds Um, co? 79 -> 61 -> 15 -> ...
Izkata,
1
Być może @eds oznaczało 59. Wszystkie liczby od 1 do 58 wydają się być uczciwą grą.
Erhannis
26

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ą.

Inaimathi
źródło
3
+1 Myślę, że to pierwsza poważna odpowiedź na to pytanie. Trochę smutny.
Jens
@Magnus Wolffelt - przypomniałem sobie o tym, jak wspomniano w wykładzie TED Rona Eglasha na temat kulturowego znaczenia geometrii fraktalnej w Afryce; „Bamana Sand Divination”. Jest to dość interesujące, choć wciąż nie mam pojęcia, do czego byś użył tej techniki, skoro nie potrzebujemy już wróżbitów. ted.com/talks/ron_eglash_on_african_fractals.html
Inaimathi
1
O ile widzę, ta metoda geomantyczna pozwala po prostu „poprawić” (przypuszczam, że „debia” byłaby lepszym terminem) źródło losowości. Nie do kichnięcia, ale nie do końca tego, czego szukał PO. Co nie znaczy, że nie jest ładna ....
Norman Gray
@Norman Gray - Ludzkie mózgi mogą domyślnie generować stronnicze dowolne liczby.
Inaimathi
@Inaimathi Dokładnie: właśnie dlatego debiugowanie liczb byłoby ważne i dlaczego wskazana metoda jest pomocna. Albo źle cię rozumiem.
Norman Gray,
10

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.

biziclop
źródło
Nawet wtedy oczekiwałbym, że będziesz stronniczy na wiele subtelnych sposobów. (IE wybiera tę samą grupę piosenek)
Zachary K
@Zachary K Bez wątpienia, ale wtedy musiałbyś również wybrać liczbę, która nieco ją rozłoży. Chociaż uprzedzenia nigdy nie można wyeliminować, ta metoda prawie na pewno nie pozwala ci dowiedzieć się, którą literę wybierzesz (chociaż z czasem będziesz musiał zapamiętać niektóre).
biziclop
Eini mini miny moe, jak to robiliśmy jako dzieci.
Zachary K
2
„wybierz liczbę k pomiędzy 10 a 20”. 17. Najmniej losowa liczba.
S.Lott
@ S.Lott Nie ma znaczenia, jak losowa jest ta liczba. Jedynym powodem, dla którego potrzebujesz, jest to, że łatwiej zapamiętujesz kilka pierwszych liter rzeczy.
biziclop
9

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.

Mark Canlas
źródło
A dla dużej liczby na minutę?
Gary Rowe
Nie jestem pewien, czy podążam. Mówisz, że pula liczb 3600 zawiera minuty? Chyba, ale im większa liczba, tym mniej przypadkowa? Jakby nie można było tak szybko pobrać próbek.
Mark Canlas
1
@Gary Rowe To kryterium musi zostać zniesione Obawiam się, po prostu dlatego, że niezależnie od zastosowanej metody, ludzki mózg jest po prostu zbyt wolny.
biziclop
Przepraszam, tylko zastanawiałem się, jak działa twoje podejście, jeśli potrzebujesz więcej niż 60 numerów na minutę. Z perspektywy czasu poproszenie ludzkiego mózgu o wyprodukowanie tak dużej liczby liczb na minutę i tak zwiększy go do maksimum, więc nie martw się o to.
Gary Rowe,
@biziclop Brak problemów. Wygląda na to, że miałem kolizję komentarza podczas rozważania sytuacji z podejściem @ Mark.
Gary Rowe,
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.

Konrad Rudolph
źródło
Myślę, że ważne jest, aby liczenie odbywało się szybko - licząca osoba powinna uważać, aby nie liczyć rytmicznie, przy zaledwie 1 lub 2 krokach na sekundę. Ponieważ powinna istnieć znaczna liczba cykli (intuicyjnie ≥4) przez wszystkie liczby, aby osiągnąć wystarczającą entropię.
Aaron Thoma,
Sugestia ulepszenia dla lepszej losowości : Osoba zliczająca wybiera najpierw tajne losowe ziarno X₀ między 0 a modułem; w połączeniu z liczeniem, powinno to zapewnić przyzwoitą losowość przy wciąż minimalnym wysiłku myślenia (nawet przy liczeniu powolnym, w stosunku do czasu liczenia; tj. niska liczba cykli - intuicyjnie ≥2 byłoby w porządku; <2 byłoby w porządku - izh).
Aaron Thoma
4

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. :)

Fixee
źródło
1
Chociaż istnienie prawdziwie losowego procesu fizycznego jest dyskusyjne (chociaż eksperymenty z paradoksem EPR sugerują pozytywną odpowiedź), istnieje teoretyczna definicja losowej sekwencji, oparta na złożoności Kołmogorowa.
biziclop
3

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.

Kramii Przywróć Monikę
źródło
1
A te fizyczne urządzenia naprawdę mają nieprzewidywalną naturę, więc w pewnym sensie są bardziej losowe niż najlepsze algorytmy komputerowe.
Omega Centauri
( @OmegaCentauri: Naturalnie widzę, co tam zrobiłeś!; O) (Nie jestem pewien, czy gra słów była zamierzona, ale podoba mi się. :)) )
Aaron Thoma
3

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.

Gary Rowe
źródło
1
Myślę, że to nie odpowiada na pytanie. 4 punkty twojej odpowiedzi mają zastosowanie tylko wtedy, gdy ludzie próbują znaleźć losowe liczby bez algorytmu. Myślę, że OP jest tego świadomy i dlatego prosi o algorytm, który ludzie mogą zrobić w swoich głowach i dać dobre wyniki, tj. Nie cierpieć z powodu problemów wymienionych w twojej odpowiedzi.
FabianB
2

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

S.Lott
źródło
7
Przegłosowany - Nie interesują mnie zewnętrzne narzędzia do generowania liczb losowych, ale raczej wewnętrzne algorytmy, które mogą polegać na pamięciach lub bodźcu do generowania liczb naprawdę losowych.
Magnus Wolffelt
3
nie możesz rzucać kostkami w głowie
jk.
2
@ jk01: Poprawnie. Nie możesz też robić losowo w swojej głowie.
S.Lott,
@ S.Lott - Myślę, że masz na myśli to, co masz na myśli, mówiąc: „Typowy człowiek nie może generować w sposób ciągły losowych liczb w swojej głowie z dużą prędkością przy użyciu naiwnej metody i bez narzędzi zewnętrznych”.
Inaimathi
1
@Inaimathi. Nie, mówię coś znacznie silniejszego. Nie możesz robić losowo w swojej głowie. Twój mózg jest pełen błędów, więc potrzebujesz algorytmu. Żaden skończony, skuteczny, deterministyczny algorytm nie jest przypadkowy. Po prostu nie możesz tego zrobić. Żaden prosty algorytm nie jest nawet pseudolosowy, więc nie można przybliżać losowo. Kostki są małe, poręczne i mają długą, długą historię użytkowania.
S.Lott
1

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.

Zachary K.
źródło
0

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.

S.Lott
źródło
Zastanawiam się, czy istnieje przyzwoicie losowa wersja tego ( liniowy generator kongruencjalny (LCG) ), który naprawdę jest łatwy do zrobienia w głowie? a = 1 idealnie, a = 2 sekundy idealnie. (Moje dotychczasowe przemyślenia na ten temat w następnym komentarzu.)
Aaron Thoma,
(( Myślałem, że a = 1, b pierwsze, b sprytnie wybrane, może być bardziej wykonalną alternatywą dla większych m, które nadal działałyby dobrze. Wtedy zauważyłem, że to prawdopodobnie nie jest prawdą: dla b≈0 lub b≈m będzie to przemierzaj raczej sekwencyjnie przez liczby, więc pomyślałem, że b /m / 2 jest odpowiedzią, ale potem zauważyłem, że może to być również sekwencyjne (dla małych | b – m / 2 | / m), tylko na przemian w dwóch pozycjach. b≈m / 3, może być sekwencyjne, naprzemiennie między 3 pozycjami; dla b≈m / 99 problem nie byłby już w naprzemiennej formie, ale zajęłoby ~ 99 kroków, aby przejść przez jedno odejmowanie modulo. ))
Aaron Thoma