Dist-0.2.0.0: A Haskell library for probability distributions

Copyright (c) William Yager 2015 MIT will (dot) yager (at) gmail (dot) com provisional portable None Haskell2010

Numeric.Probability.Distribution

Description

This module provides a data structure and associated functions for representing discrete probability distributions.

All time and space complexity metrics are given in terms of `n`. In this case, `n` refers to the number of unique outcomes inserted into the tree. If one were to construct a tree by inserting a billion of the same outcome, `n` would still be 1.

The data structure is optimized for fast sampling from the distribution. Sampling ranges from `O(1)` to `O(log(n))` depending on the distribution.

Under the hood, the distribution is represented by a perfectly balanced binary tree. The tree enforces a heap property, where more likely outcomes are closer to the top than less likely outcomes. Because we're more likely to sample from those outcomes, we minimize the amount of time spent traversing the tree.

When a duplicate outcome is inserted into the tree, the tree's "dups" counter is incremented. When more than half the tree is duplicate entries, the entire tree is rebuilt from scratch. Using amortized complexity analysis, we can show that insertion is, at worst, `log(n)` amortized complexity. This prevents the size of tree from increasing to more than `O(n)`, even with many duplicate outcomes inserted.

Synopsis

# The distribution type

data Distribution p o Source

A probability distribution with probabilities of type `p` and outcomes/events of type `o`.

Instances

 (Num p, Show p, Ord o, Show o) => Show (Distribution p o)

# Probability operations

sample :: (Ord p, Num p, Random p, MonadRandom m) => Distribution p o -> m o Source

Take a sample from the distribution. Can be used with e.g. `evalRand` or `evalRandIO` from `Control.Monad.Random`. `O(log(n))` for a uniform distribution (worst case), but approaches `O(1)` with less balanced distributions.

cumulate :: Num p => Distribution p o -> p Source

The sum of all probabilities in the distribution. `O(1)`

normalize :: Fractional p => Distribution p o -> Distribution p o Source

Normalizes the distribution. After normalizing, `cumulate distribution` is 1. `O(n)`

# Building

empty :: Num p => Distribution p o Source

The empty distribution. `O(1)`

insert :: (Ord o, Num p, Ord p) => (o, p) -> Distribution p o -> Distribution p o Source

Insert an outcome into the distribution. Inserting `(o,p1)` and `(o,p2)` results in the same sampled distribution as inserting `(o,p1+p2)`. `O(log(n))` amortized.

fromList :: (Ord o, Num p, Ord p) => [(o, p)] -> Distribution p o Source

`O(n*log(n))` amortized.

# Modifying

reweight :: (Ord o, Num p, Ord p) => ((o, p) -> p) -> Distribution p o -> Distribution p o Source

Reweights the probabilities in the distribution based on the given function. `n*log(n)`

# Reducing

toList :: (Ord o, Num p) => Distribution p o -> [(o, p)] Source

`O(n*log(n))`.

foldrWithP :: ((o, p) -> b -> b) -> b -> Distribution p o -> b Source

A right-associative fold on the tree structure, including the probabilities. Note that outcomes may be repeated within the data structure. If you want identical outcomes to be lumped together, fold on the list produced by `toList`. `O(n)`.

# Combining

joint :: (Ord o1, Ord o2, Num p, Ord p) => Distribution p o1 -> Distribution p o2 -> Distribution p (o1, o2) Source

Creates a new distribution that's the joint distribution of the two provided. `O(nm*log(nm))` amortized.

sum :: (Ord o, Num p, Ord p) => Distribution p o -> Distribution p o -> Distribution p o Source

Creates a new distribution by summing the probabilities of the outcomes in the two provided. `O((n+m)log(n+m))` amortized.

# Debugging

invariants :: (Num p, Ord p, Show p, Ord e, Show e) => Distribution p e -> Either String () Source

A series of tests on the internal structure of the distribution. For debugging purposes.