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

Houying Zhu, Josef Dick

Research output: Contribution to journalArticlepeer-review


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 O(N-2/3log N) , provided that the target density is twice continuously differentiable with non-vanishing curvature and the AR sampler uses the driver sequence KM={(jα,jβ)mod1∣j=1,…,M}, where α, β are real algebraic numbers such that 1, α, β is a basis of a number field over Q of degree 3. For the driver sequence Fk= { (j/Fk, { jFk-1/Fk}) ∣ j=1 , … , Fk} , where Fk is the k-th Fibonacci number and {x} = x- ⌊x⌋ is the fractional part of a non-negative real number x, we can remove the log factor to improve the convergence rate to O(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 KM and Fk as driver sequences. These results confirm that achieving a convergence rate beyond N-1/2 is possible in practice using KM and Fk as driver sequences in the acceptance-rejection sampler.

Original languageEnglish
Pages (from-to)901-911
Number of pages11
JournalStatistics and Computing
Issue number4
Publication statusPublished - Jul 2017
Externally publishedYes


  • Acceptance-rejection sampler
  • Discrepancy
  • Fibonacci lattice points
  • Integration error


Dive into the research topics of 'A discrepancy bound for deterministic acceptance-rejection samplers beyond N<sup>-1/2</sup> in dimension 1'. Together they form a unique fingerprint.

Cite this