Discrepancy estimates for acceptance-rejection samplers using stratified inputs

Houying Zhu; Josef Dick

doi:10.1007/978-3-319-33507-0_33

Discrepancy estimates for acceptance-rejection samplers using stratified inputs

Houying Zhu, Josef Dick

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	Monte Carlo and Quasi-Monte Carlo Methods
Subtitle of host publication	MCQMC, Leuven, Belgium, April 2014
Editors	Ronald Cools, Dirk Nuyens
Place of Publication	Cham
Publisher	Springer, Springer Nature
Pages	599-619
Number of pages	21
ISBN (Electronic)	9783319335070
ISBN (Print)	9783319335056
DOIs	https://doi.org/10.1007/978-3-319-33507-0_33
Publication status	Published - 2016
Externally published	Yes
Event	International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (11th : 2014) - KU Leuven, Belgium Duration: 6 Apr 2014 → 11 Apr 2014

Publication series

Name	Springer Proceedings in Mathematics and Statistics
Publisher	Springer
Volume	163
ISSN (Print)	2194-1009
ISSN (Electronic)	2194-1017

Conference

Conference	International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (11th : 2014)
Country/Territory	Belgium
City	KU Leuven
Period	6/04/14 → 11/04/14

Keywords

Monte Carlo method
Acceptance-rejection sampler
Discrepancy theory

Access to Document

10.1007/978-3-319-33507-0_33

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). Springer, Springer Nature. https://doi.org/10.1007/978-3-319-33507-0_33

@inproceedings{710435fb535e4f62962cb471c4308f50,

title = "Discrepancy estimates for acceptance-rejection samplers using stratified inputs",

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. ",

keywords = "Monte Carlo method, Acceptance-rejection sampler, Discrepancy theory",

author = "Houying Zhu and Josef Dick",

year = "2016",

doi = "10.1007/978-3-319-33507-0_33",

language = "English",

isbn = "9783319335056",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer, Springer Nature",

pages = "599--619",

editor = "Ronald Cools and Dirk Nuyens",

booktitle = "Monte Carlo and Quasi-Monte Carlo Methods",

address = "United States",

note = "International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (11th : 2014) ; Conference date: 06-04-2014 Through 11-04-2014",

}

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. Springer Proceedings in Mathematics and Statistics, vol. 163, Springer, Springer Nature, Cham, pp. 599-619, International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (11th : 2014), KU Leuven, Belgium, 6/04/14. https://doi.org/10.1007/978-3-319-33507-0_33

Discrepancy estimates for acceptance-rejection samplers using stratified inputs. / Zhu, Houying; Dick, Josef.
Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014. ed. / Ronald Cools; Dirk Nuyens. Cham: Springer, Springer Nature, 2016. p. 599-619 (Springer Proceedings in Mathematics and Statistics; Vol. 163).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Discrepancy estimates for acceptance-rejection samplers using stratified inputs

AU - Zhu, Houying

AU - Dick, Josef

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Monte Carlo method

KW - Acceptance-rejection sampler

KW - Discrepancy theory

UR - http://www.scopus.com/inward/record.url?scp=84977537988&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP150101770

U2 - 10.1007/978-3-319-33507-0_33

DO - 10.1007/978-3-319-33507-0_33

M3 - Conference proceeding contribution

SN - 9783319335056

T3 - Springer Proceedings in Mathematics and Statistics

SP - 599

EP - 619

BT - Monte Carlo and Quasi-Monte Carlo Methods

A2 - Cools, Ronald

A2 - Nuyens, Dirk

PB - Springer, Springer Nature

CY - Cham

T2 - International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (11th : 2014)

Y2 - 6 April 2014 through 11 April 2014

ER -

Discrepancy estimates for acceptance-rejection samplers using stratified inputs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this