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.
Expected exit time solves the Poisson equation
Statement
Assume AC (The Axiom of Choice). Let be a Markov chain on an at most countable state space with transition matrix as in Transition matrices and n-step probabilities. For , put and If for every , then where and the finite drift are as in Nonnegative kernel action and finite drift. In particular, the pointwise finiteness premise holds when is finite, is irreducible, and .
Facts & Assumptions
Given: AC; an at most countable state space with a Markov chain transition matrix ; a set ; and .
AC is the axiom that every family of nonempty sets has a choice function. It is explicitly assumed by the first-step theorem and the finite irreducible hitting-time lemma used here. (The Axiom of Choice)
, with the empty infimum equal to . (Hitting, return, and visit times)
The transition-matrix entries are . (Transition matrices and n-step probabilities)
With initial state fixed at , is the law with initial distribution and is its expectation. (Initial distribution of a Markov chain)
For bounded nonnegative boundary reward and running cost , the expected exit-cost function satisfies on and on in extended nonnegative arithmetic. (First-step equations for nonnegative exit costs)
The nonnegative kernel action is . (Nonnegative kernel action and finite drift)
If is finite-valued and , then its drift is the finite real number . (Nonnegative kernel action and finite drift)
The geometric-tail clause of the finite irreducible hitting-time lemma assumes a finite state space, an irreducible transition matrix, and a nonempty target . (Geometric tail for hitting in a finite irreducible chain)
Under those assumptions, the lemma proves for every state . (Geometric tail for hitting in a finite irreducible chain)
Proof
On each path, : if , exactly the indices contribute, while if , every index contributes and both sides are . The sum is empty when . Thus the path cost in First-step equations for nonnegative exit costs with boundary payoff and running cost equals , including nonexit paths.
The first-step theorem with and has expected cost by step 1.1 and [F3], so it gives on and for . [A1, F3, F4, step 1.1, given] The constant functions are bounded and nonnegative, so the theorem applies; its relation on is in extended nonnegative arithmetic:
If is finite at every state, then for each the first-step relation forces and hence . [F5, F6, step 2.1, given] Indeed, step 2.1 gives , so . Since is finite-valued, [F6] defines , and the finite-real equation gives Thus the Poisson equation is well-defined at every state of .
If is finite, is irreducible, and , then is nonempty. Thus [F7] holds with this target, and [F8] gives for every . Steps 2.1 and 3.1 give the asserted boundary values and equation. The nonempty-target condition matters: for in a nonempty state space, , so the global finite-mean premise fails.
If , the initial-distribution definition supplies no probability law of an -valued chain; there are no states to check. If , then from every state, so and the equation on is vacuous. For a one-state chain , this is the finite irreducible proper-domain case; if instead , then and the finite-mean premise fails. As a deterministic-row check, on a finite deterministic cycle and a proper , the nonempty target is reached within at most steps; at an interior state with successor , the first-step identity reads , hence . The endpoint is counted by the empty path sum, and for one has , so the unit cost counts precisely the steps strictly before exit. AC is used through the cited first-step and finite hitting-time results; no further choice is made here. This corollary states implications, not an iff.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
32 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
- Roch, Lecture Notes on Measure-Theoretic Probability Theory, Note 24 (standard reference, not scraped)