Certified stationary distribution and hitting statistic numerics

For each initial state $i$, choose a shortest path in [A1] to a state with positive escape probability. A shortest path has no repeated state, since deleting the segment between two repetitions leaves a shorter path with the same endpoint; hence it uses at most $n-1$ transitions. The probability of following that path and then escaping is $p_i=({\prod }_{r<k}{T}_{i_r{i}_{r+1}})d_{i_k}>0$, where the empty product is $1$. The finitely many choices are made by induction over the finite state set.

Let $L=n$ and $\epsilon ={\min }_i{p}_i$. A finite minimum of positive reals is positive, and every row loses at least $p_i\ge \epsilon$ mass by step $L$, so $T^L\mathbf{1}\le (1-\epsilon )\mathbf{1}$.

Since $T\mathbf{1}\le \mathbf{1}$, induction gives $T^r\mathbf{1}\le \mathbf{1}$ for $0\le r<L$. For $k=aL+r$, nonnegativity and step 2.1 give $T^k\mathbf{1}=(T^L{)}^a{T}^r\mathbf{1}\le (1-\epsilon {)}^a\mathbf{1}$. Thus $\mathrm{\parallel }{T}^k{\mathrm{\parallel }}_{\mathrm{\infty }}\le (1-\epsilon {)}^a$ and $T^k\to 0$.

For any $v\in {\mathbb{C}}^n$, step 2.1 gives $\mathrm{\parallel }{T}^{L}v{\mathrm{\parallel }}_{\mathrm{\infty }}\le (1-\epsilon )\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}$, by bounding each row sum of absolute values with the corresponding row sum of $T^L$. If $Tv=\lambda v$ with $v\mathrm{\ne }0$, then $\mathrm{\mid }\lambda {\mathrm{\mid }}^L\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}=\mathrm{\parallel }{T}^{L}v{\mathrm{\parallel }}_{\mathrm{\infty }}\le (1-\epsilon )\mathrm{\parallel }v{\mathrm{\parallel }}_{\mathrm{\infty }}$, so $\mathrm{\mid }\lambda \mathrm{\mid }\le (1-\epsilon {)}^{1\mathrm{/}L}<1$. Thus $\rho (T)<1$.

For every $z$, finite summation and [F1] give ${\sum }_i(Pz{)}_i={\sum }_j({\sum }_i{P}_{ij})z_j={\sum }_j{z}_j$. If $z$ is a column probability vector, each coordinate of $Pz$ is a sum of nonnegative terms, so $Pz\ge 0$ and its coordinate sum is one.

For each row $i$, $\mathrm{\mid }(Pz{)}_i\mathrm{\mid }=\mathrm{\mid }{\sum }_j{P}_{ij}{z}_j\mathrm{\mid }\le {\sum }_j{P}_{ij}\mathrm{\mid }{z}_j\mathrm{\mid }$ because $P_{ij}\ge 0$. Summing over $i$ and regrouping finite sums gives $\mathrm{\parallel }Pz{\mathrm{\parallel }}_1\le {\sum }_j\mathrm{\mid }{z}_j\mathrm{\mid }{\sum }_i{P}_{ij}=\mathrm{\parallel }z{\mathrm{\parallel }}_1$.

For $0\le r<L$, substochasticity gives $T^r\mathbf{1}\le \mathbf{1}$. Since $T^L\mathbf{1}\le (1-\epsilon )\mathbf{1}$, induction gives $(T^L{)}^q\mathbf{1}\le (1-\epsilon {)}^q\mathbf{1}$ for every $q\ge 0$. Therefore every row sum of $T^{qL+r}$ is at most $(1-\epsilon {)}^q$, and ${\sum }_{k\ge 0}\mathrm{\parallel }{T}^k{\mathrm{\parallel }}_{\mathrm{\infty }}\le L{\sum }_{q\ge 0}(1-\epsilon {)}^q=L\mathrm{/}\epsilon$.

The series $N={\sum }_{k\ge 0}{T}^k$ converges in the maximum-row-sum norm and has nonnegative entries. The finite partial sums satisfy $(I-T){\sum }_{k=0}^m{T}^k=I-T^{m+1}$ and ${\sum }_{k=0}^m{T}^k(I-T)=I-T^{m+1}$. Step 1.1 makes $T^{m+1}\to 0$, so $N$ is a two-sided inverse of $I-T$ and $\mathrm{\parallel }N{\mathrm{\parallel }}_{\mathrm{\infty }}\le L\mathrm{/}\epsilon$.

