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 \(\mathcal {O} (N^{-2/3}\log N)\), provided that the target density is twice continuously differentiable with non-vanishing curvature and the AR sampler uses the driver sequence \(\mathcal {K}_M= \{( j \alpha , j \beta ) ~~ mod~~1 \mid j = 1,\ldots ,M\},\) where \(\alpha ,\beta \) are real algebraic numbers such that \(1,\alpha ,\beta \) is a basis of a number field over \(\mathbb {Q}\) of degree 3. For the driver sequence \(\mathcal {F}_k= \{ ({j}/{F_k}, \{{jF_{k-1}}/{F_k}\} ) \mid j=1,\ldots , F_k\},\) where \(F_k\) is the k-th Fibonacci number and \(\{x\}=x-\lfloor x \rfloor \) is the fractional part of a non-negative real number x, we can remove the \(\log \) factor to improve the convergence rate to \(\mathcal {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 \(\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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aistleitner, C., Dick, J.: Low-discrepancy point sets for non-uniform measures. Acta Arith. 163, 345–369 (2014)
Aistleitner, C., Dick, J.: Functions of bounded variation, signed measures, and a general Koksma-Hlawka inequality. Acta Arith. 167, 143–171 (2015)
Brandolini, L., Colzani, L., Gigante, G., Travaglini, G.: On the Koksma-Hlawka inequality. J. Complexity 29, 158–172 (2013)
Brandolini, L., Colzani, L., Gigante, G., Travaglini, G.: Low-discrepancy sequences for piecewise smooth functions on the two-dimensional torus. J. Complexity 33, 1–13 (2016)
Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 147–269 (2004)
Cools, R.: Constructing cubature formulae: the science behind the art. Acta Numer. 6, 1–54 (1997)
Cools, R.: An encyclopaedia of cubature formulas. Numerical integration and its complexity (Oberwolfach, 2001). J. Complexity 19, 445–453 (2003)
Devroye, L.: Non-Uniform Random Variate Generation. Springer, New York (1986)
Dick, J., Pillichshammer, F.: Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010)
Farin, G.: Curves and Surfaces for Computer Aided Design: A Practical Guide, 5th edn. Morgan Kaufmann, Massachusetts (2001)
Hörmann, W., Leydold, J., Derflinger, G.: Automatic Nonuniform Random Variate Generation. Springer, Berlin (2004)
Niederreiter, H.: Dyadic fractions with small partial quotients. Monatsh. Math. 101, 309–315 (1986)
Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992)
Zhu, H., Dick, J.: Discrepancy bounds for deterministic acceptance-rejection samplers. Electron. J. Stat. 8, 678–707 (2014)
Acknowledgments
The authors are grateful to the anonymous referees and handling editor for valuable comments which improved the presentation of the results. The work was supported under the Australian Research Council’s Discovery Projects funding scheme (project DP150101770).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhu, H., Dick, J. A discrepancy bound for deterministic acceptance-rejection samplers beyond \(N^{-1/2}\) in dimension 1. Stat Comput 27, 901–911 (2017). https://doi.org/10.1007/s11222-016-9661-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11222-016-9661-2