Generatori di numeri pseudo-casuali e metodi per testarli. Generatore di numeri pseudo-casuali - casuale

Si noti che, idealmente, la curva di densità della distribuzione dei numeri casuali assomiglierebbe a quella mostrata in Fig. 22.3. Cioè, in caso ideale ogni intervallo contiene lo stesso numero di punti: n io = n/K , dove n- il numero totale di punti, K- il numero di intervalli, io= 1,…, K .

Va ricordato che la generazione di un numero casuale arbitrario consiste in due fasi:

• generare un numero casuale normalizzato (cioè distribuito uniformemente da 0 a 1);
• conversione di numeri casuali normalizzati R io a numeri casuali X io, che sono distribuiti secondo la legge di distribuzione (arbitraria) dell'utente richiesta o nell'intervallo richiesto.

I generatori di numeri casuali si dividono in:

• fisico;
• tabellare;
• algoritmico.

RNG fisico

Un esempio di RNG fisico è: una moneta (testa - 1, croce - 0); dado; un tamburo con una freccia divisa in settori con numeri; generatore di rumore hardware (HS), che viene utilizzato come dispositivo termico rumoroso, ad esempio un transistor (Fig. 22.4-22.5).

RNG tabulare

Gli RNG tabulari utilizzano tabelle appositamente compilate contenenti numeri non correlati verificati, ovvero indipendenti l'uno dall'altro, come fonte di numeri casuali. Tavolo 22.1 mostra un piccolo frammento di tale tabella. Percorrendo la tabella da sinistra a destra dall'alto verso il basso, puoi ottenere numeri casuali distribuiti uniformemente da 0 a 1 con il numero di posizioni decimali richiesto (nel nostro esempio, usiamo tre posizioni decimali per ogni numero). Poiché i numeri nella tabella non dipendono l'uno dall'altro, la tabella può essere attraversata in modi diversi, ad esempio dall'alto verso il basso o da destra a sinistra o, ad esempio, è possibile selezionare numeri che si trovano in posizione pari.

Dignità questo metodo in quanto fornisce numeri veramente casuali poiché la tabella contiene numeri non correlati verificati. Svantaggi del metodo: richiede molta memoria per memorizzare un numero elevato di cifre; grandi difficoltà nel generare e controllare tali tabelle, le ripetizioni nell'uso di una tabella non garantiscono più la casualità della sequenza numerica, e quindi l'affidabilità del risultato.

C'è una tabella contenente 500 numeri verificati assolutamente casuali (tratto dal libro di I. G. Venetsky, V. I. Venetskaya "Concetti e formule matematici e statistici di base nell'analisi economica").

RNG algoritmico

I numeri generati utilizzando questi RNG sono sempre pseudo-casuali (o quasi-casuali), ovvero ogni numero generato successivamente dipende da quello precedente:

R io + 1 = F(R io) .

Le sequenze costituite da tali numeri formano dei loop, cioè esiste necessariamente un ciclo che si ripete un numero infinito di volte. I cicli che si ripetono sono chiamati periodi.

Il vantaggio dei dati RNG è la velocità; i generatori praticamente non richiedono risorse di memoria, sono compatti. Svantaggi: i numeri non possono essere chiamati completamente casuali, poiché esiste una dipendenza tra loro, così come la presenza di periodi nella sequenza di numeri quasi casuali.

Considera diversi metodi algoritmici per ottenere un RNG:

• metodo dei quadrati medi;
• metodo dei prodotti medi;
• metodo di miscelazione;
• metodo lineare congruente.

Metodo del quadrato medio

C'è un numero di quattro cifre R 0. Questo numero è al quadrato e inserito in R uno . Lontano dalla R 1 viene preso al centro (quattro cifre centrali) - un nuovo numero casuale - e scritto in R 0. Quindi la procedura viene ripetuta (vedi fig. 22.6). Nota che in effetti non è necessario prendere come un numero casuale ghij, un 0.ghij- con uno zero e un punto decimale assegnati a sinistra. Questo fatto si riflette come in Fig. 22.6 e successive figure simili.

Svantaggi del metodo: 1) se a qualche iterazione il numero R 0 diventa uguale a zero, quindi il generatore degenera, quindi la scelta corretta del valore iniziale è importante R 0; 2) il generatore ripeterà la sequenza attraverso m n passaggi (nella migliore delle ipotesi), dove n- capacità cifre R 0 , m- la base del sistema di numerazione.

