Discrete random variates with finite support using differential search trees

Abstract

Differential search trees can be used for selection with replacement and for a form of selection without replacement. We show that they can be extended to many different types of selection, both with and without replacement. In addition, virtually every aspect of a differential search tree can be modified dynamically. We provide algorithms for making these modifications. Virtually all differential search tree algorithms are straightforward and easy to implement, especially with our preferred implementation, which is both simple and efficient. Differential search tree operations are virtually all logarithmic with the exception of building the tree and dynamically adding leaves to the tree, which are both linear.

Keywords

Random variates discrete distributions with finite support differential search trees

Get full access to this article

View all access options for this article.

References

Maurer

. Finite random variates using differential search trees. In: SummerSim ’17. Proceedings of the summer simulation multi-conference, 9–12 July 2017, Article no. 28, pp. 1–12, https://dl.acm.org/doi/abs/10.5555/3140065.3140093

Bringman

Panagiotou

. Efficient sampling methods for discrete distributions. In: International colloquium on automata, languages, and programming, 2012, pp. 133–144, https://link-springer-com-443.web.bisu.edu.cn/chapter/10.1007/978-3-642-31594-7_12

Devroye

. Non-uniform random variate generation. New York: Springer-Verlag, 1986.

Hagerup

Mehlhorn

Munro

. Optimal algorithms for generating discrete random variables with changing distributions. Proceedings of the 20th international colloquium on automata, languages and programming. Lecture Notes Comput Sci 1993; 700: 253–264, https://people.mpi-inf.mpg.de/~mehlhorn/ftp/DiscreteRandomVariates.pdf

Kochar

Korwar

. On random sampling from a finite population without replacement. Ann Inst Stat Math 2001; 3: 631–646.

Muller

. Accelerating random weighted sampling without replacement. Working paper, 2016, http://www.researchgate.net

Marsaglia

. Generating discrete random variables in a computer. Commun ACM 1963; 6: 37–38.

Marsaglia

Tsang

Wang

. Fast generation of discrete random variables. J Stat Soft 2004; 11: 1–11.

Matias

Vitter

. Dynamic generation of discrete random variates. Theory Comput Syst 2003; 36: 329–358.

10.

Rajasekaran

Ross

. Fast algorithms for generating discrete random variates with changing distributions. ACM Trans Model Comput Simul 1993; 3: 1–19.

11.

Shmerling

. A range reduction method for generating discrete random variables. Stat Probab Lett 2013; 83: 1094–1099.

12.

Stadlober

. Ratio of uniforms as a convenient method for sampling from classical discrete distributions. In: Proceedings of the 1989 winter simulation conference, Washington, DC, 4–6 December 1989. New York: IEEE.

13.

Vose

. A linear algorithm for generating random numbers with a given distribution. IEEE Trans Soft Eng 1991; 17: 972–975.

14.

Walker

. An efficient method for generating discrete random variables with general distributions. ACM Trans Math Soft 1977; 3: 253–256.

15.

Wong

Easton

. An efficient method for weighted sampling without replacement. SIAM J Comput 1980; 9: 111–114.

16.

Maurer

. Generating test data with enhanced context-free grammars. IEEE Soft 1990; 7: 50–55.

17.

Maurer

. The design and implementation of a grammar-based data generator. Soft Pract Exp 1992; 22: 223–244.

18.

Cormen

Leisersen

Rivest

, et al. Introduction to algorithms. 3rd ed. Boston, MA: Massachusetts Institute of Technology, 2009.

19.

Knuth

. Seminumerical algorithms the art of computer programming (Volume 2). Reading, MA: Addison-Wesley, 1997, pp. 10–26.