LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Finite-step escape from a transient substochastic block

Statement

Let $T \in [0, \infty)^{n \times n}$ , $n \geq 1$ , have row sums at most one. Define the one-step escape probability $d_{i} = 1 - \sum_{j} T_{i j}$ . Suppose that for each state $i$ there is a path $i = i_{0}, i_{1}, \dots, i_{k}$ with $T_{i_{r} i_{r + 1}} > 0$ for $0 \leq r < k$ and $d_{i_{k}} > 0$ . Then there are $L \leq n$ and $ε > 0$ such that $T^{L} 1 \leq (1 - ε) 1$ . Writing $k = a L + r$ with $0 \leq r < L$ gives $∥ T^{k} ∥_{\infty} \leq (1 - ε)^{a}$ , so $T^{k} \to 0$ . In particular, every complex eigenvalue $λ$ of $T$ satisfies $∣ λ ∣ < 1$ , and its spectral radius $ρ (T) : = \max {∣ λ ∣ : \det (λ I - T) = 0}$ is less than one.

Facts & Assumptions

Given: A finite nonempty state set, a nonnegative row-substochastic matrix $T$ , and from every state a positive-probability path to a row with positive escape probability.

[A1]

$T_{i j} \geq 0$ , $\sum_{j} T_{i j} \leq 1$ , and for each $i$ there is a finite path as stated, ending at $i_{k}$ with $d_{i_{k}} > 0$ .

Proof

Given: $T$ and the hypotheses [A1].

Proof technique: convert each positive path into a uniform finite-step escape probability.

1.1givenA1chooseconstruct

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.

2.1step 1.1algebra

Let $L = n$ and $ε = \min_{i} p_{i}$ . A finite minimum of positive reals is positive, and every row loses at least $p_{i} \geq ε$ mass by step $L$ , so $T^{L} 1 \leq (1 - ε) 1$ .

3.1A1step 2.1algebrainduction

Since $T 1 \leq 1$ , induction gives $T^{r} 1 \leq 1$ for $0 \leq r < L$ . For $k = a L + r$ , nonnegativity and step 2.1 give $T^{k} 1 = (T^{L})^{a} T^{r} 1 \leq (1 - ε)^{a} 1$ . Thus $∥ T^{k} ∥_{\infty} \leq (1 - ε)^{a}$ and $T^{k} \to 0$ .

4.1step 2.1algebra∎

For any $v \in C^{n}$ , step 2.1 gives $∥ T^{L} v ∥_{\infty} \leq (1 - ε) ∥ v ∥_{\infty}$ , by bounding each row sum of absolute values with the corresponding row sum of $T^{L}$ . If $T v = λ v$ with $v \neq 0$ , then $∣ λ ∣^{L} ∥ v ∥_{\infty} = ∥ T^{L} v ∥_{\infty} \leq (1 - ε) ∥ v ∥_{\infty}$ , so $∣ λ ∣ \leq (1 - ε)^{1 / L} < 1$ . Thus $ρ (T) < 1$ .

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, Chapter 11 (standard reference, not scraped)
Yuanyuan Liu, Perturbation Bounds for the Stationary Distributions of Markov Chains (standard reference, not scraped)