Ad esempio, nella Fig. 22.6: se numero R 0 sarà rappresentato in notazione binaria, la sequenza di numeri pseudocasuali sarà ripetuta in 2 4 = 16 passi. Nota che la ripetizione della sequenza può avvenire prima se il numero iniziale non è scelto bene.

Il metodo sopra descritto è stato proposto da John von Neumann e risale al 1946. Poiché questo metodo si è rivelato inaffidabile, è stato rapidamente abbandonato.

Metodo dei prodotti intermedi

Numero R 0 viene moltiplicato per R 1, dal risultato ottenuto R 2 estrarre il centro R 2 * (questo è un altro numero casuale) e moltiplicato per R uno . Tutti i successivi numeri casuali sono calcolati utilizzando questo schema (vedi Fig. 22.7).

Metodo di agitazione

Il metodo shuffle utilizza le operazioni per spostare ciclicamente il contenuto di una cella a sinistra ea destra. L'idea del metodo è la seguente. Lascia che la cellula conservi il seme R 0. Spostando ciclicamente il contenuto della cella a sinistra di 1/4 della lunghezza della cella, otteniamo un nuovo numero R 0 *. Allo stesso modo, spostando ciclicamente il contenuto di una cella R 0 a destra per 1/4 della lunghezza della cella, otteniamo il secondo numero R 0 **. Somma di numeri R 0 * e R 0 ** fornisce un nuovo numero casuale R uno . Ulteriore R 1 è inserito in R 0, e l'intera sequenza di operazioni viene ripetuta (vedi Figura 22.8).

Si prega di notare che il numero risultante dalla sommatoria R 0 * e R 0 **, potrebbe non entrare completamente nella cella R uno . In questo caso, le cifre extra dovrebbero essere scartate dal numero ricevuto. Spieghiamo questo per la Fig. 22.8, dove tutte le celle sono rappresentate da otto cifre binarie. Permettere R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , poi R 0 * + R 0 ** = 100110010 2 = 306 10 ... Come puoi vedere, il numero 306 occupa 9 cifre (nel sistema numerico binario) e la cella R 1 mi piace R 0) può contenere un massimo di 8 bit. Pertanto, prima di inserire il valore in R 1 è necessario rimuovere un "extra", il bit più a sinistra dal numero 306, per cui in R 1 non andrà a 306, ma a 00110010 2 = 50 10. Si noti inoltre che in linguaggi come Pascal, il "troncamento" dei bit extra quando una cella viene traboccata viene eseguito automaticamente in base al tipo di variabile specificato.

Metodo lineare congruente

Il metodo della congruenza lineare è una delle procedure più semplici e più comunemente utilizzate per simulare numeri casuali. Questo metodo utilizza il mod ( X, sì), che restituisce il resto del primo argomento diviso per il secondo. Ogni numero casuale successivo viene calcolato in base al numero casuale precedente utilizzando la seguente formula:

R io+ 1 = mod ( K · R io + B, m) .

Si chiama una sequenza di numeri casuali ottenuta usando questa formula sequenza lineare congruente... Molti autori chiamano una sequenza congruente lineare per B = 0 metodo moltiplicativo congruente, e a B ≠ 0 — metodo congruente misto.

Per un generatore di alta qualità, è necessario scegliere coefficienti adeguati. È necessario che il numero m era abbastanza grande, dal momento che il periodo non può avere di più m elementi. D'altra parte, la divisione utilizzata in questo metodo è un'operazione piuttosto lenta, quindi sarebbe logico che una macchina di calcolo binario scegliesse m = 2 n, poiché in questo caso trovare il resto della divisione si riduce all'interno del computer ad un'operazione logica binaria "AND". È anche comune scegliere il numero primo più grande m meno di 2 n: nella letteratura speciale si dimostra che in questo caso i bit meno significativi del numero casuale risultante R io+ 1 si comportano in modo casuale come i più vecchi, il che ha un effetto positivo sull'intera sequenza di numeri casuali nel suo insieme. Un esempio è uno di numeri di Mersenne uguale a 2 31 - 1, e quindi m= 2 31 - 1.

