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 go to or to an Absorbing state with equal probabilities, and let go directly to . The expected absorption times are , and . 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 , the same backward calculation uses
A self-loop at of Probability , with probabilities each to , gives instead of . The finite-state assumption is substantive: an infinite deterministic chain is acyclic but has no terminal Absorbing state and no finite reverse recursion of this kind.

Articles by others on the same topic (0)

There are currently no matching articles.