fulltext

(1)

PER SAPERNE DI PI `

U

Il metodo Monte Carlo di Metropolis

The Metropolis Monte Carlo method

Giovanni Ciccotti

Istituto per le Applicazioni del Calcolo “Mauro Picone” IAC-CNR, Roma, Italia Dipartimento di Fisica, Universit`a di Roma “La Sapienza”, Roma, Italia School of Physics, University College Dublin (UCD), Dublin, Ireland Mauro Ferrario

Dipartimento di Scienze Fisiche, Informatiche e Matematiche, Universit`a di Modena e Reggio Emilia, Modena, Italy

Riassunto. Con metodo Monte Carlo si indica un insieme di metodi computazio-nali di vastissima applicazione in fisica e in tutte le discipline che abbiano bisogno di calcoli intensivi. In questo articolo presentiamo l’algoritmo di Metropolis che, introdotto nel 1953 da Rosenbluth e collaboratori, è risultato lo strumento più potente della Fisica Teorica Computazionale.

Abstract. Monte Carlo method refers to a set of computational methods of ve-ry wide application in physics and in all disciplines needing intensive computa-tion. In this paper we present the Metropolis algorithm, introduced in 1953 by Rosenbluth and collaborators. It is the most powerful tool of Computational Theoretical Physics.

1. Introduzione

Alla fine della seconda guerra mondiale la disponibilità dei primi calcolatori elet-tronici diede un impulso fondamentale allo sviluppo di metodi numerici basati sulla Meccanica Statistica, in particolare all’approccio oggi noto come metodo Monte Car-lo [1]. Sono legati a Stan Ulam [2] sia il nome, che deriva dall’uso massiccio di numeri aleatori, sia l’idea di base che in molte situazioni complesse non fosse neces-sario considerare tutte le possibili traiettorie (dinamiche) ma soltanto analizzare un loro campione statistico (sufficientemente grande). L’utilizzo del caso per esperimenti modello era già utilizzato all’inizio del dicianovesimo secolo. In Italia il matematico M. Lazzarini, utilizzando un teorema del grande naturalista francese Buffon, trovò una stima del valore di pigreco, π = 3.1415929, corretta alla sesta cifra decimale, con un campione di 3408 eventi random [3] in un pomeriggio “fortunato” [4]; in Gran

(2)

Bretagna [5] lo statistico W. S. Gosset, stimò i coefficienti di correlazione della sua distribuzione t di Student con un esperimento di campionamento casuale e il fisico W. Thomson (Lord Kelvin) studiava gli urti elastici facendo generare campioni di 5000 traiettorie. Ma fu soltanto nel 1945 che grazie alle intuizioni di Ulam e von Neumann [6], stimolati da Fermi che già sperimentava soluzioni numeriche di tipo probabilistico al problema della diffusione di neutroni in materiale fissile con calcola-trici elettro-meccaniche e macchine geometriche ad hoc [7], fu possibile generalizzare la produzione di numeri aleatori al computer per generare qualsivoglia esperimento di campionamento stocastico [8].

Se il metodo Monte Carlo [9–12] è cresciuto nel tempo fino a diventare “la tecni-ca più potente e più comunemente utilizzata per analizzare problemi complessi” [13] lo si deve in gran parte al successo del cosiddetto “algoritmo di Metropolis”, che risolve, in modo elegante ma soprattutto semplice, il problema di come guidare il campionamento aleatorio conoscendo soltanto il punto di partenza (condizione ini-ziale microscopica) e il punto di arrivo (la distribuzione stazionaria o di equilibrio). Questa procedura di “campionamento per importanza” è stata formalizzata nel fon-damentale lavoro di Metropolis, Rosenbluth, Rosenbluth, Teller e Teller [14], in cui un ruolo fondamentale spetta all’idea, dovuta originalmente a von Neumann [6], di accettare/rigettare eventi (numeri) generati aleatoriamente secondo una data regola matematica in modo da campionare (efficientemente) una desiderata distribuzione di probabilità. Può essere curioso ricordare qui come soltanto recentemente, nel 2003 in occasione del cinquantenario della pubblicazione dell’articolo, sia stato chiarito come Metropolis stesso, nello sviluppo dell’algoritmo che da lui prende il nome, abbia avuto fondamentalmente solo il ruolo di costruire il computer che rese possibile realizzare i calcoli [15].

Partiamo dal metodo Monte Carlo introdotto originalmente da S. Ulam e N. Me-tropolis [1] come algoritmo computazionale che usa campionamenti statistici per realizzare calcoli analitici standard. Prendiamo il caso di un integrale deﬁnito multidimensionale di una funzione molto regolare

(1)

S⊂Rn

f (x1· · · · xn) dxn.

Chiamando μ(S) il volume associato all’ipercubo S ≡ ({0 ≤ xi ≤ 1}, i = 1, n) e supponendo di saper estrarre numeri casuali uniformi fra zero e uno, noi possiamo riscrivere l’integrale come

(2) μ(S) S⊂Rn f (x1· · · · xn) dxn μ(S)= μ(S)fU

e dunque interpretarlo come la misura del dominio di integrazione (in questo caso giu-sto 1) per quello che gli statistici chiamano il valore atteso di f (x) sulla distribuzione

(3)

uniforme della variabile casuale vettoriale x≡ (x1· · · · xn) distribuita con densit`a di

