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.
One closed class makes the normalized stationary system nonsingular
Statement
Let be a finite real column-stochastic matrix. Suppose its positive-transition graph, defined in Finite Markov closed-class graph decomposition, has exactly one closed class , with transient remainder . Then is one-dimensional, and the system
has exactly one real solution, a probability vector. More strongly, replacing any one row of by gives a nonsingular matrix, so the normalized stationary system can be reduced to a square solve.
Facts & Assumptions
Given: A finite column-stochastic matrix with exactly one closed communicating class .
Finite column-stochastic matrices and probability vectors: is column-stochastic and is the equivalent row-stochastic transition matrix.
Finite Markov closed-class graph decomposition defines the positive-transition graph by when ; its strongly connected components partition the state set, and a component is closed exactly when it has no outgoing edge.
Finite-step escape from a transient substochastic block: a transient row block has for some and .
An irreducible finite class has a unique invariant vector: on a finite irreducible class, every real invariant row vector is a scalar multiple of its positive invariant probability.
Proof
Given: as above, and set .
Proof technique: block the row transition matrix into its closed class and transient states, then add the normalization row to the one-dimensional fixed space.
If , 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 . Closedness makes the block form , where T is row-substochastic; the path property gives the escape hypothesis in [F3].
Let satisfy and put , so . In the block form of step 1.1, . If , iterating gives , and [F3] gives . Hence , so . With no transient states this conclusion is immediate.
The remaining block satisfies . The class is strongly connected, so [F4] gives for some real and the unique invariant probability . Thus every real fixed vector of is a scalar multiple of , and is one-dimensional.
Fix any row index , and let be with row replaced by . If , then is zero outside coordinate . But because P is column-stochastic, so its remaining coordinate is also zero. Hence by step 3.1; the replacement row gives , so . Therefore is nonsingular.
The vector satisfies 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 . Thus it is the unique solution, including the one-state boundary case.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
7 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)