Algoritmo di Metropolis-Hastings: differenze tra le versioni

Versione delle 11:44, 24 apr 2025

Versione attuale delle 15:46, 29 apr 2025

(3 versioni intermedie di 3 utenti non mostrate)

Riga 38:

Un processo di Markov è definito univocamente dalle sue probabilità di transizione <math>P(x' \mid x)</math>, cioè la probabilità di passare da uno stato dato <math>x</math> a un altro stato dato <math>x'</math>. Esso ammette una distribuzione stazionaria unica <math>\pi(x)</math> quando sono soddisfatte le seguenti due condizioni:

# ''Esistenza della distribuzione stazionaria'': deve esistere una distribuzione stazionaria <math>\pi(x)</math>. Una condizione sufficiente (ma non necessaria) è il detailed balance (bilanciamento dettagliato), che richiede che ogni transizione <math>x \to x'</math> sia reversibile, cioè per ogni coppia di stati <math>x, x'</math>, la probabilità di essere nello stato <math>x</math> e passare a <math>x'</math> deve essere uguale alla probabilità di essere nello stato <math>x'</math> e passare a <math>x</math>, ovvero: <math>\pi(x)P(x'\mid x)=\pi(x')P(x\mid x')</math>. Una distribuzione <math>\pi(x)</math> che soddisfa il bilancio dettagliato è necessariamente stazionaria, infatti segue che:

::<math display="block">\int \pi(x)P(x'\mid x) dx= \int \pi(x')P(x\mid x') dx = \pi(x')\int P(x\mid x') dx = \pi(x'),</math>

:cioè <math>\pi(x)</math> soddisfa la definizione di distribuzione stazionaria.

# ''Unicità della distribuzione stazionaria'': la distribuzione stazionaria <math>\pi(x)</math> deve essere unica. Questo è garantito dall'[[Processo markoviano#Catene di Markov ergodiche|ergodicità]] del processo di Markov, la quale richiede che ogni stato sia:

## ''aperiodico'' - il sistema non ritorna allo stesso stato a intervalli fissi;

## ''positivamente ricorrente'' - il numero atteso di passi per tornare nello stesso stato è finito.

L'algoritmo di Metropolis–Hastings consiste nel progettare un processo di Markov (costruendo le [[probabilità di transizione]]) che soddisfi le due condizioni sopra, in modo che la sua distribuzione stazionaria <math>\pi(x)</math> sia esattamente <math>P(x)</math>. La derivazione dell'algoritmo parte dalla condizione di bilanciamento dettagliato:

:<math display="inline">\piP(x)P(x'\mid x)=\piP(x')P(x\mid x')</math>

che può essere riscritta come:

:<math>\frac{P(x' \mid x)}{P(x \mid x')} = \frac{P(x')}{P(x)}.</math>

L'approccio consiste nel suddividere la transizione in due sotto-passi: la ''proposta'' e l'''accettazione/rifiuto''. La distribuzione di proposta <math>g(x' \mid x)</math> è la probabilità condizionata di proporre uno stato <math>x'</math> dato <math>x</math>, mentre la distribuzione di accettazione <math>A(x', x)</math> è la probabilità di accettare lo stato proposto <math>x'</math>. La probabilità di transizione può essere scritta come prodotto di queste:

:<math>P(x'\mid x) = g(x' \mid x) A(x', x).</math>

Inserendo questa relazione nell'equazione precedente si ottiene:

:<math>\frac{A(x', x)}{A(x, x')} = \frac{P(x')}{P(x)}\frac{g(x \mid x')}{g(x' \mid x)}.</math>

Il passo successivo nella derivazione è scegliere un rapporto di accettazione che soddisfi la condizione sopra. Una scelta comune è quella di Metropolis:

:<math>A(x', x) = \begin{cases}

\min\left(1, \frac{P(x')}{P(x)} \frac{g(x \mid x')}{g(x' \mid x)}\right) & \text{se } P(x)g(x' \mid x) \neqne 0; \\

1 & \text{Altrimentialtrimenti}.

\end{cases}</math>

Per questo rapporto di accettazione <math>A</math> la condizione è soddisfatta. La scelta di <math>A</math> siffatta è giustificata da due punti:

* Muoversi verso zone di più alta densità di probabilità aumenta la probabilità di accettazione, infatti in tal caso <math>\frac{P(x')}{P(x)} > 1</math>;.

* Il termine <math>\frac{g(x \mid x')}{g(x' \mid x)}</math> corregge l'eventuale asimmetraiasimmetria della probabilità di transiozionetransizione, così da rispettare il bilancio dettagliato, infatti, consideriamo il caso in cui <math>P(x)g(x'\mid x) > P(x')g(x\mid x')</math>, cioè è più probabile andare da <math>x</math> in <math>x'</math> piuttosto che da <math>x'</math> in <math>x</math>, allora <math>A(x', x) < 1</math> mentre <math>A(x, x')=1</math> e quindi

::<math display="block">P(x)P(x' \mid x) = P(x)g(x'\mid x)A(x', x) = \underbrace{P(x')g(x\mid x')\underbrace{A(x, x')}_{=1} = P(x')P(x\mid x').</math>

:Quindi <math>P(x)</math> è effettivamente la distribuzione limitre della catena di Markov.

L'algoritmo di Metropolis-Hastings può quindi essere scritto come segue:

Riga 80 ⟶ 88:

## calcoliamo la probabilità di accettazione <math>A(x', x_t)</math>.

# Accettazione o rifiuto

## generiamo un [[numero casuale]] uniforme <math>u \in [0, 1]</math>;

## se <math>u \le A(x' , x_t)</math>, allora accettiamo il candidato e assegnamo: <math>x_{t+1} = x'</math>;

## se <math>u > A(x' , x_t)</math>, allora rifiutiamo il candidato e assegnamo: <math>x_{t+1} = x_t</math>.