A proposal distribution generates a candidate next state from the current state of a Markov chain. In the Metropolis algorithm, it is sampled to suggest movement through the target distribution. section 16.4
A practical proposal is often centered on the current sample. Its spread should reflect the expected range of plausible values: a normal distribution with a suitable standard deviation is a typical choice. section 16.4 section 16.5
The proposal participates in Metropolis sampling as follows:
- Sample a candidate from the distribution conditioned on the current state. section 16.4
- Compare the candidate's target weight with the current state's weight. section 16.4
- Accept a higher-weight candidate, or accept a lower-weight candidate probabilistically; otherwise repeat the current state. section 16.4
A random-walk proposal
In C#, proposal = current => Normal.Distribution(current, stddev) creates a normal distribution centered on the current value. The Metropolis sampler can then explore a posterior built from a prior and likelihood, such as coin fairness after observing nine heads in ten flips. section 16.5
Listing 16.7 The Metropolis algorithm
public sealed class Metropolis: IContinuousDistribution
{
private readonly IEnumerator<double> enumerator;
private readonly Func<double, double> target;
public static Metropolis Distribution(
Func<double, double> target,
IDistribution<double> initial,
Func<double, IDistribution<double>> proposal)
{
var markov = Markov<double>.Distribution(initial, transition);
return new Metropolis(target, markov.Sample().GetEnumerator());
IDistribution<double> transition(double current)
{
double proposed = proposal(current).Sample();
return new Flip<double>(proposed, current,
target(proposed) / target(current));
}
}
private Metropolis(
Func<double, double> target, IEnumerator<double> enumerator)
{
this.enumerator = enumerator;
this.target = target;
}
public double Sample()
{
enumerator.MoveNext();
return enumerator.Current;
}
public double Weight(double d) => target(d);
}
The implementation makes the proposal's role explicit: sample proposed from proposal(current), then construct an acceptance distribution from the target-weight ratio. section 16.4
