Alphabeta Math
TheoremStatement: 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.

An irreducible finite class has a unique invariant vector

Statement

Let K be a finite row-stochastic transition matrix on a nonempty set C. Assume irreducibility: for every i,j∈C there is a finite directed path from i to j whose transition probabilities are positive. Then there is a unique invariant probability row vector π, all its coordinates are positive, and every real row vector w satisfying wK=w is a scalar multiple of π. Equivalently, for the column matrix P=KT, the real fixed space of P is one-dimensional.

Facts & Assumptions

Given: A finite irreducible row-stochastic matrix K on nonempty C.

[F1]

Transition matrices and n-step probabilities: the entries of K are nonnegative and each row sums to one.

[F2]

Invariant and stationary distribution for a Markov kernel: a probability row vector is invariant precisely when πK=π.

[F3]

Every transition matrix on a nonempty finite state space has a stationary distribution: every transition matrix on a nonempty finite state space has an invariant probability; this gives existence only, with no irreducibility or uniqueness conclusion.

[F4]

Finite column-stochastic matrices and probability vectors: transposing a row law and its row transition matrix gives the equivalent column law and column-stochastic matrix convention.

Proof

Given: K and its irreducibility hypothesis.

Proof technique: obtain a positive invariant vector, then apply a maximum principle to the reversed transition matrix.

1.1givenF2F3choose

By [F3], choose an invariant probability row vector π. At least one coordinate πj is positive because its finite nonnegative coordinates sum to one.

2.1F1F2step 1.1algebra

Fix any i∈C. By irreducibility there is a finite positive-probability path from j to i, so for some r≥0 the matrix power satisfies (Kr)ji>0. Invariance implies πKr=π, hence πi=∑kπk(Kr)ki≥πj(Kr)ji>0. Thus every coordinate of π is positive.

3.1F1F2step 2.1algebra

For any real invariant row vector w, define fi=wi/πi. The matrix R with entries Rik=πkKki/πi is well-defined by step 2.1, is nonnegative, and has row sums ∑kRik=∑kπkKki/πi=1 by invariance of π. Also fi=∑kRikfk, by invariance of w. The directed graph of R reverses that of K, so it is irreducible.

4.1step 3.1choosealgebra

Since C is finite, choose an index i at which fi attains its maximum M. The identity M=fi=∑kRikfk is a convex combination of numbers at most M, so every k with Rik>0 has fk=M. Repeating along directed paths of the irreducible matrix R gives fk=M for every k∈C. Therefore w=Mπ.

5.1F2F4step 4.1given∎

Taking w to be any invariant probability shows it equals π, 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.

Depends on

Used by

Dependency tree · two levels

10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources