Discrepancy estimates for acceptance-rejection samplers using stratified inputs

Houying Zhu, Josef Dick

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

Abstract

In this paper we propose an acceptance-rejection sampler using stratified inputs as driver sequence. We estimate the discrepancy of the N-point set in (s −s)-dimensions generated by this algorithm. First we show an upper bound on the star-discrepancy of order N −d/2−1/(2s). Further we prove an upper bound on the qth moment of the L q-discrepancy (E[N q L qq,N]) 1/q for 2 ≤ q ≤ ∞, which is of order N ( 1−1/s)(1−1/q). The proposed approach is numerically tested and compared with the standard acceptance-rejection algorithm using pseudo-random inputs. We also present an improved convergence rate for a deterministic acceptance-rejection algorithm using (t, m, s)-nets as driver sequence.

Original languageEnglish
Title of host publicationMonte Carlo and Quasi-Monte Carlo Methods
Subtitle of host publicationMCQMC, Leuven, Belgium, April 2014
EditorsRonald Cools, Dirk Nuyens
Place of PublicationCham
PublisherSpringer, Springer Nature
Pages599-619
Number of pages21
ISBN (Electronic)9783319335070
ISBN (Print)9783319335056
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventInternational Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (11th : 2014) - KU Leuven, Belgium
Duration: 6 Apr 201411 Apr 2014

Publication series

NameSpringer Proceedings in Mathematics and Statistics
PublisherSpringer
Volume163
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

Conference

ConferenceInternational Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (11th : 2014)
CountryBelgium
CityKU Leuven
Period6/04/1411/04/14

Keywords

  • Monte Carlo method
  • Acceptance-rejection sampler
  • Discrepancy theory

Fingerprint Dive into the research topics of 'Discrepancy estimates for acceptance-rejection samplers using stratified inputs'. Together they form a unique fingerprint.

  • Cite this

    Zhu, H., & Dick, J. (2016). Discrepancy estimates for acceptance-rejection samplers using stratified inputs. In R. Cools, & D. Nuyens (Eds.), Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014 (pp. 599-619). (Springer Proceedings in Mathematics and Statistics; Vol. 163). Cham: Springer, Springer Nature. https://doi.org/10.1007/978-3-319-33507-0_33