Alphabeta Math
CorollaryStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30
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 X be a Markov chain on an at most countable state space E with transition matrix p(x,y)=K(x,{y}) as in Transition matrices and n-step probabilities. For D⊆E, put T=TDc and v(x):=ExT,x∈E. If v(x)<∞ for every x∈E, then v(x)=0(x∈Dc),Lv(x)=−1(x∈D), where P and the finite drift L are as in Nonnegative kernel action and finite drift. In particular, the pointwise finiteness premise holds when E is finite, p is irreducible, and D⊊E.

Facts & Assumptions

Given: AC; an at most countable state space E with a Markov chain transition matrix p; a set D⊆E; and T=TDc.

[A1]

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)

[F1]

TA=inf⁡{n≥0:Xn∈A}, with the empty infimum equal to +∞. (Hitting, return, and visit times)

[F2]

The transition-matrix entries are p(x,y)=K(x,{y}). (Transition matrices and n-step probabilities)

[F3]

With initial state fixed at x, Px is the law with initial distribution δx and Ex is its expectation. (Initial distribution of a Markov chain)

[F4]

For bounded nonnegative boundary reward f and running cost c, the expected exit-cost function satisfies u=f on Dc and u=c+Pu on D in extended nonnegative arithmetic. (First-step equations for nonnegative exit costs)

[F5]

The nonnegative kernel action is Pϕ(x)=∑y:p(x,y)>0p(x,y)ϕ(y). (Nonnegative kernel action and finite drift)

[F6]

If ϕ is finite-valued and Pϕ(x)<∞, then its drift is the finite real number Lϕ(x)=Pϕ(x)−ϕ(x). (Nonnegative kernel action and finite drift)

[F7]

The geometric-tail clause of the finite irreducible hitting-time lemma assumes a finite state space, an irreducible transition matrix, and a nonempty target A. (Geometric tail for hitting in a finite irreducible chain)

[F8]

Under those assumptions, the lemma proves ExTA<∞ for every state x. (Geometric tail for hitting in a finite irreducible chain)

Proof

technique · identify the accumulated unit cost with the exit time, then apply the finite irreducible hitting-time bound
1.1F1F4given

On each path, ∑m≥01{m<T}=T: if T=t∈N0, exactly the indices m=0,…,t−1 contribute, while if T=∞, every index contributes and both sides are +∞. The sum is empty when T=0. Thus the path cost in First-step equations for nonnegative exit costs with boundary payoff f=0 and running cost c=1 equals T, including nonexit paths.

2.1

The first-step theorem with f=0 and c=1 has expected cost v by step 1.1 and [F3], so it gives v=0 on Dc and v(x)=1+Pv(x) for x∈D. [A1, F3, F4, step 1.1, given] The constant functions are bounded and nonnegative, so the theorem applies; its relation on D is in extended nonnegative arithmetic: v(x)=1+Pv(x)(x∈D)

3.1

If v is finite at every state, then for each x∈D the first-step relation forces Pv(x)<∞ and hence Lv(x)=−1. [F5, F6, step 2.1, given] Indeed, step 2.1 gives v(x)=1+Pv(x)<∞, so Pv(x)<∞. Since v is finite-valued, [F6] defines Lv(x), and the finite-real equation gives Lv(x)=Pv(x)−v(x)=(v(x)−1)−v(x)=−1. Thus the Poisson equation is well-defined at every state of D.

4.1A1F1F2F7F8step 2.1step 3.1given

If E is finite, p is irreducible, and D⊊E, then A=Dc is nonempty. Thus [F7] holds with this target, and [F8] gives ExTA<∞ for every x∈E. Steps 2.1 and 3.1 give the asserted boundary values and equation. The nonempty-target condition matters: for D=E in a nonempty state space, T∅=∞, so the global finite-mean premise fails.

5.1A1F1F2F3F4F5F6F7F8step 1.1step 2.1step 3.1given∎

If E=∅, the initial-distribution definition supplies no probability law of an E-valued chain; there are no states to check. If D=∅, then T=0 from every state, so v=0 and the equation on D is vacuous. For a one-state chain E={x}, this is the finite irreducible proper-domain case; if instead D=E, then T=∞ and the finite-mean premise fails. As a deterministic-row check, on a finite deterministic cycle and a proper D, the nonempty target is reached within at most ∣E∣−1 steps; at an interior state x with successor σ(x), the first-step identity reads v(x)=1+v(σ(x)), hence Lv(x)=−1. The endpoint T=0 is counted by the empty path sum, and for x∈D one has T≥1, 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