Fixed precision MCMC estimation by median of products of averages. (English) Zbl 1170.60327
Summary: The standard Markov chain Monte Carlo method of estimating an expected value is to generate a Markov chain which converges to the target distribution and then compute correlated sample averages. In many applications the quantity of interest \(\theta\) is represented as a product of expected values, \(\theta = \mu _{1} \dots \mu_k\), and a natural estimator is a product of averages. To increase the confidence level, we can compute a median of independent runs. The goal of this paper is to analyze such an estimator \(\hat \theta \), i.e. an estimator which is a ‘median of products of averages’ (MPA). Sufficient conditions are given for \(\hat\theta\) to have fixed relative precision at a given level of confidence, that is, to satisfy \(P(|\hat\theta- \theta | \leq \theta \varepsilon ) \geq 1 - \alpha \). Our main tool is a new bound on the mean-square error, valid also for nonreversible Markov chains on a finite state space.
MSC:
| 60J22 | Computational methods in Markov chains |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 65C05 | Monte Carlo methods |
| 68W20 | Randomized algorithms |
| 82B80 | Numerical methods in equilibrium statistical mechanics (MSC2010) |
Keywords:
Markov chain Monte Carlo; rare-event simulation; mean-square error; bias; confidence estimationReferences:
| [1] | Aldous. D. (1987). On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Prob. Eng. Inf. Sci. 1 , 33–46. · Zbl 1133.60327 · doi:10.1017/S0269964800000267 |
| [2] | Asmussen, S. (2000). Ruin Probabilities (Adv. Ser. Statist. Sci. Appl. Prob. 2 ). World Scientific, River Edge, NJ. |
| [3] | Asmussen, S. and Binswanger, K. (1997). Simulation of ruin probabilities for subexponential claims. ASTIN Bull. 27 , 297–318. |
| [4] | Asmussen, S. and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis (Stoch. Modelling Appl. Prob. 57 ). Springer, New York. · Zbl 1126.65001 |
| [5] | Asmussen, S. and Kroese, D. P. (2006). Improved algorithms for rare event simulation with heavy tails. Adv. Appl. Prob. 38 , 545–558. · Zbl 1097.65017 · doi:10.1239/aap/1151337084 |
| [6] | Bernstein, S. N. (1924). On a modification of Chebyshev’s inequality and of the error formula of Laplace. Ann. Sci. Inst. Savantes Ukraine, Sect. Math. 1 , 38–49. |
| [7] | Bremaud, P. (1999). Markov Chains . Springer, New York. |
| [8] | Diaconis, P. and Strook, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1 , 36–61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980 |
| [9] | Diaconis, P., Holmes, S. and Neal, R. M. (2000). Analysis of a nonreversible Markov chain sampler. Ann. Appl. Prob. 10 , 726–752. · Zbl 1083.60516 · doi:10.1214/aoap/1019487508 |
| [10] | Dinwoodie, I. H. (1995). A probability inequality for the occupation measure of a reversible Markov chain. Ann. Appl. Prob. 5 , 37–43. · Zbl 0829.60022 · doi:10.1214/aoap/1177004826 |
| [11] | Dyer, M. and Frieze, A. (1991). Computing the volume of convex bodies: a case where randomness provably helps. In Probabilistic Combinatorics and its Applications (Proc. AMS Symp. Appl. Math. 44 ), American Mathematical Society, Providence, RI, pp. 123–169. · Zbl 0754.68052 |
| [12] | Dyer, M., Goldberg, L. A. and Jerrum, M. (2006). Systematic scan for sampling colorings. Ann. Appl. Prob. 16 , 185–230. · Zbl 1095.60024 · doi:10.1214/105051605000000683 |
| [13] | Ferrenberg, A. M. and Swendsen, R. H. (1989). Optimized Monte Carlo data analysis. Phys. Rev. Lett. 63 , 1195–1198. |
| [14] | Fill, J. A. (1991). Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Prob. 1 , 62–87. · Zbl 0726.60069 · doi:10.1214/aoap/1177005981 |
| [15] | Gillman, D. (1998). A Chernoff bound for random walks on expander graphs. SIAM J. Comput. 27 , 1203–1220. · Zbl 0911.60016 · doi:10.1137/S0097539794268765 |
| [16] | Hartinger, J. and Kortschak, D. (2006). On the efficiency of Asmussen–Kroese-estimator and its applications to stop-loss transforms. In 6th Internat. Workshop on Rare Event Simulation (Bamberg, October 2006), pp. 162–171. · Zbl 1182.91092 |
| [17] | Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 , 13–30. JSTOR: · Zbl 0127.10602 · doi:10.2307/2282952 |
| [18] | Horn, R. and Johnson, C. R. (1985). Matrix Analysis . Cambridge University Press. · Zbl 0576.15001 |
| [19] | Jerrum, M. (2003). Counting, Sampling and Integrating: Algorithms and Complexity , Birkhäuser, Basel. · Zbl 1011.05001 |
| [20] | Jerrum, M. and Sinclair, A. (1993). Polynomial-time approximation algorithms for the Ising model. SIAM. J. Comput. 22 , 1087–1116. · Zbl 0782.05076 · doi:10.1137/0222066 |
| [21] | Jerrum, M. and Sinclair, A. (1996). The Markov chain Monte Carlo method: an approach to approximate counting and integration, In Approximation Algorithms for NP-hard Problems , ed. D. Hochbaum, PWS, Boston, pp. 482–520. |
| [22] | Jerrum, M., Sinclair, A. and Vigoda, E. (2004). A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. Assoc. Comput. Mach. 51 , 671–697. · Zbl 1204.65044 · doi:10.1145/1008731.1008738 |
| [23] | Jerrum, M. R., Valiant, L. G. and Vazirani, V. V. (1986). Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 , 169–188. · Zbl 0597.68056 · doi:10.1016/0304-3975(86)90174-X |
| [24] | Lezaud, P. (1998). Chernoff-type bound for finite Markov chains. Ann. Appl. Prob. 8 , 849–867. · Zbl 0938.60027 · doi:10.1214/aoap/1028903453 |
| [25] | Niemiro, W. (2008). Nonasymptotic bounds on the estimation error for regenerative MCMC algorithm under a drift condition. Submitted. |
| [26] | Newman, M. E. J. and Barkema, G. T. (1999). Monte Carlo Methods in Statistical Physics. Clarendon Press, New York. · Zbl 1012.82019 |
| [27] | Pokarowski, P., Droste, K. and Kolinski, A. (2005). A minimal protein-like lattice model: an alpha-helix motif. J. Chem. Phys. 122 , 214915. |
| [28] | Pokarowski, P., Kolinski, A. and Skolnick, J. (2003). A minimal physically realistic protein-like lattice model: designing an energy landscape that ensures all-or-none folding to a unique native state. Biophysical J. 84 , 1518–1526. |
| [29] | Sandman, W. (ed.) (2006). Proceedings of the 6th International Workshop on Rare Event Simulation (Bamberg, October 2006), University of Bamberg, Germany. |
| [30] | Sinclair, A. J. and Jerrum, M. R. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82 , 93–133. · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9 |
| [31] | Sokal, A. D. (1989). Monte Carlo methods in statistical mechanics: foundations and new algorithm. Lecture Notes: Cours de Troisieme Cycle de la Physique en Suisse Romande (Lausanne, June 1989). Unpublished manuscript. · Zbl 0890.65006 |
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.
