Nuovo generatore di numeri casuali senza ripetizioni. Ha un algoritmo di generazione dei numeri aggiornato. Questo generatore elimina la possibilità di ripetere i numeri. Il generatore di numeri casuali consente di escludere singoli numeri dal risultato.
Per generare un numero, seleziona un numero di origine. Seleziona il numero finale. Specificare il numero di numeri da generare. Inoltre, è possibile specificare i numeri da ignorare.
Questo generatore di numeri utilizza un algoritmo complesso. Ciò garantisce che ogni numero sia veramente casuale.
Numero casuale
Perchè ne abbiamo bisogno? Ad esempio, per la selezione cieca. Questo è utile per determinare il vincitore della lotteria. Quando si determina il vincitore del concorso. Quando giochi alla lotteria. Quando vuoi ottenere una combinazione di numeri completamente per caso.
Questo è un generatore di numeri casuali universale. È adatto a qualsiasi esigenza di ottenere un numero casuale. Tutti i numeri ricevuti sono completamente casuali. Devi solo indicare la fonte dei dati. Il nostro RNG farà il resto per te.
È bello avere un generatore casuale sempre a portata di mano. Puoi giocare facilmente alla lotteria. Avere la certezza che questi numeri siano stati ottenuti in modo casuale.
Generatore di numeri casuali per la lotteria
Vuoi ottenere numeri casuali senza ripetizioni. Inoltre non hai bisogno di alcuni numeri. Perché secondo te sicuramente non cadranno. Puoi configurare facilmente la modalità del nostro generatore di numeri di cui hai bisogno. E ti darà solo utili combinazioni di numeri. Non hai più bisogno di molti generatori diversi. Questo RNG è universale. Questo generatore è facilmente personalizzabile per te. Il generatore non ha restrizioni sul numero e sull'intervallo di numeri. Questa generazione viene eseguita lato server e non dal browser. Abbiamo eliminato tutti i fattori che potrebbero influenzare il risultato della selezione casuale.
Nuovo generatore RNG
Il nostro generatore casuale mescola i numeri più volte. Non generiamo solo numeri casuali. Per prima cosa mescoliamo tutti i numeri tra i quali dobbiamo scegliere. Questo viene fatto più volte. E solo dopo selezioniamo nuovamente in modo casuale un determinato numero di numeri. Questo approccio alla generazione di numeri casuali garantisce che la selezione sia casuale.
I numeri ci accompagnano ovunque: numeri di casa e di appartamento, numeri di telefono, numeri di auto, numeri di passaporto, carte di plastica, date, password e-mail. Scegliamo noi stessi alcune combinazioni di numeri, ma la maggior parte le otteniamo per caso. Senza rendercene conto, utilizziamo ogni giorno numeri generati casualmente. Se creiamo codici PIN, i codici univoci delle carte di credito o salariali vengono generati da sistemi affidabili che escludono l'accesso alle password. I generatori di numeri casuali forniscono sicurezza in aree che richiedono velocità di elaborazione, sicurezza e indipendenza dei dati.
Il processo di generazione di numeri pseudocasuali è soggetto a determinate leggi ed è stato utilizzato per molto tempo, ad esempio nelle lotterie. Nel recente passato, le estrazioni venivano effettuate utilizzando macchine o lotti della lotteria. Ora in molti paesi i numeri vincenti delle lotterie statali sono determinati proprio da una serie di numeri casuali generati.
Vantaggi del metodo
Quindi, un generatore di numeri casuali è un meccanismo moderno indipendente per determinare casualmente combinazioni di numeri. L'unicità e la perfezione di questo metodo risiede nell'impossibilità di un intervento esterno nel processo. Il generatore è un insieme di programmi costruiti, ad esempio, su diodi di rumore. Il dispositivo genera un flusso di rumore casuale, i cui valori attuali vengono convertiti in numeri e formano combinazioni.
La generazione di numeri fornisce risultati immediati: bastano pochi secondi per creare una combinazione. Se parliamo di lotterie, i partecipanti possono immediatamente scoprire se il numero del biglietto corrisponde a quello vincente. Ciò consente di svolgere i disegni tutte le volte che i partecipanti lo desiderano. Ma il vantaggio principale del metodo è la sua imprevedibilità e l'impossibilità di calcolare l'algoritmo per la selezione dei numeri.
Come vengono generati i numeri pseudocasuali
In effetti, i numeri casuali non sono casuali: la serie inizia da un dato numero ed è generata da un algoritmo. Un generatore di numeri pseudocasuali (PRNG o PRNG - generatore di numeri pseudocasuali) è un algoritmo che genera una sequenza di numeri apparentemente non correlati, solitamente soggetti a una distribuzione uniforme. Nell'informatica, i numeri pseudocasuali vengono utilizzati in molte applicazioni: crittografia, modellazione di simulazione, metodo Monte Carlo, ecc. La qualità del risultato dipende dalle proprietà del PRNG.
La fonte di generazione può essere il rumore fisico derivante dalla radiazione cosmica o il rumore in un resistore, ma tali dispositivi non vengono quasi mai utilizzati nelle applicazioni di sicurezza di rete. Le applicazioni crittografiche utilizzano algoritmi speciali che generano sequenze che non possono essere statisticamente casuali. Tuttavia, un algoritmo scelto correttamente può produrre serie di numeri che superano la maggior parte dei test di casualità. Il periodo di ripetizione in tali sequenze è maggiore dell'intervallo di lavoro da cui vengono presi i numeri.
Molti processori moderni contengono un PRNG, come RdRand. In alternativa, vengono creati insiemi di numeri casuali e pubblicati in un one-time pad (dizionario). La fonte dei numeri in questo caso è limitata e non fornisce una sicurezza di rete completa.
Storia del PRNG
Il prototipo di un generatore di numeri casuali può essere considerato il gioco da tavolo Senet, diffuso nell'Antico Egitto nel 3500 a.C. Secondo le condizioni, hanno partecipato due giocatori, le mosse sono state determinate lanciando quattro bastoncini piatti bianchi e neri: erano una sorta di PRNG di quel tempo. I bastoncini venivano lanciati contemporaneamente e si contavano i punti: se uno cadeva con il lato bianco, 1 punto e una mossa aggiuntiva, due bianchi - due punti e così via. Il risultato massimo di cinque punti è stato ottenuto dal giocatore che ha lanciato quattro bastoncini con il lato nero.
Al giorno d'oggi, il generatore ERNIE è utilizzato da molti anni nel Regno Unito per le estrazioni della lotteria. Esistono due metodi principali per generare i numeri vincenti: congruente lineare e congruente additivo. Questi e altri metodi si basano sul principio della selezione casuale e sono forniti da un software che produce all'infinito numeri, la cui sequenza è impossibile da indovinare.
Il PRNG funziona continuamente, ad esempio nelle slot machine. Secondo la legge statunitense, questa è una condizione obbligatoria che tutti i fornitori di software devono rispettare.
Abbiamo una sequenza di numeri costituita da elementi praticamente indipendenti che obbediscono ad una determinata distribuzione. Di regola, distribuzione uniforme.
Puoi generare numeri casuali in Excel in diversi modi e modi. Consideriamo solo i migliori.
Funzione numero casuale in Excel
- La funzione RAND restituisce un numero reale casuale e uniformemente distribuito. Sarà inferiore a 1, maggiore o uguale a 0.
- La funzione RANDBETWEEN restituisce un numero intero casuale.
Vediamo il loro utilizzo con degli esempi.
Campionamento di numeri casuali utilizzando RAND
Questa funzione non richiede argomenti (RAND()).
Per generare un numero reale casuale compreso tra 1 e 5, ad esempio, utilizzare la seguente formula: =RAND()*(5-1)+1.
Il numero casuale restituito viene distribuito uniformemente nell'intervallo.
Ogni volta che viene calcolato il foglio di lavoro o cambia il valore in qualsiasi cella del foglio di lavoro, viene restituito un nuovo numero casuale. Se vuoi salvare la popolazione generata, puoi sostituire la formula con il suo valore.
- Fare clic sulla cella con un numero casuale.
- Nella barra della formula selezionare la formula.
- Premi F9. ED ENTRA.
Controlliamo l'uniformità della distribuzione dei numeri casuali del primo campione utilizzando un istogramma di distribuzione.
L'intervallo di valori verticali è la frequenza. Orizzontale - "tasche".
Funzione CASUALETRA
La sintassi per la funzione RANDBETWEEN è (limite inferiore; limite superiore). Il primo argomento deve essere minore del secondo. Altrimenti la funzione genererà un errore. Si presuppone che i confini siano numeri interi. La formula scarta la parte frazionaria.
Esempio di utilizzo della funzione:
Numeri casuali con precisione 0,1 e 0,01:
Come creare un generatore di numeri casuali in Excel
Creiamo un generatore di numeri casuali che generi un valore da un determinato intervallo. Usiamo una formula come: =INDEX(A1:A10,INTEGER(RAND()*10)+1).
Creiamo un generatore di numeri casuali nell'intervallo da 0 a 100 in passi di 10.
È necessario selezionarne 2 casuali dall'elenco dei valori di testo. Utilizzando la funzione RAND, confrontiamo i valori di testo nell'intervallo A1:A7 con numeri casuali.
Usiamo la funzione INDICE per selezionare due valori di testo casuali dall'elenco originale.
Per selezionare un valore casuale dall'elenco, utilizzare la formula seguente: =INDEX(A1:A7,RANDBETWEEN(1,COUNT(A1:A7))).
Generatore di numeri casuali a distribuzione normale
Le funzioni CASUALE e CASUALE TRA producono numeri casuali con una distribuzione uniforme. Qualsiasi valore con la stessa probabilità può rientrare nel limite inferiore dell'intervallo richiesto e in quello superiore. Ciò si traduce in un enorme spread rispetto al valore target.
Una distribuzione normale implica che la maggior parte dei numeri generati siano vicini al numero target. Regoliamo la formula RANDBETWEEN e creiamo un array di dati con una distribuzione normale.
Il costo del prodotto X è di 100 rubli. L'intero lotto prodotto segue una distribuzione normale. Anche una variabile casuale segue una distribuzione di probabilità normale.
In tali condizioni, il valore medio dell'intervallo è di 100 rubli. Generiamo un array e costruiamo un grafico con una distribuzione normale con una deviazione standard di 1,5 rubli.
Usiamo la funzione: =NORMINV(RAND();100;1.5).
Excel ha calcolato quali valori rientravano nell'intervallo di probabilità. Poiché la probabilità di produrre un prodotto con un costo di 100 rubli è massima, la formula mostra valori vicini a 100 più spesso di altre.
Passiamo alla tracciatura del grafico. Per prima cosa devi creare una tabella con le categorie. Per fare ciò, dividiamo l'array in periodi:
Sulla base dei dati ottenuti, possiamo generare un diagramma con una distribuzione normale. L'asse dei valori è il numero di variabili nell'intervallo, l'asse delle categorie sono i periodi.
Il generatore di numeri casuali online presentato funziona sulla base di un generatore di numeri pseudocasuali con distribuzione uniforme integrato in JavaScript. Vengono generati numeri interi. Per impostazione predefinita, vengono emessi 10 numeri casuali nell'intervallo 100...999, i numeri separati da spazi.
Impostazioni di base del generatore di numeri casuali:
- Quantità di numeri
- Intervallo di numeri
- Tipo di separatore
- Attiva/disattiva la funzione di rimozione delle ripetizioni (duplicati di numeri)
Il numero totale è formalmente limitato a 1000, con un massimo di 1 miliardo. Opzioni separatore: spazio, virgola, punto e virgola.
Ora sai esattamente dove e come ottenere una sequenza gratuita di numeri casuali in un determinato intervallo su Internet.
Opzioni applicative per un generatore di numeri casuali
Un generatore di numeri casuali (RNG in JS con distribuzione uniforme) sarà utile agli specialisti SMM e ai proprietari di gruppi e comunità sui social network Instagram, Facebook, VKontakte, Odnoklassniki per determinare i vincitori di lotterie, concorsi ed estrazioni a premi.
Un generatore di numeri casuali ti consente di estrarre premi tra un numero arbitrario di partecipanti con un numero specificato di vincitori. I concorsi possono svolgersi senza ripubblicazioni e commenti: imposti tu stesso il numero di partecipanti e l'intervallo per la generazione di numeri casuali. Puoi ottenere una serie di numeri casuali online e gratuitamente su questo sito e non è necessario installare alcuna applicazione sul tuo smartphone o programma sul tuo computer.
Inoltre, è possibile utilizzare un generatore di numeri casuali online per simulare il lancio di una moneta o di un dado. Tuttavia, disponiamo di servizi specializzati separati per questi casi.
Si noti che idealmente la curva di densità di distribuzione dei numeri casuali apparirebbe come mostrata in Fig. 22.3. Cioè, idealmente, ogni intervallo contiene lo stesso numero di punti: N io = N/K , Dove N numero totale di punti, K numero di intervalli, io= 1, , K .
generato teoricamente da un generatore ideale
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 vengono distribuiti secondo la legge di distribuzione (arbitraria) richiesta dall'utente o nell'intervallo richiesto.
I generatori di numeri casuali secondo il metodo per ottenere i numeri sono suddivisi in:
- fisico;
- tabellare;
- algoritmico.
RNG fisico
Un esempio di RNG fisico può essere: una moneta (“testa” 1, “croce” 0); dado; un tamburo con una freccia divisa in settori con numeri; generatore di rumore hardware (HS), che utilizza un dispositivo termico rumoroso, ad esempio un transistor (Fig. 22.422.5).
| Compito “Generazione di numeri casuali utilizzando una moneta” | |
|
Genera un numero casuale di tre cifre, distribuito uniformemente nell'intervallo da 0 a 1, utilizzando una moneta. Precisione tre cifre decimali. |
|
Il primo modo per risolvere il problema
Disegna un intervallo da 0 a 1. Leggendo i numeri in sequenza da sinistra a destra, dividi l'intervallo a metà e scegli ogni volta una delle parti dell'intervallo successivo (se esce uno 0, allora quella di sinistra, se esce 1 appare, poi quello giusto). Pertanto, puoi arrivare a qualsiasi punto dell'intervallo, con la precisione che desideri. COSÌ, 1 : l'intervallo viene diviso a metà e , viene selezionata la metà destra, l'intervallo viene ridotto: . Numero successivo 0 : l'intervallo viene diviso a metà e , viene selezionata la metà sinistra, l'intervallo viene ridotto: . Numero successivo 0 : l'intervallo viene diviso a metà e , viene selezionata la metà sinistra, l'intervallo viene ridotto: . Numero successivo 1 : l'intervallo viene diviso a metà e , viene selezionata la metà destra, l'intervallo viene ridotto: . In base alla condizione di accuratezza del problema, è stata trovata una soluzione: è un numero qualsiasi dell'intervallo, ad esempio 0,625. In linea di principio, se adottiamo un approccio rigoroso, la divisione degli intervalli deve essere continuata fino a quando i limiti sinistro e destro dell'intervallo trovato COINCIDONO con una precisione della terza cifra decimale. Cioè, dal punto di vista della precisione, il numero generato non sarà più distinguibile da qualsiasi numero dell'intervallo in cui si trova.
Il secondo modo per risolvere il problema
|
RNG tabellare
Gli RNG tabulari utilizzano tabelle appositamente compilate contenenti numeri verificati non correlati, cioè non dipendenti l'uno dall'altro, come fonte di numeri casuali. Nella tabella La Figura 22.1 mostra un piccolo frammento di tale tabella. Percorrendo la tabella da sinistra a destra, dall'alto al basso, si ottengono numeri casuali distribuiti uniformemente da 0 a 1 con il numero di cifre decimali richiesto (nel nostro esempio utilizziamo tre cifre decimali per ogni numero). Poiché i numeri nella tabella non dipendono l'uno dall'altro, la tabella può essere attraversata in diversi modi, ad esempio dall'alto verso il basso o da destra a sinistra o, ad esempio, è possibile selezionare i numeri che si trovano in posizioni pari.
| Tabella 22.1. Numeri casuali. In modo uniforme numeri casuali distribuiti da 0 a 1 |
||||||||||||||||||||||||||||||||||||||||||||
| Numeri casuali | Distribuito uniformemente Da 0 a 1 numeri casuali |
|||||||
| 9 | 2 | 9 | 2 | 0 | 4 | 2 | 6 | 0.929 |
| 9 | 5 | 7 | 3 | 4 | 9 | 0 | 3 | 0.204 |
| 5 | 9 | 1 | 6 | 6 | 5 | 7 | 6 | 0.269 |
Il vantaggio di questo metodo è che produce numeri veramente casuali, poiché la tabella contiene numeri non correlati verificati. Svantaggi del metodo: memorizzare un gran numero di cifre richiede molta memoria; Esistono grandi difficoltà nel generare e verificare questo tipo di tabelle; le ripetizioni nell'utilizzo di una tabella non garantiscono più la casualità della sequenza numerica e quindi l'attendibilità del risultato.
C'è una tabella contenente 500 numeri verificati assolutamente casuali (tratti 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 da questi RNG sono sempre pseudo-casuali (o quasi-casuali), cioè ogni numero successivo generato dipende da quello precedente:
R io + 1 = F(R io) .
Le sequenze composte da tali numeri formano dei loop, cioè esiste necessariamente un ciclo che si ripete un numero infinito di volte. I cicli ripetuti sono chiamati periodi.
Il vantaggio di questi RNG è la loro velocità; i generatori non richiedono praticamente risorse di memoria e sono compatti. Svantaggi: i numeri non possono essere definiti completamente casuali, poiché esiste una dipendenza tra loro, così come la presenza di periodi nella sequenza di numeri quasi casuali.
Consideriamo diversi metodi algoritmici per ottenere RNG:
- metodo dei quadrati mediani;
- metodo dei prodotti medi;
- metodo di agitazione;
- metodo della congruenza lineare.
Metodo del quadrato medio
C'è un numero di quattro cifre R 0 . Questo numero viene quadrato e inserito R 1 . Avanti da R 1 prende il nuovo numero casuale centrale (quattro cifre centrali) e lo scrive R 0 . Quindi la procedura viene ripetuta (vedere Fig. 22.6). Tieni presente che in effetti non devi prendere un numero casuale ghij, UN 0.ghij con uno zero e un punto decimale aggiunti a sinistra. Questo fatto si riflette come in Fig. 22.6, e nelle successive figure simili.
 |
