Come dimostrare un generatore di numeri casuali è meglio di un altro?

Question

Come si dimostra che un RNG è migliore di un altro?

Non intendo in termini di tempo di esecuzione, ma piuttosto la quantità di entropia "generata" - che inoltre introduce la nozione di periodicità (periodo basso = bassa entropia).

È possibile garantire un RNG ottimale? O è un obiettivo irraggiungibile? Per ottimale, voglio dire qualsiasi sequenza è ugualmente probabile e indipendente da risultati passati o futuri.

Mi interessa algoritmi, non dispositivi di campionamento cosmica di fondo o di altre fonti di "casualità" fisico (è casuale o semplicemente complessa?)

Answer 1

Il vecchio standard per i test usati essere i "test duri". http://en.wikipedia.org/wiki/Diehard_tests Questo è stato sostituito dai test NIST che DKnight ha rilevato: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html. L'articolo wiki di Diehard offre una buona panoramica del tipo di cose che vengono guardate. Il bit NIST richiederà un po 'più di scavo.

Come si afferma, nessun pseudo RNG (algoritmo) può essere dimostrato ottimale. Hanno tutti un valore iniziale e dipendono dall'input per generare un valore. Se conosci il seme e lo stato, conosci il prossimo valore. Ad esempio, controlla http://en.wikipedia.org/wiki/Mersenne_twister. Mi piace soprattutto per il nome fantastico, ma l'articolo fa un buon lavoro spiegando i principi di un PRNG.

Answer 2

Vedere http://www.random.org/analysis/

L'unico e solo RNG ottimale:

Answer 3

Generare sequenze di numeri e quindi provare a comprimerli. Quelli più casuali comprimono meno. La casualità pura è incomprimibile. Sarebbe interessante vedere i risultati e se ci saranno differenze.

Answer 4

L'Istituto Nazionale di Standard e Tecnologia ha qualche buona informazione su questo articolo:

http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

Sembra che v'è una suite di test e un sacco di buon materiale di riferimento

Answer 5

Esiste una definizione oggettiva dalla teoria della complessità computazionale: la complessità temporale asintotica richiesta per distinguere l'output dai dati casuali.

Un buon PRNG dovrebbe costringere un addetto a spendere molto più tempo all'aumentare della dimensione del seme o al crescere del livello di certezza richiesto. (Con semi di dimensione fissa suppongo che ci si guarda al tempo di funzionamento reale così come la complessità del programma.)

• per il confronto di un PRNG contro un altro, quello con un/discriminante più veloce più piccolo è peggio.
• Un'ipotesi comune, anche se non è stata dimostrata, è che alcuni PRNG sono indistinguibili dal tempo casuale in polinomio. Questo è un possibile significato per "ottimale".
• I test statistici, come lo diehard tests, sono solo dei semplici riconoscitori.

Answer 6

Le basi sono in Knuth, The Art of Computer Programming Vol. 2, "Algoritmi seminali".L'idea è di escogitare test di casualità in cui ogni test cercherà di trovare aspetti non casuali di un PRNG. Si noti che ciò che potrebbe sembrare casuale per un essere umano non lo è. Ad esempio, tendiamo a dire che la sequenza "1,4,4,1" per esempio non è casuale, mentre può accadere perfettamente su una sequenza casuale più ampia.

Così l'approccio è più o meno:

• Trova diversi test per casualità, questo è essenzialmente gruppi di test DieHard e NIST.
• Eseguire detti test sul PRNG.
• Se il PRNG fallisce uno o più test, può essere percepito come un PRNG più debole di quelli che sopravvivono.

Un bell'esempio di test è l'analisi dello spazio delle fasi. Ecco un link di esso eseguito alcuni anni fa su generatori di casualità TCP per diversi sistemi operativi:

http://lcamtuf.coredump.cx/oldtcp/tcpseq.html

Altri test classici sono chi-quadrato, Komolgorov-Smirnoff, ecc, tutto spiegato in Knuth. I buoni PRNG sopravvivono a qualsiasi attacco immaginabile contro di loro.