Put $d=\mathbf{1}-T\mathbf{1}$, the vector of one-step exit weights from rows of $U$. For each $i$, the total weight of first-exit paths of length at most $N$ is ${\sum }_{k=0}^{N-1}(T^{k}d{)}_i={\sum }_{k=0}^{N-1}(T^k\mathbf{1}-T^{k+1}\mathbf{1}{)}_i=1-(T^N\mathbf{1}{)}_i$. By [F2], this tends to one. The finite-exit path set is countable, so these nonnegative weights define a probability distribution. For paths exiting into $G$ after $k$ transitions within $U$, finite matrix multiplication gives weight $(T^{k}b{)}_i$; summing over $k$ yields $h_i={\sum }_{k\ge 0}(T^{k}b{)}_i=(Nb{)}_i$.

For a path with exit length $\tau$, the indicator identity $\tau ={\sum }_{k\ge 0}{\mathbf{1}}_{\{\tau >k\}}$ holds. Summing against the countable path probability from step 2.2 gives ${\mathbb{E}}_i\tau ={\sum }_{k\ge 0}{\mathrm{Pr}}_i(\tau >k)$, since both are the same nonnegative double sum indexed by pairs $0\le k<\tau$. The total weight of paths still in $U$ after $k$ transitions is $(T^k\mathbf{1}{)}_i$, so $t_i={\sum }_{k\ge 0}(T^k\mathbf{1}{)}_i=(N\mathbf{1}{)}_i$. Step 1.1 makes this finite, and multiplying by $I-T$ gives $(I-T)t=\mathbf{1}$.

From $h-\widehat{h}=N(b-(I-T)\widehat{h})$, the operator norm bound in step 2.1 gives the stated hitting-probability residual bound. Applying the same identity to $t-\widehat{t}$ with right side $\mathbf{1}$ gives the mean-exit residual bound.

By [F3], choose an invariant probability row vector $\pi$. At least one coordinate ${\pi }_j$ is positive because its finite nonnegative coordinates sum to one.

Fix any $i\in C$. By irreducibility there is a finite positive-probability path from $j$ to $i$, so for some $r\ge 0$ the matrix power satisfies $(K^r{)}_{ji}>0$. Invariance implies $\pi K^r=\pi$, hence ${\pi }_i={\sum }_k{\pi }_k(K^r{)}_{ki}\ge {\pi }_j(K^r{)}_{ji}>0$. Thus every coordinate of $\pi$ is positive.

For any real invariant row vector $w$, define $f_i=w_i\mathrm{/}{\pi }_i$. The matrix $R$ with entries $R_{ik}={\pi }_k{K}_{ki}\mathrm{/}{\pi }_i$ is well-defined by step 2.1, is nonnegative, and has row sums ${\sum }_k{R}_{ik}={\sum }_k{\pi }_k{K}_{ki}\mathrm{/}{\pi }_i=1$ by invariance of $\pi$. Also $f_i={\sum }_k{R}_{ik}{f}_k$, by invariance of $w$. The directed graph of $R$ reverses that of $K$, so it is irreducible.

Since $C$ is finite, choose an index $i$ at which $f_i$ attains its maximum $M$. The identity $M=f_i={\sum }_k{R}_{ik}{f}_k$ is a convex combination of numbers at most $M$, so every $k$ with $R_{ik}>0$ has $f_k=M$. Repeating along directed paths of the irreducible matrix $R$ gives $f_k=M$ for every $k\in C$. Therefore $w=M\pi$.

Taking $w$ to be any invariant probability shows it equals $\pi$, because its coordinate sum is one; taking arbitrary real invariant $w$ gives the asserted one-dimensional fixed space. For $n=1$ the same argument has a single coordinate and is immediate. The proof uses finite paths, finite maxima, and finite sums only.

Let $z\in H$ with $\mathrm{\parallel }z{\mathrm{\parallel }}_1=1$. Write $z=z^{+}-z^{-}$ coordinatewise, where $z_i^{+}=\max (z_i,0)$ and $z_i^{-}=\max (-z_i,0)$. Since ${\sum }_i{z}_i=0$, the positive and negative masses agree, and their sum is one; hence ${\sum }_i{z}_i^{+}={\sum }_i{z}_i^{-}=1\mathrm{/}2$. Therefore $u=2z^{+}$ and $v=2z^{-}$ are probability vectors and $Pz=(Pu-Pv)\mathrm{/}2$.

