Generazione numeri casuali e GePaHE
Lurkos
livello scientifico/informatico, con i metodi Monte Carlo.
Sintetizzando per chi non sapesse di cosa sto parlando si tratta di
metodi simulativi probabilistici che si basano sulla disponibilit� di
un'enorme quantit� di numeri casuali.
Risultano essere sistemi molto potenti per simulare e prevedere
l'andamento di sistemi a geometria complessa, le cui equazioni
deterministiche non sono risolvibili.
L'esempio che mi viene in mente adesso � il calcolo della dose
radioattiva sommistrata ai vari organi di un paziente sottoposto a
radioterapia.
Ho visto che in Fortran (il linguaggio principe per quel che riguarda
l'analisi numerica) � presente dalla specifica del '95 una funzione
intrinseca per generare numeri pseudo-casuali: RANDOM_NUMBER
(http://gcc.gnu.org/onlinedocs/gfortran/RANDOM_005fNUMBER.html).
Il problema, come al solito, � che bisogna fornire un seed "casuale" per
inizializzare il generatore.
In questo caso, a seconda del compilatore, il seed non deve essere solo
uno, ma pi� di uno.
Mi sono allora dovuto porre il problema di trovare numeri oltre
all'orario del sistema da usare. Personalmente la soluzione proposta nel
manuale di gfortran
(http://gcc.gnu.org/onlinedocs/gfortran/RANDOM_005fSEED.html) non mi
piace per niente: prendere 8 numeri consecutivi o con
differenza fra loro predeterminata mi sembra tutto tranne che una buona
soluzione.
Ho quindi allora pensato di usare l'impredicibilit� del resto della
divisione fra numeri molti elevati. Ho quindi dato in pasto al mio
generatore di numeri casuali fatto in casa l'orario del sistema per poi
generare gli altri seed che mi servivano. Avendo a disposizione il
vettore di seed ho inizializzato la funzione random intrinseca del
compilatore.
Ho qualche domanda in proposito:
1) � corretta la procedura che ho seguito?
2) si poteva fare di meglio? se s�, come?
Parlando di numeri casuali mi � tornato in mente il programma GePaHE
(http://www.webalice.it/cristiano.pi/GePaHE/) di Cristiano.
Al momento si tratta di un progetto abbandonato oppure no?
Se non chiedo troppo, mi potreste spiegare effettivamente come funziona?
In particolare la frase
"Questo risultato viene raggiunto sfruttando adeguatamente i
temporizzatori ad alta risoluzione presenti nei comuni personal
computer con sistemi operativi Windows e CPU classe Pentium (ad es.
Athlon), non sono quindi necessari componenti elettronici aggiuntivi."
non mi � chiara.
Cosa sono effettivamente i temporizzatori? Perch� sono veramente
casuali?
Sarebbe possibile ottenere un'implementazione multipiattaforma, in
particolare anche per i sistemi *nix oppure il gioco si basa in parte
anche su funzioni intrinseche del sistema operativo Windows?
E per finire: a quale rate costante si potrebbero generare numeri
casuali?
Ho notato che generalmente l'approccio prevalenete di chi
studia/progetta codici Monte Carlo � quello di lasciare al compilatore
l'onere di dare una buona funzione generatrice di numeri casuali,
concentrandosi sulla fisica del sistema.
Questo approccio si � dimostrato nella pratica valido, anche se
personalmente non riesco ad accettare completamente che una simulazione
realistica possa fare affidamento su sequenze di numeri non veramente
casuali.
Per questo motivo mi piacerebbe approfondire la questione, magari
provando a scrivere un codice che utilizza come seed dei veri numeri
casuali e che ad intervelli veramente casuali reinizializza il
generatore PRNG.
L'ideale sarebbe avere un generatore puramente casuale, ma temo che allo
stato attuale non sia praticamente possibile, vista anche la lentezza
con cui si riempe /dev/random su sistemi GNU/Linux (a meno ovviamente
del discorso su GePaHE).
--
Lurkos
Atreides
> Il problema, come al solito, � che bisogna fornire un seed "casuale" per
> inizializzare il generatore.
Uhm... Non necessariamente. Una simulazione non ripetibile non serve a
molto. In genere non e' necessario, per le simulazioni di montecarlo,
che il seed sia casuale. Non stai crittografando stai simulando.
> Ho notato che generalmente l'approccio prevalenete di chi
> studia/progetta codici Monte Carlo � quello di lasciare al compilatore
> l'onere di dare una buona funzione generatrice di numeri casuali,
> concentrandosi sulla fisica del sistema.
> Questo approccio si � dimostrato nella pratica valido, anche se
> personalmente non riesco ad accettare completamente che una simulazione
> realistica possa fare affidamento su sequenze di numeri non veramente
> casuali.
Certo, perche' non serve. Per una simulazione fisica sono le proprieta'
statistiche della distribuzione generata ad essere importanti. Quindi la
"qualita'" del generatore da un punto di vista statistico.
Esempio: se devo simulare l'emissione isotropa (ad esempio di
particelle) occorre fare in modo che tutte le direzioni siano
equiprobabili, questo e' il punto. Non mi interessa che sia
"crittograficamente sicuro".
Il fatto che il generatore "passi" i test statistici (che vuol dire che
l'ipotesi di casualita' e' accettata con un certo livello di confidenza)
non dipende dal seed ma dalle proprieta' del generatore (fatti salvi
seed patologici) e dal contesto.
> Per questo motivo mi piacerebbe approfondire la questione, magari
> provando a scrivere un codice che utilizza come seed dei veri numeri
> casuali
Uhmm.. "veri" numeri casuali? Sei su un terreno minato!!! In pratica non
potrai mai esere "certo" che un set di numeri sia "casuale". Poi solo
accettare questa ipotesi, con una definita probabilita' di accettare
l'ipotesi in modo errato (livello di confidenza). In pratica basta che
sia "sufficientemente" casuale, dove "sufficientemente" dipende dal contesto
> L'ideale sarebbe avere un generatore puramente casuale, ma temo che allo
> stato attuale non sia praticamente possibile, vista anche la lentezza
> con cui si riempe /dev/random su sistemi GNU/Linux (a meno ovviamente
> del discorso su GePaHE).
Rimango convinto che per lo scopo di una simulazione di Montecarlo sia
una paranoia inutile. Non stai centrando il punto. Studia le proprieta'
del generatore, il modo in cui lo usi perche' ci sono alcuni pitfall
quando generi grandezze fisiche legate in modo non linerare e come
esegui il sampling.
Se poi proprio vuoi puoi cercare su google qualche sito che di permette
di selezionare un set di numeri generati da un sistema fisico
(rumore,decadimento radioattivo). Ma , spero di non offenderti, stai
perdendo tempo sull'aspettomeno meno importante di una simulazione di
montecarlo. L'argomento e' OT qui ma ti stupirai scoprendo che in molti
casi (ma non sempre) una simulazione di montecarlo di un sistema fisico
puo' essere "migliore" (ossia piu' accurata e/o piu' efficiente) usando
numeri NON casuali (quasi-random sequence) senza nessun seed. Un esempio
e' il calcolo di integrali multipli. Mai sentito parlare delle sequenze
di Sobol?
Ciao
Max
Lurkos
[extra-cut]
> Un esempio e' il calcolo di integrali multipli. Mai sentito parlare
> delle sequenze di Sobol?
Prima di tutto ti ringrazio per la risposta. Mi hai dato modo di
riflettere su diversi punti.
Mi sono documentato anche sulle sequenze di Sobol e ho capito cosa
intendi. In pratica nel calcolo di integrali conviene "sparare a caso",
ma in maniera ordinata, in modo da riempire i buchi in maniera
uniforme.
Quasi quasi provo ad implementare il solito calcolo di pigreco con una
sequenza di sobol e una "casuale" per vedere con quale arrivo prima ad
una data precisione.
P.S.: spero di non essere linciato per l'OT... :-)
--
Lurkos
Piergiorgio Sartor
[...]
Allora, come ti e` stato gia` risposto, non credo che avere
una assoluta impredicibilita` sia un requisito per questo
genere di simulazioni, anzi, forse e` uno svantaggio, dato
che non saresti in grado di riprodurre i risultati.
Un suggerimento sarebbe:
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
Da cui:
Caution: Mersenne Twister is basically for Monte-Carlo
simulations - it is not cryptographically secure "as is".
Please read FAQ.
bye,
--
piergiorgio
Cristiano
> Negli ultimi giorni mi sono dovuto confrontare, per la prima volta a
> livello scientifico/informatico, con i metodi Monte Carlo.
> Ho visto che in Fortran (il linguaggio principe per quel che riguarda
> l'analisi numerica) � presente dalla specifica del '95 una funzione
> intrinseca per generare numeri pseudo-casuali: RANDOM_NUMBER
> (http://gcc.gnu.org/onlinedocs/gfortran/RANDOM_005fNUMBER.html).
KISS va bene per molti scopi, ma per una simulazione di Montecarlo, io useri
un generatore pi� "serio". :-)
Se hai una CPU SSE2, puoi usare l'ottimo e velocissimo SFMT, altrimenti puoi
usare WELL (nella versione 19937) che ha caratteristiche migliori (ma �
anche decisamente pi� lento).
> Il problema, come al solito, � che bisogna fornire un seed "casuale"
> per inizializzare il generatore.
Nel tuo caso � sufficiente un seme che abbia una variabilit� decente (in
modo da non inizializzare il generatore sempre allo stesso modo), al limite,
potrebbe anche _non_ essere pseudo-casuale (la casualit� non � proprio
richiesta).
> In questo caso, a seconda del compilatore, il seed non deve essere
> solo uno, ma pi� di uno.
> Mi sono allora dovuto porre il problema di trovare numeri oltre
> all'orario del sistema da usare. Personalmente la soluzione proposta
> nel manuale di gfortran
> (http://gcc.gnu.org/onlinedocs/gfortran/RANDOM_005fSEED.html) non mi
> piace per niente: prendere 8 numeri consecutivi o con
> differenza fra loro predeterminata mi sembra tutto tranne che una
> buona soluzione.
Per le simulazioni di Montecarlo, potrebbe anche andar bene, l'importante �
che la sequenza di numeri utilizzata per la simulazione sia diversa di volta
in volta.
> Ho quindi allora pensato di usare l'impredicibilit� del resto della
> divisione fra numeri molti elevati. Ho quindi dato in pasto al mio
> generatore di numeri casuali fatto in casa l'orario del sistema per
> poi generare gli altri seed che mi servivano. Avendo a disposizione il
> vettore di seed ho inizializzato la funzione random intrinseca del
> compilatore.
>
> Ho qualche domanda in proposito:
> 1) � corretta la procedura che ho seguito?
Pu� andar bene, ma vanno bene anche metodi pi� semplici e banali.
> 2) si poteva fare di meglio? se s�, come?
Io ho scritto appositamente un generatore pensato per inizializzare i
generatori aventi uno stato molto grande (molte migliaia di bit).
Sotto winzozz:
ULONG init(void)
{
static ULONG A=__rdtsc(), B=time(0),
y=(__rdtsc()>>32) ^ GetTickCount();
for(int i=0; i<6; i++) {
y=y*2147001325L+715136305L;
A=_rotl(A^B,B)+y; B=_rotl(B^A,A)+y;
}
return A^B;
}
Volendo, potresti inizializzare solo A:
static ULONG A=time(0), B, y;
init passa tutti i test statistici di RaBiGeTe:
http://www.webalice.it/cristiano.pi/rabigete/
> Parlando di numeri casuali mi � tornato in mente il programma GePaHE
> (http://www.webalice.it/cristiano.pi/GePaHE/) di Cristiano.
Mi fa piacere. :-)
> Al momento si tratta di un progetto abbandonato oppure no?
S�. Purtroppo gli utenti che hanno risposto a quanto chiedevo nella sezione
"Suggerimenti" sono stati veramente pochi.
La versione pubblicata l� � superata; a chi ne ha fatto richiesta, ho
inviato il nuovo generatore.
In ogni caso, a te non serve un simile generatore.
> Se non chiedo troppo, mi potreste spiegare effettivamente come
> funziona? In particolare la frase
> "Questo risultato viene raggiunto sfruttando adeguatamente i
> temporizzatori ad alta risoluzione presenti nei comuni personal
> computer con sistemi operativi Windows e CPU classe Pentium (ad es.
> Athlon), non sono quindi necessari componenti elettronici aggiuntivi."
> non mi � chiara.
Quanto dicevo � tutt'ora valido per sistemi con CPU single-core.
L'elevata entropia che il generatore accumula deriva dalla variabilit�
(imprevedibile) del tempo richiesto per leggere il temporizzatore ad alta
risoluzione (tramite l'istruzione QueryPerformanceCounter) o quello a bassa
risoluzione (il multimedia timer tramite timeGetTime).
Purtroppo, nei sistemi multi-core, l'istruzione QueryPerformanceCounter
viene "simulata" con la lettura del TSC (un registro interno alla CPU), per
cui si viene a perdere tutta l'entropia dell'accesso a basso livello
all'hardware.
Resta soltanto timeGetTime, ma la velocit� si riduce drasticamente. Del
resto, GePaHE � nato per essere un generatore ad alta entropia.
> Cosa sono effettivamente i temporizzatori? Perch� sono veramente
> casuali?
I temporizzatori non possono essere casuali (proprio perch� devono scandire
il tempo con una certa precisione), ma con opportuni accorgimenti �
possibile "estrarre" i bit d'entropia sufficienti a generare una sequenza
avente 1 bit d'entropia per ogni bit generato.
> Sarebbe possibile ottenere un'implementazione multipiattaforma, in
> particolare anche per i sistemi *nix oppure il gioco si basa in parte
> anche su funzioni intrinseche del sistema operativo Windows?
Se qualcuno mi dice passo per passo come si fa a compilare un programma C++
sotto Linux, posso fare una prova, ma Linux ha gi� il generatore di bit
casuali (almeno cos� dicono).
> E per finire: a quale rate costante si potrebbero generare numeri
> casuali?
Usando GePaHE con le impostazioni che uso io, ottengo circa 60 bit/s (!);
direi che non � proprio il massimo per le simulazioni di Montecarlo. :-)
> Ho notato che generalmente l'approccio prevalenete di chi
> studia/progetta codici Monte Carlo � quello di lasciare al compilatore
> l'onere di dare una buona funzione generatrice di numeri casuali,
> concentrandosi sulla fisica del sistema.
Fiducia che pu� rivelarsi molto mal riposta! :-)
> Questo approccio si � dimostrato nella pratica valido, anche se
> personalmente non riesco ad accettare completamente che una
> simulazione realistica possa fare affidamento su sequenze di numeri
> non veramente casuali.
Come ti dicevo, la casualit� dei numeri non � un requisito per una
simulazione di Montecarlo. E` invece richiesto un generatore avente un
periodo molto grande e possibilmente molto veloce e che, ovviamente, generi
sequenze con ottime propriet� statistiche.
Ciao
Cristiano redivivo (la Telecom, in appena 11 mesi, mi ha portato la linea
telefonica dentro casa e dopo appena altri 15 giorni mi ha anche attivato
l'ADSL!)
Cristiano
[...]
> In pratica non potrai mai esere "certo" che un set di numeri sia
> "casuale".
Questo � vero solo se non sai come sono stati generati i numeri.
Alcune grandezze fisiche sono generate da processi fisici intrinsecamente
imprevedibili(proprio per loro natura), per cui puoi essere certo che i
numeri generati da tali processi sono veramente casuali.
> In pratica basta che sia "sufficientemente" casuale, dove
> "sufficientemente"
> dipende dal contesto
E` gi� difficile definire il concetto di casualit�, figuriamoci il concetto
di "casualit� sufficiente in base al contesto"! :-)
Cristiano
Atreides
> Atreides wrote:
> [...]
>> In pratica non potrai mai esere "certo" che un set di numeri sia
>> "casuale".
>
> Questo � vero solo se non sai come sono stati generati i numeri.
> Alcune grandezze fisiche sono generate da processi fisici intrinsecamente
> imprevedibili(proprio per loro natura), per cui puoi essere certo che i
> numeri generati da tali processi sono veramente casuali.
No! Non puoi escludere a priori malfunzionamenti. I generatori hardware
hanno all'interno una routine che analizza continuamente il flusso e, a
livello di confidenza fissato, alzano un allarme in caso il test
fallisca. Nessuno ti puo' garantire che il costruttore del dispositivo
sia onesto. Ma sono discorsi inutili...non serve.
>
>> In pratica basta che sia "sufficientemente" casuale, dove
>> "sufficientemente"
>> dipende dal contesto
>
> E` gi� difficile definire il concetto di casualit�, figuriamoci il concetto
> di "casualit� sufficiente in base al contesto"! :-)
Questo dipende dal tuo livello di conoscenza, che no mi pare eccelso.
Dai discorsi mi pare di capire che non sia chiaro ne' cosa sia ne' a
cosa serva la simulazione di Montecarlo. Il solo fatto che si ponga una
attenzione esagerata sulla casualita' del seed lo dimostra. I problemi
sono altri....
>
> Cristiano
>
>
Cristiano
> Cristiano wrote:
>> Atreides wrote:
>> [...]
>>> In pratica non potrai mai esere "certo" che un set di numeri sia
>>> "casuale".
>>
>> Questo � vero solo se non sai come sono stati generati i numeri.
>> Alcune grandezze fisiche sono generate da processi fisici
>> intrinsecamente imprevedibili(proprio per loro natura), per cui puoi
>> essere certo che i numeri generati da tali processi sono veramente
>> casuali.
>
> No! Non puoi escludere a priori malfunzionamenti. I generatori
> hardware hanno all'interno una routine che analizza continuamente il
> flusso e, a livello di confidenza fissato, alzano un allarme in caso
> il test fallisca. Nessuno ti puo' garantire che il costruttore del
> dispositivo sia onesto.
Se il costruttore sono io, posso verificare di persona che il dispositivo
stia funzionando come previsto. Inoltre, � molto semplice costruirsi degli
ottimi e semplici generatori di bit casuali da interfacciare ad un PC o
sfruttare altri dispositivi interni al PC (scheda audio, hard disk, ecc). In
entrambi i casi, il malfunzionamento sarebbe vistoso.
In definitiva, in alcuni casi puoi essere certo della casualit� dei numeri,
mentre in altri, no.
E` sbagliato dire che "non potrai mai esere "certo" che un set di numeri sia
"casuale"".
>>> In pratica basta che sia "sufficientemente" casuale, dove
>>> "sufficientemente" dipende dal contesto
>>
>> E` gi� difficile definire il concetto di casualit�, figuriamoci il
>> concetto di "casualit� sufficiente in base al contesto"! :-)
>
> Questo dipende dal tuo livello di conoscenza, che no mi pare eccelso.
E` una tipica risposta da troll. Evita questo tipo di risposte, se ti �
possibile.
Volevo dire che non esiste una definizione univoca di "casuale".
"Sufficientemente casuale", invece, � una frase del tutto priva di senso.
Si potrebbe dire che il concetto di casualit� dipende dal contesto.
> Dai discorsi mi pare di capire che non sia chiaro ne' cosa sia ne' a
> cosa serva la simulazione di Montecarlo.
Ma questo � evidente per il semplice fatto che Lurkos stia chiedendo
chiarimenti e che l'abbia scritto proprio all'inizio del suo post: "Negli
ultimi giorni mi sono dovuto confrontare, per la prima volta a livello
scientifico/informatico, con i metodi Monte Carlo.", non serve che tu lo
sottolinei.
Tra l'altro, in questo thread, Lurkos � l'unico che ha scritto "Monte Carlo"
correttamente! :-)
Cristiano
Atreides
>> No! Non puoi escludere a priori malfunzionamenti. I generatori
>> hardware hanno all'interno una routine che analizza continuamente il
>> flusso e, a livello di confidenza fissato, alzano un allarme in caso
>> il test fallisca. Nessuno ti puo' garantire che il costruttore del
>> dispositivo sia onesto.
>
> Se il costruttore sono io, posso verificare di persona che il dispositivo
> stia funzionando come previsto. Inoltre, � molto semplice costruirsi degli
> ottimi e semplici generatori di bit casuali da interfacciare ad un PC o
> sfruttare altri dispositivi interni al PC (scheda audio, hard disk, ecc). In
> entrambi i casi, il malfunzionamento sarebbe vistoso.
Vistoso? Per nulla!! Documentati.
>
> In definitiva, in alcuni casi puoi essere certo della casualit� dei numeri,
> mentre in altri, no.
> E` sbagliato dire che "non potrai mai esere "certo" che un set di numeri sia
> "casuale"".
>
Che detto in altri termini vuol dire.
Posso essere certo che una sequenza finita di numeri razionali sia casuale.
Questa affermazione oltre che falsa rivela che non hai conoscenze in
merito. Non c'e modo di essere "certi" che una sequenza finita di numeri
sia casuale (trascurando speciose speculazioni teoriche inapplicabili in
pratica). La domanda in se' e' priva di senso. Credo che una ripassata
al concetto di test statistico sia doverosa. In pratica data una
sequenza dici
Posso accettare l'ipotesi di casualita' con un livello di confidenza del
100%
Questo non ha senso in statistica.
Poi si potrebbe discutere se un dato test statistico accettato come
ipotesi sia opportuno nel contesto. Ad esempio posso accettare (ad un
livello di confidenza dato) l'ipotesi di casualita' studiando la
distribuzione per verificare la sua uniformita'. Tuttavia nel contesto
del calcolo di integrali mutipli questo non basta. Ti lascio pensare da
solo al perche'....
>>>> In pratica basta che sia "sufficientemente" casuale, dove
>>>> "sufficientemente" dipende dal contesto
>>> E` gi� difficile definire il concetto di casualit�, figuriamoci il
>>> concetto di "casualit� sufficiente in base al contesto"! :-)
>> Questo dipende dal tuo livello di conoscenza, che no mi pare eccelso.
>
> E` una tipica risposta da troll. Evita questo tipo di risposte, se ti �
> possibile.
Tutte le volte che devi risolvere un problema stabilisci un
"protocollo". Ovvero un insieme di ipotesi e di parametri (il contesto)
nel quale muoverti. Non e' da troll e' pratica del mondo reale, che
credo tu non abbia in questo campo. Altrimenti non faresti certe
affermazioni. Quando applichi un test statistico devi definire un
livello di confidenza (un parametro del contesto). E se pensi di poter
sceglire il 100% sei fuori strada.
>
> Volevo dire che non esiste una definizione univoca di "casuale".
> "Sufficientemente casuale", invece, � una frase del tutto priva di senso.
> Si potrebbe dire che il concetto di casualit� dipende dal contesto.
Dipende dal contesto quale livello di confidenza per accettare l'ipotesi
di casualita' sia opportuno' E' parte del "protocollo" di gestione del
test statistico. Non puoi dire "e' casuale!". Non ha senso. In
statistica i test (non solo di casualita') "dipendono" dal livello di
confidenza scelto. la statistica e' "scienza esatta" non perche' posso
essere "certo" di qualcosa, ma perche' posso stimare la probabilita' di
accettare l'ipotesi errata (o rigettare l'ipotesi giusta).
Cristiano
> Cristiano wrote:
>
>>> No! Non puoi escludere a priori malfunzionamenti. I generatori
>>> hardware hanno all'interno una routine che analizza continuamente il
>>> flusso e, a livello di confidenza fissato, alzano un allarme in caso
>>> il test fallisca. Nessuno ti puo' garantire che il costruttore del
>>> dispositivo sia onesto.
>>
>> Se il costruttore sono io, posso verificare di persona che il
>> dispositivo stia funzionando come previsto. Inoltre, � molto
>> semplice costruirsi degli ottimi e semplici generatori di bit
>> casuali da interfacciare ad un PC o sfruttare altri dispositivi
>> interni al PC (scheda audio, hard disk, ecc). In entrambi i casi, il
>> malfunzionamento sarebbe vistoso.
>
> Vistoso? Per nulla!! Documentati.
Mi documento su cosa? Su come si comporta un transistor o un integrato
bruciato? Su un PC con la scheda audio che non funziona?
>> In definitiva, in alcuni casi puoi essere certo della casualit� dei
>> numeri, mentre in altri, no.
>> E` sbagliato dire che "non potrai mai esere "certo" che un set di
>> numeri sia "casuale"".
>>
>
> Che detto in altri termini vuol dire.
>
> Posso essere certo che una sequenza finita di numeri razionali sia
> casuale.
> Questa affermazione oltre che falsa rivela che non hai conoscenze in
> merito. Non c'e modo di essere "certi" che una sequenza finita di
> numeri sia casuale (trascurando speciose speculazioni teoriche
> inapplicabili in pratica).
A te mancano proprio le basi! Ti ho gi� detto che sfruttando opportunamente
alcuni fenomeni fisici, si pu� essere *certi* che i bit generati siano
casuali.
Se poi continui a dire che il dispositivo *potrebbe* non funzionare, io
continuo a dirti che puoi rilevare in modo banale il malfunzionamento.
> La domanda in se' e' priva di senso.
Quale domanda?!
> Credo che una ripassata al concetto di test statistico sia doverosa. In
> pratica data una
> sequenza dici
>
> Posso accettare l'ipotesi di casualita' con un livello di confidenza
> del 100%
No, non lo direi mai, lo stai dicendo tu.
> Poi si potrebbe discutere se un dato test statistico accettato come
> ipotesi sia opportuno nel contesto. Ad esempio posso accettare (ad un
> livello di confidenza dato) l'ipotesi di casualita' studiando la
> distribuzione per verificare la sua uniformita'.
Qui si vedono le tue lacune.
La distribuzione (immagino dei numeri in uscita dal generatore) non ha
niente a che vedere con la casualit�.
Molte grandezze fisiche hanno distribuzioni normali o esponenziali, ma non
per questo non sono casuali.
Nel nostro caso (in crittografia) la distribuzione voluta � quella uniforme.
Quindi � necessario interporre un "filtro" prima dell'uscita del generatore,
proprio per trasformare la grandezza fisica in ingresso (qualunque
distribuzione essa abbia), in modo che abbia una distribuzione uniforme.
> Tuttavia nel contesto
> del calcolo di integrali mutipli questo non basta. Ti lascio pensare
> da solo al perche'....
Ci penser� stanotte nel letto.
>>>>> In pratica basta che sia "sufficientemente" casuale, dove
>>>>> "sufficientemente" dipende dal contesto
>>>> E` gi� difficile definire il concetto di casualit�, figuriamoci il
>>>> concetto di "casualit� sufficiente in base al contesto"! :-)
>>> Questo dipende dal tuo livello di conoscenza, che no mi pare
>>> eccelso.
>>
>> E` una tipica risposta da troll. Evita questo tipo di risposte, se
>> ti � possibile.
>
> Tutte le volte che devi risolvere un problema stabilisci un
> "protocollo". Ovvero un insieme di ipotesi e di parametri (il
> contesto) nel quale muoverti. Non e' da troll e' pratica del mondo
> reale che credo tu non abbia in questo campo. Altrimenti non faresti certe
> affermazioni.
Non dicevo che stabilire un "protocollo" � da troll, dicevo che la tua
risposta lo era e anche questa continua ad esserlo.
> Quando applichi un test statistico devi definire un
> livello di confidenza (un parametro del contesto).
> E se pensi di poter sceglire il 100% sei fuori strada.
Lo stai ancora dicendo tu, io non l'ho mai detto.
>> Volevo dire che non esiste una definizione univoca di "casuale".
>> "Sufficientemente casuale", invece, � una frase del tutto priva di
>> senso. Si potrebbe dire che il concetto di casualit� dipende dal
>> contesto.
>
> Dipende dal contesto quale livello di confidenza per accettare
> l'ipotesi di casualita' sia opportuno' E' parte del "protocollo" di
> gestione del test statistico. Non puoi dire "e' casuale!". Non ha
> senso.
Continui a parlare di test statistici, ma qui si stava parlando di
casualit�.
Secondo me hai le idee piuttosto confuse, ma quel che � peggio � che non
sembri aperto al dialogo costruttivo.
PLONK
Cristiano
Atreides
> Atreides wrote:
>> Cristiano wrote:
In entrambi i casi, il
>>> malfunzionamento sarebbe vistoso.
>> Vistoso? Per nulla!! Documentati.
>
> Mi documento su cosa? Su come si comporta un transistor o un integrato
> bruciato? Su un PC con la scheda audio che non funziona?
>
No, su come funziona un generatore hardware. Credo che tu non ne abbia
mai visto uno. Documentati ad esempio su HotBit, scoprirai che il test
sui numeri generati e' complesso e i problemi non sono affatto vistosi.
(cfr. DieHard, NIST, )
Non capisci che il fatto che il principio fisico sottostante puo' essere
intrinsecamente casuale (come il decadimento radioativo) ma la macchina
e' macroscopica e puo' avere problemi legati all'implementazione del suo
progetto (biasing....) davvero documentati, magari anche su come
funzionano i transistor...non vorrei che credessi che il rumore bianco
perfetto esiste davvero.
> A te mancano proprio le basi! Ti ho gi� detto che sfruttando opportunamente
> alcuni fenomeni fisici, si pu� essere *certi* che i bit generati siano
> casuali.
Agh.. dimenticavo che sei l'insigne statistico che su sci.stat.math a
provato a farsi risolvere il compito a casa ...(sia data un urna con
palle bianche e nere...) veramente ilare. Perhe' non smetti di simulare
(che a leggere i newsgroup sembra non ti riescano mai) e provi ad usare
il computer che hai tra le orecchie?
Su sci.stat.math hanno provato a spiegarti il concetto di
Significance level of a simulation ma senza successo.
******
Luis A. Afonso
View profile
More options Aug 15 2005, 1:28 pm
Newsgroups: sci.stat.math
From: "\"Luis A. Afonso\"" <lic...@hotmail.com>
Date: Mon, 15 Aug 2005 07:28:46 EDT
Local: Mon, Aug 15 2005 1:28 pm
Subject: Re: Significance level of a simulation
Reply to author | Forward | Print | Individual message | Show original |
Report this message | Find messages by this author
Critiano says
< I know the statistic parameters that characterize a process
< When I simulate the process, I see low and high
< p-values, so that H0 sometimes is rejected and sometimes < H0 is not
rejected. Is there a way to get a decisive
< answer? Thanks Cristiano
My response
Without further details nobody can help you.
*******
C'e' un modo di avere una risposta decisiva!!!!!??????!!!!!
Proprio non capisci! Forse e' troppo complicato.
>>
>> Posso accettare l'ipotesi di casualita' con un livello di confidenza
>> del 100%
>
> No, non lo direi mai, lo stai dicendo tu.
hai affermato che puoi stabilire con certezza che un sequenza prodotta
da un generatore (hw o sw) sia casuale. L'affermazione e' equivalente.
>
>> Poi si potrebbe discutere se un dato test statistico accettato come
>> ipotesi sia opportuno nel contesto. Ad esempio posso accettare (ad un
>> livello di confidenza dato) l'ipotesi di casualita' studiando la
>> distribuzione per verificare la sua uniformita'.
>
> Qui si vedono le tue lacune.
> La distribuzione (immagino dei numeri in uscita dal generatore) non ha
> niente a che vedere con la casualit�.
> Molte grandezze fisiche hanno distribuzioni normali o esponenziali, ma non
> per questo non sono casuali.
Era un esempio! Prova a rileggere. Posso dire
"Ad esempio posso accettare (ad un
livello di confidenza dato) l'ipotesi di casualita' di un generatore di
numeri con distribuzione normale studiando la
distribuzione per verificare la sua normalita'"
E' un altro esempio!!
> Nel nostro caso (in crittografia) la distribuzione voluta � quella uniforme.
> Quindi � necessario interporre un "filtro" prima dell'uscita del generatore,
> proprio per trasformare la grandezza fisica in ingresso (qualunque
> distribuzione essa abbia), in modo che abbia una distribuzione uniforme.
>
>> Tuttavia nel contesto
>> del calcolo di integrali mutipli questo non basta. Ti lascio pensare
>> da solo al perche'....
>
> Ci penser� stanotte nel letto.
>
No credo basti. Bisogna capire non simulare.
> Continui a parlare di test statistici, ma qui si stava parlando di
> casualit�.
> Secondo me hai le idee piuttosto confuse, ma quel che � peggio � che non
> sembri aperto al dialogo costruttivo.
Si parlava della non necessita' di una sequenza casuale nel metodo di
Monte-Carlo. Poi del fatto che e' comunque impossibile dimostrare con
certezza l'ipotesi di casualita'. Poi sei intervenuto (per spararti una
posa e fare la figura di esperto ) dicendo che era possibile con
"certezza" stabilirlo. Questo e' un test statistico.
Non ho interesse a discutere in modo costruttivo con te solo a non
propagare la tua ignoranza (ma e' un interesse relativo).
Quindi ora o posti un algoritmo che data una sequenza di numeri e' in
grado di certificare con "certezza" la sua casualita' o ammetti di aver
fatto una affermazione erronea..o taci che e' meglio
(nota come ti hanno fatto notare su sci.stat.math il tuo RaBiGeTe e' una
scopiazzatura di parti di Knuth, NIST tests e Diehard. Ti hanno anche
detto che e' roba vecchia..quindi non postarmi quella.)
Invece di simulare scaricati
An Introduction to Probability and Random Processes
by Gian-Carlo Rota, Kenneth Baclawski , 1979
Elementary Practical Statistics
by A. L. O'Toole - The MacMillan Company , 1964
Non-Uniform Random Variate Generation
by Luc Devroye - Springer , 1986
e studiali. Poi ti mando quelli seri.