Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 5 results · all verified · 5 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 5 also cleared it.

Certified stationary distribution and hitting statistic numerics — Examples

1 · Prerequisites

2 · Summary

These exact examples show when residuals certify stationary laws, how reducible chains retain initial-law-dependent class weights, how detailed balance gives a birth–death invariant law, and how finite-step escape certifies absorption statistics. The periodic two-state chain separates stationarity from convergence of ordinary power iteration.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Finite credit reserve: certified absorption statistics

Example

A credit reserve has levels $0, 1, 2, 3, 4$ . From an interior level it moves one level up or down with equal probability; levels 0 and 4 are absorbing failure and success states. For transient levels $U = {1, 2, 3}$ , the transient block is

$T = (\begin{array}{ccc} 0 & 1 / 2 & 0 \\ 1 / 2 & 0 & 1 / 2 \\ 0 & 1 / 2 & 0 \end{array}), b_{4} = (0, 0, 1 / 2)^{T} .$

The chance of eventual success from level i is $i / 4$ and the mean number of steps to absorption is $i (4 - i)$ . Starting from level 2, the two absorbing class weights are both $1 / 2$ . A deliberately perturbed numerical solve illustrates the residual certificate.

Verification

Given: The five-state transition rule above, transient set U, and success state 4.

[F1] Transient hitting, mean exit, and residual bounds: if the finite transient block has the escape path property, then $h = (I - T)^{- 1} b_{4}$ , $t = (I - T)^{- 1} 1$ , and both statistics have residual error bounded by $∥ (I - T)^{- 1} ∥_{\infty}$ times the equation residual.

[F2] Closed-class stationary laws and initial-law-dependent Cesàro weights: eventual class weights depend on the initial law and are computed by the transient-block exit system.

Proof technique: direct exact calculation.

1.1givenF1construct

From level 1, the path down exits within one step with probability $1 / 2$ ; from level 2, the two paths down-down and up-up exit within two steps with total probability $1 / 2$ ; from level 3, the path up exits within one step with probability $1 / 2$ . Thus every transient state escapes within $L = 2$ with probability at least $ε = 1 / 2$ , and [F1] gives $∥ (I - T)^{- 1} ∥_{\infty} \leq 4$ .

1.2F1givenalgebra

Let $\hat{h} = (13 / 50, 1 / 2, 37 / 50)^{T}$ . Direct multiplication gives $b_{4} - (I - T) \hat{h} = (- 1 / 100, 0, 1 / 100)^{T}$ , with infinity norm $1 / 100$ .

2.1F1step 1.1algebra

The success equations are $h_{1} = h_{2} / 2$ , $h_{2} = (h_{1} + h_{3}) / 2$ , and $h_{3} = 1 / 2 + h_{2} / 2$ . Substitution gives $h = (1 / 4, 1 / 2, 3 / 4)^{T}$ , which satisfies $(I - T) h = b_{4}$ by direct multiplication. The mean-exit equations are $t_{1} = 1 + t_{2} / 2$ , $t_{2} = 1 + (t_{1} + t_{3}) / 2$ , and $t_{3} = 1 + t_{2} / 2$ ; direct substitution verifies $t = (3, 4, 3)^{T}$ .

3.1F1F2step 1.1step 2.1step 1.2algebra∎

By [F1] and step 1.1, $∥ h - \hat{h} ∥_{\infty} \leq 4 / 100 = 1 / 25$ . The exact error is $1 / 100$ , so the finite-step escape certificate is valid and conservative. From level 2, step 2.1 gives success weight $1 / 2$ ; because the two closed classes exhaust probability one, the failure weight is also $1 / 2$ , as in [F2].

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A small residual can hide a large stationary error

Example

For $0 < ε ≪ 1$ , consider the two-state column-stochastic matrix

$P_{ε} = (\begin{array}{cc} 1 - ε & ε \\ ε & 1 - ε \end{array}) .$

It has stationary law $π = (1 / 2, 1 / 2)^{T}$ . Take $ε = 1 / 100$ and candidate $x = (3 / 4, 1 / 4)^{T}$ . The residual is small, while the stationary error is $1 / 2$ . The exact Dobrushin certificate is sharp and exposes the large inverse factor.

Verification

Given: The displayed matrix with $ε = 1 / 100$ and the candidate vector $x = (3 / 4, 1 / 4)^{T}$ .

[F1] Column-overlap formula for the zero-sum ℓ1 coefficient: $δ (P) = 1 - \min_{j, k} \sum_{i} \min (P_{i j}, P_{i k})$ for a column-stochastic matrix.

[F2] m-step Dobrushin certificate for a stationary probability: if $q = δ (P^{m}) < 1$ , then $∥ x - π ∥_{1} \leq m ∥ P x - x ∥_{1} / (1 - q)$ .

[F3] Correct and certify a finite-chain stationary candidate: when the raw input is the nonnegative normalized vector $y = x$ , correction distance is zero; for exact rational P and y, the algorithm returns the residual, overlap coefficient, and bound when that coefficient is below one.

Proof technique: direct exact calculation.

1.1givenF3algebra

