×

Direct sampling with a step function. (English) Zbl 1502.62023

Summary: The direct sampling method proposed by S. G. Walker et al. [“Direct sampling”, J. Comput. Graph. Stat. 20, No. 3, 692–713 (2011; doi:10.1198/jcgs.2011.09090)] can generate draws from weighted distributions possibly having intractable normalizing constants. The method may be of interest as a tool in situations which require drawing from an unfamiliar distribution. However, the original algorithm can have difficulty producing draws in some situations. The present work restricts attention to a univariate setting where the weight function and base distribution of the weighted target density meet certain criteria. Here, a variant of the direct sampler is proposed which uses a step function to approximate the density of a particular augmented random variable on which the method is based. Knots for the step function can be placed strategically to ensure the approximation is close to the underlying density. Variates may then be generated reliably while largely avoiding the need for manual tuning or rejections. A rejection sampler based on the step function allows exact draws to be generated from the target with lower rejection probability in exchange for increased computation. Several applications of the proposed sampler illustrate the method: generating draws from the Conway-Maxwell Poisson distribution, a Gibbs sampler which draws the dependence parameter in a random effects model with conditional autoregression structure, and a Gibbs sampler which draws the degrees-of-freedom parameter in a regression with \(t\)-distributed errors.

MSC:

62-08 Computational methods for problems pertaining to statistics
62P10 Applications of statistics to biology and medical sciences; meta analysis

References:

