Discrepancy bounds for deterministic acceptance-rejection samplers

DOI10.1214/14-EJS898zbMATH Open1348.60113arXiv1408.1742MaRDI QIDQ2452111FDOQ2452111

Josef Dick, Houying Zhu

Publication date: 30 May 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1408.1742

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Gaps in discrete random samples (extended abstract)
• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• The acceptance-rejection method for low-discrepancy sequences
• A quasi-Monte Carlo implementation of the ziggurat method
• Convergence analysis of quasi-Monte Carlo sampling for quantile and expected shortfall
• Discrepancy Estimates For Acceptance-Rejection Samplers Using Stratified Inputs
• Numerical Computation of Multivariate Normal Probabilities Using Bivariate Conditioning
• Quasi-Random Sampling for Multivariate Distributions via Generative Neural Networks
• 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)