Direct multiplication gives $P π = π$ for $π = (1 / 2, 1 / 2)^{T}$ . Use the raw algorithm input $y = x = (3 / 4, 1 / 4)^{T}$ ; it is nonnegative and normalized, so its correction distance is $c = 0$ .

2.1givenstep 1.1algebra

The first coordinate of $P x$ is $(99 / 100) (3 / 4) + (1 / 100) (1 / 4) = 149 / 200$ , and the second is $51 / 200$ . Hence $r = P x - x = (- 1 / 200, 1 / 200)^{T}$ and $∥ r ∥_{1} = 1 / 100$ , while $∥ x - π ∥_{1} = 1 / 2$ .

3.1F1F2step 2.1algebra∎

The columns are $(99 / 100, 1 / 100)^{T}$ and $(1 / 100, 99 / 100)^{T}$ ; their overlap is $1 / 50$ . Thus [F1] gives $q = δ (P) = 49 / 50 < 1$ . With $m = 1$ , [F2] gives the exact bound $(1 / 100) / (1 / 50) = 1 / 2$ , equal to the actual error.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Periodic iteration can fail while the stationary solve is well-defined

Example

For the two-state periodic chain

$P = (\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}),$

the unique stationary law is $(1 / 2, 1 / 2)^{T}$ , but power iteration from $e_{1}$ alternates forever. For $m = 1$ , the global overlap coefficient is one and the residual certificate is unavailable. The lazy matrix $L = (I + P) / 2$ has identical columns, coefficient zero, and certifies the stationary law after one step.

Verification

Given: The periodic matrix P, initial vector $e_{1}$ , and lazy matrix $L = (I + P) / 2$ .

[F1] An irreducible finite class has a unique invariant vector: an irreducible finite transition matrix has a unique invariant probability, even when its powers are periodic.

[F2] Column-overlap formula for the zero-sum ℓ1 coefficient: the coefficient is one minus the minimum pairwise column overlap.

[F3] Correct and certify a finite-chain stationary candidate: for exact rational P and raw y with $\sum_{i} y_{i}^{+} > 0$ , a computed coefficient at least one returns certificate-unavailable; a coefficient below one returns a residual bound.

[F4] m-step Dobrushin certificate for a stationary probability: a coefficient below one gives the stationary residual error bound.

Proof technique: direct exact calculation.

1.1givenF1algebra

The matrix P is a row and column transition matrix, is irreducible, and $π = (1 / 2, 1 / 2)^{T}$ satisfies $P π = π$ . Hence [F1] identifies it as the unique stationary law. But $P e_{1} = e_{2}$ and $P e_{2} = e_{1}$ , so $P^{n} e_{1}$ alternates between two distinct vectors and does not converge.

2.1F2F3step 1.1algebra

The columns of P are $e_{2}, e_{1}$ and have overlap zero, so [F2] gives $δ (P) = 1$ ; every power is either P or I and also has coefficient one. With exact raw input $y = e_{1}$ , the algorithm reaches its coefficient branch and [F3] returns certificate-unavailable for the ordinary chain.

3.1F2F3F4step 1.1algebra∎

The lazy matrix has both columns equal to $π$ , hence [F2] gives $δ (L) = 0$ . With raw input $y = e_{1}$ , the corrected algorithm has correction zero, residual $L e_{1} - e_{1} = (- 1 / 2, 1 / 2)^{T}$ of norm one, and bound $1 / (1 - 0) = 1$ . This equals $∥ e_{1} - π ∥_{1}$ , so [F4] certifies the stationary law.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Two absorbing classes retain initial-law-dependent weights

Example

Let $P = I_{2}$ . Its two states are separate absorbing closed classes. Every probability vector is stationary, and the Cesàro limit is the initial law. The global column-overlap coefficient equals one, so a global residual accuracy certificate is unavailable even though the stationary linear system is exactly solvable once an initial-law or class-weight convention is supplied.

Verification

Given: $P = I_{2}$ , an initial row law $u = (3 / 5, 2 / 5)$ , and raw column input $y = u^{T} = (3 / 5, 2 / 5)^{T}$ to the certificate algorithm.

[F1] Finite Markov closed-class graph decomposition: the algorithm returns the strongly connected components and identifies a component as closed exactly when it has no outgoing transition.

[F2] Closed-class stationary laws and initial-law-dependent Cesàro weights: all stationary laws are mixtures of the unique laws on closed classes, and initial-law weights are their first-entry probabilities.

[F3] Column-overlap formula for the zero-sum ℓ1 coefficient: $δ (P) = 1 - \min_{j, k} \sum_{i} \min (P_{i j}, P_{i k})$ .

[F4] Correct and certify a finite-chain stationary candidate: for exact rational P and a raw input y with $\sum_{i} y_{i}^{+} > 0$ , a computed coefficient at least one produces certificate-unavailable.

[F5] Correctness of finite Markov closed-class decomposition: the graph procedure returns exactly the strongly connected components and identifies as closed exactly those with no outgoing positive transition.

Proof technique: direct exact calculation.

1.1givenF1F5construct