Uno dei requisiti per le sequenze lineari congruenti è la massima lunghezza possibile del periodo. La durata del periodo dipende dai valori m , K e B... Il teorema che presentiamo di seguito ci permette di determinare se è possibile raggiungere un periodo di lunghezza massima per valori specifici m , K e B .

Teorema... Sequenza lineare congruente definita da numeri m , K , B e R 0, ha un periodo di lunghezza m se e solo se:

• i numeri B e m reciprocamente semplice;
• K- 1 multiplo P per ogni semplice P che è un divisore m ;
• K- 1 multiplo di 4 se m multiplo di 4.

Infine, concludiamo con un paio di esempi sull'utilizzo del metodo congruenziale lineare per generare numeri casuali.

Si è riscontrato che una serie di numeri pseudo-casuali generati dai dati dell'esempio 1 sarà ripetuta ogni m/ 4 numeri. Numero Qè impostato arbitrariamente prima di iniziare i calcoli, ma va tenuto presente che la serie dà l'impressione di essere casuale per grandi K(che significa che Q). Il risultato può essere leggermente migliorato se B strano e K= 1 + 4 Q - in questo caso la riga verrà ripetuta ogni m numeri. Dopo una lunga ricerca K i ricercatori si sono stabiliti sui valori 69069 e 71365.

Un generatore di numeri casuali che utilizza i dati dell'Esempio 2 produrrà numeri casuali non ripetuti con un periodo di 7 milioni.

Il metodo moltiplicativo per generare numeri pseudo-casuali è stato proposto da D. H. Lehmer nel 1949.

Controllo della qualità del generatore

La qualità dell'intero sistema e l'accuratezza dei risultati dipendono dalla qualità dell'RNG. Pertanto, la sequenza casuale generata dall'RNG deve soddisfare una serie di criteri.

I controlli effettuati sono di due tipi:

• controlli di uniformità di distribuzione;
• verifica dell'indipendenza statistica.

Verifiche di uniformità di distribuzione

1) RNG dovrebbe produrre vicino ai seguenti valori di parametri statistici caratteristici di una legge casuale uniforme:

2) Test di frequenza

Il test di frequenza consente di scoprire quanti numeri rientrano nell'intervallo (m R – σ R ; m R + σ R) , ovvero (0,5 - 0,2887; 0,5 + 0,2887) o, in definitiva, (0,2113; 0,7887). Poiché 0.7887 - 0.2113 = 0.5774, concludiamo che in un buon RNG, circa il 57,7% di tutti i numeri casuali caduti dovrebbe rientrare in questo intervallo (vedi Fig. 22.9).

È inoltre necessario tenere conto del fatto che il numero di numeri che rientrano nell'intervallo (0; 0,5) dovrebbe essere approssimativamente uguale al numero di numeri che rientrano nell'intervallo (0,5; 1).

3) Chi-quadro test

Il test chi quadrato (test χ 2) è uno dei test statistici più famosi; è il metodo principale utilizzato in combinazione con altri criteri. Il test chi quadrato è stato proposto nel 1900 da Karl Pearson. Il suo notevole lavoro è considerato il fondamento della moderna statistica matematica.

Nel nostro caso, il test chi-quadrato ci permetterà di scoprire quanto il vero Il RNG è vicino allo standard RNG, cioè se soddisfa o meno il requisito della distribuzione uniforme.

Diagramma di frequenza riferimento L'RNG è mostrato in Fig. 22.10. Poiché la legge di distribuzione del RNG di riferimento è uniforme, la probabilità (teorica) P io colpire i numeri in io esimo intervallo (tutti questi intervalli K) è uguale a P io = 1/K ... E così, in ciascuno di K gli intervalli cadranno liscio in poi P io · n numeri ( nÈ il numero totale di numeri generati).

Un vero RNG produrrà numeri distribuiti (e non necessariamente in modo uniforme!) K intervalli e ogni intervallo includerà n io numeri (nella somma n 1 + n 2 + ... + n K = n ). Come possiamo determinare quanto è buono l'RNG testato e quanto è vicino a quello di riferimento? È abbastanza logico considerare i quadrati delle differenze tra il numero di numeri ricevuti. n io e "riferimento" P io · n ... Aggiungiamoli e come risultato otteniamo:

χ 2 esp. = ( n 1 - P uno · n) 2 + (n 2 - P 2 n) 2 + ... + ( n K – P K · n) 2 .

