1. Markov Chain Monte Carlo
more about Markov Chains : https://d3c33hcgiwev3.cloudfront.net/adadc80290e52a99b282ca9d7c1a41ee_background_MarkovChains.html?Expires=1583020800&Signature=UJdh6PpuE3m5EvICzH476NP5PxgoQ81DO~rCGk7a7OQcAQ-gnEjYFVSNyYoFJP2427rmBkXVLCiPdzzOWDKToMHFkzMjICyFz2QIOL0Jw0qXS-4NDXiTyeFPU~RfVeM347ZuYEkhgUqpJgMsjclK11baUhZYtMmH2g97mdMki~E&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A
(1) Markov Chain
a. Algorithm
main idea : “Samples are not independent! Sampled sequentially!”
key : assigning (latent variable) Z !
It is called as chain because it is sampled sequentially, which is affected by the sample right “before the current state”! We can express this like the below
\(p(z^{m+1} \mid z^{1},...z^{m}) = p(z^{m+1} \mid z^{m})\)
[ Understanding MC graphically ]
https://encrypted-tbn0.gstatic.com/
- each node : probability distribution of states ( ex. [0.3, 0.3, 0.4] )
- each link : probabilistic state transition ( ex. 3x3 matrix )
( the transition matrix, with probability of moving to the next state )
b. Stationary Distribution
definition : probability distribution of states \(\pi\), which satisfies \(\pi\; T = \pi\)
( \(T\) : transition matrix )
So, how to find stationary distribution?
Let \(RT_i = min\{n>0 : X_n =i \mid X_0 =i\}\), which means the ‘return time
’ ( a time that takes to get back to the starting state )
If Markov chain satisfies these two properties :
1) irreducible : if 𝒊↔𝒋,∀𝒊∈𝑺𝑺,∀𝒋∈𝑺𝑺
2) ergodic : if all states are ‘recurrent’ & ‘aperiodic’
then \(\pi_i = \underset{n\rightarrow \infty}{lim}T_{i,j}^{(n)} = \frac{1}{E[RT_i]}\)
One more thing about it. If MC is reversible, which means \(\pi_i T_{i,j} = \pi_j T_{j,i}\), then \(\pi\) is the stationary distribution.
c. MCMC (Markov Chain Monte Carlo)
Traditional Markov Chain was interested in finding what the ‘stationary distribution’ was! ( given the transition rule \(p(z^{t+1} \mid z^{t}\) ) ). But in MCMC (Markov Chain Monte Carlo), we are interested in finding the “efficient transition rule”, when given the stationary distribution \(\pi(z)\). Metropolis-Hastings algorithm is a general algorithm of MCMC, and I’m going to talk about it in the next post.