×

Rigorous confidence bounds for MCMC under a geometric drift condition. (English) Zbl 1210.65004

A Markov Chain Monte Carlo (MCMC) approximation \(\hat I_{t,n}(f)={1\over n}\sum_{i=t}^{t+n-1}f(X_i)\) is considered for \(I(f)=\int f(x)\pi(dx)\), where \(X_i\) is a Markov chain with a transition kernel \(P\) and the stationary distribution \(\pi\), \(t\) is the burn-in time.
The authors derive explicit lower bounds for \(n\) and \(t\) that ensure the condition \(\Pr(|\hat I_{t,n}(f)-I(f)|\leq\varepsilon)\geq 1-\alpha\) for given \(\varepsilon\) and \(\alpha\). The bounds are given in terms of a drift condition towards a small set on the chain and in terms of the \(V\)-norm \(|\cdot|_V\) of the function \(f-I(f)\), where \(V\) is the drift function and \(|g|_V=\sup_x |g(x)|/V(x)\). In fact, some bounds are obtained for the mean square error of \(\hat I_{t,n}(f)\) and then Chebyshev’s inequality is used to derive the desired estimates for the probabilities.
The so called “median trick” is considered to minimize the computational cost. In this technique \(m\) independent copies of \(\hat I_{t,n}\) are simulated and their median is used as an estimate for \(I(f)\).
A “contracting normals” example is investigated numerically in which e.g. for \(\varepsilon=0.1\), \(\alpha=10^{-3}\) the authors obtained the estimates \(m=15\), \(n=5.4\cdot 10^9\), \(t=218\). It is noted that in real simulations it was enough to let \(m=7\), \(t=0\), \(n=726\), so the obtained bounds are “admittedly conservative”.

MSC:

