Skip to content

an Elixir library for generating random values (samples) from the given discrete distribution

License

Notifications You must be signed in to change notification settings

SergeTupchiy/nonuniform_rand

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

1 Commit
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

NonuniformRand

NonuniformRand is an Elixir library that provides the ability to generate random values (samples) from the given discrete distribution (represented as a list/map of values and their probabilities). Two algorithms are implemented:

  • alias method (implementation is based on the decent article by Keith Schwarz that you can find at: http://www.keithschwarz.com/darts-dice-coins/). This algorithm is aimed at sampling a value at a constant time O(1).
  • simple method that builds a binary search tree from the distribution's cumulative density function(CDF) and uses it for sampling random values. The complexity, therefore, is O(log n).

Both algorithms require initialization (see details in Examples section below).

Usage

Add nonuniform_random as a dependency in your mix.exs:

{:nonuniform_rand, git: "https://github.com/sergetupchiy/nonuniform_rand.git", tag: "v0.1.0"}

Usage example:

alias NonuniformRand 
probs = [high_prob: 0.6, medium_prob: 0.3, low_prob: 0.096, very_low_prob: 0.04]
alias_gen = NonuniformRand.make_generator(probs, :alias)
cdf_gen = NonuniformRand.make_generator(probs, :cdf)
cdf_gen.(:next_rand)
alias_gen.(:next_rand)

If you don't like rather weird idea of anonymous function calls with :next_rand atom as an argument, you can initialize necessary algorithm and use it directly:

probs = [high_prob: 0.6, medium_prob: 0.3, low_prob: 0.096, very_low_prob: 0.04]
alias NonuniformRand.CdfTree
cdf_tree = CdfTree.init_cdf_tree(probs)
CdfTree.next_random(cdf_tree)
alias NonuniformRand.AliasMethod
alias_tables = AliasMethod.init_prob_alias_tables(probs)
AliasMethod.next_random(alias_tables) 

Proving that it actually works...

The repository includes nested repository with some profiling of the both algorithms and simple verification that generated values do conform to the original distribution, you can run it as follows:

$ cd examples/profiling
$ mix run -e 'Profiling.run'

The output will look something like this:

Task "Alias initialization, small data input" executed in: 7048 nanoseconds
Task "CDF initialization, small data input" executed in: 4147 nanoseconds
Task "Alias small data input, generating 1_000_000 randoms" executed in: 771 milliseconds
Task "CDF small data input, generating 1_000_000 randoms" executed in: 317 milliseconds
small data input generated values accuracy report:
 -------------------------------------------------------------------------------------------------------
 | "Input probabilities" | "CDF relative freqs"                 | "Alias relative freqs"               | 
 -------------------------------------------------------------------------------------------------------
 | {"high_prob", 0.6}    | {"high_prob", 0.5992854007145992}    | {"high_prob", 0.6003303996696003}    | 
 | {"medium_prob", 0.35} | {"medium_prob", 0.35063464936535066} | {"medium_prob", 0.35016664983335016} | 
 | {"low_prob", 0.05}    | {"low_prob", 0.05007994992005008}    | {"low_prob", 0.0495029504970495}     | 
 -------------------------------------------------------------------------------------------------------
Task "Alias initialization, large data input" executed in: 10864048 nanoseconds
Task "CDF initialization, large data input" executed in: 1996765 nanoseconds
Task "Alias large data input, generating 1_000_000 randoms" executed in: 914 milliseconds
Task "CDF large data input, generating 1_000_000 randoms" executed in: 644 milliseconds
large data input generated values accuracy report:
....

About

an Elixir library for generating random values (samples) from the given discrete distribution

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages