In Section 4.4 of the excellent technical report Probabilistic Inference using Markov Chain Monte Carlo Methods, the author tries to analyze the performance of Gibbs and Metropolis algorithm with simulating samples from a bivariate Gaussian distribution. In this example, he claimed:

Notice that in this example both Gibbs sampling and the Metropolis algorithm explore less confined direction by a random walk.

This statement confuses me for a while (It also came to my attention that other books, e.g., Pattern Recognition and Machine Learning, Section 11.3, also adopted the similar perspective to estimate the number of iterations needed to obtain two nearly independent samples). What is the rationale of such statement? To me, suppose we want to sample from \begin{align*} \begin{bmatrix} X_1 \\ X_2 \end{bmatrix} \sim N\left(\begin{bmatrix} 0 \\ 0 \end{bmatrix}, \begin{bmatrix} \sigma_1^2 & \rho\sigma_1\sigma_2 \\ \rho\sigma_1\sigma_2 & \sigma_2^2\end{bmatrix}\right) \end{align*} using Gibbs sampling, the conditional distribution for $X_1$ given the current value of $X_2 = x_2$ is $N((\rho\sigma_1/\sigma_2)x_2, (1 - \rho^2)\sigma_1^2)$. Therefore in a single Gibbs pass, a Gaussian random number is generated according to this distribution, which is (in my opinion) very different from a random walk. In particular, the state will not stay at the current value with positive probability.

Does the author actually merely mean this example and the random walk share the "square root" phenomenon?


At the intuition level, the Gibbs algorithm induces a random walk on both components, eg: $$X_1'=\rho\sigma_1/\sigma_2X_2+(1 - \rho^2)^{1/2}\sigma_1\epsilon_1= \rho\sigma_1/\sigma_2\left(\rho\sigma_2/\sigma_1X_1 +(1 - \rho^2)^{1/2}\sigma_2\epsilon_2\right)+(1 - \rho^2)^{1/2}\sigma_1\epsilon_1=\rho^2 X_1 + (1 - \rho^2)^{1/2}\sigma_1[\rho\epsilon_2+\epsilon_1]$$ which is an AR(1). And makes the statement

in a single Gibbs pass, a Gaussian random number is generated according to this distribution


  • $\begingroup$ Thanks. But is "AR(1)" equivalent to "Random Walk"? It may be intuitively OK to say so if $\rho$ is close to unity, but theoretically not true, correct? $\endgroup$
    – Zhanxiong
    Feb 10 at 13:02
  • $\begingroup$ Radford considers the "random walk" behaviour of all reversible MCMC as detrimental. He thus does not mean the $x_{t+1}=x_t+\epsilon_t$ representation of a random walk, but the feature of meandering back and forth in the excursion, hence wasting time and possibly missing converging fast enough to the target. $\endgroup$
    – Xi'an
    Feb 10 at 13:09
  • $\begingroup$ Thanks for the clarification, I can see his point but just wanted to make sure I didn't miss something simple and interesting. $\endgroup$
    – Zhanxiong
    Feb 10 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.