Algoritmo di generazione di numeri casuali per cervelli umani? [chiuso]

37

Sei a conoscenza o hai escogitato algoritmi "in-testa" pratici e semplici da imparare che permettono agli umani di generare numeri casuali (un po '"veri")? Con "in-head" intendo .. preferibilmente senza strumenti o dispositivi esterni. Inoltre, è desiderabile un output elevato (molti numeri casuali al minuto).

Ho chiesto questo su SO ma non ha avuto molto interesse. Forse questo è più adatto per i programmatori.

    
posta Magnus Wolffelt 18.02.2011 - 11:56
fonte

11 risposte

36

Ecco un algoritmo di George Marsaglia :

Choose a 2-digit number, say 23, your "seed".

Form a new 2-digit number: the 10's digit plus 6 times the units digit.

The example sequence is 23 --> 20 --> 02 --> 12 --> 13 --> 19 --> 55 --> 35 --> ...

and its period is the order of the multiplier, 6, in the group of residues relatively prime to the modulus, 10. (59 in this case).

The "random digits" are the units digits of the 2-digit numbers, ie, 3,0,2,2,3,9,5,... the sequence mod 10. The arithmetic is simple enough to carry out in your head.

    
risposta data 18.02.2011 - 22:46
fonte
26

Dai un'occhiata a questo articolo su Geomancy . In particolare la sezione su che genera grafici Geomantici . Si tratta di una tecnica di generazione di numeri pseudo-casuali che utilizza cifre binarie e alcuni semplici calcoli ricorsivi. Sembra che potresti farlo nella tua testa abbastanza facilmente (anche se un foglio di carta sarebbe d'aiuto).

Disclaimer: non l'ho provato da solo; quando ho bisogno di un numero sufficientemente casuale, o ottengo un output da /dev/random , uso rand in qualsiasi lingua che ho a portata di mano, o rotolare il mio fidato d20.

Se sei un prodigio matematico, il metodo dei quadrati di mezzo è un bel calcolo computazionale, seppur sensibilmente metodo inaffidabile.

    
risposta data 18.02.2011 - 13:18
fonte
10

Penso che un ragionevole presupposto sia che devi fare affidamento sulla grande quantità di informazioni verbali che immagazzini nel tuo cervello. La fonte può essere qualsiasi cosa, testi di canzoni, poesie, schizzi di Monty Python, ma deve essere qualcosa che conosci a memoria.

Quindi devi selezionare una parte abbastanza casuale eliminando il pregiudizio inconscio il più possibile. Un modo per farlo, ad esempio, è selezionare un brano, selezionare un numero k tra 10 e 20 e trovare la lettera k th nei suoi testi.

Ovviamente questo non ti darà una distribuzione uniforme di per sé, dato che la frequenza delle lettere è diversa, ma è comunque una lettera casuale, o almeno così vicina come credo sia possibile senza una fonte esterna.

Aggiornamento: A proposito, quando viene chiesto alle persone di scrivere una sequenza casuale di lanci di monete, l'errore più comune è di rendere la sequenza "troppo casuale": esecuzioni di risultati identici sarà troppo breve, che rivelerà una semplice analisi della lunghezza della corsa. Questo metodo è principalmente finalizzato a evitare questa trappola. Ovviamente altre anomalie potrebbero sorgere dall'ombra di questo pregiudizio della durata della corsa, ma avresti bisogno di esperimenti adeguati per trovarli. Un po 'ironicamente, un algoritmo per generare numeri casuali solo pensando non può essere trovato pensando solo.

    
risposta data 18.02.2011 - 12:25
fonte
9

Prova l'orologio.

Lo faccio se ho bisogno di un numero casuale che è un fattore di 60 (secondi). Prendi il modulo appropriato di qualunque ora sia. 4:17:23 PM, simulando un tiro di dado, diventa 5.

    
risposta data 18.02.2011 - 17:04
fonte
5

Ottima domanda. Temo che una buona risposta possa rivelarsi molto difficile.

Ma come inizio, è abbastanza facile generare una "vera" casualità quando due persone sono coinvolte: semplicemente lasciare che una delle persone contenga un numero di moduli in modo silenzioso e l'altro dica "stop" dopo un intervallo arbitrario. Successivamente, questo numero può essere trasformato in altre distribuzioni utilizzando metodi standard.

Per rendere questo metodo robusto, il modulo non deve essere troppo grande, altrimenti ci sarà un strong pregiudizio contro i piccoli numeri. Sarei davvero interessato a vedere se esiste qualche lavoro che analizzi le proprietà stocastiche di questo metodo.

    
risposta data 18.02.2011 - 21:27
fonte
4

Questa è una domanda complessa; Cercherò di spiegarti un po 'senza andare troppo lontano tra le erbacce.

Per prima cosa, dobbiamo chiedere "che cos'è true randomness"? Tali discussioni degenerano rapidamente in acque filosofiche, ma il succo è questo: "è l'universo veramente casuale"? In altre parole, se si quantizza il tempo e la materia, è possibile calcolare lo stato successivo dell'universo da quello attuale? Se sì, allora l'universo è deterministico e non c'è vera casualità (vedi cosa intendo per "filosofico"?)

Poiché "la casualità vera" è difficile da definire, spesso ci accontentiamo di "pseudo-casuale". Questo è generalmente richiesto quando si generano numeri "casuali" su un computer, naturalmente.

Il generatore di numeri pseudocasuali più semplice sarebbe qualcosa come il famoso algoritmo "9 .. 9 .. 9 .." di Dilbert. Ma intuitivamente non sembra molto buono (che ovviamente è lo scherzo). Gli statistici hanno sviluppato una serie di test per dire se una sequenza di output apparentemente casuali è "buona". Inizia con la pagina di wikipedia per "chi squared test" e potresti passare un pomeriggio a leggere questi test.

