Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T17:14:26.817Z Has data issue: false hasContentIssue false
  • English
  • Français

An ergodic theorem for the weighted ensemble method

Part of: Probabilistic methods, simulation and stochastic differential equations

Published online by Cambridge University Press:  18 January 2022

David Aristoff
David Aristoff*
Affiliation:
Colorado State University
*
*Postal address: 841 Oval Drive, Fort Collins, CO 80523, USA. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study weighted ensemble, an interacting particle method for sampling distributions of Markov chains that has been used in computational chemistry since the 1990s. Many important applications of weighted ensemble require the computation of long time averages. We establish the consistency of weighted ensemble in this setting by proving an ergodic theorem for time averages. As part of the proof, we derive explicit variance formulas that could be useful for optimizing the method.

Keywords

Interacting particle systemsequential Monte Carloergodic theoremweighted ensembleimportance samplingsteady statestratification

MSC classification

Primary: 65C05: Monte Carlo methods
Secondary: 65C35: Stochastic particle methods 65C40: Computational Markov chains
Type
Original Article
Information
Journal of Applied Probability , Volume 59 , Issue 1 , March 2022 , pp. 152 - 166
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allen, R. J., Frenkel, D. and ten Wolde, P. R. (2006). Forward flux sampling-type schemes for simulating rare events: efficiency analysis. J. Chem. Phys. 124, 194111.CrossRefGoogle ScholarPubMed
Aristoff, D. (2018). Analysis and optimization of weighted ensemble sampling. ESAIM Math. Model. Numer. Anal. 52, 1219–1238.CrossRefGoogle Scholar
Aristoff, D. and Zuckerman, D. M. (2020). Optimizing weighted ensemble sampling of steady states. SIAM Multiscale Model. Simul. 18, 646–673 10.1137/18M1212100CrossRefGoogle ScholarPubMed
Assaraf, R., Caffarel, M. and Khelif, A. (2000). Diffusion Monte Carlo methods with a fixed number of walkers. Phys. Rev. E 61, 4566–4575.CrossRefGoogle ScholarPubMed
Bello-Rivas, J. M. and Elber, R. (2015). Exact milestoning. J. Chem. Phys. 142, 03B6021.10.1063/1.4913399CrossRefGoogle Scholar
Bhatt, D., Zhang, B. W. and Zuckerman, D. M. (2010). Steady-state simulations using weighted ensemble path sampling. J. Chem. Phys. 133, 014110.CrossRefGoogle Scholar
Bréhier, C.-E. Gazeau, M., Goudenège, L., Lelièvre, T. and Rousset, M. (2016). Unbiasedness of some generalized Adaptive Multilevel Splitting algorithms. Ann. Appl. Prob. 26, 3559–3601.10.1214/16-AAP1185CrossRefGoogle Scholar
Bréhier, C. E., Lelièvre, T. and Rousset, M. (2015). Analysis of Adaptive Multilevel Splitting algorithms in an idealized case. ESAIM Prob. Statist. 19, 361–394.10.1051/ps/2014029CrossRefGoogle Scholar
Cappé, O., Moulines, E. and Rydén, T. (2005). Inference in Hidden Markov Models. Springer.CrossRefGoogle Scholar
Cérou, F., Guyader, A., Lelièvre, T. and Pommier, D. (2011). A multiple replica approach to simulate reactive trajectories. J. Chem. Phys. 134, 054108.CrossRefGoogle ScholarPubMed
Chong, L. T., Saglam, A. S. and Zuckerman, D. M. (2017). Path-sampling strategies for simulating rare events in biomolecular systems. Curr. Opin. Struct. Biol. 43, 88–94.CrossRefGoogle Scholar
Chopin, N. (2004). Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference. Ann. Statist. 32, 2385–2411.10.1214/009053604000000698CrossRefGoogle Scholar
Chraibi, H., Dutfoy, A., Galtier, T. and Garnier, J. (2021). Optimal input potential functions in the interacting particle system method. Monte Carlo Methods Appl. 27, 137–152.CrossRefGoogle Scholar
Copperman, J. T. and Zuckerman, D. M. (2020). Accelerated estimation of long-timescale kinetics by combining weighted ensemble simulation with Markov model ‘microstates’ using non-Markovian theory. Biophys. J. 118, 180a.CrossRefGoogle Scholar
Copperman, J. T. and Zuckerman, D. M. (2020). Accelerated estimation of long-timescale kinetics from weighted ensemble simulation via non-Markovian ‘microbin’ analysis. J. Chem. Theory Comput. 16, 6763–6775.CrossRefGoogle ScholarPubMed
Costaouec, R., Feng, H., Izaguirre, J. and Darve, E. (2013). Analysis of the accelerated weighted ensemble methodology. Discrete Contin. Dyn. Syst. 2013, 171–181.Google Scholar
Darve, E. and Ryu, E. (2012). Computing reaction rates in bio-molecular systems using discrete macro-states. Chapter 7 of Innovations in Biomolecular Modeling and Simulations: Volume 1. RSC Publishing.Google Scholar
Del Moral, P. (2004). Feynman–Kac Formulae: Genealogical and Interacting Particle Systems with Applications (Probability and its Applications). Springer.CrossRefGoogle Scholar
Del Moral, P. and Doucet, A. (2014). Particle methods: an introduction with applications. In ESAIM: Proc. 44, 1–46.CrossRefGoogle Scholar
Del Moral, P. and Garnier, J. (2005). Genealogical particle analysis of rare events. Ann. Appl. Prob. 15, 2496–2534.10.1214/105051605000000566CrossRefGoogle Scholar
Del Moral, P., Doucet, A. and Jasra, A. (2006). Sequential Monte Carlo samplers. J. R. Statist. Soc. B 68, 411–436.CrossRefGoogle Scholar
Del Moral, P., Moulines, E., Olsson, J. and Vergé, C. (2016). Convergence properties of weighted particle islands with application to the double bootstrap algorithm. Stoch. Systems 6, 367–418.CrossRefGoogle Scholar
Dickson, A. and Brooks, C. L. III (2014). WExplore: hierarchical exploration of high-dimensional spaces using the weighted ensemble algorithm. J. Phys. Chem. B 118, 3532–3542.10.1021/jp411479cCrossRefGoogle ScholarPubMed
Dinner, A. R., Mattingly, J. C., Tempkin, J. O. B., Van Koten, B. and Weare, J. (2018). Trajectory stratification of stochastic dynamics. SIAM Rev. 60, 909–938.CrossRefGoogle ScholarPubMed
Donovan, R. M., Sedgewick, A. J., Faeder, J. R. and Zuckerman, D. M. (2013). Efficient stochastic simulation of chemical kinetics networks using a weighted ensemble of trajectories. J. Chem. Phys. 139, 09B642-1.CrossRefGoogle Scholar
Douc, R., Cappe, O. and Moulines, E. (2005). Comparison of resampling schemes for particle filtering. In ISPA 2005: Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis, pp. 64–69. IEEE.CrossRefGoogle Scholar
Douc, R., Moulines, E. and Stoffer, D. (2014). Nonlinear Time Series Theory, Methods, and Applications with R Examples. CRC Press.Google Scholar
Doucet, A., de Freitas, N. and Gordon, N. (2001). Sequential Monte Carlo Methods in Practice (Statistics for Engineering and Information Science). Springer.CrossRefGoogle Scholar
Durrett, R. (2019). Probability: Theory and Examples, 5th edn. Cambridge University Press.10.1017/9781108591034CrossRefGoogle Scholar
Glowacki, D. R., Paci, E. and Shalashilin, D. V. (2011). Boxed molecular dynamics: decorrelation time scales and the kinetic master equation. J. Chem. Theory Comput. 7, 1244–1252.CrossRefGoogle ScholarPubMed
Grimmett, G. R. and Stirzaker, D. R. (2001). Probability and Random Processes, 3rd edn. Oxford University Press.Google Scholar
Hairer, M. and Weare, J. (2014). Improved diffusion Monte Carlo. Commun. Pure Appl. Math. 67, 1995–2021.CrossRefGoogle Scholar
Hartmann, C., Banisch, R., Sarich, M., Badowski, T. and Schütte, C. (2014). Characterization of rare events in molecular dynamics. Entropy 16, 350–376.CrossRefGoogle Scholar
Hill, T. L. (1984). Free Energy Transduction and Biochemical Cycle Kinetics. Dover Publications, New York.Google Scholar
Huber, G. A. and Kim, S. (1996). Weighted-ensemble Brownian dynamics simulations for protein association reactions. Biophys. J. 70, 97–110.10.1016/S0006-3495(96)79552-8CrossRefGoogle Scholar
Lelièvre, T. (2013). Two mathematical tools to analyze metastable stochastic processes. In Numerical Mathematics and Advanced Applications 2011, eds A. Cangiani et al., pp. 791–810. Springer.CrossRefGoogle Scholar
Lelièvre, T., Rousset, M. and Stoltz, G. (2010). Free Energy Computations: A Mathematical Perspective. Imperial College Press.CrossRefGoogle Scholar
Motwani, R. and Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.CrossRefGoogle Scholar
Rojnuckarin, A., Kim, S. and Subramaniam, S. (1998). Brownian dynamics simulations of protein folding: access to milliseconds time scale and beyond. Proc. Nat. Acad. Sci. 95, 4288–4292.CrossRefGoogle ScholarPubMed
Rojnuckarin, A., Livesay, D. R. and Subramaniam, S. (2000). Bimolecular reaction simulation using weighted ensemble Brownian dynamics and the University of Houston Brownian dynamics program. Biophys. J. 79, 686–693.CrossRefGoogle ScholarPubMed
Rousset, M. (2006). Méthods population Monte-Carlo en temps continu pour la physique numérique. Doctoral Thesis, L’Université Paul Sabatier Toulouse III.Google Scholar
Rousset, M. (2006). On the control of an interacting particle estimation of Schrödinger ground states. SIAM J. Math. Anal. 38, 824–844.CrossRefGoogle Scholar
Suárez, E., Adelman, J. L. and Zuckerman, D. M. (2016). Accurate estimation of protein folding and unfolding times: beyond Markov State Models. J. Chem. Theory Comput. 12, 3473–3481.10.1021/acs.jctc.6b00339CrossRefGoogle ScholarPubMed
van Erp, T. S., Moroni, D. and Bolhuis, P. G. (2003). A novel path sampling method for the calculation of rate constants. J. Chem. Phys. 118, 7762–7774.CrossRefGoogle Scholar
Vanden-Eijnden, E. and Venturoli, M. (2009). Exact rate calculations by trajectory parallelization and tilting. J. Chem. Phys. 131, 044120.CrossRefGoogle ScholarPubMed
Vergé, C., Dubarry, C., Del Moral, P. and Moulines, E. (2015). On parallel implementation of sequential Monte Carlo methods: the island particle model. Statist. Comput. 25, 243–260.CrossRefGoogle Scholar
Warmflash, A., Bhimalapuram, P. and Dinner, A. R. (2007). Umbrella sampling for nonequilibrium processes. J. Chem. Phys. 127, 154112.CrossRefGoogle ScholarPubMed
Webber, R. J. (2019). Unifying sequential Monte Carlo with resampling matrices. Available at arXiv:1903.12583.Google Scholar
Webber, R. J., Plotkin, D. A., O’Neill, M. E., Abbot, D. S. and Weare, J. (2019). Practical rare event sampling for extreme mesoscale weather. Chaos 29, 053109.CrossRefGoogle Scholar
Wouters, J. and Bouchet, F. (2016). Rare event computation in deterministic chaotic systems using genealogical particle analysis. J. Phys. A 49, 374002.CrossRefGoogle Scholar
Zhang, B. W., Jasnow, D. and Zuckerman, D. M. (2007). Efficient and verified simulation of a path ensemble for conformational change in a united-residue model of calmodulin. Proc. Nat. Acad. Sci. 104, 18043–18048.CrossRefGoogle Scholar
Zhang, B. W., Jasnow, D. and Zuckerman, D. M. (2010). The ‘weighted ensemble’ path sampling method is statistically exact for a broad class of stochastic processes and binning procedures. J. Chem. Phys. 132, 054107.CrossRefGoogle Scholar
Zuckerman, D. M. Discrete-state kinetics and Markov models. Equation (34). Available at http://www.physicallensonthecell.org/discrete-state-kinetics-and-markov-models.Google Scholar
Zuckerman, D. M. and Chong, L. http://westpa.github.io/westpa/publications.html.Google Scholar
Zwier, M. C. and Chong, L. T. (2010). Reaching biological timescales with all-atom molecular dynamics simulations. Curr. Opin. Pharmacol. 10, 745–752.CrossRefGoogle ScholarPubMed
Zwier, M. C., Adelman, J. L., Kaus, J. W., Pratt, A. J., Wong, K. F., Rego, N. B., Suárez, E., Lettieri, S., Wang, D. W., Grabe, M., et al. (2015). WESTPA: an interoperable, highly scalable software package for weighted ensemble simulation and analysis. J. Chem. Theory Comput. 11, 800–809.CrossRefGoogle ScholarPubMed