IDEAS home Printed from https://ideas.repec.org/a/spr/metcap/v24y2022i4d10.1007_s11009-022-09949-y.html
   My bibliography  Save this article

The Computational Cost of Blocking for Sampling Discretely Observed Diffusions

Author

Listed:
  • Marcin Mider

    (Max Planck Institute for Mathematics in the Sciences)

  • Paul A. Jenkins

    (University of Warwick)

  • Murray Pollock

    (Newcastle University)

  • Gareth O. Roberts

    (University of Warwick)

Abstract

Many approaches for conducting Bayesian inference on discretely observed diffusions involve imputing diffusion bridges between observations. This can be computationally challenging in settings in which the temporal horizon between subsequent observations is large, due to the poor scaling of algorithms for simulating bridges as observation distance increases. It is common in practical settings to use a blocking scheme, in which the path is split into a (user-specified) number of overlapping segments and a Gibbs sampler is employed to update segments in turn. Substituting the independent simulation of diffusion bridges for one obtained using blocking introduces an inherent trade-off: we are now imputing shorter bridges at the cost of introducing a dependency between subsequent iterations of the bridge sampler. This is further complicated by the fact that there are a number of possible ways to implement the blocking scheme, each of which introduces a different dependency structure between iterations. Although blocking schemes have had considerable empirical success in practice, there has been no analysis of this trade-off nor guidance to practitioners on the particular specifications that should be used to obtain a computationally efficient implementation. In this article we conduct this analysis and demonstrate that the expected computational cost of a blocked path-space rejection sampler applied to Brownian bridges scales asymptotically at a cubic rate with respect to the observation distance and that this rate is linear in the case of the Ornstein–Uhlenbeck process. Numerical experiments suggest applicability both of the results of our paper and of the guidance we provide beyond the class of linear diffusions considered.