probabilit`a uniforme

(3) P (x1· · · · xn) =

1 μ(S).

La legge dei grandi numeri della probabilit`a ci dice allora che se abbiamo un campione suﬃcientemente grande di x distribuito secondo la (3),

(4) fU = lim M→∞ 1 M M i=1 f x(i)₁ · · · · x(i)n ∼ = 1 M M i=1 f x(i)₁ · · · · x(i)n ,

per M abbastanza grande. Questo procedimento `e affidabile per integrandi molto regolari ma fallisce se la funzione f (x) integranda presenta importanti irregolarit`a. Questa difficoltà può essere aggirata se le irregolarit`a della funzione f (x) possono essere isolate e f (x) pu`o essere riscritta come il prodotto di una funzione irregolare g(x), ma positiva e normalizzabile, per una funzione regolare ϕ(x):

(5) f (x1· · · · xn) = g (x1· · · · xn)· ϕ (x1· · · · xn) .

Questo permette di interpretare

(6) P (x1· · · · xn) =

g(x 1· · · · xn)

g(x) dxn =

g(x1· · · · xn)

N come una densit`a di probabilit`a e di riscrivere la funzione come (7) f (x1· · · · xn) =N P (x1· · · · xn) ϕ (x1· · · · xn) ,

doveN è una costante da calcolare a parte. In questo caso si può generalizzare il me-todo Monte Carlo risolvendo il problema di generare un campione distribuito secondo una legge di probabilità P(x) con quello che viene chiamato il metodo Monte Carlo di Metropolis che ora intendiamo introdurre.

Consideriamo dunque integrali multidimensionali del tipo

(8) I =

V

P(x1· · · · xn) ϕ(x1· · · · xn) dxn≡ ϕ

cioè valori attesi in base ad una densità di probabilitàP(x) normalizzata sul dominio V , _V P(x) dxn _{= 1. Se, come supposto, la parte} _{P è molto irregolare (grande in} certe regioni, quasi zero in altre), allora il campionamento uniforme diventa molto inefficiente e occorre poter ottenere un campione di M punti distribuiti secondo la

(4)

densità di probabilità P(x), x ∈ V . Dopodichè, di nuovo, la stima del valore di aspettazione si ottiene dalla media aritmetica

(9) I = ϕ ≈ 1 M M i=1 ϕ x(i)₁ · · · · x(i)_n . `

E questo il caso risolto dal metodo detto Monte Carlo di Metropolis [14, 16]. Il metodo deﬁnisce un algoritmo di applicazione generale che permette di campionare il dominio V direttamente secondo la legge di probabilitaP(x).

2. Generazione di numeri aleatori

Per cominciare osserviamo che alla base del metodo Monte Carlo c’è la possibilità di generare con un computer numeri casuali a partire da una legge di probabilità uniforme. Anche se può sembrare a prima vista strano, i moderni elaboratori elettro-nici sono particolarmente adatti allo scopo: possono generare estremamente grandi campioni di numeri aleatori (in realtà, pseudorandom) uniformemente distribuiti in un intervallo finito, tipicamente il segmento unitario dell’asse reale.

Considerando il caso unidimensionale per semplicit`a, realizzare un campionamento signiﬁca produrre un campione{y1, y2, y3, . . .} di numeri reali uniformi nell’intervallo

0≤ y < 1 (1_).

Questo può essere ottenuto su un calcolatore con l’algoritmo seguente, che prende la parte meno significativa di una moltiplicazione tra numeri grandi. Consideriamo una macchina che lavora su “parole” di 32 bit, cioè su un insieme equivalente di 232 numeri naturali, esattamente tutti quelli nell’intervallo semiaperto [0, 232_{). Scriviamo}

la formula di ricorrenza

(10) xj+1= xj· R0 mod 232, j = 0, 1, . . . ,

dove R0`e un numero complicato e x0, il primo elemento della successione, `e anch’esso

un numero complicato (ad esempio R0= 513 e x0= 103, un numero primo),

l’opera-zione modulo indica il resto intero della divisione di R0· xj per 232. La successione

degli xj è costituita da numeri naturali compresi tra 0 e (232− 1) senza regolarità evidente e che soddisfano tutti i test di causalità (media, varianza, . . . ) che si pos-sano immaginare. Basta normalizzare il resto della divisione di xj per 232, yj = (xj mod 232_)/232_{, per ottenere il campione casuale che si cercava nell’intervallo [0, 1). Si}

sono cos`ı generati i numeri cosiddetti pseudoaleatori. In effetti, questi anche se nella sequenza si distribuiscono con probabilità uniforme, come richiesto, in realtà proven-gono da una procedura di generazione che rimane deterministica: data la dimensione

(1_{) L’esclusione del valore 1 `}_{e legata alla procedura speciﬁca che utilizza l’operazione algebrica} modulo. Questa da come risultato il resto della divisione tra due numeri naturali e quindi identiﬁca

(5)

Fig. 1. – Istogramma (normalizzato) di una sequenza di numeri random generati con (10). La linea blu rappresenta la distribuzione uniforme P (x) = 1. Il confronto tra il risultato su un campione di 100mila punti, in rosso, con quello su un campione di 10mila, in verde, mostra come le ﬂuttuazioni legate alla grandezza del campione diminuiscono con l’aumentare della dimensione della sequenza, in accordo con la legge dei grandi numeri.