[1] Achddou, J., Lam-Weil, J., Carpentier, A., Blanchard, G.: A minimax near-optimal algorithm for adaptive rejection sampling. In Aurélien Garivier and Satyen Kale, editors, Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pages 94-126. PMLR, 22-24 Mar 2019
[2] Ahrens, JH, Sampling from general distributions by suboptimal division of domains, Grazer Math. Berichte, 319, 20 (1993) · Zbl 0771.62016
[3] Ahrens, JH, A one-table method for sampling from continuous and discrete distributions, Computing, 54, 20, 127-146 (1995) · Zbl 0821.65100 · doi:10.1007/BF02238128
[4] Alzer, H., On some inequalities for the gamma and psi functions, Math. Computat., 66, 217, 373-389 (1997) · Zbl 0854.33001 · doi:10.1090/S0025-5718-97-00807-7
[5] Banerjee, S., Roy, A.: Linear Algebra and Matrix Analysis for Statistics. CRC, Chapman and Hall (2014) · Zbl 1309.15002
[6] Benson, A.; Friel, N., Bayesian inference, model selection and likelihood estimation using fast rejection sampling: the Conway-Maxwell-Poisson distribution, Bayes. Anal., 16, 3, 905-931 (2021) · Zbl 07807546
[7] Braun, M. and Damien, P.: (2011) Generalized direct sampling for hierarchical Bayesian models. https://arxiv.org/abs/1108.2245
[8] Braun, M.; Damien, P., Scalable rejection sampling for Bayesian hierarchical models, Market. Sci., 35, 3, 427-444 (2016) · doi:10.1287/mksc.2014.0901
[9] Carpenter, B.; Gelman, A.; Hoffman, MD; Lee, D.; Goodrich, B.; Betancourt, M.; Brubaker, M.; Guo, J.; Li, P.; Riddell, A., Stan: a probabilistic programming language, J. Statist. Soft., 76, 1, 1-32 (2017) · doi:10.18637/jss.v076.i01
[10] Chanialidis, C.; Evers, L.; Neocleous, T.; Nobile, A., Efficient Bayesian inference for COM-Poisson regression models, Statist. Comput., 23, 595-608 (2018) · Zbl 1384.62266 · doi:10.1007/s11222-017-9750-x
[11] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press: 3rd edition. (2009) · Zbl 1187.68679
[12] Cressie, N., Statistics for Spatial Data (1991), New Jersey: Wiley, New Jersey · Zbl 0799.62002
[13] Devroye, L., Non-Uniform Random Variate Generation (1986), London: Springer, London · Zbl 0593.65005 · doi:10.1007/978-1-4613-8643-8
[14] Duane, S.; Kennedy, AD; Pendleton, BJ; Roweth, D., Hybrid Monte Carlo, Phys. Lett. B, 195, 2, 216-222 (1987) · doi:10.1016/0370-2693(87)91197-X
[15] Erraqabi, A., Valko, M., Carpentier, A., Maillard, O.: Pliable rejection sampling. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2121-2129, New York, USA, 20-22 Jun 2016. PMLR
[16] Eddelbuettel, D., Seamless R and C++ Integration with Rcpp (2013), New York: Springer, New York · Zbl 1283.62001 · doi:10.1007/978-1-4614-6868-4
[17] Evans, M.; Swartz, T., Random variable generation using concavity properties of transformed densities, J. Computat. Graph. Statist., 7, 4, 514-528 (1998)
[18] Gaunt, RE; Iyengar, S.; Olde Daalhuis, AB; Simsek, B., An asymptotic expansion for the normalizing constant of the Conway-Maxwell-Poisson distribution, Ann. Instit. Statist. Math., 71, 163-180 (2019) · Zbl 1415.62005 · doi:10.1007/s10463-017-0629-6
[19] Gelman, A.; Carlin, JB; Stern, HS; Dunson, DB; Vehtari, A.; Rubin, DB, Bayesian Data Analysis (2013), Chapman and Hall: CRC Press, Chapman and Hall · Zbl 1279.62004 · doi:10.1201/b16018
[20] Geman, S.; Geman, D., Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. Patt. Analy. Mach. Intell., 6, 6, 721-741 (1984) · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[21] Geweke, J., Priors for macroeconomic time series and their application, Econom. Theory, 10, 3-4, 609-632 (1994) · doi:10.1017/S0266466600008690
[22] Gilks, W.R., Wild, P.: Adaptive rejection sampling for Gibbs sampling. J. Royal Statist. Soc. Ser. C (Appl. Statist.) 41(2), 337-348 (1992) · Zbl 0825.62407
[23] Gilks, W.R., Best, N.G., Tan, K.K.C.: Adaptive rejection Metropolis sampling within Gibbs sampling. J. Royal Statist. Soc. Ser. C (Appl. Statist.) 44(4), 455-472 (1995) · Zbl 0893.62110
[24] Görür, D.; Teh, Y-W, Concave-convex adaptive rejection sampling, J. Computat. Graph. Statist., 20, 3, 670-691 (2011) · doi:10.1198/jcgs.2011.09058
[25] Guikema, SD; Goffelt, JP, A flexible count data regression model for risk analysis, Risk Analy., 28, 1, 213-223 (2008) · doi:10.1111/j.1539-6924.2008.01014.x
[26] Hastings, WK, Monte Carlo sampling methods using Markov chains and their applications, Biometrika, 57, 1, 97-109 (1970) · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97
[27] Hoffman, MD; Gelman, A., The No-U-Turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo, J. Mach. Learn. Res., 15, 47, 1593-1623 (2014) · Zbl 1319.60150
[28] Holden, L.; Hauge, R.; Holden, M., Adaptive independent Metropolis-Hastings, Ann. Appl. Probab., 19, 1, 395-413 (2009) · Zbl 1192.65009 · doi:10.1214/08-AAP545
[29] Hosszejni, D.: Bayesian estimation of the degrees of freedom parameter of the Student-\(t\) distribution—a beneficial re-parameterization, (2021). https://arxiv.org/abs/2109.01726
[30] Joseph, M. mbjoseph/carstan: First release, December (2016). doi:10.5281/zenodo.210407
[31] Lange, KL; Little, RJA; Taylor, JMG, Robust statistical modeling using the t distribution, J. Am. Statist. Assoc., 84, 408, 881-896 (1989)
[32] Lange, K., Numerical Analysis for Statisticians (2010), London: Springer, London · Zbl 1258.62003 · doi:10.1007/978-1-4419-5945-4
[33] Lee, D., CARBayes: an R package for Bayesian spatial modeling with conditional autoregressive priors, J. Statist. Soft., 55, 13, 1-24 (2013) · doi:10.18637/jss.v055.i13
[34] Levin, D.A., Peres, Y.: Markov Chains and Mixing Times. American Mathematical Society, 2nd edn, (2017) · Zbl 1390.60001
[35] Lee, D.: CARBayesdata: Data Used in the Vignettes Accompanying the CARBayes and CARBayesST Packages, (2020). URL https://CRAN.R-project.org/package=CARBayesdata. R package version 2.2
[36] Martino, L., Míguez, J.: A generalization of the adaptive rejection sampling algorithm. Statist. Comput. 21(4), 633-647 (2011) · Zbl 1223.65006
[37] Murray, I., Ghahramani, Z., MacKay, D.J.C.: MCMC for doubly-intractable distributions. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, UAI’06, pages 359-366, Arlington, Virginia, USA, 2006. AUAI Press. ISBN 0974903922
[38] Martino, L.; Read, J.; Luengo, D., Independent doubly adaptive rejection Metropolis sampling within Gibbs sampling, IEEE Trans. Sign. Process., 63, 12, 3123-3138 (2015) · Zbl 1394.94828 · doi:10.1109/TSP.2015.2420537
[39] Martino, L.; Luengo, D.; Míguez, J., Independent Random Sampling Methods (2018), Cham: Springer International Publishing, Cham · Zbl 1414.62007 · doi:10.1007/978-3-319-72634-2
[40] Møller, J.; Pettitt, AN; Reeves, R.; Berthelsen, KK, An efficient Markov chain Monte Carlo method for distributions with intractable normalising constants, Biometrika, 93, 2, 451-458 (2006) · Zbl 1158.62020 · doi:10.1093/biomet/93.2.451
[41] Metropolis, N.; Rosenbluth, AW; Rosenbluth, MN; Teller, AH; Teller, E., Equation of state calculations by fast computing machines, J. Chem. Phys., 21, 6, 1087-1092 (1953) · Zbl 1431.65006 · doi:10.1063/1.1699114
[42] Neal, RM, Slice sampling, Ann. Statist., 31, 3, 705-767 (2003) · Zbl 1051.65007 · doi:10.1214/aos/1056562461
[43] Nishimura, A.; Dunson, DB; Lu, J., Discontinuous Hamiltonian Monte Carlo for discrete parameters and discontinuous likelihoods, Biometrika., 107, 2, 365-380 (2020) · Zbl 1441.62079 · doi:10.1093/biomet/asz083
[44] R Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, (2022). https://www.R-project.org/
[45] Rivlin, T.J.: An Introduction to the Approximation of Functions. Dover, New York (1981) · Zbl 0489.41001
[46] Patil, GP; Rao, CR, Weighted distributions and size-biased sampling with applications to wildlife populations and human families, Biometrics, 34, 2, 179-189 (1978) · Zbl 0384.62014 · doi:10.2307/2530008
[47] Salvatier, J., Wiecki, T.V., Fonnesbeck, C.: Probabilistic programming in Python using PyMC3. Peer J. Comput. Sci. 2, e55 (2016)
[48] Shmueli, G, Minka, TP, Kadane JB, Borle, S, Boatwright, P: A useful distribution for fitting discrete data: revival of the Conway-Maxwell-Poisson distribution. J. Royal Statist. Soc. Ser. C (Appl. Statist) 54(1), 127-142 (2005) · Zbl 1490.62058
[49] Tanner, MA; Wong, WH, The calculation of posterior distributions by data augmentation, J. Amer. Statist. Associat., 82, 398, 528-540 (1987) · Zbl 0619.62029 · doi:10.1080/01621459.1987.10478458
[50] Walker, SG; Laud, PW; Zantedeschi, D.; Damien, P., Direct sampling. J. Computat. Graph. Statist., 20, 3, 692-713 (2011) · doi:10.1198/jcgs.2011.09090
[51] von Neumann, J.; Householder, AS; Forsythe, GE; Germond, HH, Various techniques used in connection with random digits, Monte Carlo Method, volume 12 of National Bureau of Standards Applied Mathematics Series, chapter 13, 36-38 (1951), Washington, DC.: US Government Printing Office, Washington, DC. · Zbl 0045.22105
[52] Zhou, G.: Mixed Hamiltonian Monte Carlo for mixed discrete and continuous variables. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546
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.