Efficient shape-constrained inference for the autocovariance sequence from a reversible Markov chain. (English) Zbl 1539.62078
Summary: In this paper, we study the problem of estimating the autocovariance sequence resulting from a reversible Markov chain. A motivating application for studying this problem is the estimation of the asymptotic variance in central limit theorems for Markov chains. We propose a novel shape-constrained estimator of the autocovariance sequence, which is based on the key observation that the representability of the autocovariance sequence as a moment sequence imposes certain shape constraints. We examine the theoretical properties of the proposed estimator and provide strong consistency guarantees for our estimator. In particular, for geometrically ergodic reversible Markov chains, we show that our estimator is strongly consistent for the true autocovariance sequence with respect to an \(\ell_2\) distance, and that our estimator leads to strongly consistent estimates of the asymptotic variance. Finally, we perform empirical studies to illustrate the theoretical properties of the proposed estimator as well as to demonstrate the effectiveness of our estimator in comparison with other current state-of-the-art methods for Markov chain Monte Carlo variance estimation, including batch means, spectral variance estimators, and the initial convex sequence estimator.
MSC:
| 62G05 | Nonparametric estimation |
| 60J05 | Discrete-time Markov processes on general state spaces |
| 60J22 | Computational methods in Markov chains |
| 65C05 | Monte Carlo methods |
| 62M10 | Time series, auto-correlation, regression, etc. in statistics (GARCH) |
| 62M15 | Inference from stochastic processes and spectral analysis |
Keywords:
Markov chain Monte Carlo; shape-constrained inference; asymptotic variance; autocovariance sequence estimationReferences:
| [1] | Albert, J. H. and Chib, S. (1993). Bayesian analysis of binary and polychotomous response data. J. Amer. Statist. Assoc. 88 669-679. MathSciNet: MR1224394 · Zbl 0774.62031 |
| [2] | AN, H. Z., CHEN, Z. G. and HANNAN, E. J. (1982). Autocorrelation, autoregression and autoregressive approximation. Ann. Statist. 10 926-936. MathSciNet: MR0663443 · Zbl 0512.62087 |
| [3] | ANDERSON, T. W. (1971). The Statistical Analysis of Time Series. Wiley, New York. MathSciNet: MR0283939 · Zbl 0225.62108 |
| [4] | BALABDAOUI, F. and DE FOURNAS-LABROSSE, G. (2020). Least squares estimation of a completely monotone pmf: From analysis to statistics. J. Statist. Plann. Inference 204 55-71. Digital Object Identifier: 10.1016/j.jspi.2019.04.006 Google Scholar: Lookup Link MathSciNet: MR3961929 · Zbl 1421.62034 · doi:10.1016/j.jspi.2019.04.006 |
| [5] | BALABDAOUI, F. and DUROT, C. (2015). Marshall lemma in discrete convex estimation. Statist. Probab. Lett. 99 143-148. Digital Object Identifier: 10.1016/j.spl.2015.01.016 Google Scholar: Lookup Link MathSciNet: MR3321508 · Zbl 1331.62252 · doi:10.1016/j.spl.2015.01.016 |
| [6] | Balabdaoui, F. and Wellner, J. A. (2007). Estimation of a \(k\)-monotone density: Limit distribution theory and the spline connection. Ann. Statist. 35 2536-2564. Digital Object Identifier: 10.1214/009053607000000262 Google Scholar: Lookup Link MathSciNet: MR2382657 · Zbl 1129.62019 · doi:10.1214/009053607000000262 |
| [7] | BARLOW, R. E., BARTHOLOMEW, D. J., BREMNER, J. M. and BRUNK, H. D. (1972). Statistical Inference Under Order Restrictions. The Theory and Application of Isotonic Regression. Wiley Series in Probability and Mathematical Statistics. Wiley, London-Sydney. MathSciNet: MR0326887 · Zbl 0246.62038 |
| [8] | BEDNORZ, W. and ŁATUSZYŃSKI, K. (2007). A few remarks on “Fixed-width output analysis for Markov chain Monte Carlo” by Jones et al. J. Amer. Statist. Assoc. 102 1485-1486. Digital Object Identifier: 10.1198/016214507000000914 Google Scholar: Lookup Link MathSciNet: MR2412582 · doi:10.1198/016214507000000914 |
| [9] | BERG, S. and SONG, H. (2023). Supplement to “Efficient shape-constrained inference for the autocovariance sequence from a reversible Markov chain.” https://doi.org/10.1214/23-AOS2335SUPP |
| [10] | BROCKWELL, P. J. and DAVIS, R. A. (2009). Time Series: Theory and Methods. Springer, Berlin. · Zbl 1169.62074 |
| [11] | BROOKS, S., GELMAN, A., JONES, G. L. and MENG, X.-L., eds. (2011). Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC Handbooks of Modern Statistical Methods. CRC Press, Boca Raton, FL. Digital Object Identifier: 10.1201/b10905 Google Scholar: Lookup Link MathSciNet: MR2742422 · Zbl 1218.65001 · doi:10.1201/b10905 |
| [12] | CHAKRABORTY, S., BHATTACHARYA, S. K. and KHARE, K. (2022). Estimating accuracy of the MCMC variance estimator: Asymptotic normality for batch means estimators. Statist. Probab. Lett. 183 109337. Digital Object Identifier: 10.1016/j.spl.2021.109337 Google Scholar: Lookup Link MathSciNet: MR4363701 · Zbl 1489.62086 · doi:10.1016/j.spl.2021.109337 |
| [13] | CHAKRABORTY, S. and KHARE, K. (2017). Convergence properties of Gibbs samplers for Bayesian probit regression with proper priors. Electron. J. Stat. 11 177-210. Digital Object Identifier: 10.1214/16-EJS1219 Google Scholar: Lookup Link MathSciNet: MR3604022 · Zbl 1366.60093 · doi:10.1214/16-EJS1219 |
| [14] | CHANDLER, J. D. JR. (1988). Moment problems for compact sets. Proc. Amer. Math. Soc. 104 1134-1140. Digital Object Identifier: 10.2307/2047604 Google Scholar: Lookup Link MathSciNet: MR0942632 · Zbl 0692.44006 · doi:10.2307/2047604 |
| [15] | CHEE, C.-S. and WANG, Y. (2016). Nonparametric estimation of species richness using discrete \(k\)-monotone distributions. Comput. Statist. Data Anal. 93 107-118. Digital Object Identifier: 10.1016/j.csda.2014.10.021 Google Scholar: Lookup Link MathSciNet: MR3406199 · Zbl 1468.62036 · doi:10.1016/j.csda.2014.10.021 |
| [16] | Dai, N. and Jones, G. L. (2017). Multivariate initial sequence estimators in Markov chain Monte Carlo. J. Multivariate Anal. 159 184-199. Digital Object Identifier: 10.1016/j.jmva.2017.05.009 Google Scholar: Lookup Link MathSciNet: MR3668555 · Zbl 1373.62249 · doi:10.1016/j.jmva.2017.05.009 |
| [17] | DAMERDJI, H. (1991). Strong consistency and other properties of the spectral variance estimator. Manage. Sci. 37 1424-1440. · Zbl 0741.62086 |
| [18] | DÜMBGEN, L. and RUFIBACH, K. (2011). Logcondens: Computations related to univariate log-concave density estimation. J. Stat. Softw. 39 1-28. |
| [19] | DURMUS, A., GRUFFAZ, S., KAILAS, M., SAKSMAN, E. and VIHOLA, M. (2023). On the convergence of dynamic implementations of Hamiltonian Monte Carlo and No U-Turn Samplers. ArXiv preprint. Available at arXiv:2307.03460. |
| [20] | DUROT, C., HUET, S., KOLADJO, F. and ROBIN, S. (2015). Nonparametric species richness estimation under convexity constraint. Environmetrics 26 502-513. Digital Object Identifier: 10.1002/env.2352 Google Scholar: Lookup Link MathSciNet: MR3415569 · Zbl 1525.62103 · doi:10.1002/env.2352 |
| [21] | FELLER, W. (1939). Completely monotone functions and sequences. Duke Math. J. 5 661-674. MathSciNet: MR0000315 · Zbl 0022.23001 |
| [22] | Flegal, J. M. and Gong, L. (2015). Relative fixed-width stopping rules for Markov chain Monte Carlo simulations. Statist. Sinica 25 655-675. MathSciNet: MR3379093 · Zbl 1534.62122 |
| [23] | Flegal, J. M., Haran, M. and Jones, G. L. (2008). Markov chain Monte Carlo: Can we trust the third significant figure? Statist. Sci. 23 250-260. Digital Object Identifier: 10.1214/08-STS257 Google Scholar: Lookup Link MathSciNet: MR2516823 · Zbl 1327.62017 · doi:10.1214/08-STS257 |
| [24] | FLEGAL, J. M., HUGHES, J., VATS, D., DAI, N., GUPTA, K. and MAJI, U. (2021). mcmcse: Monte Carlo Standard Errors for MCMC, Riverside, CA, and Kanpur, India. R package version 1.5-0. |
| [25] | Flegal, J. M. and Jones, G. L. (2010). Batch means and spectral variance estimators in Markov chain Monte Carlo. Ann. Statist. 38 1034-1070. Digital Object Identifier: 10.1214/09-AOS735 Google Scholar: Lookup Link MathSciNet: MR2604704 · Zbl 1184.62161 · doi:10.1214/09-AOS735 |
| [26] | Folland, G. B. (1999). Real Analysis: Modern Techniques and Their Applications, 2nd ed. Pure and Applied Mathematics (New York). Wiley, New York. MathSciNet: MR1681462 · Zbl 0924.28001 |
| [27] | GEYER, C. J. (1992). Practical Markov chain Monte Carlo. Statist. Sci. 7 473-483. |
| [28] | GEYER, C. J. and JOHNSON, L. T. (2020). mcmc: Markov Chain Monte Carlo. R package version 0.9-7. |
| [29] | GIGUELAY, J. (2017). Estimation of a discrete probability under constraint of \(k\)-monotonicity. Electron. J. Stat. 11 1-49. Digital Object Identifier: 10.1214/16-EJS1220 Google Scholar: Lookup Link MathSciNet: MR3592697 · Zbl 1357.62164 · doi:10.1214/16-EJS1220 |
| [30] | GLYNN, P. W. and WHITT, W. (1992). The asymptotic validity of sequential stopping rules for stochastic simulations. Ann. Appl. Probab. 2 180-198. MathSciNet: MR1143399 · Zbl 0792.68200 |
| [31] | GRENANDER, U. (1956). On the theory of mortality measurement. Scand. Actuar. J. 1956 70-96. · Zbl 0073.15404 |
| [32] | GROENEBOOM, P., JONGBLOED, G. and WELLNER, J. A. (2008). The support reduction algorithm for computing non-parametric function estimates in mixture models. Scand. J. Stat. 35 385-399. Digital Object Identifier: 10.1111/j.1467-9469.2007.00588.x Google Scholar: Lookup Link MathSciNet: MR2446726 · Zbl 1199.65017 · doi:10.1111/j.1467-9469.2007.00588.x |
| [33] | HÄGGSTRÖM, O. and ROSENTHAL, J. S. (2007). On variance conditions for Markov chain CLTs. Electron. Commun. Probab. 12 454-464. Digital Object Identifier: 10.1214/ECP.v12-1336 Google Scholar: Lookup Link MathSciNet: MR2365647 · Zbl 1191.60082 · doi:10.1214/ECP.v12-1336 |
| [34] | Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 97-109. Digital Object Identifier: 10.1093/biomet/57.1.97 Google Scholar: Lookup Link MathSciNet: MR3363437 · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97 |
| [35] | HAUSDORFF, F. (1921). Summationsmethoden und Momentfolgen. I. Math. Z. 9 74-109. Digital Object Identifier: 10.1007/BF01378337 Google Scholar: Lookup Link MathSciNet: MR1544453 · JFM 48.2005.01 · doi:10.1007/BF01378337 |
| [36] | JANKOWSKI, H. K. and WELLNER, J. A. (2009). Estimation of a discrete monotone distribution. Electron. J. Stat. 3 1567-1605. Digital Object Identifier: 10.1214/09-EJS526 Google Scholar: Lookup Link MathSciNet: MR2578839 · Zbl 1326.62038 · doi:10.1214/09-EJS526 |
| [37] | JARNER, S. F. and HANSEN, E. (2000). Geometric ergodicity of Metropolis algorithms. Stochastic Process. Appl. 85 341-361. Digital Object Identifier: 10.1016/S0304-4149(99)00082-4 Google Scholar: Lookup Link MathSciNet: MR1731030 · Zbl 0997.60070 · doi:10.1016/S0304-4149(99)00082-4 |
| [38] | JARNER, S. F. and TWEEDIE, R. L. (2003). Necessary conditions for geometric and polynomial ergodicity of random-walk-type Markov chains. Bernoulli 9 559-578. Digital Object Identifier: 10.3150/bj/1066223269 Google Scholar: Lookup Link MathSciNet: MR1996270 · doi:10.3150/bj/1066223269 |
| [39] | JEWELL, N. P. (1982). Mixtures of exponential distributions. Ann. Statist. 10 479-484. MathSciNet: MR0653523 · Zbl 0495.62042 |
| [40] | JOHNSON, L. T. and GEYER, C. J. (2012). Variable transformation to obtain geometric ergodicity in the random-walk Metropolis algorithm. Ann. Statist. 40 3050-3076. Digital Object Identifier: 10.1214/12-AOS1048 Google Scholar: Lookup Link MathSciNet: MR3097969 · Zbl 1297.60052 · doi:10.1214/12-AOS1048 |
| [41] | Jones, G. L. (2004). On the Markov chain central limit theorem. Probab. Surv. 1 299-320. Digital Object Identifier: 10.1214/154957804100000051 Google Scholar: Lookup Link MathSciNet: MR2068475 · Zbl 1189.60129 · doi:10.1214/154957804100000051 |
| [42] | Jones, G. L., Haran, M., Caffo, B. S. and Neath, R. (2006). Fixed-width output analysis for Markov chain Monte Carlo. J. Amer. Statist. Assoc. 101 1537-1547. Digital Object Identifier: 10.1198/016214506000000492 Google Scholar: Lookup Link MathSciNet: MR2279478 · Zbl 1171.62316 · doi:10.1198/016214506000000492 |
| [43] | JONES, G. L. and QIN, Q. (2022). Markov chain Monte Carlo in practice. Annu. Rev. Stat. Appl. 9 557-578. Digital Object Identifier: 10.1146/annurev-statistics-040220-090158 Google Scholar: Lookup Link MathSciNet: MR4394920 · doi:10.1146/annurev-statistics-040220-090158 |
| [44] | KAVALIERIS, L. (2008). Uniform convergence of autocovariances. Statist. Probab. Lett. 78 830-838. Digital Object Identifier: 10.1016/j.spl.2007.07.027 Google Scholar: Lookup Link MathSciNet: MR2409548 · Zbl 1489.62280 · doi:10.1016/j.spl.2007.07.027 |
| [45] | Kontoyiannis, I. and Meyn, S. P. (2012). Geometric ergodicity and the spectral gap of non-reversible Markov chains. Probab. Theory Related Fields 154 327-339. Digital Object Identifier: 10.1007/s00440-011-0373-4 Google Scholar: Lookup Link MathSciNet: MR2981426 · Zbl 1263.60064 · doi:10.1007/s00440-011-0373-4 |
| [46] | Kosorok, M. R. (2000). Monte Carlo error estimation for multivariate Markov chains. Statist. Probab. Lett. 46 85-93. Digital Object Identifier: 10.1016/S0167-7152(99)00090-5 Google Scholar: Lookup Link MathSciNet: MR1731349 · Zbl 0978.62071 · doi:10.1016/S0167-7152(99)00090-5 |
| [47] | KREĬN, M. G. and NUDEL’MAN, A. A. (1977). The Markov Moment Problem and Extremal Problems: Ideas and Problems of P. L. Cebysev and A. A. Markov and Their Further Development. Translations of Mathematical Monographs 50. Amer. Math. Soc., Providence, RI. MathSciNet: MR0458081 · Zbl 0361.42014 |
| [48] | KUCHIBHOTLA, A. K., PATRA, R. K. and SEN, B. (2023). Semiparametric efficiency in convexity constrained single-index model. J. Amer. Statist. Assoc. 118 272-286. Digital Object Identifier: 10.1080/01621459.2021.1927741 Google Scholar: Lookup Link MathSciNet: MR4571121 · Zbl 1514.62064 · doi:10.1080/01621459.2021.1927741 |
| [49] | LATUSZYNSKI, K. (2009). Regeneration and fixed-width analysis of Markov chain Monte Carlo algorithms. |
| [50] | LEFÈVRE, C. and LOISEL, S. (2013). On multiply monotone distributions, continuous or discrete, with applications. J. Appl. Probab. 50 827-847. Digital Object Identifier: 10.1239/jap/1378401239 Google Scholar: Lookup Link MathSciNet: MR3102517 · Zbl 1293.62028 · doi:10.1239/jap/1378401239 |
| [51] | LINDSAY, B. G. (1983). The geometry of mixture likelihoods: A general theory. Ann. Statist. 11 86-94. Digital Object Identifier: 10.1214/aos/1176346059 Google Scholar: Lookup Link MathSciNet: MR0684866 · Zbl 0512.62005 · doi:10.1214/aos/1176346059 |
| [52] | Liu, J. S., Wong, W. H. and Kong, A. (1994). Covariance structure of the Gibbs sampler with applications to the comparisons of estimators and augmentation schemes. Biometrika 81 27-40. MathSciNet: MR1279653 · Zbl 0811.62080 |
| [53] | LIU, Y., VATS, D. and FLEGAL, J. M. (2022). Batch size selection for variance estimators in MCMC. Methodol. Comput. Appl. Probab. 24 65-93. Digital Object Identifier: 10.1007/s11009-020-09841-7 Google Scholar: Lookup Link MathSciNet: MR4379481 · Zbl 1493.62130 · doi:10.1007/s11009-020-09841-7 |
| [54] | Livingstone, S., Betancourt, M., Byrne, S. and Girolami, M. (2019). On the geometric ergodicity of Hamiltonian Monte Carlo. Bernoulli 25 3109-3138. Digital Object Identifier: 10.3150/18-BEJ1083 Google Scholar: Lookup Link MathSciNet: MR4003576 MathSciNet: MR3211026 · Zbl 1428.62375 · doi:10.3150/18-BEJ1083 |
| [55] | Mengersen, K. L. and Tweedie, R. L. (1996). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Statist. 24 101-121. Digital Object Identifier: 10.1214/aos/1033066201 Google Scholar: Lookup Link MathSciNet: MR1389882 · doi:10.1214/aos/1033066201 |
| [56] | Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E. (1953). Equation of state calculations by fast computing machines. J. Chem. Phys. 21 1087-1092. · Zbl 1431.65006 |
| [57] | Meyn, S. and Tweedie, R. L. (2009). Markov Chains and Stochastic Stability, 2nd ed. Cambridge Univ. Press, Cambridge. Digital Object Identifier: 10.1017/CBO9780511626630 Google Scholar: Lookup Link MathSciNet: MR2509253 · Zbl 1165.60001 · doi:10.1017/CBO9780511626630 |
| [58] | POLITIS, D. N. (2003). Adaptive bandwidth choice. J. Nonparametr. Stat. 15 517-533. Digital Object Identifier: 10.1080/10485250310001604659 Google Scholar: Lookup Link MathSciNet: MR2017485 · Zbl 1054.62038 · doi:10.1080/10485250310001604659 |
| [59] | PRIESTLEY, M. B. (1981). Spectral Analysis and Time Series. Probability and Mathematical Statistics: A Series of Monographs and Textbooks Bd. 1-2. Academic Press, San Diego. · Zbl 0537.62075 |
| [60] | R Core Team (2020). R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. |
| [61] | Robert, C. P. and Casella, G. (2004). Monte Carlo Statistical Methods, 2nd ed. Springer Texts in Statistics. Springer, New York. Digital Object Identifier: 10.1007/978-1-4757-4145-2 Google Scholar: Lookup Link MathSciNet: MR2080278 · Zbl 1096.62003 · doi:10.1007/978-1-4757-4145-2 |
| [62] | Roberts, G. O. and Rosenthal, J. S. (1997). Geometric ergodicity and hybrid Markov chains. Electron. Commun. Probab. 2 13-25. Digital Object Identifier: 10.1214/ECP.v2-981 Google Scholar: Lookup Link MathSciNet: MR1448322 · Zbl 0890.60061 · doi:10.1214/ECP.v2-981 |
| [63] | ROBERTS, G. O. and ROSENTHAL, J. S. (1998). Markov-chain Monte Carlo: Some practical implications of theoretical results. Canad. J. Statist. 5-20. · Zbl 0920.62105 |
| [64] | Roberts, G. O. and Tweedie, R. L. (1996). Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83 95-110. Digital Object Identifier: 10.1093/biomet/83.1.95 Google Scholar: Lookup Link MathSciNet: MR1399158 · Zbl 0888.60064 · doi:10.1093/biomet/83.1.95 |
| [65] | ROBERTSON, T. (1988). Order restricted statistical inference Technical Report. · Zbl 0645.62028 |
| [66] | RUDIN, W. (1991). Functional Analysis, 2nd ed. International Series in Pure and Applied Mathematics. McGraw-Hill, New York. MathSciNet: MR1157815 · Zbl 0867.46001 |
| [67] | SCHMÜDGEN, K. (2017). The Moment Problem. Graduate Texts in Mathematics 277. Springer, Cham. MathSciNet: MR3729411 |
| [68] | STAN DEVELOPMENT TEAM (2019). Stan Reference Manual, Version 2.28. |
| [69] | STEUTEL, F. W. (1969). Note on completely monotone densities. Ann. Math. Stat. 40 1130-1131. Digital Object Identifier: 10.1214/aoms/1177697626 Google Scholar: Lookup Link MathSciNet: MR0254949 · Zbl 0183.47601 · doi:10.1214/aoms/1177697626 |
| [70] | Vats, D., Flegal, J. M. and Jones, G. L. (2018). Strong consistency of multivariate spectral variance estimators in Markov chain Monte Carlo. Bernoulli 24 1860-1909. Digital Object Identifier: 10.3150/16-BEJ914 Google Scholar: Lookup Link MathSciNet: MR3757517 · Zbl 1419.62141 · doi:10.3150/16-BEJ914 |
| [71] | Vats, D., Flegal, J. M. and Jones, G. L. (2019). Multivariate output analysis for Markov chain Monte Carlo. Biometrika 106 321-337. Digital Object Identifier: 10.1093/biomet/asz002 Google Scholar: Lookup Link MathSciNet: MR3949306 · Zbl 1434.62100 · doi:10.1093/biomet/asz002 |
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.