Suggested Citation

  • Marcin Mider & Paul A. Jenkins & Murray Pollock & Gareth O. Roberts, 2022. "The Computational Cost of Blocking for Sampling Discretely Observed Diffusions," Methodology and Computing in Applied Probability, Springer, vol. 24(4), pages 3007-3027, December.
  • Handle: RePEc:spr:metcap:v:24:y:2022:i:4:d:10.1007_s11009-022-09949-y
    DOI: 10.1007/s11009-022-09949-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11009-022-09949-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s11009-022-09949-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Neil Shephard & Siddhartha Chib & Olin School of Business & Washington University & Michael K. Pitt & Department of Economics & University of Warwick, 2004. "Likelihood based inference for diffusion driven models," Economics Series Working Papers 2004-FE-17, University of Oxford, Department of Economics.
    2. Delyon, Bernard & Hu, Ying, 2006. "Simulation of conditioned diffusion and application to parameter estimation," Stochastic Processes and their Applications, Elsevier, vol. 116(11), pages 1660-1675, November.
    3. Michael K. Pitt & Neil Shephard, 1999. "Analytic Convergence Rates and Parameterization Issues for the Gibbs Sampler Applied to State Space Models," Journal of Time Series Analysis, Wiley Blackwell, vol. 20(1), pages 63-85, January.
    4. Alexandros Beskos & Omiros Papaspiliopoulos & Gareth O. Roberts, 2008. "A Factorisation of Diffusion Measure and Finite Sample Path Constructions," Methodology and Computing in Applied Probability, Springer, vol. 10(1), pages 85-104, March.
    5. Kalogeropoulos, Konstantinos, 2007. "Likelihood-based inference for a class of multivariate diffusions with unobserved paths," LSE Research Online Documents on Economics 31423, London School of Economics and Political Science, LSE Library.
    6. Siddhartha Chib & Michael K Pitt & Neil Shephard, 2004. "Likelihood based inference for diffusion driven models," OFRC Working Papers Series 2004fe17, Oxford Financial Research Centre.
    7. Kalogeropoulos, Konstantinos & Roberts, Gareth O. & Dellaportas, Petros, 2007. "Inference for stochastic volatility model using time change transformations," MPRA Paper 5697, University Library of Munich, Germany.
    8. Golightly, A. & Wilkinson, D.J., 2008. "Bayesian inference for nonlinear multivariate diffusion models observed with error," Computational Statistics & Data Analysis, Elsevier, vol. 52(3), pages 1674-1693, January.
    9. Durham, Garland B & Gallant, A Ronald, 2002. "Numerical Techniques for Maximum Likelihood Estimation of Continuous-Time Diffusion Processes," Journal of Business & Economic Statistics, American Statistical Association, vol. 20(3), pages 297-316, July.
    10. Amit, Yali, 1991. "On rates of convergence of stochastic relaxation for Gaussian and non-Gaussian distributions," Journal of Multivariate Analysis, Elsevier, vol. 38(1), pages 82-99, July.
    11. Durham, Garland B & Gallant, A Ronald, 2002. "Numerical Techniques for Maximum Likelihood Estimation of Continuous-Time Diffusion Processes: Reply," Journal of Business & Economic Statistics, American Statistical Association, vol. 20(3), pages 335-338, July.
    12. G. O. Roberts & S. K. Sahu, 1997. "Updating Schemes, Correlation Structure, Blocking and Parameterization for the Gibbs Sampler," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 59(2), pages 291-317.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Peavoy, Daniel & Franzke, Christian L.E. & Roberts, Gareth O., 2015. "Systematic physics constrained parameter estimation of stochastic differential equations," Computational Statistics & Data Analysis, Elsevier, vol. 83(C), pages 182-199.
    2. S. C. Kou & Benjamin P. Olding & Martin Lysy & Jun S. Liu, 2012. "A Multiresolution Method for Parameter Estimation of Diffusion Processes," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 107(500), pages 1558-1574, December.
    3. Beskos, Alexandros & Kalogeropoulos, Konstantinos & Pazos, Erik, 2013. "Advanced MCMC methods for sampling on diffusion pathspace," Stochastic Processes and their Applications, Elsevier, vol. 123(4), pages 1415-1453.
    4. Osnat Stramer & Jun Yan, 2007. "Asymptotics of an Efficient Monte Carlo Estimation for the Transition Density of Diffusion Processes," Methodology and Computing in Applied Probability, Springer, vol. 9(4), pages 483-496, December.
    5. Kalogeropoulos, Konstantinos & Dellaportas, Petros & Roberts, Gareth O., 2007. "Likelihood-based inference for correlated diffusions," MPRA Paper 5696, University Library of Munich, Germany.
    6. Mogens Bladt & Samuel Finch & Michael Sørensen, 2016. "Simulation of multivariate diffusion bridges," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 78(2), pages 343-369, March.
    7. Golightly, A. & Wilkinson, D.J., 2008. "Bayesian inference for nonlinear multivariate diffusion models observed with error," Computational Statistics & Data Analysis, Elsevier, vol. 52(3), pages 1674-1693, January.
    8. Martin J. Lenardon & Anna Amirdjanova, 2006. "Interaction between stock indices via changepoint analysis," Applied Stochastic Models in Business and Industry, John Wiley & Sons, vol. 22(5‐6), pages 573-586, September.
    9. Golightly Andrew & Wilkinson Darren J., 2015. "Bayesian inference for Markov jump processes with informative observations," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 14(2), pages 169-188, April.
    10. Aliu, A. Hassan & Abiodun A. A. & Ipinyomi R.A., 2017. "Statistical Inference for Discretely Observed Diffusion Epidemic Models," International Journal of Mathematics Research, Conscientia Beam, vol. 6(1), pages 29-35.
    11. Golightly, Andrew & Bradley, Emma & Lowe, Tom & Gillespie, Colin S., 2019. "Correlated pseudo-marginal schemes for time-discretised stochastic kinetic models," Computational Statistics & Data Analysis, Elsevier, vol. 136(C), pages 92-107.
    12. Quentin Clairon & Adeline Samson, 2020. "Optimal control for estimation in partially observed elliptic and hypoelliptic linear stochastic differential equations," Statistical Inference for Stochastic Processes, Springer, vol. 23(1), pages 105-127, April.
    13. Nina Munkholt Jakobsen & Michael Sørensen, 2015. "Efficient Estimation for Diffusions Sampled at High Frequency Over a Fixed Time Interval," CREATES Research Papers 2015-33, Department of Economics and Business Economics, Aarhus University.
    14. Zhao-Hua Lu & Sy-Miin Chow & Nilam Ram & Pamela M. Cole, 2019. "Zero-Inflated Regime-Switching Stochastic Differential Equation Models for Highly Unbalanced Multivariate, Multi-Subject Time-Series Data," Psychometrika, Springer;The Psychometric Society, vol. 84(2), pages 611-645, June.
    15. Libo Sun & Chihoon Lee & Jennifer A. Hoeting, 2019. "A penalized simulated maximum likelihood method to estimate parameters for SDEs with measurement error," Computational Statistics, Springer, vol. 34(2), pages 847-863, June.
    16. Matthew M. Graham & Alexandre H. Thiery & Alexandros Beskos, 2022. "Manifold Markov chain Monte Carlo methods for Bayesian inference in diffusion models," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 84(4), pages 1229-1256, September.
    17. Konstantinos Kalogeropoulos & Gareth O. Roberts & Petros Dellaportas, 2007. "Inference for stochastic volatility models using time change transformations," Papers 0711.1594, arXiv.org.
    18. Paul Fearnhead & Vasilieos Giagos & Chris Sherlock, 2014. "Inference for reaction networks using the linear noise approximation," Biometrics, The International Biometric Society, vol. 70(2), pages 457-466, June.
    19. Strickland, Chris M. & Martin, Gael M. & Forbes, Catherine S., 2008. "Parameterisation and efficient MCMC estimation of non-Gaussian state space models," Computational Statistics & Data Analysis, Elsevier, vol. 52(6), pages 2911-2930, February.
    20. Mengheng Li & Siem Jan (S.J.) Koopman, 2018. "Unobserved Components with Stochastic Volatility in U.S. Inflation: Estimation and Signal Extraction," Tinbergen Institute Discussion Papers 18-027/III, Tinbergen Institute.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:metcap:v:24:y:2022:i:4:d:10.1007_s11009-022-09949-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.