This page describes the work in Yunpeng Tang's MSc thesis: An Empirical Study of Random Sampling Methods for Changing Discrete Distributions
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 example we provide, readers can easily find the most efficient methods for any usage scenario.
Created: Jan 18, 2020 Last modified: Jan 22, 2020
Yunpeng Tang and Martin Müller