Implementazioni di algoritmi/Metodo Monte Carlo

Il Metodo Monte Carlo fa parte della famiglia dei metodi statistici non parametrici.

È utile per superare i problemi computazionali legati ai test esatti (ad esempio i metodi basati sulla distribuzione binomiale e calcolo combinatorio, che per grandi campioni generano un numero di permutazioni eccessivo).

Il metodo è usato per trarre stime attraverso simulazioni.

Si basa su un algoritmo che genera una serie di numeri tra loro incorrelati, che seguono la distribuzione di probabilità che si suppone abbia il fenomeno da indagare.

L'incorrelazione tra i numeri è assicurata da un test chi quadrato.

Determinare il valore π

Sia M un punto di coordinate $(x,y)\,$ con $0<x<1\,$ e $0<y<1\,$.

Scegliamo aleatoriamente i valori di x e y.

La probabilità che il punto M appartenga al disco di centro $(0,0)\,$ di raggio 1 è π/4. Questo si può verificare semplicemente, infatti se $x^{2}+y^{2}<1\,$ allora il punto $(x,y)\,$ appartiene al disco.

Facendo il rapporto del numero dei punti che cadono nel disco con il numero dei tiri effettuati si ottiene un'approssimazione del numero π/4. Aumentando il numero dei tiri la precisione del calcolo aumenterà, rimanendo però decisamente bassa rispetto a quella di altri algoritmi per il calcolo del π.

Implementazione in Perl

my $i; my $count;
while (1) {
    my $x = rand();
    my $y = rand();
    $i++ if (($x * $x + $y * $y) < 1);
    $count++;
    print $i/$count*4, "\n";
}

Implementazione in Python

import random
i=0.0
count=0.0
while 1:
    x=random.random()
    y=random.random()
    if (((x**2)+(y**2))<1):
        i=i+1;
    count=count+1
    print ((i/count)*4)

Implementazione in Pascal

{CALCOLA il valore di pigreco usando il metodo di montecarlo}
program pigreco;
uses crt;
var i, n, dentro : integer;
    x, y , pi : real;
begin
    randomize;
    clrscr;
 
    write('Quanti punti vuoi estrarre? ');
    readln(n);
 
    dentro:=0;
    for i := 1 to n do
    begin
        {estrae un punto nel quadrato di raggio unitario}
        x:=random();
        y:=random();
        if (x*x + y*y) < 1 then
            dentro:=dentro + 1;
    end;
 
{abbiamo valutato un quarto di cerchio}
writeln('Valore approssimato di pi greco: ', (4 * dentro / n):10:8);
readln;
end.

Implementazione in Lisp

Funzione che restituisce il valore approssimato del pi fornito il numero di lanci.

; Interprete: GNU CLISP 2.49
(defun MonteCarlo(n)
 (setq dentro 0)
 (dotimes (j n)
  (setq x (random 1.0))
  (setq y (random 1.0))
  (if (< (+ (expt x 2) (expt y 2)) 1) (setq dentro (+ dentro 1)))
 )
 (/ (* dentro 4.0) n)
)

Implementazione in Java

    n=50000001;
    c=0;
    for(i=1;i<n+1;i=i+1){
    a = Math.random();
    b = Math.random();
    if (Math.sqrt(a*a+b*b)<=1){c=c+1};
   }
   document.write((c/n)*4);

Bibliografia

• W.K Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrikam, 1970; 57: 97-109
• Bernd A. Berg, Markov Chain Monte Carlo Simulations and Their Statistical Analysis (With Web-Based Fortran Code), World Scientific 2004, ISBN 981-238-935-0.
• P. Kevin MacKeown, Stochastic Simulation in Physics, 1997, ISBN 981-3083-26-3
• Harvey Gould & Jan Tobochnik, An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems, 1988, ISBN 0-201-16504-X
• C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004, ISBN 0-387-21239-6
• Mosegaard, Klaus., and Tarantola, Albert, 1995. Monte Carlo sampling of solutions to inverse problems. J. Geophys. Res., 100, B7, 12431-12447.
• Tarantola, Albert, Inverse Problem Theory (free PDF version), Society for Industrial and Applied Mathematics, 2005. ISBN 0898715725
• Morin, L. Richard, Monte Carlo Simulation in the Radiological Sciences, CRC Press, ISBN 0-8493-5559-1.

Altri progetti

Altri progetti

• Wikipedia
• Wikimedia Commons

• Wikipedia contiene una voce riguardante il metodo Monte Carlo
• Wikimedia Commons contiene immagini o altri file sul metodo Monte Carlo