Suppose a gambler’s chips rise or fall by one after each bet. To choose the next chip count, a simulation needs the current count, not the whole betting history. That is the Markov property: the distribution of the next state depends only on the current state. Sampling an initial state, then repeatedly sampling a transition distribution, produces a random sequence of states. States may be discrete or continuous, and the sequence may be finite or infinite. 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 C# implementation makes the distinction between a state and its possible successors explicit. `Markov<T>` stores an initial `IDistribution<T>` and a transition function from `T` to `IDistribution<T>`. `Sample()` yields each sampled state, then asks the transition function what can happen next. An `Empty<T>` distribution ends the sequence. section 16.1
Gambler’s ruin
Let the state be the number of chips in a pocket. From an intermediate count, the transition samples either one chip fewer or one chip more; at zero or ten, it returns an empty distribution. A sample might wander through `5,4,3,4,5` before eventually reaching zero. Repeated samples can be counted to examine how long these walks last. The stopping rule belongs in the transition function, not in a separate history of bets. section 16.1
A word can be a state too. For a small text generator, count the first words of existing sentences to form the initial distribution. For each word, count the words observed immediately after it to form that word’s transition distribution. Sampling then joins locally plausible word pairs into new sentences; the resulting text can sound recognizably like its source while making little sense overall. 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));
}
}
`MarkovBuilder<T>` keeps one categorical builder for initial states and a dictionary of categorical builders for transitions. Converting the recorded counts to distributions supplies the two inputs required by `Markov<T>`; a state with no recorded successor maps to `Empty<T>`. section 16.2
The same sequence structure also supports the Metropolis algorithm. Its states are samples from a target distribution: each transition proposes a value near the current one, then chooses either the proposal or the current value again. This connects a simple random walk to sampling continuous distributions, including posterior distributions. section 16.4 section 16.6
