Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
arXiv:1311.1890 · doi:10.1214/EJP.v19-3132
Abstract
Markov chain Monte Carlo (MCMC) simulations are modeled as driven by true random numbers. We consider variance bounding Markov chains driven by a deterministic sequence of numbers. The star-discrepancy provides a measure of efficiency of such Markov chain quasi-Monte Carlo methods. We define a pull-back discrepancy of the driver sequence and state a close relation to the star-discrepancy of the Markov chain-quasi Monte Carlo samples. We prove that there exists a deterministic driver sequence such that the discrepancies decrease almost with the Monte Carlo rate . As for MCMC simulations, a burn-in period can also be taken into account for Markov chain quasi-Monte Carlo to reduce the influence of the initial state. In particular, our discrepancy bound leads to an estimate of the error for the computation of expectations. To illustrate our theory we provide an example for the Metropolis algorithm based on a ball walk. Furthermore, under additional assumptions we prove the existence of a driver sequence such that the discrepancy of the corresponding deterministic Markov chain sample decreases with order for every .
arXiv comment24 pages
References in corpus (14)
- Multilevel Monte Carlo algorithms for Lévy-driven SDEs with Gaussian correction
- Explicit error bounds for Markov chain Monte Carlo
- Greedy Solution of Ill-Posed Problems: Error Bounds and Exact Inversion
- Optimal Hoeffding bounds for discrete reversible Markov chains
- Consistency of Markov chain quasi-Monte Carlo on continuous state spaces
- Variance bounding Markov chains
- Multiconfigurational time-dependent Hartree method for describing particle loss due to absorbing boundary conditions
- A characterization of Sobolev spaces on the sphere and an extension of Stolarsky's invariance principle to arbitrary smoothness
- Positivity of hit-and-run and related algorithms
- Hit-and-run for numerical integration
- Construction of weakly CUD sequences for MCMC sampling
- Error bounds of MCMC for functions with unbounded stationary variance
- Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
- Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo
Cited by in corpus (5)
- Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
- Computation of expectations by Markov chain Monte Carlo methods
- A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo
- Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy
- A search for short-period Tausworthe generators over with application to Markov chain quasi-Monte Carlo