×
Zhu, Houying; Dick, Josef

Discrepancy bounds for deterministic acceptance-rejection samplers. (English) Zbl 1348.60113

Electron. J. Stat. 8, No. 1, 678-707 (2014).
Summary: We consider an acceptance-rejection sampler based on a deterministic driver sequence. The deterministic sequence is chosen such that the discrepancy between the empirical target distribution and the target distribution is small. We use quasi-Monte Carlo (QMC) point sets for this purpose. The empirical evidence shows convergence rates beyond the crude Monte Carlo rate of \(N^{-1/2}\). We prove that the discrepancy of samples generated by the QMC acceptance-rejection sampler is bounded from above by \(N^{-1/s}\). A lower bound shows that for any given driver sequence, there always exists a target density such that the star discrepancy is at most \(N^{-2/(s+1)}\). For a general density, whose domain is the real state space \(\mathbb{R}^{s-1}\), the inverse Rosenblatt transformation can be used to convert samples from the \((s-1)\)-dimensional cube to \(\mathbb{R}^{s-1}\). We show that this transformation is measure preserving. This way, under certain conditions, we obtain the same convergence rate for a general target density defined in \(\mathbb{R}^{s-1}\). Moreover, we also consider a deterministic reduced acceptance-rejection algorithm recently introduced by F. Barekat and R. Caflisch [“Simulation with fluctuation and singular rates”, Commun. Comput. Phys. 16, No. 2, 287–306 (2014; doi:10.4208/cicp.300313.130114a)].

Cited in 7 Documents

MSC:

60J22 Computational methods in Markov chains
62F15 Bayesian inference
65C05 Monte Carlo methods

Keywords:

\((t, m, s)\)-nets
Cite Review PDF
Full Text: DOI arXiv Euclid

References:

