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

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 F_k= { (j/F_k, { jF_k-1/F_k}) ∣ j=1 , … , F_k} , where F_k 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 K_M and F_k as driver sequences. These results confirm that achieving a convergence rate beyond N^-1/2 is possible in practice using K_M and F_k as driver sequences in the acceptance-rejection sampler.