IDEAS home Printed from https://ideas.repec.org/a/bpj/sagmbi/v12y2013i1p39-48n5.html
   My bibliography  Save this article

Monte Carlo estimation of total variation distance of Markov chains on large spaces, with application to phylogenetics

Author

Listed:
  • Herbei Radu

    (The Ohio State University – Statistics, Columbus, OH, USA)

  • Kubatko Laura

    (The Ohio State University – Statistics, Columbus, OH, USA)

Abstract

Markov chains are widely used for modeling in many areas of molecular biology and genetics. As the complexity of such models advances, it becomes increasingly important to assess the rate at which a Markov chain converges to its stationary distribution in order to carry out accurate inference. A common measure of convergence to the stationary distribution is the total variation distance, but this measure can be difficult to compute when the state space of the chain is large. We propose a Monte Carlo method to estimate the total variation distance that can be applied in this situation, and we demonstrate how the method can be efficiently implemented by taking advantage of GPU computing techniques. We apply the method to two Markov chains on the space of phylogenetic trees, and discuss the implications of our findings for the development of algorithms for phylogenetic inference.

Suggested Citation

  • Herbei Radu & Kubatko Laura, 2013. "Monte Carlo estimation of total variation distance of Markov chains on large spaces, with application to phylogenetics," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 12(1), pages 39-48, March.
    • Handle: RePEc:bpj:sagmbi:v:12:y:2013:i:1:p:39-48:n:5
    DOI: 10.1515/sagmb-2012-0023
    as

    Download full text from publisher

    File URL: https://doi.org/10.1515/sagmb-2012-0023
    Download Restriction: For access to full text, subscription to the journal or payment for the individual article is required.
    File URL: https://libkey.io/10.1515/sagmb-2012-0023?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. Pierre L'Ecuyer & Richard Simard & E. Jack Chen & W. David Kelton, 2002. "An Object-Oriented Random-Number Package with Many Long Streams and Substreams," Operations Research, INFORMS, vol. 50(6), pages 1073-1075, December.
    2. Cron, Andrew J. & West, Mike, 2011. "Efficient Classification-Based Relabeling in Mixture Models," The American Statistician, American Statistical Association, vol. 65(1), pages 16-20.
    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. Radu Herbei & L. Mark Berliner, 2014. "Estimating Ocean Circulation: An MCMC Approach With Approximated Likelihoods via the Bernoulli Factory," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 109(507), pages 944-954, September.
    2. Bivand, Roger, 2010. "Exploiting Parallelization in Spatial Statistics: an Applied Survey using R," Discussion Paper Series in Economics 25/2010, Norwegian School of Economics, Department of Economics.
    3. Pierre L'Ecuyer & Richard Simard, 2014. "On the Lattice Structure of a Special Class of Multiple Recursive Random Number Generators," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 449-460, August.
    4. Gilles Pag`es & Benedikt Wilbertz, 2011. "GPGPUs in computational finance: Massive parallel computing for American style options," Papers 1101.3228, arXiv.org.
    5. Mehmet Tolga Cezik & Pierre L'Ecuyer, 2008. "Staffing Multiskill Call Centers via Linear Programming and Simulation," Management Science, INFORMS, vol. 54(2), pages 310-323, February.
    6. Iago Medeiros & Lucas Pacheco & Denis Rosário & Cristiano Both & Jéferson Nobre & Eduardo Cerqueira & Lisandro Granville, 2021. "Quality of experience and quality of service‐aware handover for video transmission in heterogeneous networks," International Journal of Network Management, John Wiley & Sons, vol. 31(5), September.
    7. Kampf, M. & Kochel, P., 2006. "Simulation-based sequencing and lot size optimisation for a production-and-inventory system with multiple items," International Journal of Production Economics, Elsevier, vol. 104(1), pages 191-200, November.
    8. Hiroshi Haramoto & Makoto Matsumoto & Takuji Nishimura & François Panneton & Pierre L'Ecuyer, 2008. "Efficient Jump Ahead for (F-openface) 2 -Linear Random Number Generators," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 385-390, August.
    9. Tang, Hui-Chin, 2005. "Reverse multiple recursive random number generators," European Journal of Operational Research, Elsevier, vol. 164(2), pages 402-405, July.
    10. Eric C. Ni & Dragos F. Ciocan & Shane G. Henderson & Susan R. Hunter, 2017. "Efficient Ranking and Selection in Parallel Computing Environments," Operations Research, INFORMS, vol. 65(3), pages 821-836, June.
    11. Arthur Hau, 2011. "Pricing of Loan Commitments for Facilitating Stochastic Liquidity Needs," Journal of Financial Services Research, Springer;Western Finance Association, vol. 39(1), pages 71-94, April.
    12. Avramidis, Athanassios N. & Chan, Wyean & Gendreau, Michel & L'Ecuyer, Pierre & Pisacane, Ornella, 2010. "Optimizing daily agent scheduling in a multiskill call center," European Journal of Operational Research, Elsevier, vol. 200(3), pages 822-832, February.
    13. Kyle Cooper & Susan R. Hunter, 2020. "PyMOSO: Software for Multiobjective Simulation Optimization with R-PERLE and R-MinRLE," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1101-1108, October.
    14. Mascagni Michael & Hin Lin-Yee, 2013. "Parallel pseudo-random number generators: A derivative pricing perspective with the Heston stochastic volatility model," Monte Carlo Methods and Applications, De Gruyter, vol. 19(2), pages 77-105, July.
    15. Natasha Stout & Sue Goldie, 2008. "Keeping the noise down: common random numbers for disease simulation modeling," Health Care Management Science, Springer, vol. 11(4), pages 399-406, December.
    16. Andrew Cron & Cécile Gouttefangeas & Jacob Frelinger & Lin Lin & Satwinder K Singh & Cedrik M Britten & Marij J P Welters & Sjoerd H van der Burg & Mike West & Cliburn Chan, 2013. "Hierarchical Modeling for Rare Event Detection and Cell Subset Alignment across Flow Cytometry Samples," PLOS Computational Biology, Public Library of Science, vol. 9(7), pages 1-14, July.
    17. Thomas W. Lucas & W. David Kelton & Paul J. Sánchez & Susan M. Sanchez & Ben L. Anderson, 2015. "Changing the paradigm: Simulation, now a method of first resort," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 293-303, June.
    18. Kastner, Gregor & Frühwirth-Schnatter, Sylvia, 2014. "Ancillarity-sufficiency interweaving strategy (ASIS) for boosting MCMC estimation of stochastic volatility models," Computational Statistics & Data Analysis, Elsevier, vol. 76(C), pages 408-423.
    19. Céline Labart & Jérôme Lelong, 2011. "A Parallel Algorithm for solving BSDEs - Application to the pricing and hedging of American options," Working Papers hal-00567729, HAL.
    20. Albert Solernou & Benjamin S Hanson & Robin A Richardson & Robert Welch & Daniel J Read & Oliver G Harlen & Sarah A Harris, 2018. "Fluctuating Finite Element Analysis (FFEA): A continuum mechanics software tool for mesoscale simulation of biomolecules," PLOS Computational Biology, Public Library of Science, vol. 14(3), pages 1-29, March.

    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:bpj:sagmbi:v:12:y:2013:i:1:p:39-48:n:5. 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: Peter Golla (email available below). General contact details of provider: https://www.degruyter.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.