# Fast sampling from discrete distributions

**URL:** <https://discourse.julialang.org/t/fast-sampling-from-discrete-distributions/16372>\
**Category:** Statistics\
**Created:** [October 15, 2018, 11:40pm UTC](https://discourse.julialang.org/t/fast-sampling-from-discrete-distributions/16372 "2018-10-15T23:40:45Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![vancleve](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vancleve/32/4183_2.png) [@vancleve](https://discourse.julialang.org/u/vancleve)\
**Post date:** [October 15, 2018, 11:40pm UTC](https://discourse.julialang.org/t/fast-sampling-from-discrete-distributions/16372/1 "2018-10-15T23:40:45Z")

</div>

I’m writing some population simulations that make heavy use of categorical/multinomial sampling. I can see from the code that the categorical and multinomial samplers use the alias table method.

In this multinomial, the alias method is only used when `n^2 < k` where `n` is the number of trials and `k` is the number of possible events.

> <https://github.com/JuliaStats/Distributions.jl/blob/8bdcda68f903cf377ce37ee4540a3e4d936877e1/src/samplers/multinomial.jl#L53>

At some point I think that @johnmyleswhite added this cutoff; I was wondering what the rationale for it was?

Also, I wonder if there are some faster methods available. For example, [https://arxiv.org/pdf/1611.00532.pdf](https://arxiv.org/pdf/1611.00532.pdf)  
present an algorithm (#5 in Table 1) that appears to scale better with `k` than the alias table method (Walker’s algorithm). I don’t know the literature well, so I thought I’d mention this in case its new to folks but am generally interested in what are the fastest methods (big surprise 🙂 ).