Data.Buffon.Machine

• Buffon machines* is a simple, monadic implementation of Buffon machines [1] meant for *perfect* simulation of discrete random variables using a discrete oracle of random bits. Buffon machines are implemented as monadic computations consuming random bits, provided by a 32-bit buffered oracle. Bit regeneration and computation composition is handled within the monad itself.

The main purpose of *Buffon machines* is to provide an experimental framework for discrete random variable generation required in the design and implementation of various combinatorial samplers, such as analytic samplers (a.k.a. Boltzmann samplers). In particular, its goal is to provide tools to *perfectly* simulate discrete distributions using as few random bits as possible.

The current implementation provides several basic generators discussed in [1]. In particular, it offers perfect generators for geometric, Poisson, and logarithmic distributions with given rational or real (i.e. double-precision floating) parameters, as well as a bit-optimal discrete uniform variable and Bernoulli generators described in [2]. More involved Buffon machines can be compiled using the provided combinators.

General, non-uniform discrete variable generation, in the spirit of Knuth and Yao [3], is also available. However, it should be noted that the current implementation does not achieve optimal average bit consumption, except for a limited number of special cases.

References:

1

Ph. Flajolet, M. Pelletier, M. Soria : “On Buffon Machines and Numbers”, SODA'11 - ACM/SIAM Symposium on Discrete Algorithms, San Francisco, USA, pp. 172-183, (Society for Industrial and Applied Mathematics) (2011)

2

J. Lumbroso : "Optimal Discrete Uniform Generation from Coin Flips, and Applications".

3

D. Knuth, A. Yao : "The complexity of nonuniform random number generation", in Algorithms and Complexity: New Directions and Recent Results, Academic Press, (1976)

Buffon machines and related utilities.

data Rand g

32-bit buffered random bit generator (RBG).

Constructors

Rand

Fields

• buffer :: !Word32

  Generator buffer.

• counter :: !Int

  Number of consumed buffer bits.

• oracle :: !g

  Random bit oracle.

empty :: Rand g -> Bool

Checks if the given RBG is empty or not. In other words, if a buffer refill is required.

init :: RandomGen g => g -> Rand g

A fresh RBG.

type BuffonMachine g a = State (Rand g) a

Computations consuming random bits using RBGs. Note that the implementation is essentially a State monad, passing RNG throughout its computations.

runRIO :: BuffonMachine StdGen a -> IO a

Runs the given Buffon machine within the IO monad using StdGen as its random bit oracle.

histogram :: RandomGen g => Discrete g -> Int -> BuffonMachine g [(Int, Occur)]

Computes a histogram of the given discrete random variable. The variable (Buffon machine) is evaluated n times and the data is collected in form of a multiset occurrence list.

histogramIO :: BuffonMachine StdGen Int -> Int -> IO ()

A histogram variant within the IO monad.

samples :: RandomGen g => BuffonMachine g a -> Int -> BuffonMachine g [a]

Using the given discrete variable (Buffon machine) outputs n random samples.

samplesIO :: BuffonMachine StdGen a -> Int -> IO [a]

Runs samples within the IO monad.

samplesIO' :: BuffonMachine StdGen a -> Int -> IO [a]

A space efficient variant of samplesIO.

Random variables.

type Bern g = BuffonMachine g Bool

Bernoulli variables.

type Discrete g = BuffonMachine g Int

General discrete variables.

toDiscrete :: Bern g -> Discrete g

Lifts a Bernoulli variable to a discrete one.

Coin flips.

flip :: RandomGen g => Bern g

Random coin flip. Note that the implementation handles the regeneration of the RBG, see Rand.

flip' :: RandomGen g => Bern g

Fair variant of flip. Implements the following, standard trick. Use flip twice and continue if and only if both coin flips yield the same bits. Although such a trick yields a truly fair coin flip, it should be noted that the standard flip is reasonably fair (and at the same time more efficient).

Bernoulli variable generators.

rational :: RandomGen g => Int -> Int -> Bern g

Given parameters a < b, both positive, returns a Bernoulli variable with rational parameter λ = a/b. Note: Implements the algorithm Bernoulli described by J. Lumbroso.

real :: RandomGen g => Double -> Bern g

Bernoulli variable with the given double-precision parameter. Note: the given parameter has to lie within 0 and 1 as otherwise the outcome is undefined.

Buffon machine combinators.

repeat :: RandomGen g => Int -> Bern g -> BuffonMachine g [Bool]

Evaluates the given Bernoulli variable n times and returns a list of resulting values.

