Expand description
Solving loops as absorbing Markov chains (docs/semantics.md, section 10).
A loop’s states are its worlds at the loop’s start, told apart by the variables read later. Running the body once from each state gives the chance of going on to each state, and of leaving the loop. The expected number of times each state is visited, from the weights the loop starts with, then says how much weight leaves by each way out.
States are solved one strongly connected group at a time, in the order weight flows through them. Within a group, states are eliminated one by one (Grassmann, Taksar and Heyman, 1985). Every step adds nonnegative numbers: the chance of leaving a state is the sum of its ways out, never 1 minus the chance of staying, so a chain whose exits are rare loses no precision.
Structs§
- Chain
- One step of a chain from each of its states.