Un semplice algoritmo del computer come un "generatore di congruenza lineare" produce numeri abbastanza buoni per un test chi quadrato (è comunque necessario "seminare" questo algoritmo da qualcosa, comunque).

Il prossimo passo in "bontà" è "casualità crittograficamente strong" che significa che data una sequenza a1, a2, ... non puoi predire il numero successivo nella sequenza con "probabilità ragionevole" a meno che tu non usi un sacco di calcolo. Questi numeri sono talvolta chiamati "computazionalmente pseudocasuali". Un modo comune per ottenere tale sequenza è tramite una "catena di hash" come questa: a1 = SHA512 (a2), a2 = SHA512 (a3), ... Poiché crediamo (basato sull'esperienza, non sulla prova matematica) che SHA512 è computazionalmente difficile da inverdire, crediamo che a2 sia "impossibile" prevedere solo dato a1.

Quindi ora sorge la domanda, qual è la cosa migliore che l'uomo possa fare secondo le regole stabilite nella sua domanda? Gli umani sono notoriamente cattivi nel generare casualità; c'era un sito web che avrebbe tentato di generare lanci di monete digitando "a caso" H, T, T, H, H, T, T, ecc. come se stessi lanciando una moneta (ma lo fai in la tua testa). Dopo un po ', il sito web inizierà a prevedere i lanci meglio del 50% delle volte (usando un modello di Markov nascosto). Siamo solo cattivi in questo.

Ci sono modi per migliorare la situazione usando varie tecniche di missaggio che sono probabilmente fattibili nella tua testa. E ci sono persino delle domande che potrei immaginare perché potresti volere questo (il prigioniero politico vuole criptare un messaggio agli alleati esterni). Ma penso che questo post sia abbastanza lungo. :)

    
risposta data 18.02.2011 - 17:20
fonte
3

La vera ragione della proliferazione degli RNG basati sugli strumenti è che un buon algoritmo in testa per la generazione di numeri casuali deve ancora essere sviluppato .

Fortunatamente i generatori portatili di numeri casuali - tra cui monete per il flopping, dadi (con vari numeri di faccette) per il rotolamento, carte per il prelievo e cannucce per il disegno - sono relativamente facili da ottenere a basso costo. Inoltre, per i tecnofili tra di noi, ci sono alcune simulazioni piuttosto buone di questi strumenti disponibili per la maggior parte delle piattaforme mobili.

Raccomando caldamente qualcuno di questi su qualsiasi alternativa di carne.

    
risposta data 18.02.2011 - 13:22
fonte
3

Quantità elevata al minuto altamente randomizzata e generata dagli esseri umani? Non succederà

I principali problemi che incontrerai sono

  • Le persone si annoiano rapidamente, quindi i pattern si verificano rapidamente
  • Il cervello umano ha molte strutture dedicate al riconoscimento / alla creazione di modelli, quindi dovrai sconfiggerlo
  • I numeri veramente casuali contengono ripetizioni che gli umani cercano di evitare
  • Gli umani non sono bravi con i grandi numeri

Ciò ha portato molti crittografi ad abbandonare le tecniche "in-head" a favore di processi esterni casuali perché era semplicemente troppo semplice elaborare schemi basati su numeri "in-head".

Off-topic ma interessante

Sebbene non sia un meccanismo per generare numeri casuali nella tua testa, l'algoritmo Solitaire (come ritratto in Cryptonomicon di Neal Stephenson) dimostra quanto sia difficile utilizzare numeri casuali per scopi crittografici. Richiede solo un pacchetto di normali carte da gioco per creare un output ragionevolmente sicuro, ma il metodo da fare è abbastanza complicato.

    
risposta data 18.02.2011 - 13:05
fonte
2

I'm genuinely curious about anything that people might have come up with on this problem.

Per favore, allontanati dalla scrivania e vai a Las Vegas.

L'umanità ha dozzine di procedure randomizzate. Puoi vederli tutti a Las Vegas.

Hai cerchi rotanti. Hai cubetti di ruzzoloni. E hai pedine mescolate. Funzionano tutti meravigliosamente bene.

I cubi sono forse i più vecchi. Apparentemente c'erano bastoni allungati a 4 lati usati in un punto. I noduli simmetrici di pecore cubiche erano popolari da millenni. Abbiamo usato questo tipo di randomizzatori poiché probabilmente lo stesso tempo abbiamo sviluppato il linguaggio.

link

"Chiunque consideri i metodi aritmetici per produrre cifre casuali è, naturalmente, in uno stato di peccato"

--- John von Neumann

    
risposta data 18.02.2011 - 12:08
fonte
1

Non riesco a pensare a nessuno. In effetti, mi aspetterei che qualsiasi cosa ti sia venuta in mente con avrebbe tanti pregiudizi in esso che sarebbe inutile.

Se ho bisogno di numeri casuali di solito tiro i dadi.

    
risposta data 18.02.2011 - 12:05
fonte
0

Stai chiedendo un LCM che puoi fare nella tua testa? Nota che l'idea che questo sia meglio dei dadi rimane assurda.

Tuttavia, questo è casuale come qualsiasi algoritmo finito, definito ed efficace può essere.

link

link

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

È più facile vedere che cosa sta facendo se selezioniamo valori piccoli a = 5, b = 1 e m = 7. Dovresti riuscire a farlo nella tua testa.

    
risposta data 19.02.2011 - 14:48
fonte

Leggi altre domande sui tag