ﬁnita dello spazio campione (232_{) la successione ad un certo punto presenter`}_a

sicura-mente delle ricorrenze, al pi`u tardi dopo 232 _{iterazioni. Il difetto di questo algoritmo}

`

e che in presenza di una ricorrenza yj = yk con j > k ≥ 0 la successione ripeterà esattamente la sequenza gi`a estratta: yj+1= yk+1, yj+2= yk+2, . . .. Tuttavia, in as-senza di ricorrenze, essi forniscono, per tutti gli scopi pratici, un campione di numeri aleatori, distribuiti uniformemente, con densità di probabilit`a P (y) = 1, nell’interval-lo y∈ [0, 1). Ci si può convincere di ciò guardando (fig. 1) la stima della distribuzione ottenuta calcolando l’istogramma della frequenza dei valori estratti da un campione di 104 _{e uno di 10}5 _valori.

Con algoritmi per la generazione di numeri random appena più complessi di quello presentato, il problema della ricorrenza è stato, a tutti gli effetti pratici, superato. Ad esempio un generatore di numeri random, attualmente molto utilizzato, denominato Mersenne Twister (MT19937) [17] utilizza una generalizzazione della (10) in cui un nuovo valore viene generato come combinazione lineare dei 623 valori precedenti, ottenendo un periodo di ricorrenza record, pari a 219937_{− 1 (cioè circa 10}6000_{, basta}

(6)

In una dimensione, partendo da numeri pseudorandom generati uniformemente nell’intervallo [0, 1) è anche possibile costruire numeri pseudorandom x distribuiti secondo una desiderata probabilità P(x) in un dato intervallo [a, b] utilizzando un teorema matematico noto come legge di trasformazione delle probabilità [6]. Questa procedura è però esponenzialmente più costosa al crescere della dimensione e non è più realizzabile nei casi multidimensionali di interesse come il calcolo dell’integrale in (8) per n appena grande dove, invece, il metodo Monte Carlo di Metropolis eccelle. 3. Catene di Markov

Consideriamo ora un problema pi`u generale. Pensiamo di campionare non una variabile casuale vettoriale X (2

) ma una successione discreta X1, X2, . . . , Xmdi

va-riabili casuali identiche. Per semplicit`a consideriamo variabili casuali che possono assumere solo valori discreti (stati) che immaginiamo di numerare progressivamente e identiﬁcare con un numero naturale j = 1, 2, 3, . . . (cos`ı come si fa quando si asso-ciano le facce di un dado con gli interi da 1 a 6. Il caso continuo si riduce a questo sostituendo, per ogni dimensione della variabile X, all’insieme continuo dei valori un set discreto di intervallini rappresentati, per esempio, dai loro valori centrali).

La probabilit`a di una determinata sequenza X1 = j1, X2 = j2, . . . , Xm = jm pu`o essere costruita immaginando di eseguire una successione ordinata di prove sulle singole variabili casuali. Dette

• p1(j1) = P (X1= j1) la probabilit`a di avere ottenuto come esito della prima prova

lo stato j1;

• p2(j2 | j1) = P (X2 = j2 | X1 = j1) la probabilit`a condizionata di avere ottenuto

nella seconda prova j2 dato che la prima prova ha dato come esito j1;

• p3(j3 | j2 j1) = P (X3 = j3 | X2 = j2 e X1 = j1) la probabilit`a condizionata di

avere ottenuto nella terza prova j3dato che la prima prova ha dato come esito j1

e la seconda prova j2;

• . . .

• pm(jm| jm−1. . . j1) = P (Xm= jm| Xm−1 = jm−1e . . . e X1= j1) la probabilit`a

condizionata di avere ottenuto nella m-esima prova jm dato che la prima prova ha dato come esito j1, . . . e la (m− 1)-esima prova jm−1;

la probabilit`a congiunta P(j1j2. . . jm) di uscita di una certa sequenza di lunghezza

m, X1 = j1, X2 = j2, . . . , Xm = jm, diventa, in generale, in termini di p1 e delle

probabilit`a condizionate p2, p3, . . . successive

(11) P (j1j2. . . jm) = p1(j1) p2(j2| j1) p3(j3| j2j1) . . . pm(jm| jm−1. . . j1) .

Una sequenza di numeri random generata al calcolatore con l’algoritmo discusso nella precedente sezione si pu`o considerare come un campione di una successione di varia-bili casuali indipendenti, ovverossia come una successione di prove indipendenti che

(2_{) I “valori” di X}_{≡ (x}

(7)

associa alle possibili uscite successive sempre la stessa probabilità: ogni numero è un valore estratto con probabilità uniforme dallo stesso insieme discreto (232 _valori,

l’esito di ciascuna prova è agli effetti statistici indipendente da tutti i precedenti). De-nominata πj1 = p1(j1) la probabilit`a di uscita del valore j1, indipendenza significa che

p2(j2 | j1) = p1(j2) = πj2, p3(j3 | j2j1) = p1(j3) = πj3, . . . e cos`ı via: la probabilit`a

della sequenza, di lunghezza m, `e data semplicemente dal prodotto delle probabilit`a dei singoli m stati

(12) P(j1j2. . . jm−1jm) = πj1πj2 · · · πjm−1πjm

