×

zbMATH — the first resource for mathematics

Construction of weakly CUD sequences for MCMC sampling. (English) Zbl 1320.62055
Summary: In Markov chain Monte Carlo (MCMC) sampling considerable thought goes into constructing random transitions. But those transitions are almost always driven by a simulated IID sequence. Recently it has been shown that replacing an IID sequence by a weakly completely uniformly distributed (WCUD) sequence leads to consistent estimation in finite state spaces. Unfortunately, few WCUD sequences are known. This paper gives general methods for proving that a sequence is WCUD, shows that some specific sequences are WCUD, and shows that certain operations on WCUD sequences yield new WCUD sequences. A numerical example on a 42-dimensional continuous Gibbs sampler found that some WCUD inputs sequences produced variance reductions ranging from tens to hundreds for posterior means of the parameters, compared to IID inputs.

MSC:
62F15 Bayesian inference
11K45 Pseudo-random numbers; Monte Carlo methods
11K41 Continuous, \(p\)-adic and abstract analogues
60J22 Computational methods in Markov chains
Software:
SSJ
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Albert, J. and Chib, S. (1993). Bayesian analysis of binary and polychotomous response data., Journal of the American Statistical Association , 88:669-679. · Zbl 0774.62031 · doi:10.2307/2290350
[2] Blair, J. M., Edwards, C. A., and Johnson, J. H. (1976). Rational Chebyshev approximation for the inverse of the error function., Mathematics of Computation , 30(136):827-830. · Zbl 0344.65001 · doi:10.2307/2005402
[3] Caflisch, R. E., Morokoff, W., and Owen, A. B. (1997). Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension., Journal of Computational Finance , 1:27-46.
[4] Chaudary, S. (2004)., Acceleration of Monte Carlo methods using low discrepancy sequences . PhD thesis, UCLA.
[5] Chentsov, N. (1967). Pseudorandom numbers for modelling Markov chains., Computational Mathematics and Mathematical Physics , 7:218-2332. · Zbl 0181.45105 · doi:10.1016/0041-5553(67)90041-9
[6] Craiu, R. V. and Lemieux, C. (2007). Acceleration of multiple-try Metropolis algorithm using antithetic and stratified sampling., Statistics and computing , 17(2). · doi:10.1007/s11222-006-9009-4
[7] Cranley, R. and Patterson, T. (1976). Randomization of number theoretic methods for multiple integration., SIAM Journal of Numerical Analysis , 13:904-914. · Zbl 0354.65016 · doi:10.1137/0713071
[8] Devroye, L. (1986)., Non-uniform Random Variate Generation . Springer. · Zbl 0593.65005
[9] Finney, D. J. (1947). The estimation from individual records of the relationship between dose and quantal response., Biometrika , 34:320-334. · Zbl 0036.09701 · doi:10.1093/biomet/34.3-4.320
[10] Gilks, W., Richardson, S., and Spiegelhalter, D. (1996)., Markov Chain Monte Carlo in Practice . Chapman and Hall, Boca Raton. · Zbl 0832.00018
[11] Hörmann, W., Leydold, J., and Derflinger, G. (2004)., Automatic Nonuniform Random Variate Generation . Springer, Berlin. · Zbl 1038.65002
[12] Knuth, D. E. (1998)., The Art of Computer Programming , volume 2: Seminumerical algorithms. Addison-Wesley, Reading MA, Third edition. · Zbl 0895.65001
[13] Korobov, N. M. (1948). On functions with uniformly distributed fractional parts., Dokl. Akad. Nauk SSSR , 62:21-22. (In Russian).
[14] Landau, D. P. and Binder, K. (2005)., A Guide to Monte Carlo Simulations in Statistical Physics . Cambridge University Press, New York, second edition. · Zbl 1086.82001
[15] L’Ecuyer, P. (1999). Tables of linear congruential generators of different sizes and good lattice structure., Mathematics of Computation , 68:249-260. · Zbl 0917.65002 · doi:10.1090/S0025-5718-99-00996-5
[16] L’Ecuyer, P. (2008)., SSJ: A Java Library for Stochastic Simulation . Software user’s guide, Available at http://www.iro.umontreal.ca/ lecuyer.
[17] L’Ecuyer, P., Lécot, C., and Tuffin, B. (2005). Randomized Quasi-Monte Carlo simulation of Markov chains with an ordered state space. In Niederreiter, H. and Talay, D., editors, Monte Carlo and Quasi-Monte Carlo Methods 2004 . Springer. · Zbl 1097.65016
[18] Lemieux, C. and Sidorsky, P. (2005). Exact sampling with highly-uniform point sets. Technical, report. · Zbl 1138.62004 · doi:10.1016/j.mcm.2005.12.006
[19] Levin, M. (1999). Discrepancy estimates of completely uniformly distributed and pseudo-random number sequences., International Mathematics Research Notices , pages 1231-1251. · Zbl 0943.11036 · doi:10.1155/S1073792899000677
[20] Liao, L. G. (1998). Variance reduction in Gibbs sampler using quasi random numbers., Journal of Computational and Graphical Statistics , 7:253-266.
[21] Liu, J. S. (2001)., Monte Carlo strategies in scientific computing . Springer, New York. · Zbl 0991.65001
[22] Liu, J. S., Liang, F., and Wong, W. H. (2000). The use of multiple-try method and local optimization in Metropolis sampling., Journal of the American Statistical Association , 95:121-134. · Zbl 1072.65505 · doi:10.2307/2669532
[23] Newman, M. E. J. and Barkema, G. T. (1999)., Monte Carlo Methods in Statistical Physics . Oxford University Press, New York. · Zbl 1012.82019
[24] Niederreiter, H. (1977). Pseudo-random numbers and optimal coefficients., Advances in Mathematics , 26:99-181. · Zbl 0366.65004 · doi:10.1016/0001-8708(77)90028-7
[25] Niederreiter, H. (1992)., Random Number Generation and Quasi-Monte Carlo Methods . S.I.A.M., Philadelphia, PA. · Zbl 0761.65002
[26] Owen, A. B. (2005). Multidimensional variation for quasi-Monte Carlo. In Fan, J. and Li, G., editors, International Conference on Statistics in honour of Professor Kai-Tai Fang’s 65th birthday . · Zbl 1266.26024 · doi:10.1142/9789812567765_0004
[27] Owen, A. B. and Tribble, S. D. (2005). A quasi-Monte Carlo Metropolis algorithm., Proceedings of the National Academy of Science , 102(25):8844-8849. · Zbl 1135.65001 · doi:10.1073/pnas.0409596102
[28] Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics., Random Structures and Algorithms , 9:223-252. · Zbl 0859.60067 · doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O
[29] Robert, C. and Casella, G. (2004)., Monte Carlo Statistical Methods . Springer, New York, 2nd edition. · Zbl 1096.62003
[30] Sloan, I. H. and Joe, S. (1994)., Lattice Methods for Multiple Integration . Oxford Science Publications, Oxford. · Zbl 0855.65013
[31] Tribble, S. D. (2007)., Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences . PhD thesis, Stanford University.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.