# WALKER_SAMPLE Efficient Probability Vector Sampling

WALKER_SAMPLE is a FORTRAN90 library which efficiently samples a discrete probability vector.

For outcomes labeled 1, 2, 3, ..., N, a discrete probability vector X is an array of N non-negative values which sum to 1, such that X[i] is the probability of outcome i.

To sample the probability vector is to produce a sequence of outcomes i1, i2, i3, ..., which are each drawn with probability corresponding to X. For a general discrete probability vector X, a single sample operation might be expected to take a time that is proportional to O(N), the number of outcomes. Walker showed that, by constructing a new data structure, it was possible to carry out a sample in time of order O(1), that is, independent of the number of possible outcomes.

### Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

### Languages:

WALKER_SAMPLE is available in a C version and a C++ version and a FORTRAN90 version and a Matlab version and a Python version.

### Related Data and Programs:

HISTOGRAM_DATA_2D_SAMPLE, a FORTRAN90 program which demonstrates how to construct a Probability Density Function (PDF) from a frequency table over a 2D domain, and then to use that PDF to create new samples.

IEEE_UNIFORM_SAMPLE, a FORTRAN90 library which tries to uniformly sample the discrete set of values that represent the legal IEEE real numbers;

PDFLIB, a FORTRAN90 library which evaluates Probability Density Functions (PDF's) and produces random samples from them, including beta, binomial, chi, exponential, gamma, inverse chi, inverse gamma, multinomial, normal, scaled inverse chi, and uniform.

PROB, a FORTRAN90 library which evaluates, samples, inverts, and characterizes a number of Probability Density Functions (PDF's) and Cumulative Density Functions (CDF's), including anglit, arcsin, benford, birthday, bernoulli, beta_binomial, beta, binomial, bradford, burr, cardiod, cauchy, chi, chi squared, circular, cosine, deranged, dipole, dirichlet mixture, discrete, empirical, english sentence and word length, error, exponential, extreme values, f, fisk, folded normal, frechet, gamma, generalized logistic, geometric, gompertz, gumbel, half normal, hypergeometric, inverse gaussian, laplace, levy, logistic, log normal, log series, log uniform, lorentz, maxwell, multinomial, nakagami, negative binomial, normal, pareto, planck, poisson, power, quasigeometric, rayleigh, reciprocal, runs, sech, semicircular, student t, triangle, uniform, von mises, weibull, zipf.

RANLIB, a FORTRAN90 library which produces random samples from Probability Density Functions (PDF's), including Beta, Chi-square Exponential, F, Gamma, Multivariate normal, Noncentral chi-square, Noncentral F, Univariate normal, random permutations, Real uniform, Binomial, Negative Binomial, Multinomial, Poisson and Integer uniform, by Barry Brown and James Lovato.

### Reference:

1. Donald Knuth,
Seminumerical algorithms,
2. Warren Smith,
How to sample from a probability distribution,
April 18, 2002.
3. Alastair Walker,
An efficient method for generating discrete random variables with general distributions,
ACM Transactions on Mathematical Software,
Volume 3, Number 3, September 1977, pages 253-256.

### List of Routines:

• I4_CHOOSE computes the binomial coefficient C(N,K) as an I4.
• I4_CHOOSE_TEST tests I4_CHOOSE.
• I4_UNIFORM_AB returns a scaled pseudorandom I4 between A and B.
• I4_UNIFORM_AB_TEST tests I4_UNIFORM_AB.
• NORMALIZE scales a vector X so its entries sum to 1.
• NORMALIZE_TEST tests NORMALIZE.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8_UNIFORM_01_TEST tests R8_UNIFORM_01
• R8VEC_PRINT prints an R8VEC.
• R8VEC_PRINT_TEST tests R8VEC_PRINT.
• R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
• R8VEC_UNIFORM_01_TEST tests R8VEC_UNIFORM_01.
• RANDOM_PERMUTATION applies a random permutation to an array.
• RANDOM_PERMUTATION_TEST tests RANDOM_PERMUTATION.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• WALKER_BUILD sets up the data for a Walker sampler.
• WALKER_BUILD_TEST tests WALKER_BUILD.
• WALKER_SAMPLER returns a random sample i=1..N with prob X(i).
• WALKER_SAMPLER_TEST tests WALKER_SAMPLER.
• WALKER_VERIFY verifies a Walker Sampler structure.
• WALKER_VERIFY_TEST tests WALKER_VERIFY.
• ZIPF_PROBABILITY sets up a Zipf probability vector.
• ZIPF_PROBABILITY_TEST tests ZIPF_PROBABILITY.

You can go up one level to the FORTRAN90 source codes.

Last revised on 20 February 2016.