ed `e suﬃciente conoscere la probabilit`a della singola prova πk= p1(k) per descrivere

statisticamente sequenze di lunghezza m arbitraria.

Con estrazioni indipendenti la probabilità della singola prova non cambia e se prendiamo πk uniforme la probabilità congiunta (12) è esattamente quella associata al calcolo dell’integrale con il metodo Monte Carlo diretto, cioè utilizzando la stima (4). Questo approccio è però inefficiente nei veri casi di interesse e quindi vogliamo passare ad un caso più generale. Immaginiamo di scandire la successione ordinata con un tempio fittizio (discreto) τ , la prima prova corrisponde all’istante iniziale τ = 0, la seconda prova al tempo τ = 1, e cos`ı via. Data a(0)_k = P(k, 0) la probabilit`a di avere come esito il valore k all’istante iniziale τ = 0, la probabilità a(m)_jm = P(jm, m), di avere come esito il valore jmal tempo τ = m (nb: (m + 1)-esima prova), `e data dalla somma su tutti i tempi intermedi

(13) a(m)_jm = k j1 · · · jm−1 a(0)_k p2(j1| k) p3(j2| j1k) . . . pm+1(jm| jm−1. . . j1k)

e può cambiare da prova a prova. Il caso più semplice è dato da una catena di Markov (vedi di seguito) e vedremo che è sufficiente per i nostri scopi.

Le successioni, note come “Catene di Markov” stazionarie (3

), sono quelle in cui le variabili casuali della successione non sono indipendenti ma hanno la proprietà che l’esito della k-esima prova dipende dall’esito della prova (k− 1)-esima, direttamente precedente, e solo da essa, cioè dalla probabilità condizionata

p2(jk| jk−1) = wjkjk−1, (14)

(8)

La probabilit`a delle sequenze campionarie corrispondenti ai tempi successivi τ = 1, 2, . . . , m sono deﬁnite da P(j0j1) = a(0)j0 wj0j1, (15) P(j0j1j2) = a(0)j0 wj0j1wj1j2, . . . P(j0j1. . . jm) = a(0)j0 wj0j1wj1j2· · · wjm−1jm.

Una successione di prove con esiti j0, j1, . . . , jm`e detta catena di Markov se le

proba-bilit`a delle successioni campionarie sono deﬁnite da (15) in termini della condizione iniziale data dal vettore di probabilit`a (A)j ≡ (a(0)j ) alla prima prova e della matrice

W delle probabilit`a condizionate, o matrice di transizione, con elementi (W)kj≡ wkj nelle prove successive. W ha elementi positivi o nulli e _jwkj= 1. Una tale matrice si dice matrice stocastica.

