×

Exact sublinear binomial sampling. (English) Zbl 1331.68279

Summary: Drawing a random variate from a given binomial distribution \(B(n,p)\) is an important subroutine in many large-scale simulations. The naive algorithm takes \(\mathcal {O}(n)\) time w.h.p. in the WordRAM model, which is too slow in many settings, though to its credit, it does not suffer from precision loss. The problem of sampling from a binomial distribution in sublinear time has been extensively studied and implemented in such packages as R and the GNU Scientific Library, however, all previous sublinear-time algorithms involve precision loss, which introduces artifacts such as discontinuities into the sampling. In this paper, we present the first algorithm, to the best of our knowledge, that samples binomial distributions in sublinear time with no precision loss. We assume that each bit of \(p\) can be obtained in \(\mathcal {O}(1)\) time.

MSC:

68U20 Simulation (MSC2010)

Software:

R; car; GSL; carData; gmp
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abe, J., Kamimura, Y.: Do female parasitoid wasps recognize and adjust sex ratios to build cooperative relationships? J. Evol. Biol. 25(7), 1427-1437 (2012) · doi:10.1111/j.1420-9101.2012.02532.x
[2] Ahrens, J.H., Dieter, U.: Sampling from binomial and Poisson distributions: A method with bounded computation times. Computing 25(3), 193-208 (1980) · Zbl 0424.60018 · doi:10.1007/BF02241999
[3] Batagelj, V., Brandes, U.: Efficient generation of large random networks. Phys. Rev. E 71(3), 36113 (2005) · doi:10.1103/PhysRevE.71.036113
[4] Blanca, A., Mihail, M.: Efficient generation \[\varepsilon\] ε-close to G(n,p) and generalizations. CoRR (2012). arXiv:1204.5834 · Zbl 0421.65001
[5] Bringmann, K., Friedrich, T.: Exact and efficient generation of geometric random variates and random graphs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M.Z., Peleg, D. (eds.) Automata, Languages, and Programming (ICALP), vol. 7965, pp. 267-278. Springer, Berlin, Heidelberg (2013) · Zbl 1336.05114
[6] Bringmann, K., Kuhn, F., Panagiotou, K., Peter, U., Thomas, H.: Internal dla: Efficient simulation of a physical growth model. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming (ICALP), vol. 8572, pp. 247-258. Springer, Berlin, Heidelberg (2014) · Zbl 1409.68134
[7] Devroye, L.: Generating the maximum of independent identically distributed random variables. Comput. Math. Appl. 6(3), 305-315 (1980) · Zbl 0439.65005 · doi:10.1016/0898-1221(80)90039-5
[8] Devroye, L.: Non-Uniform Random Variate Generation. Springer, Berlin (1986) · Zbl 0593.65005 · doi:10.1007/978-1-4613-8643-8
[9] Farach-Colton, M., Tsai, M.T.: Exact sublinear binomial sampling. In: Cai, L., Cheng, S.-W., Lam, T.W. (eds.) Algorithms and Computation (ISAAC), vol. 8283, pp. 240-250. Springer, Berlin, Heidelberg (2013) · Zbl 1331.68278
[10] Fox, J., Weisberg, S.: An R Companion to Applied Regression. Sage Publications, New York (2010)
[11] Galassi, M.: Gnu Scientific Library: Reference Manual (2003)
[12] Granlund, T.: The GMP Development Team. GNU MP: The GNU Multiple Precision Arithmetic Library (2012)
[13] Hörmann, W.: The generation of binomial random variates. J. Stat. Comput. Simul. 46(1-2), 101-110 (1993) · Zbl 0829.65001 · doi:10.1080/00949659308811496
[14] Hörmann, W., Leydold, J., Derflinger, G.: Automatic Nonuniform Random Variate Generation. Springer, Berlin (2004) · Zbl 1038.65002 · doi:10.1007/978-3-662-05946-3
[15] Kachitvichyanukul, V., Schmeiser, B.W.: Binomial random variate generation. Commun. ACM 31(2), 216-222 (1988) · doi:10.1145/42372.42381
[16] Karney, C.F.F.: Sampling exactly from the normal distribution. CoRR (2013). arXiv:1303.6257 · Zbl 1357.65008
[17] Knuth, D., Yao, A.: Algorithms and Complexity: New Directions and Recent Results, Chap. The Complexity of Nonuniform Random Number Generation. Academic Press, Waltham (1976)
[18] Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, vol. 2. Addison-Wesley, Boston (1997) · Zbl 0895.65001
[19] Kronmal, R.A., Peterson, A.V.J.: On the alias method for generating random variables from a discrete distribution. Am. Stat. 33(4), 214-218 (1979) · Zbl 0421.65001
[20] Miller, J.C., Hagberg, A.: Efficient generation of networks with given expected degrees. In: Frieze, A.M., Horn, P., Pralat, P. (eds.) Algorithms and Models for the Web Graph (WAW), vol. 6732, pp. 115-126. Springer, Berlin, Heidelberg (2011) · Zbl 1328.05183
[21] Patterson, R.S., Louisville, U.: Testing the Effects of Predictors Using Data Generated by Non-identity Link Functions of the Single-Index Model: A Monte Carlo Approach. University of Louisville, Louisville (2008)
[22] R Development Core Team: R: A Language and Environment for Statistical Computing (2008)
[23] Stadlober, E., Zechner, H.: The patchwork rejection technique for sampling from unimodal distributions. Trans. Model. Comput. Simul. 9(1), 59-80 (1999) · Zbl 1391.65016 · doi:10.1145/301677.301685
[24] Stillwell, J.: Elements of Number Theory. Springer, Berlin (2003) · Zbl 1112.11002 · doi:10.1007/978-0-387-21735-2
[25] Tsai, M., Wang, D., Liau, C., Hsu, T.: Heterogeneous subset sampling. In: Thai, M.T., Sahni, S. (eds.) Computing and Combinatorics (COCOON). vol. 6196, pp. 500-509. Springer, Berlin, Heidelberg (2010) · Zbl 1286.68363
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.