On the Markov chain Monte Carlo (MCMC) method (Q2371215)

Let \(f(x)\) be a density of a distribution of some random variable \(X.\) We are interested in computing the integral \(\int\limits g(x) f(x)\,dx = E g(X)\) for a given function \(g.\) If we can generate a random sample \(x_1, \ldots, x_n\) of size \(n\) from this distribution and compute \(a_n ={1\over n} \sum_{i=1}^n g(x_i)\), then by the law of large numbers \(a_n\) approximates \(E g(X).\) The problem is to simulate \(x_i\). Suppose that we know only the function \(f_1 (x) = K f(x)\) where \(f(x)\) is the density of \(X.\) The author proves the following theorem: suppose there exists a density \(h(x)\) and a constant \(M\) such that \(f_1 (x) \leq M h (x)\) \(\forall x.\) Let \(x_k\) be i.i.d. with common density \(h\), \(U_k\) be i.i.d. uniformly on \((0, 1).\) Let \(B\) be given by \(B = \{ (x, u): u \leq f_1(x)/ M h (x) \}\) and \(\tau\) be the first \(m\) such that \((X_m, U_m) \in B\) and let \(w = x_\tau.\) Then \(w\) has density \(f.\) The author considers another method to estimate the integral \(\int g(x) p(x)\,dx.\) He considers a Markov chain \(X_n\) in such way that the given distribution \(p\) is the stationary distribution for the chain. If this distribution is unique then \({1\over N} \sum\limits_{n=1}^N g(x_n) \to \int g(x) p(x)\,dx\) as \(n \to \infty.\) This method is called Markov Chain Monte Carlo method. The author gives an introduction to this method. Some examples are considered as well.