Svantaggi del metodo: 1) se ad alcune iterazioni il numero R 0 diventa uguale a zero, quindi il generatore degenera, quindi è importante la scelta corretta del valore iniziale R 0; 2) il generatore ripeterà la sequenza M N passi (nella migliore delle ipotesi), dove N cifra del numero R 0 , M base del sistema numerico.
Ad esempio nella Fig. 22.6: se il numero R 0 verrà rappresentato nel sistema di numerazione binario, quindi la sequenza di numeri pseudo-casuali verrà ripetuta in 2 4 = 16 passi. Si noti che la ripetizione della sequenza può avvenire prima se il numero iniziale viene scelto male.
Il metodo sopra descritto è stato proposto da John von Neumann e risale al 1946. Poiché questo metodo si è rivelato inaffidabile, è stato rapidamente abbandonato.
Metodo del prodotto medio
Numero R 0 moltiplicato per R 1, dal risultato ottenuto R 2 viene estratta la parte centrale R 2 * (questo è un altro numero casuale) e moltiplicato per R 1 . Tutti i numeri casuali successivi vengono 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 e a destra. L'idea del metodo è la seguente. Lascia che la cella memorizzi il numero iniziale R 0 . Spostando ciclicamente il contenuto della cella verso sinistra di 1/4 della lunghezza della cella, otteniamo un nuovo numero R 0*. Allo stesso modo, ciclando il contenuto della cella R 0 a destra di 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 1 . Ulteriore R 1 è inserito R 0, e l'intera sequenza di operazioni viene ripetuta (vedi Fig. 22.8).
 |
