User Tools

Site Tools


ransampl

This is the home page of libransampl, a small C library for sampling random events from a discrete probability distribution, using the Walker-Vose alias method.

Introduction

This library solves the task of drawing random numbers from the finite set {0, …,n-1}, respecting given probabilities p0, …, pn-1.

This is an important problem with many applications, especially in Monte-Carlo simulations. There are several solutions to it. They all start with a standard random number u that is uniformly distributed in the interval [0,1). The simplest algorithm would then proceed as follows:

  if      u<p[0]            then return 0;
  else if u<p[0]+p[1]       then return 1;
  else if u<p[0]+p[1]+p[2]  then return 2;
  ... and so on ...

This algorithm is O(n). Using binary search, it can be brought down to O(log(n)).

However, there is another solution that is O(1). It uses precomputed arrays. Effort for this precomputation is O(n). Drawing a representative event requires just drawing of u plus two array lookups plus little arithemetics, independent of n. This ingenious algorithm is called the alias method. It is due to Walker (1974/77), with refinements by Vose (1991). It is the preferred method for M > > n > > 1, where M is the number of drawings. This is the method implemented in libransampl.

References

Original papers:

  • A. J. Walker, Electronics Letters 10, 127 (1974); ACM TOMS 3, 253 (1977)
  • M. D. Vose, IEEE T. Software Eng. 17, 972 (1991)

Textbooks that discuss the alias method include:

  • G. S. Fishman, Monte Carlo. Concepts, Algorithms, Applications. Springer (1995)
  • D. E. Knuth, The Art of Computer Programming, Vol 2: Seminumerical Algorithms. Sect. 3.4.1. Addison-Wesley( 31998)

A web ressource that explains the alias method in much detail:

User Documentation

See the manual page ransampl(3).

Installation

Dependencies

While the library itself has no external dependencies, the demo program sampling1 requires uniform random numbers from the GNU Scientific Library GSL. We therefore link with -lgslcblas -lgsl.

From source

Download location: http://apps.jcns.fz-juelich.de/src/ransampl/

The source package comes with build scripts generated with GNU autotools, to be run with the usual commands ./configure, make, sudo make install. To test, run the program demo/sampling1.