tuitions of momo The practice of mcmc 一Burn-in start the next run where the last run ended All decisions about starting points are based on the output of some preliminary runs that appear to have "converged 200040006000800010000 Unnecessary Time Diagnostics Perfect sampling guaranteed to produce an i i d sample from the equilibrium distribution of the markov chain Does not work on black box mcmc
Intuitions of MCMC • The Practice of MCMC – Burn-in • start the next run where the last run ended • All decisions about starting points are based on the output of some preliminary runs that appear to have “converged”. • Unnecessary – Diagnostics • Perfect sampling, guaranteed to produce an i.i.d. sample from the equilibrium distribution of the Markov chain • Does not work on black box MCMC
Elementary theory of mcmc The metropolis-Hastings Update h(x): the distribution from which we want to sample, the desired stationary distribution of the mcmc(need not to be normalized Updating rules: When the current state is x, propose a move to y, having conditional probability density given x denoted q(x,) Calculate the hastings ratio r(x, y) h(y)9(y,x) h(x)9(x,y) Accept the proposed move y with probability a(x, y)=min(l, r(x, y)) The hastings ratio is well defined as long as h(xq(x y)>0 for starting state x
Elementary Theory of MCMC • The Metropolis-Hastings Update – ℎ(𝑥): the distribution from which we want to sample, the desired stationary distribution of the MCMC (need not to be normalized) – Updating rules: • When the current state is 𝑥, propose a move to 𝑦, having conditional probability density given 𝑥 denoted 𝑞(𝑥,· ). • Calculate the Hastings ratio • Accept the proposed move 𝑦 with probability – The Hastings ratio is well defined as long as ℎ 𝑥 𝑞 𝑥, 𝑦 > 0 for starting state 𝑥
Elementary theory of mcmc The Metropolis-Hastings Theorem: the mh update is reversible wrth, and so h is its equilibrium distribution If the proposal of the next state is rejected Xn+1=X (Xn Xn+1 is exchangeable given rejection If the proposal is accepted, we need to show that Elf(Xn, Yn)a(Xn, Yn))=Eff(Yn, Xn)a(Xn,Yn) i. e. we can exchange arguments of f in f(x, y)h(r)a(x, y)q(x, y)dx dy i. e. we can exchange x and y in h(x)a(x, y)q(x,y) holy,x) h(xa(,yq(x,y=h(xq, y) min h(x)q(,y) min(n(x)q(x,y),h(y)q(,x)) =hoya,x) min x) q(x, hoq,x hoya,xq,x)
Elementary Theory of MCMC • The Metropolis-Hastings Theorem: the MH update is reversible w.r.t. ℎ, and so ℎ is its equilibrium distribution – If the proposal of the next state is rejected, 𝑋𝑛+1 = 𝑋𝑛, (𝑋𝑛, 𝑋𝑛+1) is exchangeable given rejection. – If the proposal is accepted, we need to show that i.e. we can exchange arguments of 𝑓 in i.e. we can exchange 𝑥 and 𝑦 in ℎ 𝑥 𝑎 𝑥, 𝑦 𝑞(𝑥,𝑦) ℎ 𝑥 𝑎 𝑥, 𝑦 𝑞 𝑥, 𝑦 = ℎ 𝑥 𝑞 𝑥, 𝑦 min 1, ℎ 𝑦 𝑞 𝑦, 𝑥 ℎ 𝑥 𝑞 𝑥, 𝑦 = min ℎ 𝑥 𝑞 𝑥, 𝑦 , ℎ 𝑦 𝑞 𝑦, 𝑥 = ℎ 𝑦 𝑞 𝑦, 𝑥 min ℎ 𝑥 𝑞 𝑥, 𝑦 ℎ 𝑦 𝑞 𝑦, 𝑥 , 1 = ℎ 𝑦 𝑎 𝑦, 𝑥 𝑞 𝑦, 𝑥
Elementary theory of mcmc The metropolis Update When q(x, y)=q(y, x),r(x, y)=h(y) Metropolis ratio Variable-at-a-time Metropolis-Hastings Divide the state vector into two parts,x=(u, v. Let the proposal alter u but not v, the proposal q(x, y) q(x,)=q(14,v,) Elementary updating rules When the current state is x =(u, 1), propose a move to y (u, v), where u has conditional probability density given x denoted q(x, =qu, v, Calculate the hastings ratio h(,v)q(,v,) r(x, y) h(u, v)q(u, v,u") Accept the proposed move y with probability min(, r(x, y)
Elementary Theory of MCMC • The Metropolis Update – When 𝑞 𝑥, 𝑦 = 𝑞 𝑦, 𝑥 , 𝑟 𝑥, 𝑦 = ℎ 𝑥 ℎ 𝑦 : Metropolis ratio • Variable-at-a-time Metropolis-Hastings – Divide the state vector into two parts, 𝑥 = 𝑢, 𝑣 . Let the proposal alter 𝑢 but not 𝑣, the proposal 𝑞 𝑥,𝑦 = 𝑞 𝑥, 𝑢 ∗ = 𝑞 𝑢, 𝑣, 𝑢 ∗ – Elementary updating rules: • When the current state is 𝑥 = (𝑢, 𝑣), propose a move to 𝑦 = (𝑢 ∗ , 𝑣), where 𝑢 ∗ has conditional probability density given 𝑥 denoted 𝑞 𝑥,· = 𝑞 𝑢, 𝑣,· . • Calculate the Hastings ratio • Accept the proposed move 𝑦 with probability min 1, 𝑟 𝑥, 𝑦
Elementary theory of mcmc The gibbs Update The proposal is from a conditional distribution of h(x) q(,y=holf(), f(x is a part of the components of x Commonly, f(x) is x with one component omitted: full conditionals". f(x)is x with several components omitted block Gibbs"or generalized Gibbs Idempotent: the property that the effect of multiple updates is the same as that of one. The update keeps f(Xn)unchanged. - No rejection: x=(u,v),y=(u,v).f(x=v unchanged, q(x,y)=h(ulv h(u,vh(ulv) h(uh((ulv x,y =1 hlu, vh(uvhuhlulvhlulv
Elementary Theory of MCMC • The Gibbs Update – The proposal is from a conditional distribution of ℎ 𝑥 : 𝑞 𝑥, 𝑦 = ℎ 𝑦 𝑓 𝑥 , 𝑓 𝑥 is a part of the components of 𝑥. – Commonly, 𝑓(𝑥) is 𝑥 with one component omitted: “full conditionals”. 𝑓 𝑥 is 𝑥 with several components omitted: “block Gibbs” or “generalized Gibbs” – Idempotent: the property that the effect of multiple updates is the same as that of one. (The update keeps 𝑓 𝑋𝑛 unchanged.) – No rejection: 𝑥 = 𝑢, 𝑣 ,𝑦 = 𝑢 ∗ , 𝑣 . 𝑓 𝑥 = 𝑣 unchanged, 𝑞 𝑥,𝑦 = ℎ(𝑢 ∗ |𝑣) 𝑟 𝑥, 𝑦 = ℎ 𝑢 ∗ , 𝑣 ℎ 𝑢 𝑣 ℎ 𝑢, 𝑣 ℎ 𝑢 ∗ 𝑣 = ℎ 𝑣 ℎ 𝑢 ∗ |𝑣 ℎ(𝑢|𝑣) ℎ 𝑣 ℎ 𝑢 𝑣 ℎ 𝑢 ∗ |𝑣 = 1