Molto probabilmente, se capitate da queste parti, avrete sentito parlare di Metodi Monte Carlo o di sequenze pseudorandom. Nel mio caso si è trattato di un incontro fortuito quando studiavo ancora al primo anno delle superiori (se non addirittura in terza media): la sensazione fu di perplessità (anzi, di buio totale): cosa diavolo potevano avere a che fare dei numeri random con la sicurezza informatica? E soprattutto come mai un capitolone di più di 50 pagine di un libro su questo argomento veniva dedicato a come creare numeri casuali? La risposta, o meglio le risposte, sono arrivate piano piano, con il proseguire degli studi e forse è il momento di mettere un po’ in ordine le idee.
Anzitutto, perchè generare numeri casuali? La domanda è già di per se formulata male: i numeri infatti non sono casuali: può essere casuale una loro sequenza, tuttavia per comodità si utilizza, anche in testi tecnici questa espressione. Numeri casuali o numeri random: non sembrano nulla di complicato, si tratta di sequenze di numeri non correlati fra di loro. Si possono costruire abbastanza facilmente: basta lanciare un dado, far girare una roulette o tirare una moneta. Intuitivamente si potrebbe pensare di farlo anche a mente, inventando numeri a caso: in merito a questa possibilità vi sono studi contrastanti. Alcune ricerche, sicuramente meno aggiornate, sostengono l’ipotesi che non siamo veramente in grado di generare sequenze di numeri casuali: compaiono una serie di pattern abbastanza naif tra cui una netta predominanza di numeri dispari e l’assoluta assenza di numeri consecutivi (che nelle sequenze veramente casuali compaiono, seppur raramente). Altri studi più recenti, ma meno confermati, sembrano dar credito all’idea opposta: i numeri generati a ruota libera dai campioni di persone studiati hanno superato tutti i test di casualità (in seguito vedremo di cosa si tratta).
da sinistra: Stan Ulam, Richard Feynman e John Von Neumann
In ogni caso, di fronte alle esigenze pratiche, l’obiettivo è quello di far produrre ad un computer sequenze di numeri casuali, così da avere sequenze molto grandi. E la domanda da un milione di dollari è: perchè?
Le applicazioni sono in realtà talmente tante che non so da dove cominciare. Tra i primi ad avere l’idea di utilizzare numeri casuali per ricerche scientifiche troviamo Enrico Fermi, uno dei più illustri fisici italiani, nel 1930 che pensò di usarli per simulare fenomeni nucleari, in particolare la diffusione casuale di neutroni. (In effetti,uno dei migliori generatori di numeri random è un campione di un materiale che decade, perciò non c’è da stupirsi che le sequenze casuali trovino applicazioni in fisica nucleare e subnucleare!) Sempre in ambito nucleare se ne occuparono John Von Neumann e Stanislaw Ulam, nei laboratori di Los Alamos. In generale in ambito scientifico, i metodi Monte Carlo (il nome deriva dalla denominazione in codice utilizzata durante il Progetto Manhattan) vengono utilizzati per simulare un fenomeno fisico (ad esempio il comportamento delle molecole in un gas, il comportamento del traffico su una strada, etc…), ma anche per confrontare i dati di una misura e le conclusioni da essi tratte con dei dati casuali (effettuando in questo modo un test denominato proprio Metodo Monte Carlo).
Le applicazioni non si fermano qui: la generazione di numeri casuali può essere utilizzata anche per il calcolo di integrali definiti, spesso multidimensionali ,(si veda l’esempio nella figura), ma anche per la grafica computerizzata, la crittografia (le chiavi dovrebbero essere il più casuale possibile in modo che sia molto difficle riprodurle), le analisi di borsa, le simulazioni dei giochi d’azzardo,etc…
Ecco un esempio di integrazione con Metodo Monte Carlo per calcolare il valore di pi. Si estraggono n coppie di numeri casuali all'interno del quadrato e si calcola il rapporto tra i punti interni alla circonferenza e quelli totali. Tramite questo rapporto si può calcolare facilmente il valore di pi.
In questo grafico si può vedere come il valore del rapporto tra i punti interni e quelli totali converga al crescere del numero di prove
In tutti questi ambiti le sequenze è bene che siano molto lunghe in modo da poter fare simulazioni più corpose e analisi più affidabili: per questa ragione utilizzare un calcolatore è l’ideale. E qui sorge un grosso problema: il computer è una macchina che esegue istruzioni codificate, come è possibile che generi numeri casuali? Effettivamente, nel caso di sequenze che vengono prodotte da un computer si parla di numeri pseudo-casuali o pseudo-random. Tali sequenze vengono generate da algoritmi i cui risultati, però, riescono a superare una serie di test che verificano, ad esempio, che i numeri generati all’interno della stessa sequenza non siano tra loro correlati. Di questo tipo di algoritmi ne sono stati proposti molti: uno dei primi è il Middle Square (proposto da Von Neumann nel 1946), il quale è piuttosto semplice e si presta bene per fare un esempio.
Middle Square, come tutti i generatori di numeri pseudo-random che conosco, richiede all’utente di inserire un seed, vale a dire un numero da cui partire per il calcolo. Di questo numero (il primo della sequenza) di, supponiamo, 6 cifre, computa il quadrato e il termine successivo della sequenza è rappresentato dalle 6 cifre centrali del quadrato calcolato. E così via…Non è nulla di complicato da descrivere, ma non è un buon algoritmo (perlomeno non lo è più) in quanto è possibile entrare in loop periodici e per essere vagamente valido il numero di cifre che deve avere ogni numero deve essere piuttosto alto.
I metodi più noti sono quelli appartenenti alla categoria dei metodi lineari congruenti (proposti da Lehmer nel 1948) abbreviati LCG. Questi metodi richiedono un seed per costruire una sequenza secondo questa regola:
xn+1 = (a xn + c) mod m, n≥0,
Dove a, c ed m sono numeri interi. Il problema di questo metodo consiste nel fatto che la scelta dei parametri è cruciale ed è molto difficile prevedere quali siano le conseguenze della scelta di un particolare set di parametri. E’ stato inoltre dimostrato che si presentano particolari correlazioni: in particolare tutti i numeri di una sequenza tendono a disporsi su iperpiano di dimensione collegata alla scelta di m. In realtà questo tipo di generatori viene comunque utilizzato, ma non per simulazioni di esperimenti fisici o per applicazioni crittografiche (proprio a causa di queste correlazioni).
In questa animazione è rappresentata la generazione di numeri casuali con un algoritmo di tipo LCG. Si può osservare che all'aumentare dei numeri generati questi tendono a disporsi su un piano.
Ma allora cosa si utilizza per le simulazioni di esperimenti? In realtà ogni framework di analisi dati ha fatto le sue scelte (e spesso ne offrono all’utente anche più di una). Tuttavia al momento lo strumento migliore a disposizione di chi vuole generare numeri casuali è l’algoritmo Mersenne Twister presentato nel 1997 da M. Matsumoto and T. Nishimura il quale consiste in una variante dei generatori LCG, ma che non presenta la criticità legata alla disposizione su iperpiani e ha superato tutti i più severi test di casualità.
Commenti recenti