We have $Pu={\sum }_j{u}_j{p}_j$ and $Pv={\sum }_k{v}_k{p}_k$. Thus $Pz=\frac{1}{2}{\sum }_{j,k}{u}_j{v}_k(p_j-p_k)$. The coefficients $u_j{v}_k$ are nonnegative and sum to one, so the triangle inequality gives $\mathrm{\parallel }Pz{\mathrm{\parallel }}_1\le \frac{1}{2}{\max }_{j,k}\mathrm{\parallel }{p}_j-p_k{\mathrm{\parallel }}_1$. Taking the supremum over such $z$ proves the upper bound.

If $n\ge 2$ and the maximum is positive, a maximizing pair has $j\mathrm{\ne }k$; if the maximum is zero, any distinct pair maximizes it. Choose such a distinct pair and set $z=(e_j-e_k)\mathrm{/}2$. Then $z\in H$, $\mathrm{\parallel }z{\mathrm{\parallel }}_1=1$, and $Pz=(p_j-p_k)\mathrm{/}2$, so the supremum is at least $\frac{1}{2}{\max }_{j,k}\mathrm{\parallel }{p}_j-p_k{\mathrm{\parallel }}_1$. If $n=1$, both sides are zero by definition. This proves the first equality.

For two nonnegative probability columns $a,b$, $\mathrm{\mid }{a}_i-b_i\mathrm{\mid }=a_i+b_i-2\min (a_i,b_i)$. Summing gives $\frac{1}{2}\mathrm{\parallel }a-b{\mathrm{\parallel }}_1=1-{\sum }_i\min (a_i,b_i)$. Apply this to every pair of columns; taking the maximum of the left side is one minus the minimum overlap on the right.

If $n\ge 2$, [F2] bounds every norm in the defining supremum by one, so $0\le \delta (P)\le 1$; if $n=1$, $\delta (P)=0$ by definition. For nonzero $z\in H$, apply the definition of $\delta (P)$ to $z\mathrm{/}\mathrm{\parallel }z{\mathrm{\parallel }}_1$ and use homogeneity; for $z=0$ the inequality is immediate. Thus $\mathrm{\parallel }Pz{\mathrm{\parallel }}_1\le \delta (P)\mathrm{\parallel }z{\mathrm{\parallel }}_1$ on all of $H$.

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$.

The finite graph's strongly connected components form a partition, and its component graph has no directed cycle: a cycle would make its components mutually reachable and hence one component. Following outgoing edges from any component must therefore terminate at a sink, since the component graph is finite and acyclic. A sink is exactly a closed component by [F2]. From any state outside the closed classes, follow a component path to a sink. Each component edge is realized by a positive transition, and strong connectivity supplies finite positive paths from the current state to the source of each such transition and from its endpoint to the next transition's source. Concatenating these paths gives a positive-transition path into a closed class. Before its first entry, this path stays in U because a closed class has no outgoing edge. If U is nonempty, [F3] applies to T. Writing k=aL+r as in [F3] gives $\mathrm{\parallel }{T}^k{\mathrm{\parallel }}_{\mathrm{\infty }}\to 0$, so the Neumann series $N={\sum }_{k\ge 0}{T}^k$ converges and is $(I-T{)}^{-1}$.

For each closed class $C_j$, the restriction $K_{C_j,C_j}$ is a finite irreducible row-stochastic matrix. By [F5] it has a unique invariant probability ${\pi }_j$. Extending ${\pi }_j$ by zero outside $C_j$ preserves invariance because no transition leaves the class. Thus every convex combination in the statement is invariant.

