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 be a finite row-stochastic transition matrix on a nonempty set . Assume irreducibility: for every there is a finite directed path from to whose transition probabilities are positive. Then there is a unique invariant probability row vector , all its coordinates are positive, and every real row vector satisfying is a scalar multiple of . Equivalently, for the column matrix , the real fixed space of is one-dimensional.
Facts & Assumptions
Given: A finite irreducible row-stochastic matrix on nonempty .
Transition matrices and n-step probabilities: the entries of are nonnegative and each row sums to one.
Invariant and stationary distribution for a Markov kernel: a probability row vector is invariant precisely when .
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.
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: and its irreducibility hypothesis.
Proof technique: obtain a positive invariant vector, then apply a maximum principle to the reversed transition matrix.
By [F3], choose an invariant probability row vector . At least one coordinate is positive because its finite nonnegative coordinates sum to one.
Fix any . By irreducibility there is a finite positive-probability path from to , so for some the matrix power satisfies . Invariance implies , hence . Thus every coordinate of is positive.
For any real invariant row vector , define . The matrix with entries is well-defined by step 2.1, is nonnegative, and has row sums by invariance of . Also , by invariance of . The directed graph of reverses that of , so it is irreducible.
Since is finite, choose an index at which attains its maximum . The identity is a convex combination of numbers at most , so every with has . Repeating along directed paths of the irreducible matrix gives for every . Therefore .
Taking to be any invariant probability shows it equals , because its coordinate sum is one; taking arbitrary real invariant gives the asserted one-dimensional fixed space. For 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
- Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, Chapter 11 (standard reference, not scraped)