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.
Kac return-time formula for a state
Statement
Assume AC (The Axiom of Choice). Let be an irreducible transition matrix on a countable state space with invariant probability (Invariant and stationary distribution for a Markov kernel), and for let be the return-cycle occupation measure (Return-cycle occupation measure and minimality). Then for every :
- ;
- , finite; and
- for every .
Facts & Assumptions
Given: AC, an irreducible countable transition matrix , an invariant probability , and a state .
Every family of nonempty sets has a choice function; AC is assumed and is used through the chain-law and occupation-measure supplier [F2]. (The Axiom of Choice)
Assume AC. For an irreducible countable chain, existence of an invariant probability makes every state positive recurrent; an invariant probability satisfies and for every ; and is an invariant probability when is positive recurrent. (Positive recurrence and stationary probability for irreducible countable chains)
Assume AC. For a countable -chain started at : , , for , is pointwise minimal among nonnegative solutions of , , and when is recurrent. (Return-cycle occupation measure and minimality)
Irreducibility means that for all there is with . (Accessibility, communication, and irreducibility)
On a countable state space a probability measure is invariant exactly when for every . (Invariant and stationary distribution for a Markov kernel)
for all . (Matrix Chapman–Kolmogorov equations)
For every double sequence in the order of summation may be interchanged, the two iterated sums being equal even when the common value is . (Tonelli's theorem for double series of nonnegative extended real numbers)
Proof
Given: AC, an irreducible countable transition matrix , an invariant probability , a state , and the return-cycle occupation measure of [F2].
Proof technique: form the nonnegative defect of against the normalized stationary measure, observe that it is invariant, and evaluate the resulting conservation identity at , where irreducibility forces every defect value to vanish.
By [F1] the invariant probability satisfies and the chain is positive recurrent with ; hence is finite-valued with , and since positive recurrence makes recurrent, [F2] gives as well as .
Define for ; this is nonnegative and finite by step 1.1, , and for the invariance identity [F4] gives .
By the minimality clause of [F2] applied to , one has for every ; hence is a well-defined nonnegative extended function with and finite total mass .
The defect is invariant: for every , , using the invariance identity [F4] for , the identity from step 1.1, and the fact that both subtracted series have finite values; iterating with the Chapman–Kolmogorov identity [F5] and the interchange of nonnegative sums [F6] gives for every .
Evaluate the conservation identity of step 4.1 at and arbitrary: , a sum of nonnegative terms, so for every and every ; for fixed , [F3] provides with , hence . Therefore , that is, and so for every .
Summing the identity of step 5.1 and using from [F2] gives , that is, , finite and positive.
The three assertions of the statement hold: by step 1.1, by step 6.1, and by step 5.1.
Boundary and axiom cases: if is a singleton the formulas give , and , matching step 6.1; if is not unique the argument applies to each invariant probability separately, since only invariance of and irreducibility are used, and no uniqueness is asserted; a transient or null-recurrent chain has no invariant probability by [F1], so the hypothesis cannot be vacuous in those cases; is nonnegative by the minimality clause, so no infinite minus infinite subtraction occurs in step 4.1, and the subtracted series there are separately finite; the identities are equalities, not implications, so there is no iff case separation; and AC [A1] enters exactly through [F2] and [F1], both of which assume it.
Depends on
- The Axiom of Choice
- Positive recurrence and stationary probability for irreducible countable chains
- Return-cycle occupation measure and minimality
- Accessibility, communication, and irreducibility
- Invariant and stationary distribution for a Markov kernel
- Matrix Chapman–Kolmogorov equations
- Tonelli's theorem for double series of nonnegative extended real numbers
Used by
- Stationary irreducible Markov shift is ergodic Corollary
- Uniqueness of the stationary law for an irreducible positive-recurrent chain Corollary
- Convergence to stationarity for irreducible aperiodic positive-recurrent chains Theorem
- Ergodic theorem for an irreducible positive-recurrent Markov chain Theorem
- Kac return-time formula for a positive-mass set Theorem
Dependency tree · two levels
22 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
- Durrett, Probability: Theory and Examples, fifth edition, §5.5–5.6, Kac's formula (standard reference, not scraped)
- Levin–Peres–Wilmer, Markov Chains and Mixing Times, second edition, §21.3 and Appendix C.1 (standard reference, not scraped)
- Aldous–Chewi, Probability Theory, Lectures 13–15 (standard reference, not scraped)