Editing Markov chain Monte Carlo (section)

=== Quasi-Monte Carlo ===

The [[quasi-Monte Carlo method]] is an analog to the normal Monte Carlo method that uses [[low-discrepancy sequence]]s instead of random numbers.<ref name="beating">{{cite journal |last1=Papageorgiou |first1=Anargyros |first2=Joseph |last2=Traub |title=Beating Monte Carlo |journal=Risk |volume=9 |issue=6 |year=1996 |pages=63–65 | url=https://iiif.library.cmu.edu/file/Traub_box00030_fld00008_bdl0001_doc0001/Traub_box00030_fld00008_bdl0001_doc0001.pdf}}</ref><ref>{{cite journal | last1 = Sobol | first1 = Ilya M | year = 1998 | title = On quasi-monte carlo integrations | journal = Mathematics and Computers in Simulation | volume = 47 | issue = 2| pages = 103–112 | doi=10.1016/s0378-4754(98)00096-2 }}</ref> It yields an integration error that decays faster than that of true random sampling, as quantified by the [[Low-discrepancy sequence#The Koksma–Hlawka inequality|Koksma–Hlawka inequality]]. Empirically it allows the reduction of both estimation error and convergence time by an order of magnitude.<ref name="beating" /> Markov chain quasi-Monte Carlo methods<ref>{{cite journal |last1=Chen |first1=S. |first2=Josef |last2=Dick |first3=Art B. |last3=Owen |title=Consistency of Markov chain quasi-Monte Carlo on continuous state spaces |journal=[[Annals of Statistics]] |volume=39 |issue=2 |year=2011 |pages=673–701 |doi=10.1214/10-AOS831 |arxiv=1105.1896 |doi-access=free }}</ref><ref>{{cite thesis |last=Tribble |first=Seth D. |title=Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences |type=Diss. |publisher=Stanford University |year=2007 |id={{ProQuest|304808879}} }}</ref> such as the Array–RQMC method combine randomized quasi–Monte Carlo and Markov chain simulation by simulating <math>n</math> chains simultaneously in a way that better approximates the true distribution of the chain than with ordinary MCMC.<ref>{{cite journal |last1=L'Ecuyer |first1=P. |first2=C. |last2=Lécot |first3=B. |last3=Tuffin |title=A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains |journal=[[Operations Research (journal)|Operations Research]] |volume=56 |issue=4 |year=2008 |pages=958–975 |doi=10.1287/opre.1080.0556 |url=https://hal.inria.fr/inria-00070462/file/RR-5545.pdf }}</ref> In empirical experiments, the variance of the average of a function of the state sometimes converges at rate <math>O(n^{-2})</math> or even faster, instead of the <math>O(n^{-1})</math> Monte Carlo rate.<ref>{{cite journal |last1=L'Ecuyer |first1=P. |first2=D. |last2=Munger |first3=C. |last3=Lécot |first4=B. |last4=Tuffin |title=Sorting Methods and Convergence Rates for Array-RQMC: Some Empirical Comparisons |journal=Mathematics and Computers in Simulation |volume=143 |year=2018 |pages=191–201 |doi=10.1016/j.matcom.2016.07.010 }}</ref>