Indicando con w(m)_kj la probabilit`a di una “transizione” dal valore k-esimo al valore j-esimo in m passi, si ha w(1)_kj = wkj, (16) w_kj(m+1) = ν wkνw_νj(m)= ν1 ν2 · · · νm−1 wkν1wν1ν2· · · wνm−1j, . . . w_kj(m+) = ν w()_kνw(m)_νj .

In termini matriciali W(m+1)_{= (W)}m+1_{= W}_{· W}m_{e (W)}m+_{= W}_{· W}(m)_{, dove}

“·” indica il classico prodotto matriciale righe per colonne.

Se a(0)_k `e la probabilit`a dello stato k all’inizio delle prove, la probabilit`a di avere come esito lo stato j all’m-esimo passo `e data da

(17) a(m)_j =

k

a(0)_k w_kj(m).

In particolare se a(0)_k = δα k (si inizia sempre con dato valore, α) al passo m-esimo si avr`a a(m)_j = w_αj(m). Ciò che ci si aspetta `e che al crescere di m diminuisca la dipendenza dalla scelta iniziale del valore α-esimo. Questa aspettativa risulta confermata, sotto certe condizioni, da un teorema che precisa la proprietà delle catene di Markov, dette irriducibili (definite qui sotto), che vogliamo sfruttare.

In una catena di Markov irriducibile con soli stati ergodici (4_{) i limiti}

(18) uj = lim

m→∞w

(m)

kj , ∀k, j

(4_{) L’ergodicit`}_{a degli stati e la irreducibilit`}_{a si riducono nel caso in cui il numero di stati sia}

ﬁnito alle propriet`a seguenti:

• (ergodico) Ogni stato ricorre sicuramente e con tempo medio di ricorrenza minore di ∞; • (irriducibile) ∀k, j ∃ m: w(m)

(9)

esistono e sono indipendenti da k (stato iniziale). Inoltre uj > 0, ∀j, (19a) j uj = 1, (19b) uj = i uiwij, (19c)

o in altre parole, u ≡ (uj) `e autovettore sinistro con autovalore 1 della matrice stocastica di transizione W. Viceversa un set di wij irriducibile che individui una uj soddisfacente (19a), (19b) e (19c) e che abbia solo stati ergodici implica che la (18) `e soddisfatta (cio`e ha una w(m)_kj che converge a uj con m→ ∞).

Il signiﬁcato del teorema, che non dimostriamo [18], pu`o essere apprezzato con-siderando lo sviluppo della distribuzione iniziale a(0)_k . La probabilit`a dello stato j all’m-esimo passo `e data da

(20) a(m)_j = k a(0)_k w_kj(m)−−−−−→(m→∞) k a(0)_k uj = uj,

dove si `e usato il teorema, vero per qualsiasi distribuzione iniziale, e il fatto che

ka

(0)

k = 1. Poich´e inoltre se a

(0)

k = uk, a(m)j = uj ∀m (è questa la ragione per cui uj è detta la distribuzione invariante) si può dire che, a partire da un tempo sufficientemente lungo, gli stati saranno distribuiti a tutte le estrazioni con la stessa distribuzione invariante u≡ (uj), che è la distribuzione stazionaria di equilibrio della catena. Quindi le successive estrazioni possono essere usate per campionare la u. 4. L’algoritmo di Metropolis

Torniamo al nostro problema e invertiamo il procedimento: definita una proba-bilit`a di equilibrio ui, vogliamo individuare un set di probabilit`a condizionate wki, cio`e una catena di Markov che abbia ui come distribuzione invariante. Perché la con-dizione (19c) del teorema precedente sia soddisfatta è sufficiente che le probabilità condizionate wki e la distribuzione iniziale invariante uk soddisfino la condizione di reversibilità microscopica, che in termini della probabilità congiunta si legge

(21) P (k, τ ; i, τ + 1) = P (i, τ ; k, τ + 1) , ∀τ e ∀i, k.

E cio`e anche (la catena `e stazionaria e, quindi, la condizione non dipende da τ )

(22) ukwki= uiwik, ∀i, k

e che siano normalizzate

(23)

i

wki= 1, ∀k.

La prova `e immediata: basta sommare la (22) sull’indice i per veriﬁcare che la (19c) `

(10)

catena di Markov cos`ı costruita converge alla distribuzione di equilibrio nel senso che, asintoticamente, i vari stati accadranno con frequenza proporzionale alla probabilit`a ui,∀i.

La condizione (22) non determina univocamente la matrice stocastica W, ma non `

e difficile trovare un set che la soddisfi. La scelta conveniente proposta nell’articolo del 1953 (per il caso della distribuzione canonica della Meccanica Statistica) è di generare una sequenza di stati partendo da uno stato iniziale j0, scelto in modo

arbitrario, e campionando gli stati successivi j1, j2, . . . , jm accettando la transizione

dallo stato jm= k al tempo m allo stato i, scelto arbitrariamente, al tempo m + 1 con probabilit`a pari a min(1, ui/uk). Se la transizione `e accettata jm+1= i, se `e rigettata si resta nello stato di partenza e jm+1= k. Con questa scelta si ha:

• wkiè costante se la probabilit`a dello stato di arrivo uiè maggiore della probabilità dello stato di partenza uk: lo stato finale è accettato.

• wki`e ridotta del rapporto ui/uk se la probabilit`a dello stato di arrivo uiè minore di quella dello stato di partenza uk. In questo caso lo stato finale è solo accettato in una frazione di casi data da ui/uk < 1 (5).

(24) wki= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Aki, se i = k e ui≥ uk, Aki ui uk , se i = k e ui< uk, 1− j=k wkj, se i = k, = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ Aki· min 1,ui uk , se i = k, 1− j=k wkj, se i = k,

dove Akiè la probabilit`a di scegliere arbitrariamente lo stato i a partire dallo stato k. Può convenire limitare questa arbitrarietà per controllare il numero degli stati finali non accettati. Per esempio se consideriamo il campionamento di stati discretizzati in uno spazio di dimensione n, si prende nulla la probabilità Aki di generare lo spo-stamento x(k) _{→ x}(i) _{nello spazio a n dimensioni se gli stati k} _{≡ (x}(k)

1 · · · · x (k)

n ) e i≡ (x(i)₁ · · · ·x(i)n ) diﬀeriscono per il valore di pi`u di una coordinata. Per stati che sod-disfano questa condizione, la posizione x(i) _{viene generata cominciando con la scelta}

a caso di un intero ν, con probabilit`a 1

n uniforme nell’intervallo [1, n], per identiﬁcare la componente x(k)ν da modiﬁcare, e poi estraendo un nuovo valore x(i)ν distribuito uniformemente nel segmento di lunghezza 2d centrato in x(k)ν . Si ottiene

(25) Aki= ⎧ ⎪ ⎨ ⎪ ⎩ 1 2d, se x(i) ν − x(k)ν  < d e x(i)α = x(k)α , ∀α = ν , 0, altrimenti.

Operativamente, lo spostamento a caso nell’intervallo [−d, d], si genera con x(i)ν =

(5_{) Osserviamo che, data la distribuzione uniforme}_{P(x) = 1, x ∈ [0, 1) nel segmento unitario,}

la probabilit`a di estrarre un valore minore di ξ `e data da P(x≤ ξ) =R₀ξP(x)dx = ξ. Per accettare una transizione con la probabilit`a richiesta ξ = ui

uk `e suﬃciente generare un numero aleatorio η

uniforme in [0, 1): se `e vera la condizione η < ui

u_k (che si realizza con probabilit`a ui

u_k) la transizione

(11)

