Jaki jest związek między łańcuchem Markov a łańcuchem Markov monte carlo

15

Próbuję zrozumieć łańcuchy Markowa za pomocą SAS. Rozumiem, że proces Markowa to taki, w którym przyszły stan zależy tylko od stanu bieżącego, a nie od stanu przeszłego, i istnieje matryca przejścia, która wychwytuje prawdopodobieństwo przejścia z jednego stanu do drugiego.

Ale potem natrafiłem na ten termin: Markov Chain Monte Carlo. Chcę wiedzieć, czy Markov Chain Monte Carlo jest w jakikolwiek sposób związany z procesem Markowa, który opisałem powyżej?

Zwycięzca
źródło

Odpowiedzi:

9

Cóż, tak, istnieje związek między tymi dwoma terminami, ponieważ losowania z MCMC tworzą łańcuch Markowa. Od Gelman, Analiza danych bayesowskich (wydanie 3), s. 1. 265:

Symulacja łańcucha Markowa (zwana także łańcuchem Markowa Monte Carlo lub MCMC) jest ogólną metodą opartą na rysowaniu wartości z odpowiednich rozkładów, a następnie korygowaniu tych rysunków, aby lepiej przybliżać docelowy rozkład tylny, p ( θ | y ) . Próbkowanie odbywa się sekwencyjnie, z rozkładem losowań w zależności od ostatniej losowanej wartości; stąd losowania tworzą łańcuch Markowa.θp(θ|y)

Sycorax mówi Przywróć Monikę
źródło
Umm ok, ale dlaczego muszę rysować losowe próbki z procesu markowa, istnieje wiele innych rodzajów procesów, takich jak normalny, bernoulli, opcjonalny itp.
Victor
2
@Victor Myślę, że straciłeś z oczu przypadek użycia MCMC. Używamy MCMC w statystykach bayesowskich, gdy nie ma analitycznej postaci rozkładu tylnego.
Sycorax mówi Przywróć Monikę
3
+1 statystyki bayesowskie są prawdopodobnie najbardziej oczywistym zastosowaniem MCMC (gdzie rozkład celu jest połączony z tyłu), ale nie jedyny możliwy.
Glen_b
18

Związek między obiema koncepcjami polega na tym, że metody Markowa Monte Carlo (znane również jako MCMC) wykorzystują teorię łańcucha Markowa do tworzenia symulacji i aproksymacji Monte Carlo ze złożonego rozkładu docelowego .π

W praktyce te metody symulacyjne generują ciąg który jest łańcuchem Markowa, tj. Taki, że rozkład X i dla całej przeszłości { X i - 1 , , X 1 } zależy tylko od X i - 1 . Innymi słowy, X i = f ( X i - 1X1,,XNXi{Xi1,,X1}Xi1 gdzie f

Xi=f(Xi1,ϵi)
fjest funkcją określoną przez algorytm, a rozkład docelowy i ϵ i są iid. Gwarancje (ergodyczny) teorię, że X i zbieżny (w dystrybucji) do gatunku , jak i trafia do .πϵiXiπi

Najprostszym przykładem algorytmu MCMC jest próbnik wycinków : w iteracji i tego algorytmu wykonaj

  1. symulacja ϵi1U(0,1)
  2. symulować (co oznacza wygenerowanie drugiego niezależnego ϵ 2XiU({x;π(x)ϵi1π(Xi1)}) )ϵi2

Na przykład, jeśli rozkład docelowy jest normalnym [dla którego oczywiście nie potrzebujesz MCMC w praktyce, jest to zabawkowy przykład!]Powyższe tłumaczy się jakoN(0,1)

  1. symulować ϵi1U(0,1)
  2. symulować , tj.Xi=±ϵ 2 i {-2log(XiU({x;x22log(2πϵi1}) zε 2 i ~U(0,1)Xi=±ϵi2{2log(2πϵi1)φ(Xi1)}1/2ϵi2U(0,1)

lub w R.

T=1e4
x=y=runif(T) #random initial value
for (t in 2:T){
  epsilon=runif(2)#uniform white noise 
  y[t]=epsilon[1]*dnorm(x[t-1])#vertical move       
  x[t]=sample(c(-1,1),1)*epsilon[2]*sqrt(-2*#Markov move from
        log(sqrt(2*pi)*y[t]))}#x[t-1] to x[t]

N(0,1)(Xi)top: Histogram of 10⁴ iterations of the slice sampler and normal N(0,1) fit; bottom: sequence $(X_i)$

(Xi,ϵi1π(Xi))

curve(dnorm,-3,3,lwd=2,col="sienna",ylab="")
for (t in (T-100):T){
lines(rep(x[t-1],2),c(y[t-1],y[t]),col="steelblue");
lines(x[(t-1):t],rep(y[t],2),col="steelblue")}

który podąża za pionowymi i poziomymi ruchami łańcucha Markowa pod docelową krzywą gęstości.100 last moves of the slice sampler

Xi'an
źródło