Markov chain methods consist of repeatedly applying stochastic updates until eventually the state begins to yield samples from the equilibrium. However, samples drawn from the equilibrium distribution are identically distributed, any two successive samples will be highly correlated with each other. We should return only every n successive sample to avoid the bias of the correlation. Thus Markov chains require time to burn in to the equilibrium distribution and the time to transition from one sample to another reasonably decorrelated sample after reaching equilibrium.

Expensive to Use

We do not know in advance how many steps the Markov chain must run before reaching its equilibrium distribution. This length of time is called the mixing time. Testing whether a Markov chain has reached equilibrium is also diﬃcult. We do not have a precise enough theory for guiding us in answering this question. So, we simply run the Markov chain for an amount of time that we roughly estimate to be suﬃcient, and use heuristic methods to determine whether the chain has mixed. These heuristic methods include manually inspecting samples or measuring correlations between successive samples.

Hard to Evaluate the Length of Running Time

There are some drawbacks of using Markov chain Monte Carlo methods. It is expensive to use because it required more time, and it is hard to evaluate the length of running time because we do not know in advance how many steps the Markov chain must run before reaching its equilibrium distribution. 


State University of New York at Stony Brook

Markov Chain is a useful tool to approximately sample from $P_{model} (X)$, when $P_{model} (X)$ is represented by an undirected model that there is no tractable method to draw exact samples. The most standard, generic guarantees for Markov chain Monte Carlo methods (MCMC) techniques are the model does not assign zero probability to any state. Therefore, it is most convenient to present these techniques as sampling from an energy-based model (EBM) because every state is guaranteed to have nonzero probability in EBM.

Markov Chain Monte Carlo Methods

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

In EBM, if there are just two variables, deﬁning a distribution $p(a, b)$. In order to sample $a$, we must draw a from $p(a | b)$, and in order to sample $b$, we must draw it from $p(b | a)$. It seems to be an intractable chicken-and-egg problem. We can use Markov chain to avoid this situation. 

Reason of using MCMC

- In statistics, Gibbs sampling or a Gibbs sampler is a Markov chain Monte Carlo (MCMC) algorithm for obtaining a sequence of observations which are approximated from a specified multivariate probability distribution, when direct sampling is difficult. 
- This sequence can be used to approximate the joint distribution (e.g., to generate a histogram of the distribution); to approximate the marginal distribution of one of the variables, or some subset of the variables.
-  Gibbs Sampling is applicable when the joint distribution is not known explicitly or is difficult to sample from directly, but the conditional distribution of each variable is known and is easier to sample from.
- A blocked Gibbs sampler groups two or more variables together and samples from their joint distribution conditioned on all other variables, rather than sampling from each one individually. 

Gibbs sampling in RBM

Annealed Importance Sampling (AIS) is a strategy of importance sampling, applied to an extended state with a sequence of intermediate distributions ($ p_0 $ to $ p_1 $). AIS is the most common way of estimating partition function for undirected probabilistic models, such as a trained model of Restricted Boltzmann Machine.

Annealed Importance Sampling

The core idea of a Markov chain is to have a state $x$ that begins as an arbitrary value. Over time, we randomly update $x$ repeatedly. Eventually $x$ becomes a fair sample from $p(x)$. Formally, a Markov chain is deﬁned by a random state $x$ and a transition distribution $T(x^{’}| x)$ specifying the probability that a random update will go to state $x^’$ if it starts in state x. Running the Markov chain means repeatedly updating the state x to a value $x^’$  sampled from $T(x^{’}| x)$.

Learn Before

Related

Learn After