x(k)ν + (2ξ− 1)d, dove ξ è un numero pseudoaleatorio estratto uniformemente in [0, 1). La (25) soddisfa ∀d la condizione Aki = Aik che, come ora mostriamo, deve essere rispettata. Il valore del parametro d ovviamente influenza la rapidit`a di convergenza ed è generalmente scelto in modo che circa metà o poco più delle mosse siano rifiutate. Osserviamo infine che con le definizioni (24) si ottiene

(26) wki

wik =

Aki· min(1, ui/uk) Aik· min(1, uk/ui) =

Aki Aik ·

ui uk ,

sia nel caso _ukui ≥ 1 che nel caso uk_ui ≥ 1. Risulta quindi necessario imporre Aki= Aik, ∀i, k perché le (24) soddisfino la condizione di reversibilità microscopica, (22).

Il metodo Monte Carlo di Metropolis in quanto basato su un campionamento statistico finito fornisce una stima del valore di aspettazione desiderato con una accu-ratezza che può essere analizzata in termini statistici. Tipicamente una volta generata una sequenza di M stati la si suddivide in sottosequenze successive e si calcolano su di esse stime distinte dell’integraleI , una su ciascuna sottosequenza di lunghezza M/ . Per valori di M/ sufficientemente grandi si possono considerare i valori medi I1,I2, . . . ,Icos`ı ottenuti dell’integraleI come misure indipendenti Una

sempli-ce analisi statistica su media e varianza permette di valutare l’errore sulla stima (9) dell’integrale I . Come `e ben noto agli statistici, l’errore sulla media diminuisce proporzionalmente almeno a 1/√ .

5. Illustrazione

Come illustrazione immaginiamo di voler calcolare con il metodo Monte Carlo il valore di aspettazione dell’energia E(v) == 1₂m[v21+ v22+ v32] di una particella di gas

ideale, massa m = 1 e kBT = 1, in tre dimensioni spaziali con velocit`a v = (v1, v2, v3)

integrando la distribuzione di Maxwell u(v) = (1/√2π)3_e−E(v)

(27) I =

u (v1, v2, v3) E(v1, v2, v3) dv1dv2dv3≡ E.

Esaminiamo l’algoritmo che permette di generare lo stato al passo τ + 1 partendo dalla situazione acquisita al passo corrente τ :

• al tempo τ la particella sia nello stato k-esimo descritto dalle tre componenti della velocit`a v₁(k), v₂(k)e v₃(k);

• si sceglie a caso una componente estraendo un intero pseudoaleatorio η nel set (1, 2, 3) con probabilit`a uniforme P (1) = P (2) = P (3) = 1/3;

• si genera un valore di prova della componente v(j)

η con uno spostamento alea-torio uniforme nell’intervallo [−d, d). Operativamente si estrae un numero pseudoaleatorio ξ distribuito con probabilit`a uniforme in [0, 1) e si ottiene

v(j)_η = v(k)_η + (2ξ− 1)d,

corrispondente ad uno stato j-esimo in cui le altre due componenti della velocit`a v(j) _{rimangono invariate rispetto ai valori nello stato k-simo;}

(12)

• si calcola la corrispondente variazione di energia ΔEkj = 1₂[(vη(j))2− (vη(k))2], in termini della quale si ha uj/uk = e−ΔEkj:

se ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ΔEkj≤ 0, i.e. Ej ≤ Ek ⇒ uj

uk ≥ 1, al tempo τ + 1 si passa allo stato j; ΔEkj> 0, i.e. Ej > Ek ⇒ estratto χ numero pseudoaleatorio uniforme

in [0, 1), se χ≤_ukuj, al tempo τ + 1 si passa allo stato j, altrimenti la mossa `e riﬁutata, al tempo τ + 1 si resta nello stato k.

La procedura può essere iterata per un numero di passi a piacere, vincolati soltanto dal tempo di calcolo a disposizione. Sappiamo che il teorema è vero asintoticamente. Perciò si scarta una sequenza iniziale, detta di equilibrazione, per portare il sistema in condizioni asintotiche e perdere “memoria” dello stato iniziale arbitrariamente scelto. Nel nostro esempio, per mostrare la lunghezza della sequenza iniziale da trascurare abbiamo scelto v(τ = 0) = (6,−3, −6). Si continua generando la successione di M stati j1, j2, . . . , jM distribuita secondo la probabilit`a asintotica uj su cui calcolare la media di ensemble (28) v2= 1 M i=1,M v(ji) 1 2 + v(ji) 2 2 + v(ji) 3 2 −→ E = 1 2m v2.

Il programma Python fornito in Appendice contiene il codice per calcolare il risulta-to (28). Lo utilizziamo per illustrare come l’algoritmo di Metropolis generi una catena di Markov che evolve rapidamente dalla condizione iniziale arbitrariamente scelta alla condizione asintotica in cui gli stati vengono campionati in accordo alla distribuzio-ne invariante uk. Per fare questo il programma genera non una ma un ensemble di nval catene di Markov, a partire dalla stessa condizione iniziale, δ(v1− 6) δ(v2+ 3)

δ(v3+ 6) corrispondente a una grande deviazione dalla media. Ciascuna delle nval

