TY - JOUR

T1 - Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo

AU - Dick, Josef

AU - Rudolf, Daniel

AU - Zhu, Houying

PY - 2016/10

Y1 - 2016/10

N2 - Markov chains can be used to generate samples whose distribution approximates a given target distribution. The quality of the samples of such Markov chains can be measured by the discrepancy between the empirical distribution of the samples and the target distribution. We prove upper bounds on this discrepancy under the assumption that the Markov chain is uniformly ergodic and the driver sequence is deterministic rather than independent U(0,1) random variables. In particular, we show the existence of driver sequences for which the discrepancy of the Markov chain from the target distribution with respect to certain test sets converges with (almost) the usual Monte Carlo rate of n-1/2.

AB - Markov chains can be used to generate samples whose distribution approximates a given target distribution. The quality of the samples of such Markov chains can be measured by the discrepancy between the empirical distribution of the samples and the target distribution. We prove upper bounds on this discrepancy under the assumption that the Markov chain is uniformly ergodic and the driver sequence is deterministic rather than independent U(0,1) random variables. In particular, we show the existence of driver sequences for which the discrepancy of the Markov chain from the target distribution with respect to certain test sets converges with (almost) the usual Monte Carlo rate of n-1/2.

KW - Markov chain Monte Carlo

KW - uniformly ergodic Markov chain

KW - discrepancy theory

KW - probabilistic method

UR - http://www.scopus.com/inward/record.url?scp=84994491959&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP1097023

UR - http://purl.org/au-research/grants/arc/DP120101816

U2 - 10.1214/16-AAP1173

DO - 10.1214/16-AAP1173

M3 - Article

SN - 1050-5164

VL - 26

SP - 3178

EP - 3205

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 5

ER -