Newsgroup: it.scienza.fisica
Titolo: chi-squared test per la verifica della randomicità

Ciao a tutti,
stavo leggendo "The art of computer programming" (vol.2) e ho dei dubbi sul test chi-quadrato applicato alla verifica dei numeri randomici.
Premetto che non sono nè un matematico nè un fisico: correggetemi pure se dico inesattezze.
 
Il test del chi-quadrato serve a comparare due distribuzioni di probabilità (in soldoni): per la verifica del PRNG la "comparazione" viene effettuata con una gaussiana.
 
E' stata scelta la gaussiana come riferimento in quanto è la distribuzione di probabilità che meglio descrive la probabilità di ottenere un risultato dopo n osservazioni (tipico esempio è il lancio del dado).
 
Il libro dice che se il risultato ottenuto dal chi-quadrato è elevato, i risultati ottenuti non possono essere considerati randomici (la loro distribuzione è troppo differente rispetto a quella gaussiana).
 
Tuttavia dice anche che in numeri non possono essere considerati randomici se il risultato del chi-squared test è molto basso: non capisco il perchè.
 
Ottenere dal test un risultato molto basso vuol dire che la distribuzione osservata è paragonabile ad una gaussiana: questo non dovrebbe essere il risultato ottimale?
Il libro giustifica dicendo che in tal caso la probabilità di ottenere un risultato è prevedibile: perchè?
Grazie

 un risultato è prevedibile: perchè? Grazie
 
 
Non conosco il libro, mi spiace (ho solo il I volume)
 
 
-- 
E-S °¿°
Ho plonkato tutti quelli che postano da Google Groups!
Qui è Usenet, non è il Web!


Scusa
la domanda qual è?
 
vedi se può esserti utile
http://simul.iro.umontreal.ca/testu01/tu01.html
 

 
http://simul.iro.umontreal.ca/testu01/tu01.html
 
 
Darò un'occhiata, grazie!

 ottenere un risultato è prevedibile: perché?
Ho qui davanti il libro, e non dice proprio quello che gli fai dire tu.
Ecco le parole esatte (vol. 2, pag. 42):
"The chi-square table tellls us, in fact, that V2 /is much too low/:
the observed values are so close to the expected values, we cannot
consider the result to be random!"
 
Se l'esempio che Knuth fa (il lancio di due dadi) ti pare è troppo
complicato, usiamo un dado solo.
Lo lanciamo 120 volte, e troviamo le seguenti frequenze:
 
20, 19, 19, 21, 20, 21.
 
Il chi-quadro vale 0.2, mentre non dovrebbe essere troppo diverso da 5
(n. di gradi di libertà).
La tabella che dà Knuth (pag. 41) mostra che la prob. di quel valore è
ben < 1%.
 
Ma anche a lume di naso, quella serie di numeri è sospetta: è vero che
la freq. attesa è 120/6=20, ma *le fluttuazioni sono troppo scarse*:
io me le aspetterei dell'ordine di sqrt(20), ossia 4 o 5.
 
Che cosa diresti davanti a quei numeri?
Probab. che non sono veri risultati di lancio di un dado.
Se hai ancora dei dubbi, fai una prova con un dado, e dicci che numeri
hai trovato in 120 prove.
 
 
-- 
Elio Fabri

 hai trovato in 120 prove.
 
Ok: è questo il punto che non mi è chiaro.
 
Ad intuito ti dò ragione ma è anche vero che dopo un numero molto elevato di prove dovrei aspettarmi una distribuzione prossima al caso ideale (ovvero la gaussiana).  
 
Se dopo 10000 tentativi (numero di tentativi molto elevato) ottengo una distribuzione che è prossima alla gaussiana perchè dovrei considerare i risultati come "sospetti"? Perchè sono molto prossimi al caso ideale?

 ideale?
 
 
Potrebbe venire una distribuzione di dati che "assomiglia" a
una gaussiana, o che ha troppi o troppo pochi valori estremi,
non so.


 al caso ideale?
Vedo che insisti sulla gaussiana, ma io voglio insistere sull'esempio
del dado singolo, perché è del tutto equivalente come problema ma è di
gran lunga più semplice da capire.
 
Il tuo errore sta nel farti trascinare dalle parole, senza sapere (o
tener conto di) quale significato abbiano nel contesto scientifico di
cui stiamo parlando.
Concentriamoci su un singolo numero, per es. il 5.
Che cosa vuol dire "mi aspetto che in molte prove la freq. osservata
sia vicina a 1/6?
 
Esattamente questo. Essendo p la prob. dell'evento, in una successione
di n prove indipendenti il numero X di risultati favorevoli è una
variabile casuale con distribuzione binomiale.
Le probab. dei possibili esiti, che vanno da 0 a n, sono
 
p_x = C(n,x) p^x q^(n-x)  (q = 1-p).
 
La media è E(x) = np
La varianza è Var(x) = npq.
Lo s.q.m. è la radice della varianza, ossia sqrt(npq).
 
Per p = 1/6, n = 120 (mio esempio) avrai s.q.m. = sqrt(50/3) = 4.08.
Avrai una probab. del 68% di uno scarto dalla media inferiore allo
s.q.m., quindi nel nostro caso (media 20) tra 16 e 24.
 
Come vedi dalle formule che ho scritto, lo s.q.m. va come sqrt(n).
Se quindi prendiamo n 100 volte più grande (n=12000) lo s.q.m. sarà
circa 40, la media 2000, e ti devi aspettare valori di X tra 1960 e
2040 nel 68% dei casi.
In termini relativi, la fluttuazione al 68% è 4/20 = 0.2 per n=120,
mentre è 40/2000 = 0.02 per n=12000.
 
Questo significa in termini semplici (esiste un preciso enunciato come
teorema) che la frequenza "si avvicina" alla probab. al crescere del
numero di prove.
Si avvicina, ma senpre con un certo campo di fluttuazione.
 
Ora accade che la formula del chi^2 (guardala) tiene conto di questo,
perché a num. ha il quadrato dello scostamento dal valore atteso
(media); a denominatore ha (circa) la varianza.
Tanto il num. quanto il den. crescono allo stesso modo al crescere di
n, per cui il valore atteso per chi^2 è pressoché indip. da n:
all'incirca uguale al n. di gradi di libertà, quindi 5 nell'esempio del
dado.
 
Ecco perché sia un vaore troppo grande di chi^2, sia un valore troppo
piccolo, sono sospetti.
Il primo caso indica che la vera distrib. di probab. non è quella con
cui stai facendo i conti.
Il secondo caso dice che gli eventi non sono del tutto casuali; cosa
che può avvenire per diverse ragioni: caso più banale, perché il dado è
truccato.
 
 
-- 
Elio Fabri