Da questa formula segue che minore è la differenza in ciascuno dei termini (e quindi minore è il valore di 2 exp.), più forte è la legge di distribuzione dei numeri casuali generati dal RNG reale tende ad essere uniforme.

Nell'espressione precedente, a ciascuno dei termini viene assegnato lo stesso peso (uguale a 1), che di fatto potrebbe non corrispondere alla realtà; quindi, per la statistica chi-quadrato, è necessario normalizzare ciascuno io-esimo termine dividendo per P io · n :

Infine, scriviamo l'espressione risultante in modo più compatto e la semplifichiamo:

Abbiamo ottenuto il valore del test chi quadrato per sperimentale dati.

Tavolo 22,2 sono dati teorico valori chi-quadrato (teoria χ 2), dove ν = n- 1 è il numero di gradi di libertà, PÈ il livello di confidenza definito dall'utente che indica quanto l'RNG deve soddisfare i requisiti di distribuzione uniforme, oppure? P — questa è la probabilità che il valore sperimentale di 2 exp. sarà inferiore alla teoria tabulata (teorica) χ 2. o uguale a lui.

Considerato accettabile P dal 10% al 90%.

Se 2 esp. molto più della teoria 2. (questo è P- ottimo), quindi il generatore non soddisfa requisito di distribuzione uniforme, poiché i valori osservati n io vai troppo lontano dal teorico P io · n e non può essere considerato casuale. In altre parole, l'intervallo di confidenza è così grande che i vincoli sui numeri diventano molto allentati, i requisiti sui numeri sono deboli. In questo caso, si osserverà un errore assoluto molto grande.

Anche D. Knut nel suo libro "The Art of Programming" ha notato che avere 2 exp. anche piccolo, in generale, non va bene, sebbene sembri, a prima vista, meraviglioso dal punto di vista dell'uniformità. Infatti, prendi una serie di numeri 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, 0,7, 0,8, 0,9, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, ... - sono ideali dal punto di vista di uniformità, e 2 exp. saranno praticamente zero, ma è improbabile che tu li riconosca come casuali.

Se 2 esp. molto meno della teoria χ2. (questo è P- poco), quindi il generatore non soddisfa il requisito di una distribuzione uniforme casuale, poiché i valori osservati n io troppo vicino al teorico P io · n e non può essere considerato casuale.

Ma se 2 esp. giace in un certo intervallo, tra due valori di 2 theor. che corrispondono, ad esempio, P= 25% e P= 50%, quindi possiamo assumere che i valori dei numeri casuali generati dal sensore siano del tutto casuali.

Inoltre, va tenuto presente che tutti i valori P io · n deve essere abbastanza grande, ad esempio, più di 5 (scoperto empiricamente). Solo allora (con un campione statistico sufficientemente ampio) le condizioni sperimentali possono essere considerate soddisfacenti.

Quindi, la procedura di verifica è la seguente.

Test di indipendenza statistica

1) Verificare la frequenza di occorrenza di una cifra in una sequenza

Diamo un'occhiata a un esempio. Il numero casuale 0.2463389991 è composto dalle cifre 2463389991, e il numero 0.5467766618 è composto dalle cifre 5467766618. Combinando le sequenze di cifre, abbiamo: 24633899915467766618.

È chiaro che la probabilità teorica P io ricadute io-esima cifra (da 0 a 9) è 0.1.

2) Verifica dell'aspetto di serie di numeri identici

Indichiamo con n l numero di serie di cifre consecutive di lunghezza l... Tutto da verificare l da 1 a m, dove mÈ un numero specificato dall'utente: il numero massimo che si verifica di cifre identiche in una serie.

Nell'esempio "24633899915467766618" sono state trovate 2 serie di lunghezza 2 (33 e 77), cioè n 2 = 2 e 2 serie 3 lunghe (999 e 666), cioè n 3 = 2 .

La probabilità di occorrenza di una serie di lunghezza lè uguale a: P l= 9 10 - l (teorico). Cioè, la probabilità di una serie di un carattere di lunghezza è: P 1 = 0,9 (teorico). La probabilità di una serie di due caratteri di lunghezza è: P 2 = 0,09 (teorico). La probabilità di una serie di tre caratteri di lunghezza è: P 3 = 0.009 (teorico).

