A Tree here is a lazy, infinitely wide and infinitely deep rose tree, labelled by Doubles.

A probability distribution over a is a function Tree -> a .

We can think of this as the law of a random variable, indexed by the source of randomness, which is Tree.

According to the monad implementation, a program uses up bits of the tree as it runs. The tree being infinitely wide and deep allows for lazy computation.

An unnormalized measure is represented by a probability distribution over pairs of a weight and a result.

A uniform sample is a building block for probability distributions.

This is implemented by getting the label at the head of the tree and discarding the rest.

Regard a probability measure as an unnormalized measure.

A one point measure with a given score (or weight, or mass, or likelihood), which should be a positive real number.

A score of 0 describes impossibility. To avoid numeric issues, we encode it as exp(-300) instead.

Produce a stream of samples, using Metropolis Hastings simulation.

The weights are also returned. Often the weights can be discarded, but sometimes we may search for a sample of maximum score.

The algorithm works as follows.

At each step, we randomly change some sites (nodes in the tree). We then accept or reject these proposed changes, using a probability that is determined by the weight of the measure at the new tree. If rejected, we repeat the previous sample.

This kernel is related to the one introduced by Wingate, Stuhlmuller, Goodman, AISTATS 2011, but it is different in that it works when the number of sites is unknown. Moreover, since a site is a path through the tree, the address is more informative than a number, which avoids some addressing issues.

When 1/p is roughly the number of used sites, then this will be a bit like "single-site lightweight" MH. If p = 1 then this is "multi-site lightweight" MH.

Tip: if m :: Prob a then use map fst $ (mh 1 $ sample m) to get a stream of samples from a probability distribution without conditioning. -

Irreducible form of mh. Takes p like mh, but also q, which is the chance of proposing an all-sites change. Irreducibility means that, asymptotically, the sequence of samples will converge in distribution to the renormalized version of m.

The kernel in mh is not formally irreducible in the usual sense, although it is an open question whether this is a problem for asymptotic convergence in any definable model. In any case, convergence is only asymptotic, and so it can be helpful to use mhirreducible is that in some situations.

Roughly this avoids mh getting stuck in one particular mode, although it is a rather brutal method.

Runs an unnormalized measure and gets out a stream of (result,weight) pairs.

These are not samples from the renormalized distribution, just plain (result,weight) pairs. This is useful when the distribution is known to be normalized already.

Weighted importance sampling first draws n weighted samples, and then samples a stream of results from that, regarded as an empirical distribution. Sometimes called "likelihood weighted importance sampling".

This is a reference implementation. It will not usually be very efficient at all, but may be useful for debugging.

Useful function which thins out a stream of results, as is common in Markov Chain Monte Carlo simulation.

every n xs returns only the elements at indices that are multiples of n.-

Generate a tree with uniform random labels.

This uses split to split a random seed.

runProb runs a probability deterministically, given a source of randomness.