turi::random::alias_sampler Class Reference

#include <core/random/alias.hpp>

Public Member Functions
	alias_sampler (const std::vector< double > &p)
size_t	sample ()

Detailed Description

This is a standard algorithm for sampling from probability mass functions. It is also known as the Walker Method. Typically sampling from general discrete functions requires the inverse CDF method, which means each sample is O(K) where K is the number of outcomes in the pmf. The alias method, on the other hand, requires O(K) setup but requires only O(1) for each sample. To be specific, each sample only requires a uniformly generated float and a uniformly generated integer.

For more details, see http://www.cs.toronto.edu/~gdahl/papers/aliasMethod.pdf http://luc.devroye.org/chapter_three.pdf, p. 107

Definition at line 29 of file alias.hpp.

Constructor & Destructor Documentation

alias_sampler()

turi::random::alias_sampler::alias_sampler ( const std::vector< double > &  p )

explicit

Constructor.

Parameters

p	Vector representing the probability mass function with K outcomes, where K is the size of the vector. Values should be nonnegative, but they need not sum to 1.

Member Function Documentation

sample()

size_t turi::random::alias_sampler::sample

(

)

Sample from the PMF using the alias method.

Returns

an integer between 0 and K-1, where K is the number of outcomes in the provided pmf. A value i is returned with probability

p_i / sum_{j=0}^{K-1} p_j

---

The documentation for this class was generated from the following file:

• core/random/alias.hpp