cond

Arguments

:: Bern g

'if' condition ...

-> BuffonMachine g a

... 'then' expression ...

-> BuffonMachine g a

... 'else' expression.

-> BuffonMachine g a

Conditional if-then-else combinator.

neg :: Bern g -> Bern g

Negation combinator.

(/\) :: Bern g -> Bern g -> Bern g

Conjunction combinator.

(\/) :: Bern g -> Bern g -> Bern g

Disjunction combinator.

square :: Bern g -> Bern g

Squaring combinator.

mean :: RandomGen g => BuffonMachine g a -> BuffonMachine g a -> BuffonMachine g a

Mean combinator.

even :: RandomGen g => Bern g -> Bern g

Even-parity combinator.

exp :: RandomGen g => Bern g -> Bern g

Given a Bernoulli variable with parameter λ realises a Bernoulli variable with the parameter exp(-λ).

recipLog :: RandomGen g => Bern g -> Bern g

Given a Bernoulli variable with parameter λ realises a Bernoulli variable with the parameter λ/(log(1-λ)^{-1}).

Discrete variable generators.

geometric :: Bern g -> Discrete g

Given a Bernoulli variable with parameter λ, realises a geometric variable with the same parameter λ.

geometricReal :: RandomGen g => Double -> Discrete g

A variant of geometric using the real Bernoulli generator.

geometricRational :: RandomGen g => Int -> Int -> Discrete g

A variant of geometric using the rational Bernoulli generator.

vonNeumann

Arguments

:: RandomGen g

=> ([Int] -> Bool)

Permutation tester.

-> Discrete g

Geometric variable (Buffon machine).

-> Discrete g

General, von Neumann generation scheme.

poisson :: RandomGen g => Discrete g -> Discrete g

Given a geometric variable with parameter λ realises a Poisson variable with the same parameter λ. Note: the parameter λ has to lie within (0,1).

generalPoisson :: RandomGen g => Double -> Discrete g

Given a geometric variable with parameter λ realises a Poisson variable with the same parameter λ. Note: the current implementation is linear in the parameter λ.

poissonReal :: RandomGen g => Double -> Discrete g

Poisson distribution with the given double-precision parameter.

poissonRational :: RandomGen g => Int -> Int -> Discrete g

Given two positive and relatively prime integers p and q realises a Poisson variable with the paramter p/q.

logarithmic :: RandomGen g => Discrete g -> Discrete g

Given a geometric variable with parameter λ realises a logarithmic variable with the same parameter λ.

logarithmicReal :: RandomGen g => Double -> Discrete g

Logarithmic distribution with the given double-precision parameter.

logarithmicRational :: RandomGen g => Int -> Int -> Discrete g

Given two positive and relatively prime integers p and q realises a logarithmic variable with the paramter p/q.

Uniform variable generator.

uniform :: RandomGen g => Int -> Discrete g

Uniform random variable with support {0,1,...,n-1}. Note: uniform is an implementation of the FastDiceRoller algorithm described by J. Lumbroso.

Non-uniform variable generator.

data DecisionTree a

Decision trees.

Constructors

Decision a

Toss (DecisionTree a) (DecisionTree a)

Instances

Show a => Show (DecisionTree a)

Defined in Data.Buffon.Machine

Methods

showsPrec :: Int -> DecisionTree a -> ShowS

show :: DecisionTree a -> String

showList :: [DecisionTree a] -> ShowS

Lift a => Lift (DecisionTree a)

Defined in Data.Buffon.Machine

Methods

lift :: DecisionTree a -> Q Exp

decisionTree :: [Double] -> DecisionTree Int

Computes a decition tree for the given set of probabilities corresponding to successive outcomes 0,1,...,n-1. Note: the outcome decision tree is not guaranteed to be optimal, in the sense that it minimises the average-case bit consumption. Also, the final probability corresponding to the outcome n is computed automatically, so that it holds p_1 + ... + p_n = 1.

unveil :: Show a => Int -> DecisionTree a -> String

Returns a string representation of a suitably truncated variant of the given decision tree up to the given depth parameter.

maxFlips :: DecisionTree a -> Int

Computes the maximal number of flips required to make a definite decision for the given tree.

minFlips :: DecisionTree a -> Int

Computes the minimal number of flips required to make a definite decision for the given tree.

avgFlips :: DecisionTree a -> Double

Computes the average-case number of flips required to make a definite decision for the given tree.

choice :: RandomGen g => DecisionTree a -> BuffonMachine g a

Draws a discrete variable according to the given decision tree.