[1] Aistleitner, C., Brauchart, J.S. and Dick, J., Point sets on the sphere \(\mathbbS^2\) with small spherical cap discrepancy . Discrete and Computational Geometry, 48, 990 -1024, 2012. · Zbl 1272.65003
[2] Barekat, F. and Caflisch, R., Simulation with Fluctuation and Singular Rates . ArXiv :1310.4555 [math.NA], 2013.
[3] Beck, J., On the discrepancy of convex plane sets . Monatshefte Mathematik, 105, 91-106, 1988. · Zbl 0635.10044 · doi:10.1007/BF01501162
[4] Botts, C., Hörmann, W. and Leydold, J., Transformed density rejection with inflection points . Statistics and Computing, 23, 251-260, 2013. · Zbl 1322.62127 · doi:10.1007/s11222-011-9306-4
[5] Caflisch, R.E., Monte Carlo and quasi-Monte Carlo methods . Acta Numerica, 1-49, 1998. · Zbl 0949.65003
[6] Chen, S., Consistency and convergence rate of Markov chain quasi Monte Carlo with examples . PhD thesis, Stanford University, 2011.
[7] Chen, S., Dick, J. and Owen, A.B., Consistency of Markov chain quasi-Monte Carlo on continuous state spaces . Annals of Statistics, 39, 673-701, 2011. · Zbl 1225.65010 · doi:10.1214/10-AOS831
[8] Chentsov, N.N., Pseudorandom numbers for modelling Markov chains . Computational Mathematics and Mathematical Physics, 7, 218-233, 1967. · Zbl 0181.45105 · doi:10.1016/0041-5553(67)90041-9
[9] Devroye, L., Nonuniform Random Variate Generation . Springer-Verlag, New York, 1986. · Zbl 0593.65005
[10] Dick, J., Kuo, F. and Sloan, I.H., High dimensional integration-the quasi-Monte Carlo way . Acta Numerica, 22, 133-288, 2013. · Zbl 1296.65004 · doi:10.1017/S0962492913000044
[11] Dick, J. and Pillichshammer, F., Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration . Cambridge University Press, Cambridge, 2010. · Zbl 1282.65012
[12] Dick, J., Rudolf, D. and Zhu, H., Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo . Available at arxiv.org/abs /1303.2423 [stat.CO], submitted, 2013.
[13] Faure, H., Discrépance de suites associées à un système de numération (en dimension \(s\)) . Acta Arithmetica, 4, 337-351, 1982. · Zbl 0442.10035
[14] Gerber, M. and Chopin, N., Sequential quasi-Monte Carlo . Available at arXiv :1402.4039 [stat.CO], 2014.
[15] Gnewuch, M., Bracketing numbers for axis-parallel boxes and application to geometric discrepancy . Journal of Complexity, 24, 154-172, 2008. · Zbl 1138.11031 · doi:10.1016/j.jco.2007.08.003
[16] Kuipers, L. and Niederreiter, H., Uniform Distribution of Sequences . John Wiley, New York, 2006. · Zbl 0281.10001
[17] Halton, J.H., On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals . Numerische Mathematik, 2, 84-90, 1960. · Zbl 0090.34505 · doi:10.1007/BF01386213
[18] Hesse, K., A lower bound for the worst-case cubature error on spheres of arbitrary dimension . Numerische Mathematik, 103, 413-433, 2006. · Zbl 1089.41025 · doi:10.1007/s00211-006-0686-x
[19] Hörmann, W., Leydold, J. and Derflinger, G., Automatic Nonuniform Random Variate Generation . Statistics and Computing. Springer-Verlag, Berlin, 2004. · Zbl 1038.65002
[20] Kritzer, P., Improved upper bounds on the star discrepancy of \((t,m,s)\)-nets and \((t,s)\)-sequences . Journal of Complexity, 22, 336-347, 2006. · Zbl 1155.11336 · doi:10.1016/j.jco.2005.10.004
[21] L’Ecuyer, P., Lecot, C. and Tuffin, B., A randomized quasi-Monte Carlo simulation method for Markov chains . Operation Research, 56, 958-975, 2008. · Zbl 1167.90673 · doi:10.1287/opre.1080.0556
[22] Meyn, M.P. and Tweedie, T.L., Markov Chain and Stochastic Stability . Springer-Verlag, London, 1993.
[23] Morokoff, W.J. and Caflisch, R.E., Quasi-Monte Carlo integration . Journal of Computational Physics, 122, 218-230, 1995. · Zbl 0863.65005 · doi:10.1006/jcph.1995.1209
[24] Moskowitz, B. and Caflisch, R.E., Smoothness and dimension reduction in quasi-Monte Carlo methods . Mathematical and Computer Modelling, 23, 37-54, 1996. · Zbl 0858.65023 · doi:10.1016/0895-7177(96)00038-6
[25] Nguyen, N. and Ökten, G., The acceptance-rejection method for low discrepancy sequences . Submitted, 2014. · Zbl 1405.65013
[26] Niederreiter, H., Low-discrepancy and low-dispersion sequences . Journal of Number Theory, 30, 51-70, 1988. · Zbl 0651.10034 · doi:10.1016/0022-314X(88)90025-X
[27] Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods . SIAM, Philadelphia, Pennsylvania, 1992. · Zbl 0761.65002
[28] Niederreiter, H. and Wills, J.M., Diskrepanz und Distanz von Maßen bezüglich konvexer und Jordanscher Mengen (German). Mathematische Zeitschrift, 144, 125-134, 1975. · Zbl 0295.28028 · doi:10.1007/BF01190941
[29] Noh, Y., Choi, K.K. and Du, L., New Transformation of Dependent Input Variables Using Copula for RBDO . 7th World Congresses of Structural and Multidisciplinary Optimization COEX Seoul, Korea, 21-25 May 2007.
[30] Owen, A.B., Randomly permuted \((t,m,s)\)-nets and \((t,s)\)-sequences . In: H. Niederreiter and P.J. Shiue (Eds.). Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (Las Vegas, NV, 1994), 299-317. Lecture Notes in Statist., 106. Springer, New York, 1995. · doi:10.1007/978-1-4612-2552-2_19
[31] Owen, A.B., Monte Carlo variance of scrambled net quadrature . SIAM Journal on Numerical Analysis, 34, 1884-1910, 1997. · Zbl 0890.65023 · doi:10.1137/S0036142994277468
[32] Owen, A.B., Scrambled net variance for integrals of smooth functions . Annals of Statistics, 25, 1541-1562, 1997. · Zbl 0886.65018 · doi:10.1214/aos/1031594731
[33] Owen, A.B., Monte Carlo theory, methods and examples (book draft) . Available at . Last accessed on 16 May 2014.
[34] Robert, C. and Casella, G., Monte Carlo Statistical Methods . Springer-Verlag, New York, second edition, 2004. · Zbl 1096.62003
[35] Rosenblatt, M., Remarks on a multivariate transformation . Annals of Mathematical Statistics, 23, 470-472, 1952. · Zbl 0047.13104 · doi:10.1214/aoms/1177729394
[36] Schmidt, W.M., Irregularities of distribution . Acta Arithmetica, 27, 385-396, 1975. · Zbl 0274.10038
[37] Sobol, I.M., Distribution of points in a cube and approximate evaluation of integrals . Akademija Nauk SSSR. Žurnal Vyčislitel’ noĭ Matematiki i Matematičeskoĭ Fiziki 7, 784-802, 1967 (in Russian); U.S.S.R Computational Mathematics and Mathematical Physics 7, 86-112, 1967 (in English). · Zbl 0185.41103 · doi:10.1016/0041-5553(67)90144-9
[38] Stute, W., Convergence rates for the isotrope discrepancy . Annals of Probability, 5, 707-723, 1977. · Zbl 0382.60029 · doi:10.1214/aop/1176995714
[39] Tribble, S.D., Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences . PhD thesis, Stanford University, 2007.
[40] Tribble, S.D. and Owen, A.B., Constructions of weakly CUD sequences for MCMC . Electronic Journal of Statistics, 2, 634-660, 2008. · Zbl 1320.62055 · doi:10.1214/07-EJS162
[41] Wang, X., Quasi-Monte Carlo integration of characteristic functions and the rejection sampling method . Comupter Physics Communication, 123, 16-26, 1999. · Zbl 0942.65023 · doi:10.1016/S0010-4655(99)00253-2
[42] Wang, X., Improving the rejection sampling method in quasi-Monte Carlo methods . Journal of Computational and Applied Mathematics, 114, 231-246, 2000. · Zbl 0959.65006 · doi:10.1016/S0377-0427(99)00194-6
[43] Wyner, A.D., Capabilities of bounded discrepancy decoding . The Bell System Technical Journal, 44, 1061-1122, 1965. · doi:10.1002/j.1538-7305.1965.tb04170.x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.