A discrepancy bound for deterministic acceptance-rejection samplers beyond N^-1/2 in dimension 1

DOI10.1007/S11222-016-9661-2MaRDI QIDQ1703804zbMATH OpenOpenAlexFDO

Authors Houying Zhu, Josef Dick

Publication date 7 March 2018

Published in Statistics and Computing (Search for Journal in Brave)

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

zbMATH Keywords

acceptance-rejection samplerdiscrepancyFibonacci lattice pointsintegration error

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) General considerations in statistical decision theory (62C05) Random number generation in numerical analysis (65C10)

Abstract: In this paper we consider an acceptance-rejection (AR) sampler based on deterministic driver sequences. We prove that the discrepancy of an $N$ element sample set generated in this way is bounded by $mathcalO(N^{-2/3}logN)$, provided that the target density is twice continuously differentiable with non-vanishing curvature and the AR sampler uses the driver sequence ${\displaystyle }$mathcal{K}_M= {( j alpha, j �eta ) ~~ mod~~1 mid j = 1,ldots,M}, ${\displaystyle }$ where $$ are real algebraic numbers such that $$ is a basis of a number field over $mathbbQ$ of degree $3$. For the driver sequence ${\displaystyle }$mathcal{F}_k= { ({j}/{F_k}, {{jF_{k-1}}/{F_k}} ) mid j=1,ldots, F_k},${\displaystyle }$ where $F_k$ is the $k$-th Fibonacci number and $x=x-lfloorxfloor$ is the fractional part of a non-negative real number $x$, we can remove the $log$ factor to improve the convergence rate to $mathcalO(N^{-2/3})$, where again $N$ is the number of samples we accepted. We also introduce a criterion for measuring the goodness of driver sequences. The proposed approach is numerically tested by calculating the star-discrepancy of samples generated for some target densities using $mathcal{K}_M$ and $mathcal{F}_k$ as driver sequences. These results confirm that achieving a convergence rate beyond $N^{-1/2}$ is possible in practice using $mathcal{K}_M$ and $mathcal{F}_k$ as driver sequences in the acceptance-rejection sampler.

Recommendations

• Discrepancy bounds for deterministic acceptance-rejection samplers
• Discrepancy estimates for acceptance-rejection samplers using stratified inputs
• Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo
• Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo
• The acceptance-rejection method for low-discrepancy sequences

Cites work

• An encyclopaedia of cubature formulas.
• Discrepancy bounds for deterministic acceptance-rejection samplers
• Dyadic fractions with small partial quotients
• Functions of bounded variation, signed measures, and a general Koksma–Hlawka inequality
• 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 47178 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1069610 (Why is no real title available?)
• scientific article; zbMATH DE number 2002843 (Why is no real title available?)
• Low-discrepancy point sets for non-uniform measures
• Low-discrepancy sequences for piecewise smooth functions on the two-dimensional torus
• On the Koksma-Hlawka inequality
• Sparse grids

Cited in

(3)

• On a partition with a lower expected \(\mathcal{L}_2\)-discrepancy than classical jittered sampling
• Discrepancy bounds for deterministic acceptance-rejection samplers
• Discrepancy estimates for acceptance-rejection samplers using stratified inputs

This page was built for publication: A discrepancy bound for deterministic acceptance-rejection samplers beyond \(N^{-1/2}\) in dimension 1

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