Ad esempio, la probabilità di una serie di un carattere di lunghezza è P l= 0,9, poiché può esserci un solo carattere su 10 e ci sono 9 caratteri in totale (zero non conta). E la probabilità che due simboli identici "XX" compaiano in una riga è 0,1 · 0,1 · 9, cioè la probabilità di 0,1 che il simbolo "X" appaia nella prima posizione è moltiplicata per la probabilità 0,1 che lo stesso il simbolo apparirà nella seconda posizione "X" e moltiplicato per il numero di tali combinazioni 9.

La frequenza di comparsa della serie è calcolata secondo la formula "chi-quadrato" precedentemente analizzata utilizzando i valori P l .

Nota: il generatore può essere controllato più volte, tuttavia i controlli non sono completi e non garantiscono che il generatore produca numeri casuali. Ad esempio, un generatore che emette la sequenza 12345678912345 ... sarà considerato ideale durante i controlli, il che ovviamente non è del tutto vero.

In conclusione, notiamo che il terzo capitolo del libro di Donald E. Knuth "The Art of Programming" (volume 2) è completamente dedicato allo studio dei numeri casuali. si studia metodi diversi generazione di numeri casuali, test statistici di casualità e conversione di numeri casuali uniformemente distribuiti in altri tipi di variabili casuali. Più di duecento pagine sono state dedicate alla presentazione di questo materiale.

La simulazione della casualità è spesso richiesta nei programmi per computer. Ad esempio, durante lo sviluppo di giochi. Se il programma ha un generatore, cioè un produttore, di un numero casuale, quindi utilizzando il numero ottenuto in questo modo, è possibile selezionare l'uno o l'altro ramo dell'esecuzione del programma o un oggetto arbitrario dalla raccolta. In altre parole, la cosa principale è generare un numero. Su di essa si basa l'emulazione di un diverso tipo di casualità.

Non sappiamo con certezza se c'è un incidente in natura, o ci sembra solo a causa della limitatezza delle nostre conoscenze. Sappiamo solo che non esiste una vera casualità nella programmazione. Non c'è nessun posto dove prendere un numero arbitrario, non puoi programmarne l'aspetto dal nulla. Puoi solo creare un programma che, come risultato dell'applicazione di una formula complessa al "grano", produrrà un numero e ci sembrerà che questo numero sia casuale.

Il "grano" è l'input della formula. Questo può essere, ad esempio, il tempo di sistema in millisecondi, che cambia continuamente. Di conseguenza, il "grano" sarà costantemente diverso. Oppure il programmatore può impostarlo da solo.

Tale programma (in realtà, un modulo o una funzione) è chiamato generatore di numeri pseudo-casuali. La libreria Python standard include il modulo random. Contiene molte funzioni legate all'emulazione della casualità (ad esempio, "mescolando" gli elementi di una sequenza), non solo funzioni per la generazione di numeri pseudo-casuali.

Questo tutorial ti guiderà attraverso le funzioni random(), randrange() e randint() dal modulo random. Notare che il modulo random contiene la funzione random() con lo stesso nome. Succede.

Per accedere alle funzioni è necessario importare il modulo random:

>>> importa casuale

Oppure importare singole funzioni da esso:

>>> da importazione casuale random, randrange, randint

Funzioni per ottenere numeri interi "casuali" - randint () e randrange ()

Le funzioni randint() e randrange() generano interi pseudo-casuali. Il primo è il più semplice e richiede sempre solo due argomenti: i limiti di un intervallo di interi, da cui viene selezionato qualsiasi numero:

>>> casuale .randint (0, 10) 6

oppure (se sono state importate singole funzioni):

>>> randinto (100, 200) 110

Nel caso di randint (), entrambi i limiti sono inclusi nell'intervallo, ovvero nel linguaggio della matematica il segmento è descritto come.

I numeri possono essere negativi:

>>> .randint casuale (-100, 10) -83 >>> .randint casuale (-100, -10) -38

Ma il primo numero deve essere sempre minore o almeno uguale al secondo. Cioè un<= b.

La funzione randrange() è più complessa. Può richiedere un argomento, due o anche tre. Se ne viene specificato solo uno, restituisce un numero casuale compreso tra 0 e l'argomento specificato. Inoltre, l'argomento in sé non è incluso nell'intervallo. Nel linguaggio della matematica, questo è)