# How to generate the transition matrix of Markov Chain needed for Markov Chain Monte Carlo simulation?

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?
• The transition matrix (or more generally, transition kernel) is normally implicit in MCMC. – Glen_b Apr 3 '16 at 13:47

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.

A transition matrix determines the movement of a Markov chain when the space over which the chain is defined (the state space) is finite or countable. If the Markov chain is at state $x$, element $(x,y)$ in the transition matrix is the probability of moving to $y$. For example, consider a Markov chain that has only two possible states, $\{0, 1\}$. Then the transition matrix be $P(x, y)$,

$$P(x,y) = \left[\begin{array}{cc} 1/2 & 1/2\\ 1/3 & 2/3 \end{array}\right],$$

determines how the Markov chain moves. For example, $P(x=1, y=1) = Pr(y = 1|x = 1) = 2/3$.

1. I am a little unfamiliar with using transition matrixes, but I know you can use R package markovchain to deal with such Markov chains. Read the vignette here for help.

Consider the case where the Markov chain can move to infinite states. For example when the state space is $\mathbb{R} = (-\infty, \infty)$ or even $(0,1)$. It is then impossible to write down a transition matrix, since the number of possible states are uncountably infinite. In addition, the probably of going from one state to any other state is exactly 0, due to the infinite size of the state space.

Such a space for a Markov chain is called general state space. The transition of the Markov chain over such a state space is instead defined with a Markov transition kernel $P(x, A)$, where $x$ is an element, and $A$ is a measurable set in the state space.

You can find some theoretical references for general state space Markov chains here:

For MCMC, if you are in a general state space, you don't need to necessarily understand what $P(x,A)$ exactly looks like as long as you have an algorithm that tells you exactly how the Markov chain moves from one step to the other. One of the most common MCMC techniques is the Metropolis-Hastings algorithm.

Every Markov Chain can be viewed as a random walk.

If you're implementing MCMC, you don't need to explicitly specify or know the transition function(matrix), as Greenparker suggested, M-H algorithm is a common technique, which allows you achieve the stationary distribution.

If you know and prescribe transition matrix beforehand, then you could just keep doing multiplication till convergence, I don't think MCMC would be necessary in this scenario.

• Could you expand on your first sentence? In the literature, "random walk" usually has a very specific meaning. – Xi'an Apr 4 '16 at 6:36