Copyright | (c) Maciej Bendkowski 2019 |
---|---|

License | BSD3 |

Maintainer | maciej.bendkowski@tcs.uj.edu.pl |

Stability | experimental |

Safe Haskell | Safe |

Language | Haskell2010 |

- 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)

## Synopsis

- data Rand g = Rand {}
- empty :: Rand g -> Bool
- init :: RandomGen g => g -> Rand g
- type BuffonMachine g = State (Rand g)
- runRIO :: BuffonMachine StdGen a -> IO a
- histogram :: RandomGen g => Discrete g -> Int -> BuffonMachine g [(Int, Occur)]
- histogramIO :: BuffonMachine StdGen Int -> Int -> IO ()
- samples :: RandomGen g => BuffonMachine g a -> Int -> BuffonMachine g [a]
- samplesIO :: BuffonMachine StdGen a -> Int -> IO [a]
- samplesIO' :: BuffonMachine StdGen a -> Int -> IO [a]
- type Bern g = BuffonMachine g Bool
- type Discrete g = BuffonMachine g Int
- toDiscrete :: Bern g -> Discrete g
- flip :: RandomGen g => Bern g
- flip' :: RandomGen g => Bern g
- rational :: RandomGen g => Int -> Int -> Bern g
- real :: RandomGen g => Double -> Bern g
- repeat :: RandomGen g => Int -> Bern g -> BuffonMachine g [Bool]
- cond :: Bern g -> BuffonMachine g a -> BuffonMachine g a -> BuffonMachine g a
- neg :: Bern g -> Bern g
- (/\) :: Bern g -> Bern g -> Bern g
- (\/) :: Bern g -> Bern g -> Bern g
- square :: Bern g -> Bern g
- mean :: RandomGen g => BuffonMachine g a -> BuffonMachine g a -> BuffonMachine g a
- even :: RandomGen g => Bern g -> Bern g
- exp :: RandomGen g => Bern g -> Bern g
- recipLog :: RandomGen g => Bern g -> Bern g
- geometric :: Bern g -> Discrete g
- geometricReal :: RandomGen g => Double -> Discrete g
- geometricRational :: RandomGen g => Int -> Int -> Discrete g
- vonNeumann :: RandomGen g => ([Int] -> Bool) -> Discrete g -> Discrete g
- poisson :: RandomGen g => Discrete g -> Discrete g
- generalPoisson :: RandomGen g => Double -> Discrete g
- poissonReal :: RandomGen g => Double -> Discrete g
- poissonRational :: RandomGen g => Int -> Int -> Discrete g
- logarithmic :: RandomGen g => Discrete g -> Discrete g
- logarithmicReal :: RandomGen g => Double -> Discrete g
- logarithmicRational :: RandomGen g => Int -> Int -> Discrete g
- uniform :: RandomGen g => Int -> Discrete g
- data DecisionTree a
- = Decision a
- | Toss (DecisionTree a) (DecisionTree a)

- decisionTree :: [Double] -> DecisionTree Int
- unveil :: Show a => Int -> DecisionTree a -> String
- maxFlips :: DecisionTree a -> Int
- minFlips :: DecisionTree a -> Int
- avgFlips :: DecisionTree a -> Double
- choice :: RandomGen g => DecisionTree a -> BuffonMachine g a

# Buffon machines and related utilities.

32-bit buffered random bit generator (RBG).

empty :: Rand g -> Bool Source #

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

type BuffonMachine g = State (Rand g) Source #

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 Source #

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)] Source #

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 () Source #

A `histogram`

variant within the IO monad.

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

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

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

A space efficient variant of `samplesIO`

.

# Random variables.

type Bern g = BuffonMachine g Bool Source #

Bernoulli variables.

type Discrete g = BuffonMachine g Int Source #

General discrete variables.

toDiscrete :: Bern g -> Discrete g Source #

Lifts a Bernoulli variable to a discrete one.

# Coin flips.

flip :: RandomGen g => Bern g Source #

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

.

# Bernoulli variable generators.

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

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 Source #

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] Source #

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

:: Bern g | 'if' condition ... |

-> BuffonMachine g a | ... 'then' expression ... |

-> BuffonMachine g a | ... 'else' expression. |

-> BuffonMachine g a |

Conditional if-then-else combinator.

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

Mean combinator.

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

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

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

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

# Discrete variable generators.

geometric :: Bern g -> Discrete g Source #

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

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

A variant of geometric using the `real`

Bernoulli generator.

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

A variant of geometric using the `rational`

Bernoulli generator.

:: 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 Source #

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 Source #

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 Source #

Poisson distribution with the given double-precision parameter.

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

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 Source #

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

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

Logarithmic distribution with the given double-precision parameter.

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

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 Source #

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 Source #

Decision trees.

Decision a | |

Toss (DecisionTree a) (DecisionTree a) |

## Instances

Show a => Show (DecisionTree a) Source # | |

Defined in Data.Buffon.Machine showsPrec :: Int -> DecisionTree a -> ShowS # show :: DecisionTree a -> String # showList :: [DecisionTree a] -> ShowS # | |

Lift a => Lift (DecisionTree a) Source # | |

Defined in Data.Buffon.Machine lift :: DecisionTree a -> Q Exp # |

decisionTree :: [Double] -> DecisionTree Int Source #

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 Source #

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

maxFlips :: DecisionTree a -> Int Source #

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

minFlips :: DecisionTree a -> Int Source #

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

avgFlips :: DecisionTree a -> Double Source #

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 Source #

Draws a discrete variable according to the given decision tree.