# When would it be computationally inefficient to sample from a distribution?

I am reading some stuff about MCMC simulation and using that as a method to sample from a distribution. I understand that MCMC algos can be used to approximate a distribution when we are unable to obtain a closed form solution for the PDF. However, the book also mentions that we can use MCMC simulation when it is not "computationally efficient" to directly sample from the distribution.

What would cause it to be computationally inefficient to sample directly from a distribution? What would be a good example?

• It might be the case that in order to sample from a density, we might have to compute high dimensional integrals. Numerical integration in high dimensions is tough, and so MCMC is a way we can avoid those integrals. Oct 30, 2019 at 4:14
• I agree that high dimensional situations are most likely what the author had in mind. Conversely, my answer briefly looks at a couple of examples in which MCMC methods are used for pedagogical purposes to illustrate particular MCMC methods when a more direct method is available and more efficient. Oct 30, 2019 at 7:21
• A somewhat analogous issue has to do with deciding when to use ordinary (nonstochastic) numerical integration and when to use simulation methods. In one dim, if the want the expected value resulting from a messy PDF, approximating the integral by rectangles (or trapezoids) is usually the most accurate way to compute the result. However, in 3-D or higher simulation generally wins out. E.g., finding the probability of the first octant of a ball in 3-space, it can get messy programming hyper-posts that fit inside the desired region. But simulation can be easier and surprisingly accurate. Oct 30, 2019 at 7:41
• @DemetriPananos Ok Thanks! So the higher the dimension, the more likely it would be difficult to directly sample from the distribution. Oct 31, 2019 at 15:46
• @confused Not necessarily. Sampling from a high dimensional gaussian seems pretty easy. Sampling from more complex distributions in high dimensions may be tricky. Sampling from marginal distributions may also be tricky. Oct 31, 2019 at 18:21

(1) Simple Gibbs example: Sample from bivariate normal distribution with $$\mu_x = \mu_y= 0, \sigma_x = \sigma_y = 1, \rho = .8.$$ This can be done as follows using a Gibbs sampler, based on $$X|Y=y \sim \mathsf{Norm}(\rho y, \sqrt{1-\rho^2})$$ and $$Y|X=x \sim \mathsf{Norm}(\rho x, \sqrt{1-\rho^2}).$$

One cycles back and forth between the two conditional distributions to get a Markov chain with the desired bivariate distribution as its limiting distribution. The burn-in period used below is at half of the iterations.

set.seed(1029); m=100000
xc = yc = numeric(m)
rho=.8; sgm=sqrt(1-rho^2)
xc[1]=-3; yc[1]=3  # start step
for(i in 2:m) {
xc[i] = rnorm(1,rho*yc[i-1],sgm)
yc[i] = rnorm(1,rho*xc[i],sgm)  }
x = xc[(m/2+1):m]; y = yc[(m/2+1):m]
round(c(mean(x),mean(y), sd(x),sd(y), cor(x,y)),3)
[1] 0.001 0.004 1.004 1.003 0.800


(2) Chib and Greenberg (1994), Understanding the Metropolis-Hastings Algorithm, The American Statistician, 49 327-335, generate a correlated bivariate normal distribution as a simple illustration of the M-H algorithm.

Any pedagogical purposes aside, both (1) and (2) are inefficient for this simple simulation because @glen-b's method is simpler.