Discrepancy bounds for deterministic acceptance-rejection samplers

DOI10.1214/14-EJS898MaRDI QIDQ2452111zbMATH OpenFDO

Authors Houying Zhu, Josef Dick

Publication date 30 May 2014

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.1742, https://projecteuclid.org/euclid.ejs/1400703410

zbMATH Keywords

\((t, m, s)\)-nets

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Bayesian inference (62F15) Monte Carlo methods (65C05)

Abstract: In this paper we propose an acceptance-rejection sampler using stratified inputs as diver sequence. We estimate the discrepancy of the points generated by this algorithm. First we show an upper bound on the star discrepancy of order $N^{-1/2-1/(2s)}$. Further we prove an upper bound on the $q$-th moment of the $L_q$-discrepancy $(mathbbE[N^q{L}_{q,N}^q]{)}^{1/q}$ for $2leqleinfty$, which is of order $N^{(1-1/s)(1-1/q)}$. We also present an improved convergence rate for a deterministic acceptance-rejection algorithm using $(t,m,s)-$nets as driver sequence.

Recommendations

• A discrepancy bound for deterministic acceptance-rejection samplers beyond \(N^{-1/2}\) in dimension 1
• Discrepancy estimates for acceptance-rejection samplers using stratified inputs
• Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
• The acceptance-rejection method for low-discrepancy sequences
• Improving the rejection sampling method in quasi-Monte Carlo methods

Cites work

• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1215244 (Why is no real title available?)
• scientific article; zbMATH DE number 2002843 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 2117879 (Why is no real title available?)
• A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains
• A lower bound for the worst-case cubature error on spheres of arbitrary dimension
• Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy
• Consistency of Markov chain quasi-Monte Carlo on continuous state spaces
• Construction of weakly CUD sequences for MCMC sampling
• Convergence rates for the isotrope discrepancy
• Discrépance de suites associées à un système de numération (en dimension s)
• Diskrepanz und Distanz von Maßen bezüglich konvexer und Jordanscher Mengen. (Discrepancy and distance of measures with respect to convex and Jordan sets)
• High-dimensional integration: The quasi-Monte Carlo way
• Improved upper bounds on the star discrepancy of \((t,m,s)\)-nets and \((t,s)\)-sequences
• Improving the rejection sampling method in quasi-Monte Carlo methods
• Irregularities for distribution IX
• Low-discrepancy and low-dispersion sequences
• Monte Carlo Variance of Scrambled Net Quadrature
• On the discrepancy of convex plane sets
• On the distribution of points in a cube and the approximate evaluation of integrals
• On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals
• Point sets on the sphere \(\mathbb{S}^{2}\) with small spherical cap discrepancy
• Pseudorandom numbers for modelling Markov chains
• Quasi-Monte Carlo integration
• Quasi-Monte Carlo integration of characteristic functions and the rejection sampling method
• Remarks on a Multivariate Transformation
• Scrambled net variance for integrals of smooth functions
• Smoothness and dimension reduction in quasi-Monte Carlo methods
• The acceptance-rejection method for low-discrepancy sequences
• Transformed density rejection with inflection points

Cited in

(12)

• A quasi-Monte Carlo implementation of the ziggurat method
• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• Discrepancy estimates for acceptance-rejection samplers using stratified inputs
• Convergence analysis of quasi-Monte Carlo sampling for quantile and expected shortfall
• Discrepancy-based inference for intractable generative models using quasi-Monte Carlo
• Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo
• Quasi-Random Sampling for Multivariate Distributions via Generative Neural Networks
• Numerical computation of multivariate normal probabilities using bivariate conditioning
• Gaps in discrete random samples (extended abstract)
• Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
• The acceptance-rejection method for low-discrepancy sequences
• A discrepancy bound for deterministic acceptance-rejection samplers beyond \(N^{-1/2}\) in dimension 1

This page was built for publication: Discrepancy bounds for deterministic acceptance-rejection samplers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2452111)