First hitting time analysis of the independence Metropolis sampler. (English) Zbl 1104.60043
Summary: We study a special case of the Metropolis algorithm, the Independence Metropolis Sampler (IMS), in the finite state space case. The IMS is often used in designing components of more complex Markov Chain Monte Carlo algorithms. We present new results related to the first hitting time of individual states for the IMS. These results are expressed mostly in terms of the eigenvalues of the transition kernel. We derive a simple form formula for the mean first hitting time and we show tight lower and upper bounds on the mean first hitting time with the upper bound being the product of two factors: a “local” factor corresponding to the target state and a “global” factor, common to all the states, which is expressed in terms of the total variation distance between the target and the proposal probabilities. We also briefly discuss properties of the distribution of the first hitting time for the IMS and analyze its variance. We conclude by showing how some non-independence Metropolis-Hastings algorithms can perform better than the IMS and deriving general lower and upper bounds for the mean first hitting times of a Metropolis-Hastings algorithm.
MSC:
| 60J22 | Computational methods in Markov chains |
References:
| [1] | Abadi M., Galves A. (2001). Inequalities for the occurrence times of rare events in mixing processes. The state of the art. Markov Proc. Relat. Fields 7, 97–112 · Zbl 0973.60035 |
| [2] | Bremaud P. (1999). Markov Chains: Gibbs Fields, Monte Carlo Simulation and Queues, Springer, New York |
| [3] | Diaconis P., Hanlon P. (1992). Eigen analysis for some examples of the Metropolis algorithm. Contem. Math. 138, 99–117 · Zbl 0789.05091 |
| [4] | Hastings W.K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 97–109 · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97 |
| [5] | Kemeny J.G., Snell J.L. (1976). Finite Markov Chains, Springer Verlag. · Zbl 0328.60035 |
| [6] | Liu, J. S. (1996). Metropolized Gibbs Sampler: An Improvement, Technical report, Dept. Statistics, Stanford Univ. |
| [7] | Liu J.S. (1996), Metropolized independence sampling with comparisons to rejection sampling and importance sampling. Stat. Comput. 6, 113–119 · doi:10.1007/BF00162521 |
| [8] | Mengersen K.L., Tweedie R.L. (1994). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Stat. 24, 101–121 · Zbl 0854.60065 |
| [9] | Mira A. (2002). Ordering and improving the performance of Monte Carlo Markov Chains. Stat. Sci. 16, 340–350 · Zbl 1127.60312 · doi:10.1214/ss/1015346319 |
| [10] | Smith, R. L., and Tierney, L. (1996). Exact Transition Probabilities for Metropolized Independence Sampling, Technical Report, Dept. of Statistics, Univ. of North Carolina. |
| [11] | Tu, Z. W., and Zhu, S. C. (2006). Parsing Images into Regions, Curves, and Curve Groups. Int. J. Comput. Vision (accepted). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