catene evolve indipendentemente, guidata da sequenze diverse. In fig. 2 sono mostrati gli andamenti, in funzione del numero di passi Monte Carlo, del valor medio delle sin-gole componenti delle velocità. Si nota come rapidamente le grandi deviazioni iniziali decadano e tutte e tre le componenti si portino vicino allo zero, cioè al valor asinto-tico atteso, continuando poi a fluttuare, in misura minore, intorno ad esso. In fig. 3 e 4 riportiamo, invece, l’andamento degli istogrammi corrispondente alla probabilità a(τ )_k delle singole componenti, che mostrano come non solo il valor medio ma anche la forma della distribuzione evolve, dalla singolarit`a iniziale del tipo a(0)_k = δα k, al classico andamento gaussiano che corrisponde alla distribuzione di Maxwell uk.

(13)

τ(passi)

Fig. 2. – Andamento della media di vατ, α = 1, 2, 3 sull’ensemble di catene di Markov in funzione

del numero di passi Monte Carlo τ = 1, 2, . . . , M = 1000 (ciascun punto `e ottenuto mediando su = 100 traiettorie indipendenti).

τ=0

τ=5

τ=25

τ=50

Fig. 3. – Evoluzione dell’istogramma (normalizzato con intervallo di classe 0.28) che rappresenta la distribuzione a(τ )_k per le componenti v1 in rosso, v2 in blu e v3 in verde, ottenute da un ensemble

con nval = 2000 repliche a partire dalla condizione iniziale v1 = 6, v2 =−3, v3 =−6, per valori

di τ = 0, 5, 25, 50. Come riferimento `e mostrata, linea grigia in tutti i pannelli, la distribuzione gaussiana asintotica (la sua variazione in altezza riﬂette solo il cambiamento della scala verticale).

(14)

τ=100

τ=250

τ=500

τ= 1000

Fig. 4. – Vedi ﬁg. 3 ma con τ = 100, 250, 500, 1000.

Appendice

from numpy . random i m p o r t u n i f o r m , r a n d i n t from numpy i m p o r t z e r o s , r i n t , exp , sum , s q r t from t i m e i m p o r t p r o c e s s t i m e

d e f m e t r o p o l i s (M, vx0 , vy0 , vz0 , kt , d ) : ”””

Genera una Catena d i Markov d i l u n g h e z z a M

p e r l a d i s t r i b u z i o n e d i Maxwell con t e m p e r a t u r a k t con c o n d i z i o n e i n i z i a l e ( vx0 , vy0 , vz0 ) e s p o s t a m e n t o con p r o b a b i l i t a ’ u n i f o r m e n e l l ’ i n t e r v a l l o [−d , d ] i n o u t p u t : c o u n t = numero mosse a c c e t t a t e vx , vy , vz = a r r a y d i d i m e n s i o n e M+1 s e q u e n z e g e n e r a t e ””” vx = z e r o s (M+1)

(15)

vy = z e r o s (M+1) vz = z e r o s (M+1) vx [ 0 ] = vx0 vy [ 0 ] = vy0 vz [ 0 ] = vz0 # c o u n t = 0 vn = z e r o s ( 3 ) e k j = 0 . 5∗ ( vx [ 0 ] ∗ ∗ 2 + vy [ 0 ] ∗ ∗ 2 + vz [ 0 ] ∗ ∗ 2 ) p x j = exp(_{− e k j / kt )} f o r j i n r a n g e (M) : vn [ 0 ] = vx [ j ] vn [ 1 ] = vy [ j ] vn [ 2 ] = vz [ j ] nu = r a n d i n t ( 3 ) vn [ nu ] += ( 2 .∗ uniform ( 0 . , 1 . ) − 1 . ) ∗ d ekn = 0 . 5∗ ( vn [ 0 ] ∗ ∗ 2 + vn [ 1 ] ∗ ∗ 2 + vn [ 2 ] ∗ ∗ 2 ) pxn = exp(−ekn/ kt ) wt = pxn / p x j i f wt >= u n i f o r m ( 0 . , 1 . ) : vx [ j +1] = vn [ 0 ] vy [ j +1] = vn [ 1 ] vz [ j +1] = vn [ 2 ] e k j = ekn p x j = pxn c o u n t += 1 . e l s e : vx [ j +1] = vx [ j ] vy [ j +1] = vy [ j ] vz [ j +1] = vz [ j ] r e t u r n count , vx , vy , vz i f n a m e == ” m a i n ” : ””” n v a l = numero d i s e q u e n z e d i Markov g e n e r a t e i n d i p e n d e n t e m e n t e Meq = numero d i p a s s i Monte C a r l o da s c a r t a r e ( e q u i l i b r a z i o n e ) kt , d e l t a = p a r a m e t r i Monte C a r l o ( v e d i f u n z i o n e m e t r o p o l i s ) ””” n v a l = 100 Meq = 20000 k t = 1 . d = 0 . 5 # a l l o c a z i o n e a r r a y d i d i m e n s i o n e ( n v a l , Meq+1) ove m e m o r i z z a r e l e s e q u e n z e ux = z e r o s ( ( n v a l , Meq+1)) uy = z e r o s ( ( n v a l , Meq+1)) uz = z e r o s ( ( n v a l , Meq+1)) # C o n d i z i o n e i n i z i a l e comune a t u t t e l e n v a l s e q u e n z e vx0 = 6 . vy0 = −3. vz0 = −6. # E q u i l i b r a t u r a : c i c l o c h e g e n e r a n v a l s e q u e n z e i n d i p e n d e n t i f o r i i n r a n g e ( n v a l ) : # e q u i l i b r a t i o n t i c = p r o c e s s t i m e ( ) # g e n e r a z i o n e s e q u e n z a i−sima

(16)

t o c = p r o c e s s t i m e ( )

p r i n t ( ” c p u t i m e p e r run MC %4d = %8.5 f s ” % ( i , t o c−t i c ) ) p r i n t ( ” p e r c e n t u a l e mosse a c c e t t a t e : %5.1 f ” % ( 1 0 0∗ acc /Meq) ) # # Run d i e q u i l i b r i o e c a l c o l o n v a l s t i m e i n t e g r a l e i n t e l l = z e r o s ( n v a l ) media = 0 . # M = numero d i s t e p Monte C a r l o su c u i c a l c o l a r e l a s i n g o l a s t i m a M = 40000 t i m i n t= z e r o s (M+1) d = 1 . t i c = p r o c e s s t i m e ( ) f o r i i n r a n g e ( n v a l ) : # c o n d i z i o n e i n i z i a l e : u l t i m o s t a t o s e q u e n z a d i e q u l i b r a z i o n e vx0=ux [ i , Meq ] vy0=uy [ i , Meq ] vz0=uz [ i , Meq ] # g e n e r a z i o n e s e q u e n z a i−sima con p r o b a b i l i t a ’ i n v a r i a n t e acc , v1 , v2 , v3 = m e t r o p o l i s (M, vx0 , vy0 , vz0 , kt , d ) t i m i n t += v1∗∗2 + v2 ∗∗2 + v3 ∗∗2 # s t i m a i n t e g r a l e s u l l a s e q u e n z a i−esima i n t e l l [ i ] = sum ( v1 [ 1 :M+1]∗∗2+v2 [ 1 :M+1]∗∗2+v3 [ 1 :M+1]∗∗2) i n t e l l [ i ] /= M media += i n t e l l [ i ] t o c = p r o c e s s t i m e ( ) p r i n t ( ” c p u t i m e p e r %4d s t i m e d i %6d p a s s i MC = %8.3 f s ” % ( n v a l ,M, t o c−t i c ) ) t i m i n t /=n v a l media /= n v a l v a r i a n z a = 0 . f o r i i n r a n g e ( n v a l ) : v a r i a n z a += ( i n t e l l [ i ]−media )∗∗2 v a r i a n z a /= ( n v a l−1)

p r i n t ( ” v a l o r medio i n t e g r a l e %8.3 f (%8.3 f ) ” % ( media , 2∗ s q r t ( v a r i a n z a / nval ) ) )

Bibliograﬁa

[1] Metropolis N.e Ulam S., “The Monte Carlo Method”, J. Am. Stat. Assoc., 44 (1949) 335. [2] Rosenbluth M. N._{, “Genesis of the Monte Carlo algorithm for Statistical Mechanics”, AIP}

Conf. Proc., 690 (2003) 22.

[3] Lazzarini M._{, “Un’applicazione del calcolo della probabilit`}_{a alla ricerca sperimentale di un} valore approssimato di π”, Periodico di Matematica, 4 (1901) 140.

