Examples comparing importance sampling and the Metropolis algorithm (Q2505465)

For a finite set \(\chi\) with a probality \(\pi(x)\) and a function \(f: \chi \to {\mathbb R}\) the quantity \( \mu = \sum_{x} f(x)\pi(x)\) must be approximated. A reversible Markov chain \(K(x,y)\) with stationary distribution \(\sigma(x) > 0\) for all \(x\) in \(\chi\) is used. Two classical procedures -- the Metropolis algorithm and importance sampling -- are used for solving the main problems of the paper. As a product of these procedures two quantities, the so-called Metropolis estimate \(\widehat{\mu}_{M}\) and importance sampling estimate \(\widehat{\mu}_{I}\) are suggested. In Section 2 the general idea for variance computation is presented. A functional space \(L^{2}(p)\) depending on the stationary distribution \(p(x),\) an inner product on \(L^{2}(p),\) the development of the functions of \(L^{2}(p)\) as series with respect to orthonormal basis of eigenfunctions are presented. In Proposition 2.1 for a reversible Markov chain \(P(x,y)\) a function in \(L^{2}(p)\) and \(N\) realizations of \(P(x,y)\) the quantity \(\widehat{\mu}_{P}\) is introduced, and an exact formula for a variance \(\text{ Var}_{p}(\widehat{\mu}_{P})\) is given. The asymptotic variance \(\sigma_{\infty}\) which gives the exact constant in the order \({\mathcal{O}}(N^{-1})\) of the variance is considered. In the next three sections concrete realizations of the ideas developed in Section 2 are shown. In Section 3 the set \(\chi\) is the set of binary \(d\)-tuples \({\mathbb Z}_{2}^{d}.\) Propositions 3.2 and 3.5, respectively, give the formulae for the variance \(\text{ Var}_{\pi}(\widehat{\mu}_{M})\) of the Metropolis chain and the variance \(\text{ Var}_{\sigma}(\widehat{\mu}_{I})\) of the importance sampling with respect to given function \(f.\) The asymptotic variance \(\sigma_{\infty}(\widehat{\mu}_{M})\) and the lead term in \(\text{ Var}_{\sigma}(\widehat{\mu}_{I})\) are presented. Another example of a choice of a function \(f\) is shown. Proposition 3.8 gives formulae for the variance \(\text{ Var}_{\pi}(\widehat{\mu}_{M})\) with respect to the Metropolis chain and the variance \(\text{ Var}_{\sigma}(\widehat{\mu}_{I})\) with respect to the importance sampling. The asymptotical behaviour of these variances are exposed in Proposition 3.10. In Section 4 the proposed chain is a sequence of independent and identically distributed variables with common probability density \(\sigma.\) Here \(\chi= \{0,1, \ldots , m-1 \}.\) The Metropolis chain in this case is described. Proposition 4.1 presents a formula for the variance \(\text{ Var}_{\pi}(\widehat{\mu}_{M})\) of the Metropolis estimator based on the independent proposals. The variance of the importance sampling estimator \(\text{ Var}_{\sigma}(\widehat{\mu}_{I})\) is given in explicit form. In Example 4.6 the set \(\chi\) is \(\chi= \{0,1, \ldots , m-1 \}\) and there is a special choice of the probability on \(\chi\) and a function \(f.\) Proposition 4.7 gives a formula for the variance \(\text{ Var}_{\pi}(\widehat{\mu}_{M}(f)).\) A formula for the variance \(\text{ Var}_{\sigma}(\widehat{\mu}_{I})\) of the importance sampling is presented. These results show that in this case the importance sampling and the Metropolis algorithm are roughly comparable. In Section 5 \(\chi\) is set of all monotone paths from \((0,0)\) to \((n,n).\) In this case the sequental importance sampling estimate is used. Proposition 5.3 gives the variance \(\text{ Var}_{\sigma}(\widehat{\mu}_{SIS})\) of the sequental importance sampling estimator. The details of the importance sampling and Metropolis sampling are developed. The orders of the variances \(\text{ Var}_{\sigma}(\widehat{\mu}_{SIS})\) and \(\text{ Var}_{\sigma}(\widehat{\mu}_{MET})\) are shown and the obtained orders are compared.