Let $v$ be any invariant probability row vector and write its coordinates as $(v_C,v_U)$. Since closed classes have no transitions to U, the stationary equation on the transient coordinates is $v_U=v_{U}T$. If U is nonempty, [F3] gives $T^L\mathbf{1}\le (1-\epsilon )\mathbf{1}$ for some $\epsilon >0$, and therefore $\mathrm{\parallel }{v}_U{\mathrm{\parallel }}_1=\mathrm{\parallel }{v}_U{T}^L{\mathrm{\parallel }}_1\le {\sum }_{i\in U}(v_U{)}_i{\sum }_{k\in U}(T^L{)}_{ik}\le (1-\epsilon )\mathrm{\parallel }{v}_U{\mathrm{\parallel }}_1$. Hence $v_U=0$. Since no closed class has transitions to another closed class, the stationary equation now restricts separately to each block $C_j$. Thus each $v_{C_j}$ is invariant on its class, so [F5] makes it ${\alpha }_j{\pi }_j$ with ${\alpha }_j\ge 0$; their masses sum to one. This proves the asserted full set of invariant probabilities.

For each transient state i, the probability weight of first entering class $C_j$ after k transient transitions is $(e_i^{\mathsf{T}}{T}^k{b}_j)$. These disjoint first-entry weights sum, by [F4], to $((I-T{)}^{-1}{b}_j{)}_i$. Initial mass already in $C_j$ remains there, so the total class weight from u is ${\alpha }_j=u(C_j)+u_U(I-T{)}^{-1}{b}_j$. Moreover ${\sum }_j{b}_j=(I-T)\mathbf{1}$, since every transition from a transient state either remains in U or enters exactly one of the closed classes; thus ${\sum }_j{\alpha }_j=u(C_1\cup \cdots \cup C_s)+u_U\mathbf{1}=1$. If U is empty, the same formula reduces directly to $u(C_j)$.

Define ${\bar{u}}_N=N^{-1}{\sum }_{k=0}^{N-1}u{K}^k$. Every coordinate lies in [0,1]. From any subsequence, apply [F7] to its first coordinate, restrict to that subsequence, and repeat for the finitely many remaining coordinates; the final subsequence converges coordinatewise. Also ${\bar{u}}_{N}K-{\bar{u}}_N=(u{K}^N-u)\mathrm{/}N$, whose ℓ1 norm is at most $2\mathrm{/}N$. Hence every subsequential limit is an invariant probability.

The mass $a_n=u{K}^n(C_j)$ is nondecreasing because $C_j$ is closed; its increment at each step is the first-entry weight from step 1.4. The partial sums of these weights tend to $u_U(I-T{)}^{-1}{b}_j$ by [F3]–[F4], and the unabsorbed transient mass tends to zero, so $a_n\to {\alpha }_j$. For any η>0, choose N₀ so |uKⁿ(Cⱼ)−αⱼ|<η for n≥N₀; the average error is at most the finite sum of the first N₀ errors divided by N, plus η, and hence tends to at most η. Since η is arbitrary, the Cesàro class mass tends to αⱼ. Thus every subsequential limit $\bar{u}$ has $\bar{u}(C_j)={\alpha }_j$ for each j. By step 1.3 this invariant probability must be ${\sum }_j{\alpha }_j{\pi }_j$.

Every convergent subsequence of $({\bar{u}}_N)$ has the same limit from step 2.1. If the full sequence did not converge to that limit, there would be ε>0 and a subsequence staying at least ε away. Its finitely many bounded coordinates admit a convergent further subsequence by repeated finite applications of [F7]; step 2.1 forces that further limit to be the stated mixture, a contradiction. Thus the full Cesàro sequence converges to the initial-law-dependent mixture stated.

The transpose $K=P^{\mathsf{T}}$ is a finite row transition matrix by [F1]. By [F5] it has an invariant probability row vector, and [F4] transposes this to a stationary column probability $\pi$ for P.

If ${\pi }_1,{\pi }_2$ are stationary column probabilities, then $z={\pi }_1-{\pi }_2$ lies in H and $P^{m}z=z$. By [F3], $\mathrm{\parallel }z{\mathrm{\parallel }}_1=\mathrm{\parallel }{P}^{m}z{\mathrm{\parallel }}_1\le q\mathrm{\parallel }z{\mathrm{\parallel }}_1$; since $q<1$, this forces $z=0$. Thus $\pi$ is unique.

Let $e=x-\pi$. Both vectors have coordinate sum one, so $e\in H$. Since $P^m\pi =\pi$, reverse triangle inequality and [F3] give $\mathrm{\parallel }{P}^{m}x-x{\mathrm{\parallel }}_1=\mathrm{\parallel }{P}^{m}e-e{\mathrm{\parallel }}_1\ge \mathrm{\parallel }e{\mathrm{\parallel }}_1-\mathrm{\parallel }{P}^{m}e{\mathrm{\parallel }}_1\ge (1-q)\mathrm{\parallel }e{\mathrm{\parallel }}_1$. Dividing by $1-q>0$ proves the first bound.

