An Empirical Study of Random Sampling Methods for Changing Discrete Distributions
Yunpeng Tang · ERA: Education and Research Archive (University of Alberta) · 2020
In this thesis, we focus on finding efficient practical random sampling methods for time-changing discrete distributions. We empirically study ten methods including existing algorithms, and two new ones: three level search and the flat method. We review the core ideas of existing methods including their runtime complexity and correctness. We study how algorithms for static distribution can be adapted to the dynamic case that we find in many scenarios. We also implement all methods in a software package UpdateRandom. All methods were tested in the test platform described in the thesis to make sure they are able to generate random numbers properly according to the distribution and their performance matches the analytical result. In order to measure their performance in practice, we used a linear regression model to determine the cost of reference implementations as a function of the number of random samples, the number of weight updates, and the size of the weight array. With the models and application examples we provide, readers can easily find the most efficient methods for any usage scenario.