Solved – How to generate the transition matrix of Markov Chain needed for Markov Chain Monte Carlo simulation

markov-chain-montecarlomarkov-processmonte carlo

I'm conducting a sensitivity analysis of a model using MCMC approaches. By reading the code of the sensitivity test procedure, I find the steps in Markov Chain is quite similar to random walk.

Also, from my understanding of Markov Chain, a transition matrix is generally prescribed for such simulations.

So I'm confused whether or not MCMC needs a transition matrix:

  1. If so, how to generate the transition matrix of Markov Chain needed for MCMC simulation?
  2. If not, why can't such a transition matrix be generated for Markov Chain?

Best Answer

There are several levels of confusion exposed by your question:

By reading the code of the sensitivity test procedure, I find the steps in Markov Chain is quite similar to random walk.

It would be most profitable to read further than "the code" about Markov chain Monte Carlo methods. For instance, the Wikipedia entry on the Metropolis-Hastings algorithm is pretty informative. And Charlie Geyer has a very good introduction to MCMC available online. A random walk is a special case of Markov chain with (a) symmetry constraints in the moves and (b) no stationary distribution in most cases. Markov chains produced by MCMC must have a stationary distribution, which is the distribution of interest.

Also, from my understanding of Markov Chain, a transition matrix is generally prescribed for such simulations.

Markov chain Monte Carlo methods are producing Markov chains and are justified by Markov chain theory. In discrete (finite or countable) state spaces, the Markov chains are defined by a transition matrix $(K(x,y))_{(x,y)\in\mathfrak{X}^2}$ while in general spaces the Markov chains are defined by a transition kernel.

So I'm confused whether or not MCMC needs a transition matrix:

To be implemented, MCMC requires a practical solution to the generation from the transition kernel, i.e., to be able to generate $X_{t+1}$ given $X_t$. For instance, the Metropolis-Hastings algorithm relies on an auxiliary transition kernel $Q$ and proceeds in two steps:

  1. Generate $Y_t\sim Q(x_t,y)$ when $X_t=x_t$
  2. Take $$X_{t+1}=\begin{cases} Y_t &\text{with probability }\alpha(x_t,y_t)\\X_t &\text{with probability }1-\alpha(x_t,y_t)\\\end{cases}$$where$$\alpha(x,y)=\frac{\pi(y)Q(y,x)}{\pi(x)Q(x,y)} \wedge 1$$

This is an implementable algorithm even though the associated transition kernel $K(x,y)$ is usually not available in closed form because the rejection probability $$\beta(x)=\int_\mathfrak{X} \{1-\alpha(x,y)\} Q(x,\text{d}y)$$ most often cannot be derived.

If so, how to generate the transition matrix of Markov Chain needed for MCMC simulation? If not, why can't such a transition matrix be generated for Markov Chain?

It is obviously possible to both be able to generate from the MCMC transition kernel (as otherwise the algorithm could not run) and be unable to produce the transition kernel in closed form.

Related Question