The graph has no edge between its distinct vertices, so [F5] shows the decomposition in [F1] returns $C_{1} = {1}$ and $C_{2} = {2}$ , with no transient states. Each class law is its point mass.

2.1F2step 1.1algebra

Since $u P^{k} = u$ for every $k$ , every Cesàro average is u. By [F2], the weights are $α_{1} = u (C_{1}) = 3 / 5$ and $α_{2} = u (C_{2}) = 2 / 5$ . The full stationary family is ${(a, 1 - a)^{T} : 0 \leq a \leq 1}$ , so no unique stationary vector is selected.

3.1F3F4step 2.1algebra∎

Since $P = I_{2}$ , $P^{m} = I_{2}$ for every $m \geq 1$ . Its columns are $e_{1}$ and $e_{2}$ , whose overlap is zero, so [F3] gives $δ (P^{m}) = 1$ . The given raw input is normalized, hence [F4] returns certificate-unavailable for every $m \geq 1$ . This is consistent with the continuum of stationary laws: the strict-contraction hypothesis fails.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A three-state birth–death generator and detailed balance

Example

On states ${0, 1, 2}$ , let the birth rates be $2$ from 0 to 1 and $2$ from 1 to 2, and the death rates be $1$ from 1 to 0 and $1$ from 2 to 1. The column generator, uniformization matrix at $ν = 3$ , and stationary probability are

$Q = (\begin{array}{ccc} - 2 & 1 & 0 \\ 2 & - 3 & 1 \\ 0 & 2 & - 1 \end{array}), P = I + Q / 3 = (\begin{array}{ccc} 1 / 3 & 1 / 3 & 0 \\ 2 / 3 & 0 & 1 / 3 \\ 0 & 2 / 3 & 2 / 3 \end{array}), π = (1, 2, 4)^{T} / 7.$

Detailed balance verifies the law. Moreover, $δ (P^{2}) = 2 / 9$ , so the stationary residual certificate is available, and at $x = π$ its bound is zero.

Verification

Given: The displayed column generator Q, rate $ν = 3$ , matrix P, probability vector $π$ , and raw candidate $y = π$ .

[F1] Finite column generator: off-diagonal generator entries are nonnegative, columns sum to zero, and the source column's exit rate is $r_{j} = - Q_{j j}$ .

[F2] Correct and certify a finite-chain stationary candidate: a nonnegative normalized input is unchanged by correction, so the output candidate is $x = y$ with correction distance $c = 0$ .

[F3] Uniformized finite-generator stationary residual certificate: for an admissible uniformization with $q = δ (P^{m}) < 1$ , the corrected raw candidate y satisfies $∥ y - π ∥_{1} \leq c + m ∥ Q x ∥_{1} / (ν (1 - q))$ .

[F4] Detailed balance implies invariance: for a row transition matrix K and finite state measure $μ$ satisfying $μ_{i} K_{i j} = μ_{j} K_{j i}$ , one has $μ K = μ$ ; if its mass is one, it is an invariant probability.

Proof technique: direct exact calculation; set $K = P^{T}$ .

1.1givenF1algebra

The off-diagonal entries of Q are nonnegative and its columns sum to zero; the exit rates are $2, 3, 1$ . Thus $ν = 3$ is admissible in [F1]. Directly, $P = I + Q / 3$ is the displayed nonnegative matrix and its columns each sum to one.

2.1F1F4step 1.1algebra

The coordinates of $π$ are nonnegative and sum to one. In the row kernel K, $π_{0} K_{01} = (1 / 7) (2 / 3) = 2 / 21 = π_{1} K_{10}$ and $π_{1} K_{12} = (2 / 7) (2 / 3) = 4 / 21 = π_{2} K_{21}$ ; the reverse equalities hold, all non-neighbor flows are zero in both directions, and diagonal balance is automatic. Therefore [F4] gives the row law $π^{T} K = π^{T}$ , equivalently $P π = π$ . Direct multiplication also gives $Q π = 0$ .

3.1F2F3step 2.1algebra∎

Multiplication gives $P^{2} = (\begin{array}{ccc} 1 / 3 & 1 / 9 & 1 / 9 \\ 2 / 9 & 4 / 9 & 2 / 9 \\ 4 / 9 & 4 / 9 & 2 / 3 \end{array})$ . Each pair of distinct columns has overlap $7 / 9$ , and each self-pair has overlap $1$ ; hence the minimum overlap is $7 / 9$ and the coefficient is $q = 1 - 7 / 9 = 2 / 9 < 1$ for $m = 2$ . With raw candidate $y = π$ , [F2] gives $x = π$ and $c = 0$ ; also $Q x = 0$ . Applying [F3] certifies the exact stationary law with error bound zero.

Certified stationary distribution and hitting statistic numerics — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Finite credit reserve: certified absorption statistics

Example

Verification

A small residual can hide a large stationary error

Example

Verification

Periodic iteration can fail while the stationary solve is well-defined

Example

Verification

Two absorbing classes retain initial-law-dependent weights

Example

Verification

A three-state birth–death generator and detailed balance

Example

Verification

Sources