Abstract
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 and has no precision loss, however, this method is often too slow in many settings. The problem of sampling from a binomial distribution in sublinear time has been extensively studied and implemented in such packages as R [22] and the GNU Scientific Library (GSL) [10], however, all known sublinear-time algorithms involve precisions loss, which introduces artifacts into the sampling, such as discontinuities.
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.
This research was supported by NSF Grants IIS-1247750 and CCF-1114930.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Abe, J., Kamimura, Y.: Do female parasitoid wasps recognize and adjust sex ratios to build cooperative relationships? Journal of Evolutionary Biology 25(7), 1427–1437 (2012)
Ahrens, J.H., Dieter, U.: Sampling from binomial and poisson distributions: A method with bounded computation times. Computing 25(3), 193–208 (1980)
Batagelj, V., Brandes, U.: Efficient generation of large random networks. Physical Review E 71(3), 36113 (2005)
Blanca, A., Mihail, M.: Efficient generation - close to G(n,p) and generalizations. CoRR abs/1204.5834 (2012)
Bringmann, K., Friedrich, T.: Exact and efficient generation of geometric random variates and random graphs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 267–278. Springer, Heidelberg (2013)
Devroye, L.: Generating the maximum of independent identically distributed random variables. Computers and Mathematics with Applications 6(3), 305–315 (1980)
Devroye, L.: Non-Uniform Random Variate Generation. Springer (1986)
Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley (January 1968)
Fox, J., Weisberg, S.: An R Companion to Applied Regression. SAGE Publications (2010)
Galassi, M., et al.: Gnu Scientific Library: Reference Manual. Network Theory Ltd. (2003)
Granlund, T.: The GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library, 5.0.5 edn. (2012), http://gmplib.org/
Hörmann, W.: The generation of binomial random variates. Journal of Statistical Computation and Simulation 46, 101–110 (1993)
Hörmann, W., Leydold, J., Derflinger, G.: Automatic nonuniform random variate generation. Springer (2004)
Kachitvichyanukul, V., Schmeiser, B.W.: Binomial random variate generation. Commun. ACM 31, 216–222 (1988)
Karney, C.F.F.: Sampling exactly from the normal distribution. CoRR abs/1303.6257 (2013)
Knuth, D., Yao, A.: The complexity of nonuniform random number generation. In: Algorithms and Complexity: New Directions and Recent Results. Academic Press (1976)
Knuth, D.E.: The art of computer programming. Seminumerical algorithms, vol. 2. Addison-Wesley Longman Publishing Co., Inc. (1997)
Kronmal, R.A., Peterson, A.V.J.: On the alias method for generating random variables from a discrete distribution. The American Statistician 33(4), 214–218 (1979)
Miller, J.C., Hagberg, A.: Efficient generation of networks with given expected degrees. In: Frieze, A., Horn, P., Prałat, P. (eds.) WAW 2011. LNCS, vol. 6732, pp. 115–126. Springer, Heidelberg (2011)
Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press (1995)
Patterson, R.S.: of 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 (2008)
R Development Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing (2008)
Sauerhoff, M., Woelfel, P.: Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. In: STOC, pp. 186–195. ACM (2003)
Serfling, R.J.: Probability Inequalities for the Sum in Sampling without Replacement. The Annals of Statistics 2(1), 39–48 (1974)
Stadlober, E., Zechner, H.: The patchwork rejection technique for sampling from unimodal distributions. ACM Trans. Model. Comput. Simul. 9(1), 59–80 (1999)
Stillwell, J.: Elements of Number Theory. Springer (2003)
Tsai, M.-T., Wang, D.-W., Liau, C.-J., Hsu, T.-S.: Heterogeneous subset sampling. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 500–509. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farach-Colton, M., Tsai, MT. (2013). Exact Sublinear Binomial Sampling. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)