Correctness of finite Markov closed-class decomposition

Before processing vertex $k$, the Boolean relation records exactly the positive paths whose intermediate vertices lie among $1,\dots ,k-1$: this is true initially because the relation contains precisely zero-step paths and one-edge paths. A path with intermediate vertices among $1,\dots ,k$ either avoids $k$, or can have repeated visits to $k$ removed and be split at its single remaining visit into two paths whose intermediate vertices are among $1,\dots ,k-1$. Conversely, concatenating those two paths gives a path through $k$. Thus the update $R_{ij}\leftarrow R_{ij}\vee (R_{ik}\wedge R_{kj})$ gives exactly the reachability relation after processing $k$. The three loops range over the finite set $S$ and all required comparisons terminate by hypothesis, so the algorithm terminates.

After $k=n$, $R_{ij}$ holds exactly when $j$ is reachable from $i$. Mutual reachability is reflexive, symmetric, and transitive by zero-step paths, reversal of the two reachability assertions, and path concatenation, respectively; hence the algorithm's grouping is exactly the strongly connected component partition. Its finite scan marks a component closed exactly when there is no edge from one of its vertices to a vertex outside it, which is precisely the definition of a closed component.

The directed graph obtained by contracting each strongly connected component is finite and has no directed cycle, since a cycle would make its components mutually reachable and therefore a single component. Starting from any component and following outgoing edges must therefore reach a sink after finitely many steps; sinks are exactly the closed components from step 2.1. Lift this component path to a state path by joining each consecutive pair of intercomponent-edge endpoints with a path inside the current strongly connected component. All edges on the resulting finite state path have positive transition probabilities. A path from a nonclosed component cannot enter a closed component and later leave it, so before its first entry into a closed class it stays in $U$. Therefore every state in $U$ has a positive path through $U$ to a row with positive escape probability into a closed class.

The block $T=K_{U,U}$ is nonnegative and row-substochastic because each row of $K$ sums to one. For every row reached at the end of the path in step 3.1, the positive transition into a closed class is omitted from $T$, so its escape probability $1-{\sum }_{j\in U}{T}_{ij}$ is positive. Thus every state of $U$ satisfies the path hypothesis of [F3], which gives the claimed finite-step escape bound and geometric decay. If $U=\mathrm{\varnothing }$, there is no transient remainder and the same output description holds without a block $T$.