Loops — Markov chains
Solving nᵀ(I − P) = e₀ᵀ instead of cutting the loop.
This is the core part where the tool differs from most spreadsheets: loops are solved exactly with linear algebra, not by trying a few turns and stopping.
The idea
Treat the process as an absorbing Markov chain: each step is a state, each flow is a transition probability, and the end points are absorbing states. The question “how many times on average does step v run in one pass of a case” is exactly the classic question about the expected number of visits.
The formula
Written compactly in matrix form:
Read out in words: “the number of visits to step v equals 1 if v is the start point, plus the total number of times the other steps transition into v”. This is a system of linear equations — solve it once and you have them all, and the solution already includes the infinite number of loop turns.
The case of a single rework loop
For a simple loop, system (5) reduces to the geometric series formula:
A hand-calculated example
The step Reconcile (35 minutes) → gateway Match? → 22% goes to Handle the mismatch (90 minutes) and back to reconciliation; 78% carries on to Payment.
Let nreconcile be the number of runs of the reconciliation step:
The mismatch-handling step runs less often, exactly as often as cases are sent back:
The time this cluster contributes:
For comparison: ignore the rework and you count only 35 minutes. Naively “add 22%” and you get 42,7 minutes. The correct number is 70,25 minutes — double the rough estimate.
How the tool solves this
def expected_visits(node_ids, transitions, start):
# Dựng (I - P^T), vế phải là e_0
matrix = [[1.0 if r == c else 0.0 for c in range(size)] for r in range(size)]
for source, targets in transitions.items():
for target, probability in targets.items():
matrix[index[target]][index[source]] -= probability
vector = [0.0] * size
vector[index[start]] = 1.0
return solve(matrix, vector) # khử Gauss có chọn trụcIf there is a loop in which every step has no escape branch, the matrix is singular — mathematically, the expected time is infinite. The tool raises a clear error instead of returning a wrong finite number. Note: a loop-back flow with probability 100% is perfectly normal, as long as somewhere in the loop there is a branch that escapes.