Algoritmo di Metropolis-Hastings: differenze tra le versioni

Versione delle 16:47, 15 set 2007

Versione delle 22:39, 10 nov 2007

Riga 1:

L''''algoritmo di Metropolis-Hastings''' serve a generare dei numeri x₁, x₂, .., x_n che presentano una [[distribuzione di probabilità|distribuzione]] ''p(x)'' fissata a priori.

Il metodo si basa sulla generazione di numeri di 'test' che vengono accettati o rigettati in modo da ottenere la distribuzione voluta. Il metodo sarà presentato nel caso di una sola [[variabile randomcasuale continua]]; esso può essere facilmente esteso al caso di distribuzioni di probabilità ''P(x₁, x₂, ..., x_N)'' di un numero qualsiasi di variabili.

Il metodo può essere facilmente esteso al caso di distribuzioni di probabilità P(x₁, x₂, ..., x_N) di un numero qualsiasi di variabili.

L'algoritmo di [[Nicholas Constantine Metropolis|Metropolis]] è realizzabile utilizzando un generatore di numeri casuali con [[variabile casuale uniforme continua|distribuzione uniforme]] in ''[0, 1]''. La procedura è la seguente:

1)# Preso, per convenzione, l'ultimo valore x_i della variabile random nella sequenza si sceglie un valore di prova x^* diverso da x_i tra tutti i valori possibili della variabile random. Nel caso delle variabili random continue si può prendere x^* = x_i +δx dove δx è un numero distribuito uniformemente nell'intervallo ''[−δ, δ]'';

2)# Si calcola il rapporto w = <math> \frac{p(x^{*})}{p(x_i)} </math>;

3)# Se ''w ≥ 1'', la probabilità che nella sequenza al valore x_i segua il valore x^* è pari ad uno per cui si accetta il nuovo valore x^* = x_i+1

4)# Se ''w < 1'' il nuovo valore deve essere accettato con probabilità w. Si genera quindi un numero random r distribuito uniformemente nell'intervallo [0, 1);

5)# Se ''r ≤ w'' si accetta il nuovo valore x^* = x_i+1 ;

6)# Se invece ''r > w'' il nuovo valore viene rigettato dal momento che x_i+1 = x_i.

Per generare una sequenza di ''N'' elementi basta ripetere queste operazioni ''N'' volte a partire da un valore iniziale x₀. Per avere una buona stima della ''p(x)'' è necessario generare sequenze molto lunghe. La scelta del valore di ''δ'' può essere cruciale, se è troppo grande solo una piccola parte dei valori di prova proposti verrà accettato. Se invece il valore di ''δ'' è troppo piccolo quasi tutti i valori di prova proposti saranno accettati.

2) Si calcola il rapporto w = <math> \frac{p(x^{*})}{p(x_i)} </math>;

Di conseguenza, essendo ''δ'' dipendente dalla forma di ''p(x)'', deve essere di volta in volta scelto,; per la sua stima si piòpuò procedere per approssimazione successiva in modo che, fissato un delta, il numero di valori accettati sia un terzo del totale.

3) Se w ≥ 1, la probabilità che nella sequenza al valore x_i segua il valore x^* è pari ad uno per cui si accetta il nuovo valore x^* = x_i+1

Anche la scelta del valore iniziale è molto importante, in genere conviene partire da valori di ''x'' tali che ''p(x)'' assuma valori massimi in modo da avere una buona statistica nelle zone più probabili.

4) Se w < 1 il nuovo valore deve essere accettato con probabilità w. Si genera quindi un numero random r distribuito uniformemente nell'intervallo [0, 1);

5) Se r ≤ w si accetta il nuovo valore x^* = x_i+1 ;

6) Se invece r > w il nuovo valore viene rigettato dal momento che x_i+1 = x_i.

Per generare una sequenza di N elementi basta ripetere queste operazioni N volte a partire da un valore iniziale x₀.

Per avere una buona stima della p(x) è necessario generare sequenze molto lunghe.

La scelta del valore di δ può essere cruciale, se è troppo grande solo una piccola parte dei valori di prova proposti verrà accettato. Se invece il valore di δ è troppo piccolo quasi tutti i valori di prova proposti saranno accettati.

Di conseguenza essendo δ dipendente dalla forma di p(x) deve essere di volta in volta scelto, per la sua stima si piò procedere per approssimazione successiva in modo che, fissato un delta, il numero di valori accettati sia un terzo del totale.

Anche la scelta del valore iniziale è molto importante, in genere conviene partire da valori di x tali che p(x) assuma valori massimi in modo da avere una buona statistica nelle zone più probabili.

== Voci correlate ==

*[[Nicholas Constantine Metropolis]]

== Bibliografia ==

Riga 36 ⟶ 25:

W.K Hastings, ''Monte Carlo sampling methods using Markov chains and their applications'',

Biometrikam, [[1970]]; 57: 97-109

[[Categoria:Algoritmi numerici]]