Numeric.Probability.Distribution

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.

The distribution type

data Distribution p o

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

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

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

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

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

Building

empty :: Num p => Distribution p o

The empty distribution. O(1)

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

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

O(n*log(n)) amortized.

Modifying

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

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

O(n*log(n)).

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

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)

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

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

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