Si prega di notare che il numero risultante dalla somma R 0* e R 0 ** , potrebbe non rientrare completamente nella cella R 1 . In questo caso, le cifre extra devono essere scartate dal numero risultante. Spieghiamo questo in 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 (uguale a R 0) può contenere un massimo di 8 bit. Pertanto, prima di inserire il valore in R 1, è necessario rimuovere un bit “extra”, più a sinistra, dal numero 306, ottenendo come risultato R 1 non andrà più a 306, ma a 00110010 2 = 50 10 . Si noti inoltre che in linguaggi come Pascal, il "ritaglio" di bit extra quando una cella trabocca viene eseguito automaticamente in base al tipo specificato di variabile.
Metodo della congruenza lineare
Il metodo della congruenza lineare è una delle procedure più semplici e comunemente utilizzate attualmente per simulare numeri casuali. Questo metodo utilizza il mod( X, sì) , che restituisce il resto quando il primo argomento viene 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) .
Viene chiamata la sequenza di numeri casuali ottenuta utilizzando questa formula sequenza lineare congruente. Molti autori chiamano una successione lineare congruente quando B = 0 metodo moltiplicativo congruente, e quando B ≠ 0 metodo misto congruente.
Per un generatore di alta qualità, è necessario selezionare coefficienti adeguati. È necessario che il numero M era piuttosto grande, poiché il periodo non può averne di più M elementi. D’altra parte, la divisione utilizzata in questo metodo è un’operazione piuttosto lenta, quindi per un computer binario la scelta logica sarebbe M = 2 N, poiché in questo caso la ricerca del resto della divisione si riduce all'interno del computer all'operazione logica binaria “AND”. È comune anche la scelta del numero primo più grande M, meno di 2 N: nella letteratura specializzata è dimostrato che in questo caso le cifre di ordine basso del numero casuale risultante R io+1 si comportano in modo altrettanto casuale come quelli più vecchi, il che ha un effetto positivo sull'intera sequenza di numeri casuali nel suo insieme. Ad esempio, uno dei Numeri di Mersenne, pari a 2 31 1, e quindi, M= 2 31 1 .
Uno dei requisiti per le sequenze lineari congruenti è che la lunghezza del periodo sia la più lunga possibile. 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 durata 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:
- numeri B E M relativamente semplice;
- K 1 volta P per ogni numero primo P, che è un divisore M ;
- K 1 è un multiplo di 4, se M multiplo di 4.
Infine, concludiamo con un paio di esempi di utilizzo del metodo della congruenza lineare per generare numeri casuali.
È stato stabilito che una serie di numeri pseudo-casuali generati sulla base dei dati dell'esempio 1 verrebbe ripetuta ogni M/4 numeri. Numero Qè impostato arbitrariamente prima dell'inizio dei calcoli, tuttavia, va tenuto presente che la serie dà l'impressione di essere in generale casuale K(e quindi 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 di 69069 e 71365.
Un generatore di numeri casuali che utilizza i dati dell'esempio 2 produrrà numeri casuali non ripetitivi con un periodo di 7 milioni.
Il metodo moltiplicativo per generare numeri pseudocasuali fu 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 dal RNG deve soddisfare una serie di criteri.
I controlli effettuati sono di due tipi:
- controlli sull'uniformità della distribuzione;
- test di indipendenza statistica.
Controlla l'uniformità della distribuzione
1) L'RNG dovrebbe produrre valori prossimi ai seguenti parametri statistici caratteristici di una legge casuale uniforme:
2) Prova di frequenza
Un test di frequenza ti consente di scoprire quanti numeri rientrano in un intervallo (M R σ R ; M R + σ R) , cioè (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 estratti dovrebbe rientrare in questo intervallo (vedere Figura 22.9).
in caso di controllo per il test di frequenza
È 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) Test del chi quadrato
Il test del chi quadrato (test del χ2) è uno dei test statistici più conosciuti; è il metodo principale utilizzato in combinazione con altri criteri. Il test del chi quadrato fu proposto nel 1900 da Karl Pearson. Il suo notevole lavoro è considerato il fondamento della moderna statistica matematica.
Nel nostro caso, il controllo utilizzando il criterio del chi-quadrato ci consentirà di scoprire quanto il vero L'RNG è vicino al benchmark RNG, vale a dire se soddisfa o meno il requisito di distribuzione uniforme.
Diagramma di frequenza riferimento L'RNG è mostrato in Fig. 22.10. Poiché la legge di distribuzione del RNG di riferimento è uniforme, allora la probabilità (teorica). P io inserire i numeri io th intervallo (il totale di questi intervalli K) è uguale a P io = 1/K . E così, in ciascuno di K gli intervalli colpiranno liscio Di P io · N numeri ( N numero totale di numeri generati).
Un vero RNG produrrà numeri distribuiti (e non necessariamente in modo uniforme!) K intervalli e ogni intervallo conterrà N io numeri (in totale 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 le differenze al quadrato tra il numero di numeri risultante N io e "riferimento" P io · N . Sommiamoli e il risultato è:
χ2 esp. = ( N 1 P 1 · N) 2 + (N 2 P 2 · N) 2 + + ( N K P K · N) 2 .
Da questa formula segue che quanto più piccola è la differenza in ciascuno dei termini (e quindi quanto più piccolo è il valore di χ 2 exp.), tanto più forte tende ad essere uniforme la legge di distribuzione dei numeri casuali generati da un RNG reale.
Nell'espressione precedente a ciascuno dei termini viene assegnato lo stesso peso (pari a 1), il che di fatto potrebbe non essere vero; pertanto, per le statistiche chi-quadrato, è necessario normalizzarli ciascuno io termine, dividendolo per P io · N :
Infine, scriviamo l’espressione risultante in modo più compatto e semplifichiamola:
Abbiamo ottenuto il valore del test chi quadrato per sperimentale dati.
Nella tabella 22.2 sono dati teorico valori del chi-quadrato (χ 2 teorico), dove ν = N 1 è il numero di gradi di libertà, P questo è un livello di confidenza specificato dall'utente che indica in che misura l'RNG dovrebbe soddisfare i requisiti di una distribuzione uniforme, oppure P è la probabilità che il valore sperimentale di χ 2 exp. sarà inferiore al χ 2 teorico tabulato. o uguale ad esso.
| Tabella 22.2. Alcuni punti percentuali della distribuzione χ 2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| p = 1% | p = 5% | p = 25% | p = 50% | p = 75% | p = 95% | p = 99% | |
| ν = 1 | 0.00016 | 0.00393 | 0.1015 | 0.4549 | 1.323 | 3.841 | 6.635 |
| ν = 2 | 0.02010 | 0.1026 | 0.5754 | 1.386 | 2.773 | 5.991 | 9.210 |
| ν = 3 | 0.1148 | 0.3518 | 1.213 | 2.366 | 4.108 | 7.815 | 11.34 |
| ν = 4 | 0.2971 | 0.7107 | 1.923 | 3.357 | 5.385 | 9.488 | 13.28 |
| ν = 5 | 0.5543 | 1.1455 | 2.675 | 4.351 | 6.626 | 11.07 | 15.09 |
| ν = 6 | 0.8721 | 1.635 | 3.455 | 5.348 | 7.841 | 12.59 | 16.81 |
| ν = 7 | 1.239 | 2.167 | 4.255 | 6.346 | 9.037 | 14.07 | 18.48 |
| ν = 8 | 1.646 | 2.733 | 5.071 | 7.344 | 10.22 | 15.51 | 20.09 |
| ν = 9 | 2.088 | 3.325 | 5.899 | 8.343 | 11.39 | 16.92 | 21.67 |
| ν = 10 | 2.558 | 3.940 | 6.737 | 9.342 | 12.55 | 18.31 | 23.21 |
| ν = 11 | 3.053 | 4.575 | 7.584 | 10.34 | 13.70 | 19.68 | 24.72 |
| ν = 12 | 3.571 | 5.226 | 8.438 | 11.34 | 14.85 | 21.03 | 26.22 |
| ν = 15 | 5.229 | 7.261 | 11.04 | 14.34 | 18.25 | 25.00 | 30.58 |
| ν = 20 | 8.260 | 10.85 | 15.45 | 19.34 | 23.83 | 31.41 | 37.57 |
| ν = 30 | 14.95 | 18.49 | 24.48 | 29.34 | 34.80 | 43.77 | 50.89 |
| ν = 50 | 29.71 | 34.76 | 42.94 | 49.33 | 56.33 | 67.50 | 76.15 |
| ν > 30 | ν +qrt(2 ν ) · X P+ 2/3 · X 2 P 2/3+ O(1/quadrato( ν )) | ||||||
| X P = | 2.33 | 1.64 | 0,674 | 0.00 | 0.674 | 1.64 | 2.33 |
Considerato accettabile P dal 10% al 90%.
Se χ 2 esp. molto più della teoria del χ2. (questo è Pè grande), quindi il generatore non soddisfa il requisito della distribuzione uniforme, a partire dai valori osservati N io andare troppo lontano dal teorico P io · N e non può essere considerato casuale. In altre parole, viene stabilito un intervallo di confidenza così ampio che le restrizioni sui numeri diventano molto allentate, i requisiti sui numeri diventano deboli. In questo caso, si osserverà un errore assoluto molto grande.
Anche D. Knuth nel suo libro “The Art of Programming” ha notato che avendo χ 2 exp. per i piccoli, in generale, non va bene nemmeno, anche se questo sembra, a prima vista, meraviglioso dal punto di vista dell'uniformità. Infatti, prendiamo 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 dell'uniformità, e χ 2 esp. saranno praticamente zero, ma difficilmente li riconoscerete come casuali.
Se χ 2 esp. molto meno della teoria del χ2. (questo è P piccolo), quindi il generatore non soddisfa il requisito di una distribuzione uniforme e casuale, a partire dai valori osservati N io troppo vicino al teorico P io · N e non può essere considerato casuale.
Ma se χ 2 esp. si trova in un certo intervallo tra due valori di χ 2 o. , che corrispondono, ad esempio, P= 25% e P= 50%, allora possiamo supporre che i valori dei numeri casuali generati dal sensore siano completamente casuali.
Inoltre, va tenuto presente che tutti i valori P io · N deve essere abbastanza grande, ad esempio più di 5 (trovato empiricamente). Solo allora (con un campione statistico sufficientemente ampio) le condizioni sperimentali potranno essere considerate soddisfacenti.
Pertanto, la procedura di verifica è la seguente.
Test di indipendenza statistica
1) Controllo della frequenza di occorrenza dei numeri nella sequenza
Diamo un'occhiata a un esempio. Il numero casuale 0.2463389991 è composto dalle cifre 2463389991, mentre il numero 0.5467766618 è composto dalle cifre 5467766618. Collegando le sequenze di cifre, abbiamo: 24633899915467766618.
È chiaro che la probabilità teorica P io perdita io L'esima cifra (da 0 a 9) è pari a 0,1.
2) Controllare l'aspetto di serie di numeri identici
Indichiamo con N l numero di serie di cifre identiche in una riga di lunghezza l. Tutto deve essere controllato l da 1 a M, Dove M questo è un numero specificato dall'utente: il numero massimo di cifre identiche presenti in una serie.
Nell’esempio “24633899915467766618” sono state trovate 2 serie di lunghezza 2 (33 e 77), cioè N 2 = 2 e 2 serie di lunghezza 3 (999 e 666), cioè N 3 = 2 .
La probabilità che si verifichi una serie di lunghezza lè uguale a: P l= 9 10 l (teorico). Cioè, la probabilità che si verifichi una serie lunga un carattere è uguale a: P 1 = 0,9 (teorico). La probabilità che appaia una serie di due caratteri è: P 2 = 0,09 (teorico). La probabilità che appaia una serie di tre caratteri è: P 3 = 0,009 (teorico).
Ad esempio, la probabilità che si verifichi una serie lunga un carattere è P l= 0,9, poiché può esserci un solo simbolo su 10 e ci sono 9 simboli in totale (lo zero non conta). E la probabilità che due simboli identici “XX” appaiano in fila è 0,1 · 0,1 · 9, cioè la probabilità di 0,1 che il simbolo “X” appaia in prima posizione è moltiplicata per la probabilità di 0,1 che il simbolo “X” appaia in prima posizione lo stesso simbolo apparirà nella seconda posizione “X” e moltiplicato per il numero di tali combinazioni 9.
La frequenza di occorrenza delle serie viene calcolata utilizzando la formula del chi quadrato di cui abbiamo discusso in precedenza utilizzando i valori P l .
Nota: il generatore può essere testato più volte, ma i test non sono completi e non garantiscono che il generatore produca numeri casuali. Ad esempio, un generatore che produce la sequenza 12345678912345 sarà considerato ideale durante i test, 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) è interamente dedicato allo studio dei numeri casuali. Esamina vari metodi per generare numeri casuali, test statistici di casualità e conversione di numeri casuali distribuiti uniformemente in altri tipi di variabili casuali. Più di duecento pagine sono dedicate alla presentazione di questo materiale.