The telescoping identity $P^{m}x-x={\sum }_{k=0}^{m-1}{P}^k(Px-x)$ follows by cancellation of adjacent terms. Applying [F2] repeatedly gives $\mathrm{\parallel }{P}^k(Px-x){\mathrm{\parallel }}_1\le \mathrm{\parallel }Px-x{\mathrm{\parallel }}_1$ for each k; the triangle inequality therefore yields $\mathrm{\parallel }{P}^{m}x-x{\mathrm{\parallel }}_1\le m\mathrm{\parallel }Px-x{\mathrm{\parallel }}_1$.

Combine steps 2.2 and 3.1. The proof does not require irreducibility or aperiodicity once the stated m-step contraction is certified; if $q\ge 1$, the division step is unavailable and no bound is asserted.

If $U=\mathrm{\varnothing }$, $K=K_C$ is irreducible and row-stochastic. Otherwise, contract the strongly connected components of the finite positive-transition graph to form its component graph. This graph is acyclic, since a directed cycle would make its components mutually reachable and hence a single component. Every component therefore reaches a sink by following outgoing edges; the process terminates because the component graph is finite and acyclic. By [F2], sinks are exactly closed classes; C is the unique sink class. From each state in U, follow a component path to C. Each component edge is realized by a positive transition, and strong connectivity supplies finite positive paths from the current state to the source of each such transition and from its endpoint to the next transition's source. Concatenating these paths gives a positive path to C; before its first entry into C it stays in U. Order the states as $C,U$. Closedness makes the block form $K=\left(\begin{array}{cc}{K}_C& 0\\ R& T\end{array}\right)$, where T is row-substochastic; the path property gives the escape hypothesis in [F3].

Let $x$ satisfy $Px=x$ and put $w=x^{\mathsf{T}}$, so $wK=w$. In the block form of step 1.1, $w_U=w_{U}T$. If $U\mathrm{\ne }\mathrm{\varnothing }$, iterating $w_U=w_{U}T$ gives $w_U=w_U{T}^L$, and [F3] gives $T^L\mathbf{1}\le (1-\epsilon )\mathbf{1}$. Hence $\mathrm{\parallel }{w}_U{\mathrm{\parallel }}_1=\mathrm{\parallel }{w}_U{T}^L{\mathrm{\parallel }}_1\le {\sum }_{i\in U}\mathrm{\mid }(w_U{)}_i\mathrm{\mid }{\sum }_{j\in U}(T^L{)}_{ij}\le (1-\epsilon )\mathrm{\parallel }{w}_U{\mathrm{\parallel }}_1$, so $w_U=0$. With no transient states this conclusion is immediate.

The remaining block satisfies $w_C{K}_C=w_C$. The class $C$ is strongly connected, so [F4] gives $w_C=s{\pi }_C$ for some real $s$ and the unique invariant probability ${\pi }_C$. Thus every real fixed vector of $P$ is a scalar multiple of ${\pi }_C^{\mathsf{T}}$, and $\ker (I-P)$ is one-dimensional.

Fix any row index $r$, and let $A_r$ be $I-P$ with row $r$ replaced by ${\mathbf{1}}^{\mathsf{T}}$. If $A_{r}z=0$, then $(I-P)z$ is zero outside coordinate $r$. But ${\mathbf{1}}^{\mathsf{T}}(I-P)=0$ because P is column-stochastic, so its remaining coordinate is also zero. Hence $z=c{\pi }_C^{\mathsf{T}}$ by step 3.1; the replacement row gives $0={\mathbf{1}}^{\mathsf{T}}z=c$, so $z=0$. Therefore $A_r$ is nonsingular.

The vector ${\pi }_C^{\mathsf{T}}$ satisfies $(I-P){\pi }_C^{\mathsf{T}}=0$ and has coordinate sum one. Any real solution of the normalized system is fixed by P and has the same normalization, so step 3.1 makes it ${\pi }_C^{\mathsf{T}}$. Thus it is the unique solution, including the one-state boundary case.