Acyclic Markov chain (source code)

= Acyclic Markov chain

On a finite <state space>, an <acyclic Markov chain> has no directed cycle among its nonabsorbing states. Order those states topologically by their possible transitions. Hitting <probabilities> and expected absorption times can then be calculated in reverse order, because a state's equations involve only later states.

For example, let $A$ go to $B$ or to an <Absorbing state> $C$ with equal <probabilities>, and let $B$ go directly to $C$. The expected absorption times are $t_C=0$, $t_B=1$ and $t_A=1+t_B/2=3/2$. This is dynamic programming on the transition <graph>, rather than a general simultaneous linear solve.

If a convention permits self-transitions while forbidding cycles between distinct nonabsorbing states, the holding <probabilities> must be retained. Provided $P_{ii}<1$, the same backward calculation uses
$$
t_i=\frac{1+\sum_{j\ne i}P_{ij}t_j}{1-P_{ii}}.
$$
A self-loop at $A$ of <Probability> $1/2$, with <probabilities> $1/4$ each to $B,C$, gives $t_A=5/2$ instead of $3/2$. The finite-state assumption is substantive: an infinite deterministic chain $i\mapsto i+1$ is acyclic but has no terminal <Absorbing state> and no finite reverse recursion of this kind.