Advanced Search
Article Contents
Article Contents

Markov chain simulation for multilevel Monte Carlo

  • * Corresponding author

    * Corresponding author 
Abstract Full Text(HTML) Figure(2) Related Papers Cited by
  • This paper considers a new approach to using Markov chain Monte Carlo (MCMC) in contexts where one may adopt multilevel (ML) Monte Carlo. The underlying problem is to approximate expectations w.r.t. an underlying probability measure that is associated to a continuum problem, such as a continuous-time stochastic process. It is then assumed that the associated probability measure can only be used (e.g. sampled) under a discretized approximation. In such scenarios, it is known that to achieve a target error, the computational effort can be reduced when using MLMC relative to i.i.d. sampling from the most accurate discretized probability. The ideas rely upon introducing hierarchies of the discretizations where less accurate approximations cost less to compute, and using an appropriate collapsing sum expression for the target expectation. If a suitable coupling of the probability measures in the hierarchy is achieved, then a reduction in cost is possible. This article focused on the case where exact sampling from such coupling is not possible. We show that one can construct suitably coupled MCMC kernels when given only access to MCMC kernels which are invariant with respect to each discretized probability measure. We prove, under verifiable assumptions, that this coupled MCMC approach in a ML context can reduce the cost to achieve a given error, relative to exact sampling. Our approach is illustrated on a numerical example.

    Mathematics Subject Classification: Primary: 62C10, 65C05.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Estimates of the Variance and Bias Rates

    Figure 2.  Cost against MSE

  • [1] S. Agapiou, J. M. Bardsley, O. Papaspiliopoulos and A. M. Stuart, Analysis of the Gibbs sampler for hierarchical inverse problems, SIAM/ASA J. Uncertain. Quantif., 2 (2014), 514–544. doi: 10.1137/130944229.
    [2] S. Agapiou, G. O. Roberts and S. J. Vollmer, Unbiased Monte Carlo: Posterior estimation for intractable/infinite-dimensional models, Bernoulli, 24 (2018), 1726–1786. doi: 10.3150/16-BEJ911.
    [3] C. Andrieu, A. Jasra, A. Doucet and P. Del Moral, On non-linear Markov chain Monte Carlo, Bernoulli, 17 (2011), 987–1014. doi: 10.3150/10-BEJ307.
    [4] A. BeskosA. JasraK. LawR. Tempone and Y. Zhou, Multilevel Sequential Monte Carlo samplers, Stochastic Process. Appl., 127 (2017), 1417-1440.  doi: 10.1016/j.spa.2016.08.004.
    [5] A. BeskosA. JasraK. LawY. Marzouk and Y. Zhou, Multilevel Sequential Monte Carlo samplers with dimension independent likelihood informed proposals, SIAM/ASA J. Uncertain. Quantif., 6 (2018), 762-786.  doi: 10.1137/17M1120993.
    [6] N. Bou-RabeeA. Eberle and R. Zimmer, Coupling and convergence for Hamiltonian Monte Carlo, Ann. Appl. Probab., 30 (2020), 1209-1250.  doi: 10.1214/19-AAP1528.
    [7] A. Bouchard-CôtéS. J. Vollmer and A. Doucet, The bouncy particle sampler: A non-reversible rejection-free Markov chain Monte Carlo method, J. Amer. Statist. Assoc., 113 (2018), 855-867.  doi: 10.1080/01621459.2017.1294075.
    [8] S. Chen, J. Dick and A. B. Owen, Consistency of Markov chain quasi-Monte Carlo on continuous state spaces, Ann. Statist., 39 (2011), 673–701. doi: 10.1214/10-AOS831.
    [9] P. Del Moral, A. Jasra, K. J. H. Law and Y. Zhou, Multilevel SMC samplers for normalizing constants., TOMACS, 27 (2017), article 20.
    [10] P. Diaconis and D. Freedman, Iterated random functions, SIAM Rev., 41 (1999), 45–76. doi: 10.1137/S0036144598338446.
    [11] T. J. Dodwell, C. Ketelsen, R. Scheichl and A. L. Teckentrup, A hierarchical multilevel Markov chain Monte Carlo algorithm with applications to uncertainty quantification in subsurface flow, SIAM/ASA J. Uncer. Quant., 3 (2015), 1075–1108. doi: 10.1137/130915005.
    [12] M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56 (2008), 607–617. doi: 10.1287/opre.1070.0496.
    [13] M. B. Giles, Multilevel Monte Carlo methods, Acta Numer., 24 (2015), 259–328. doi: 10.1017/S096249291500001X.
    [14] P. W. Glynn and S. P. Meyn, A Lyapunov bound for solutions of the Poisson equation, Ann. Probab., 24 (1996), 916–931. doi: 10.1214/aop/1039639370.
    [15] A.-L. Haji-Ali, F. Nobile and R. Tempone, Multi-index Monte Carlo: When sparsity meets sampling, Numer. Math., 132 (2016), 767–806. doi: 10.1007/s00211-015-0734-5.
    [16] S. Heinrich, Multilevel Monte Carlo methods, In Large-Scale Scientific Computing, (eds. S. Margenov, J. Wasniewski & P. Yalamov), Springer: Berlin, 2001.
    [17] J. Heng and P. E. Jacob, Unbiased Hamiltonian Monte Carlo with couplings, Biometrika, 106 (2019), 287-302.  doi: 10.1093/biomet/asy074.
    [18] V. H. Hoang, K. J. H. Law, and A. M. Stuart, Determining white noise forcing from Eulerian observations in the Navier-stokes equation, Stoch. Partial Differ. Equ. Anal. Comput., 2 (2014), 233–261. doi: 10.1007/s40072-014-0028-4.
    [19] V. H. Hoang, C. Schwab and A. M. Stuart, Complexity analysis of accelerated MCMC methods for Bayesian inversion, Inverse Problems, 29 (2013), 085010, 37 pp. doi: 10.1088/0266-5611/29/8/085010.
    [20] S. F. Jarner and R. L. Tweedie, Locally contracting iterated functions and stability of Markov chains, J. Appl. Probab., 38 (2001), 494–507. doi: 10.1239/jap/996986758.
    [21] A. Jasra, K. Kamatani, K. J. H. Law and Y. Zhou, Multilevel particle filters, SIAM J. Numer. Anal., 55 (2017), 3068–3096. doi: 10.1137/17M1111553.
    [22] A. Jasra, K. Kamatani, K. Law and Y. Zhou, Bayesian static parameter estimation for partially observed diffusions via multilevel Monte Carlo, SIAM J. Sci. Comp., 40 (2018), A887–A902. doi: 10.1137/17M1112595.
    [23] A. Jasra, K. Kamatani, K. J. H. Law and Y. Zhou, A multi-index markov Chain Monte Carlo method, Int. J. Uncertain. Quantif., 8 (2018), 61–73. doi: 10.1615/Int.J.UncertaintyQuantification.2018021551.
    [24] A. Jasra, K. Law and C. Suciu, Advanced multilevel Monte Carlo methods, Int. Stat. Rev., 88 (2020), 548–579. doi: 10.1111/insr.12365.
    [25] K. Law, A. Stuart and K. Zygalakis, Data Assimilation, Springer-Verlag, New York, 2015. doi: 10.1007/978-3-319-20325-6.
    [26] S. Meyn, and R. L. Tweedie, Markov Chains and Stochastic Stability, Second edition, CUP: Cambridge, 2009. doi: 10.1017/CBO9780511626630.
    [27] D. S. OliverA. C. Reynolds and  N. LiuInverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008. 
    [28] C.-H. Rhee and P. W. Glynn, Unbiased estimation with square root convergence for SDE models, Oper. Res., 63 (2015), 1026–1043. doi: 10.1287/opre.2015.1404.
    [29] A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451–559. doi: 10.1017/S0962492910000061.
  • 加载中



Article Metrics

HTML views(1985) PDF downloads(241) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint