A transition probability describes what can happen next, given the current state. In a Markov process, the transition function expresses that rule by taking a state and returning a distribution of possible next states. The next choice depends on the current state, not the earlier path. A separate initial distribution chooses the first state. section 16.1
Listing 16.1 A general-purpose Markov process
sealed class Markov<T> : IDistribution<IEnumerable<T>>
{
private readonly IDistribution<T> initial;
private readonly Func<T, IDistribution<T>> transition;
public static Markov<T> Distribution(
IDistribution<T> initial,
Func<T, IDistribution<T>> transition) =>
new Markov<T>(initial, transition);
private Markov(
IDistribution<T> initial,
Func<T, IDistribution<T>> transition)
{
this.initial = initial;
this.transition = transition;
}
public IEnumerable<T> Sample()
{
var distribution = initial;
while (distribution is not Empty<T>)
{
var state = distribution.Sample();
yield return state;
distribution = transition(state);
}
}
}
The generic C# sampler draws an initial state, then repeatedly calls `transition(state)` and samples the distribution it returns. An empty distribution ends the sequence. section 16.1
A gambler’s next chip count
Suppose the state is the number of chips in a pocket. At any count between 1 and 9, a coin flip makes the next count one lower or one higher, with equal probability. At 0 or 10, the transition returns an empty distribution: the gambler goes home. Starting from a randomly chosen count between 4 and 7 produces a sequence whose length is also random. section 16.1
A transition rule need not be written as a fixed table of numbers. It can be built from observations: count how often each word follows a given word, then use those counts as weights for that word’s next-word distribution. Count sentence openings separately to build the initial distribution. If a word has no recorded successor, the builder supplies an empty distribution. section 16.2
Listing 16.4 A mutable builder for Markov processes
sealed class MarkovBuilder<T> where T : notnull
{
private CategoricalBuilder<T> initial = new();
private Dictionary<T, CategoricalBuilder<T>> transitions = new();
public void AddInitial(T t)
{
initial.Add(t);
}
public void AddTransition(T t1, T t2)
{
if (!transitions.ContainsKey(t1))
transitions[t1] = new();
transitions[t1].Add(t2);
}
public Markov<T> ToDistribution()
{
var init = initial.ToDistribution();
var trans = transitions.ToDictionary(
kv => kv.Key,
kv => kv.Value.ToDistribution()); #1
return Markov<T>.Distribution(init,
k => trans.GetValueOrDefault(k, Empty<T>.Distribution));
}
}
The builder keeps a separate categorical-distribution builder for each current state. `AddTransition(t1, t2)` records an observed successor; `ToDistribution()` turns the recorded counts into a transition function. section 16.2
A transition that sometimes stays put
In Metropolis sampling, the current numerical sample is the state. The transition first samples a proposed value near it. A coin-flip distribution then selects either the proposal or the current value, using their target-density ratio to set the acceptance chance. Rejection therefore produces a repeated state, not a missing state. The choice of proposal distance matters: very small moves clump samples, while very large moves are often rejected. section 16.4