[4] Badger L._{, “Lazzarini’s Lucky Approxmation of π”, Math. Mag., 67 (1994) 83.}

[5] Allen M. P._{e Tildesley D. J., Computer Simulation of Liquids (Oxford University Press,} Oxford) 1987, p. 110.

[6] Eckhardt R._{, “Stan Ulam, John von Neumann, and the Monte Carlo Method”, Los Alamos}

Sci., 14 (1986) 131.

[7] Anderson H. L._{, “Metropolis, Monte Carlo and the MANIAC”, Los Alamos Sci., 14 (1986)} 96.

[8] Haigh T., Priestley M. _{e Rope C., “Los Alamos Bets On ENIAC: Nuclear Monte Carlo} Simulations 1947-48”, IEEE Ann. History Comput., 36 (2014) 42.

[9] Binder K. _{(Editor), Monte Carlo Method in Statistical Physics (Springer-Verlag, Berlin,} Heidelberg) 1979, 1986.

[10] Binder K.(Editor), Application of Monte Carlo Method in Statistical Physics (Springer-Verlag, Berlin, Heidelberg) 1984, 1987.

(17)

[11] Landau G. _{e Binder K., A Guide to Monte Carlo Simulations in Statistical Physics} (Cambridge University Press, Cambridge) 2000, 2015.

[12] Frenkel D._{e Smit B., Understanding Molecular Simulations. From Algorithms to Applications} (Academic Press, London) 1996, 2002.

[13] Rubinstein R. Y._{, Simulation and Monte Carlo methods (Wiley, New York) 1981.}

[14] Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H. _{e Teller E.,} “Equation of state calculations by fast computing machines”, J. Chem. Phys., 21 (1953) 1087. [15] Gubernatis J. E._{, “Marshall Rosenbluth and the Metropolis algorithm”, Phys. Plasmas, 12}

(2005) 057303.

[16] Wood W. W.e Parker F. R., “Monte Carlo Equation of State of Molecules Interacting with the Lennard-Jones Potential. I. A Supercritical Isotherm at about Twice the Critical Temperature”,

J. Chem. Phys., 27 (1957) 720.

[17] Matsumoto M. e Nishimura T., “Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator”, ACM Trans. Model. Comput. Simul., 8 (1998) 3. [18] Feller R._{, An introduction to Probability theory and its applications, Vol. 1 (Wiley, New York)}