An Empirical Study of Random Sampling Methods for Changing Discrete Distributions

• Author / Creator

  Tang, Yunpeng

• 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.

• Subjects / Keywords

  • Sampling Methods
  • Changing Discrete Distributions
  • Random Sampling

• Graduation date

  Spring 2020

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-781s-df42

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.