65C05 Monte Carlo methods
65C40 Numerical analysis or methods applied to Markov chains
60J22 Computational methods in Markov chains
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adamczak, R., A tail inequality for suprema of unbounded empirical processes with applications to Markov chains, Electron. J. Probab., 34, 1000-1034 (2008) · Zbl 1190.60010
[2] Aldous, D., On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing, Probab. Engrg. Inform. Sci., 1, 33-46 (1987) · Zbl 1133.60327
[3] Baxendale, P. H., Renewal theory and computable convergence rates for geometrically ergodic Markov Chains, Ann. Appl. Probab., 15, 700-738 (2005) · Zbl 1070.60061
[4] W. Bednorz, On the Kendall Theorem and its application to the geometric ergodicity of Markov chains, 2010 (preprint).; W. Bednorz, On the Kendall Theorem and its application to the geometric ergodicity of Markov chains, 2010 (preprint). · Zbl 1274.60237
[5] Bednorz, W.; Łatuszyński, K., A few remarks on “Fixed-width output analysis for Markov Chain Monte Carlo” by Jones et al., J. Amer. Statist. Assoc., 102, 480, 1485-1486 (2007)
[6] Bednorz, W.; Latała, R.; Łatuszyński, K., A regeneration proof of the Central Limit Theorem for uniformly ergodic Markov chains, Electron. Comm. Probab., 13, 85-98 (2008) · Zbl 1194.60046
[7] Bertail, P.; Clémençon, S. J.M., Regeneration-based statistics for Harris recurrent Markov chains, (Lecture Notes in Statistics, vol. 187 (2006), Springer), 1-54 · Zbl 1118.62086
[8] Bertail, P.; Clémençon, S. J.M., Sharp bounds for the tails of functionals of Harris Markov chains, Theory Probab. Appl., 54, 3, 1-19 (2009)
[9] Casella, G.; Robert, C. P., Monte Carlo Statistical Methods (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0935.62005
[10] Chan, K. S.; Yue, H., Asymptotic efficiency of the sample mean in Markov Chain Monte Carlo schemes, J. Roy. Statist. Soc. Ser. B, 58, 3, 525-539 (1996) · Zbl 0855.62070
[11] Clémençon, S. J.M., Moment and probability inequalities for sums of bounded functionals of regular Markov chains via the Nummelin splitting technique, Statist. Probab. Lett., 55, 227-238 (2001) · Zbl 1078.60508
[12] Diaconis, P.; Khare, K.; Saloff-Coste, L., Gibbs sampling, exponential families and orthogonal polynomials (with discussion and rejoinder), Statist. Sci., 23, 2, 151-178 (2008) · Zbl 1327.62058
[13] Douc, R.; Guillin, A.; Moulines, E., Bounds on regeneration times and limit theorems for subgeometric Markov chains, Ann. Inst. H. Poincaré Probab. Statist., 44, 239-257 (2008) · Zbl 1176.60063
[14] Douc, R.; Moulines, E.; Rosenthal, J. S., Quantitative bounds on convergence of time-inhomogeneous Markov chains, Ann. Appl. Probab., 14, 1643-1665 (2003) · Zbl 1072.60059
[15] Flegal, J. M.; Jones, G. L., Batch means and spectral variance estimators in Markov Chain Monte Carlo, Ann. Statist., 38, 2, 1034-1070 (2010) · Zbl 1184.62161
[16] Fort, G.; Moulines, E.; Roberts, G. O.; Rosenthal, J. S., On geometric ergodicity of hybrid samplers, J. Appl. Probab., 40, 1, 123-146 (2003) · Zbl 1028.65002
[17] G. Fort, Computable bounds for V-geometric ergodicity of Markov transition kernels, 2002 (preprint).; G. Fort, Computable bounds for V-geometric ergodicity of Markov transition kernels, 2002 (preprint).
[18] Geyer, C. J., Practical Markov Chain Monte Carlo, Statist. Sci., 7, 4, 473-511 (1992)
[19] Gilks, W. R.; Roberts, G. O.; Sahu, S. K., Adaptive Markov Chain Monte Carlo through regeneration, J. Amer. Statist. Assoc., 93, 443, 1045-1054 (1998) · Zbl 1064.65503
[20] Gillman, D., A Chernoff bound for random walks on expander graphs, SIAM J. Comput., 27, 4, 1203-1220 (1998) · Zbl 0911.60016
[21] Glynn, P. W.; Ormoneit, D., Hoeffding’s inequality for uniformly ergodic Markov chains, Statist. Probab. Lett., 56, 143-146 (2002) · Zbl 0999.60019
[22] Hobert, J. P.; Jones, G. L., Honest exploration of intractable probability distributions via Markov Chain Monte Carlo, Statist. Sci., 16, 4, 312-334 (2001) · Zbl 1127.60309
[23] Jerrum, M. R.; Valiant, L. G.; Vizirani, V. V., Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci., 43, 169-188 (1986) · Zbl 0597.68056
[24] A.A. Johnson, G.L. Jones, Gibbs sampling for a Bayesian hierarchical version of the general linear mixed model, 2007 (preprint) arXiv:0712.3056v3; A.A. Johnson, G.L. Jones, Gibbs sampling for a Bayesian hierarchical version of the general linear mixed model, 2007 (preprint) arXiv:0712.3056v3
[25] Johnson, A. A.; Jones, G. L., Gibbs sampling for a Bayesian hierarchical general linear model, Electron. J. Stat., 4, 313-333 (2010) · Zbl 1329.62336
[26] Jones, G. L., On the Markov chain Central Limit Theorem, Probab. Surv., 1, 299-320 (2005) · Zbl 1189.60129
[27] Jones, G. L.; Haran, M.; Caffo, B. S.; Neath, R., Fixed-width output analysis for Markov chain Monte Carlo, J. Amer. Statist. Assoc., 101, 1537-1547 (2006) · Zbl 1171.62316
[28] Jones, G. L.; Hobert, J. P., Sufficient burn-in for Gibbs samplers for a hierarchical random effects model, Ann. Statist., 32, 2, 784-817 (2004) · Zbl 1048.62069
[29] K. Łatuszyński, Regeneration and fixed-width analysis of Markov Chain Monte Carlo algorithms, Ph.D. Dissertation, 2008. Available at: arXiv:0907.4716v1; K. Łatuszyński, Regeneration and fixed-width analysis of Markov Chain Monte Carlo algorithms, Ph.D. Dissertation, 2008. Available at: arXiv:0907.4716v1
[30] K. Łatuszyński, B. Miasojedow, W. Niemiro, Nonasymptotic bounds on the estimation error for regenerative MCMC algorithms, 2009 (submitted for publication) arXiv:0907.4915v1; K. Łatuszyński, B. Miasojedow, W. Niemiro, Nonasymptotic bounds on the estimation error for regenerative MCMC algorithms, 2009 (submitted for publication) arXiv:0907.4915v1
[31] Marchev, D.; Hobert, J. P., Geometric ergodicity of van Dyk and Meng’s Algorithm for the multivariate Student’s \(t\) model, J. Amer. Statist. Assoc., 99, 228-238 (2004) · Zbl 1089.60518
[32] I. Kontoyiannis, L. Lastras-Montano, S.P. Meyn, Relative entropy and exponential deviation bounds for general Markov chains, in: 2005 IEEE International Symposium on Information Theory, 2005.; I. Kontoyiannis, L. Lastras-Montano, S.P. Meyn, Relative entropy and exponential deviation bounds for general Markov chains, in: 2005 IEEE International Symposium on Information Theory, 2005.
[33] León, C. A.; Perron, F., Optimal Chernoff bounds for finite reversible Markov chains, Ann. Appl. Probab., 14, 958-970 (2004) · Zbl 1056.60070
[34] Liu, J. S., Monte Carlo Strategies in Scientific Computing (2001), Springer · Zbl 0991.65001
[35] Mathé, P., Numerical integration using \(V\)-uniformly ergodic Markov chains, J. Appl. Probab., 41, 1104-1112 (2004) · Zbl 1076.65004
[36] Mathé, P.; Novak, E., Simple Monte Carlo and the Metropolis algorithm, J. Complexity, 23, 673-696 (2007) · Zbl 1132.65004
[37] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E., Equations of state calculations by fast computing machines, J. Chem. Phys., 21, 1087-1091 (1953) · Zbl 1431.65006
[38] Meyn, S. P.; Tweedie, R. L., Markov Chains and Stochastic Stability (1993), Springer-Verlag · Zbl 0925.60001
[39] Niemiro, W.; Pokarowski, P., Fixed precision MCMC estimation by median of products of averages, J. Appl. Probab., 46, 2, 309-329 (2009) · Zbl 1170.60327
[40] Novak, E., On the power of adaption, J. Complexity, 11, 199-237 (1996) · Zbl 0870.65042
[41] Randall, D., Rapidly mixing Markov chains with applications in computer science and physics, Comput. Sci. Eng., 8, 2, 30-41 (2006)
[42] Roberts, G. O.; Rosenthal, J. S., General state space Markov chains and MCMC algorithms, Probab. Surv., 1, 20-71 (2005) · Zbl 1189.60131
[43] Roberts, G. O.; Rosenthal, J. S., Shift-coupling and convergence rates of ergodic averages, Comm. Statist. Stoch. Models, 13, 147-165 (1997) · Zbl 0871.60046
[44] Roberts, G. O.; Tweedie, R. L., Bounds on regeneration times and convergence rates for Markov chains, Stochastic Process. Appl., 91, 337-338 (1999) · Zbl 1047.60072
[45] Rosenthal, J. S., Minorization conditions and convergence rates for Markov Chain Monte Carlo, J. Amer. Statist. Assoc., 90, 558-566 (1995) · Zbl 0824.60077
[46] Rosenthal, J. S., Rates of convergence for Gibbs sampling for variance component models, Ann. Statist., 23, 740-761 (1995) · Zbl 0841.62074
[47] Roy, V.; Hobert, J. P., On Monte Carlo methods for Bayesian multivariate regression models with heavy-tailed errors, J. Multivariate Anal., 5, 1190-1202 (2009) · Zbl 1184.62040
[48] Rudolf, D., Explicit error bounds for lazy reversible Markov Chain Monte Carlo, J. Complexity, 25, 11-24 (2008) · Zbl 1160.65004
[49] Sahu, S. K.; Zhigljavsky, A. A., Self-regenerative Markov chain Monte Carlo with adaptation, Bernoulli, 9, 395-422 (2003) · Zbl 1044.62033
[50] Tan, A.; Hobert, J. P., Block Gibbs sampling for Bayesian random effects models with improper priors: convergence and regeneration, J. Comput. Graph. Statist., 4, 861-878 (2009)
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.