Pipeline-generated

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.

✓ 19 results · all verified · 18 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Recurrence Transience and Hitting Times for Markov Chains

1 · Prerequisites

2 · Summary

This page develops countable-state, discrete-time recurrence and hitting-time theory from the transition-matrix and stopping-time conventions. It proves the matrix Chapman–Kolmogorov identities, communication-class results, renewal and Green-kernel criteria, class invariance and the irreducible dichotomy. It then treats harmonic hitting probabilities, finite-state Dirichlet problems, periods, and the recurrence classification of simple symmetric walks on $Z^{d}$ .

The final sections develop nonnegative exit costs, superharmonic bounds, the Poisson equation for expected exit times, and Lyapunov estimates. AC is stated where canonical chain laws and probability interfaces require it; local matrix and drift calculations remain choice-free.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Transition matrices and n-step probabilities

Definition

Let $E$ be countable with sigma-algebra $2^{E}$ , and let $K$ be a probability kernel on it. For $x, y \in E$ , set

$p (x, y) : = K (x, {y}), p^{(n)} (x, y) : = K^{n} (x, {y}) (n \in N_{0}),$

where $K^{0}$ is the identity kernel, so $p^{(0)} (x, y) = 1_{{x = y}}$ . By Iterated transition kernels, each $K^{n}$ is a probability kernel. Since measures on countable discrete spaces are their singleton-weighted sums (Every measure on a countable discrete space is its weighted sum of Dirac measures), every row satisfies

$\sum_{y \in E} p^{(n)} (x, y) = K^{n} (x, E) = 1.$

No conditional-expectation version or choice function is used in this matrix definition.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Matrix Chapman–Kolmogorov equations

Statement

For $m, n \geq 0$ and $x, y$ in countable $E$ ,

$p^{(m + n)} (x, y) = \sum_{z \in E} p^{(m)} (x, z) p^{(n)} (z, y) .$

Facts & Assumptions

Given: A countable state space $E$ , a probability kernel $K$ on $(E, 2^{E})$ , $m, n \in N_{0}$ , and $x, y \in E$ .

[F1]

Iterated kernels start with $K^{0} = I$ and satisfy $K^{j + 1} = K^{j} K$ . Iterated transition kernels

[F2]

Kernel composition is defined by $(K L) (s, A) = \int_{T} L (t, A) K (s, d t)$ . Composition of probability kernels

[F3]

Kernel composition is associative at each source point and measurable set. Kernel composition is well defined and associative

[F4]

A measure on a countable discrete space is determined by its singleton weights and is their weighted sum. Every measure on a countable discrete space is its weighted sum of Dirac measures

[F5]

An increasing sequence of nonnegative measurable functions passes to the limit under the integral. Monotone convergence for the integral

[F6]

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

Proof

technique · direct induction and monotone convergence

1.1

For all $m, n \geq 0$ , $K^{m + n} = K^{m} K^{n}$ . For $n = 0$ , the composition formula in [F2] and $K^{0} = I$ in [F1] give $K^{m} K^{0} = K^{m}$ . If the identity holds at $n$ , then [F1] and associativity [F3] give

$K^{m + n + 1} = K^{m + n} K = (K^{m} K^{n}) K = K^{m} (K^{n} K) = K^{m} K^{n + 1} .$

Induction proves the kernel identity. [F1, F2, F3, given, induction]

2.1F2F3F6step 1.1given

Apply step 1.1 to the singleton ${y}$ . By [F2] and [F6], $p^{(m + n)} (x, y) = \int_{E} K^{n} (z, {y}) K^{m} (x, d z)$ . The integrand is measurable and between zero and one because $K^{n}$ is a probability kernel, so the integral is defined.

3.1F4F5F6step 2.1

If $E$ is finite, list it without repetition as $e (0), \dots, e (r - 1)$ ; if it is countably infinite, fix a bijection $e : N \to E$ . Let $J = {0, \dots, r - 1}$ in the finite case and $J = N$ in the infinite case, and set $g_{N} (z) = \sum_{k \in J, k < N} K^{n} (e (k), {y}) 1_{{z = e (k)}}$ . These finite-support functions increase pointwise to $g (z) = K^{n} (z, {y})$ and are constant once $N \geq r$ in the finite case. By [F4], the singleton weights of $K^{m} (x, \cdot)$ are $p^{(m)} (x, e (k))$ ; [F5] therefore gives $\int_{E} g d K^{m} (x, \cdot) = \lim_{N} \sum_{k \in J, k < N} p^{(m)} (x, e (k)) p^{(n)} (e (k), y) = \sum_{z \in E} p^{(m)} (x, z) p^{(n)} (z, y)$ . Combining with step 2.1 proves the formula, with the nonnegative series interpreted by its finite partial sums.

4.1F1F6step 3.1given∎

If $m = 0$ , the row $p^{(0)} (x, z) = 1_{{x = z}}$ leaves only the term $z = x$ ; if $n = 0$ , $p^{(0)} (z, y) = 1_{{z = y}}$ leaves only $z = y$ . When $m = n = 0$ , both sides are $1_{{x = y}}$ . Thus the zero-time endpoints, including the one-state and deterministic cases, agree. If $E = \emptyset$ , there are no $x, y$ and the assertion is vacuous. The proof uses kernel algebra and nonnegative sums only; no AC or conditional-probability version enters.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Accessibility, communication, and irreducibility

Definition

For the countable transition matrix $p$ of Transition matrices and n-step probabilities, define accessibility by

$x \to y ⟺ p^{(n)} (x, y) > 0 for some n \in N_{0} .$

States communicate, written $x \leftrightarrow y$ , when $x \to y$ and $y \to x$ . The chain is irreducible when every pair of states communicates. Because $p^{(0)} (x, y) = 1_{{x = y}}$ , every state is accessible from itself with a zero-step path.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Communication is an equivalence relation

Statement

For a countable transition matrix on $E$ , communication is an equivalence relation on $E$ , and its equivalence classes partition $E$ .

Facts & Assumptions

Given: A countable state space $E$ and its transition matrix $p$ .

[F1]

Accessibility means $x \to y$ exactly when $p^{(n)} (x, y) > 0$ for some $n \in N_{0}$ . Accessibility, communication, and irreducibility

[F2]

Communication is mutual accessibility: $x \leftrightarrow y$ means $x \to y$ and $y \to x$ . Accessibility, communication, and irreducibility

[F3]

The zero-step row satisfies $p^{(0)} (x, y) = 1_{{x = y}}$ , so each state is accessible from itself. Accessibility, communication, and irreducibility

[F4]

For $m, n \in N_{0}$ , $p^{(m + n)} (x, z) = \sum_{w \in E} p^{(m)} (x, w) p^{(n)} (w, z)$ . Matrix Chapman–Kolmogorov equations

Proof

technique · direct

1.1F2F3given

By [F3], $p^{(0)} (x, x) = 1$ , hence $x \to x$ and $x \leftrightarrow x$ for every $x \in E$ . The definition in [F2] is symmetric in $x, y$ , so communication is symmetric.

1.2F1F4given

Suppose $x \to y$ and $y \to z$ . By [F1], choose $m, n \in N_{0}$ with $p^{(m)} (x, y) > 0$ and $p^{(n)} (y, z) > 0$ . The nonnegative series in [F4] contains the term at $w = y$ , so $p^{(m + n)} (x, z) \geq p^{(m)} (x, y) p^{(n)} (y, z) > 0$ . Thus $x \to z$ . The argument permits either witness length to be zero.

2.1F2step 1.2given

If $x \leftrightarrow y$ and $y \leftrightarrow z$ , then $x \to y \to z$ gives $x \to z$ by step 1.2, and $z \to y \to x$ gives $z \to x$ by the same step. Therefore $x \leftrightarrow z$ , proving transitivity of communication.

3.1step 1.1step 2.1given

Define $[x] : = {y \in E : x \leftrightarrow y}$ . Reflexivity makes each $[x]$ contain $x$ , so these classes cover $E$ . If $c \in [x] \cap [z]$ , symmetry and transitivity give $x \leftrightarrow z$ ; then every member of either class belongs to the other, so $[x] = [z]$ . Thus distinct classes are disjoint and the classes partition $E$ .

4.1F1F3step 1.1step 1.2step 3.1given∎

If $E = \emptyset$ , there are no states or classes and the assertion is vacuous. If $E$ has one state, step 1.1 gives its sole class. Absorbing or otherwise degenerate rows cause no exception: the proof uses only zero-step identity and positive accessibility witnesses. No global choice is made; for each fixed triple in step 1.2, the two existential witnesses are used locally.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Hitting, return, and visit times

Definition

Let $(X_{n}, F_{n})_{n \geq 0}$ be an adapted Stochastic processes and their finite-dimensional distributions with values in a countable set $E$ equipped with $2^{E}$ . For $A \subseteq E$ , define

$T_{A} : = \inf {n \geq 0 : X_{n} \in A}, T_{x} : = T_{{x}}, T_{x}^{+} : = \inf {n \geq 1 : X_{n} = x} .$

The infimum of the empty set is $+ \infty$ . The visit count is the extended nonnegative integer

$N_{x} : = \sum_{n \geq 0} 1_{{X_{n} = x}} \in N_{0} \cup {+ \infty} .$

For a process started at $x$ , put $R_{0} = 0$ and define recursively

$R_{k} = {\begin{cases} \inf {n > R_{k - 1} : X_{n} = x}, & R_{k - 1} < \infty, \\ + \infty, & R_{k - 1} = \infty . \end{cases}$

Thus a later return time is assigned $+ \infty$ if the preceding one is infinite; the expression $X_{\infty}$ is never used. For every $A$ and $n \geq 0$ ,

${T_{A} \leq n} = ⋃_{j = 0}^{n} {X_{j} \in A}, {T_{x}^{+} \leq n} = ⋃_{j = 1}^{n} {X_{j} = x},$

where the second union is empty when $n = 0$ . Adaptedness makes these events belong to $F_{n}$ , so these are stopping times under Discrete stopping time.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Recurrent and transient states

Definition

For a specified Markov chain law with transition matrix $p$ and deterministic initial state $x$ , write $P_{x}$ for that law. The state $x$ is recurrent when

$P_{x} (T_{x}^{+} < \infty) = 1,$

and transient when

$P_{x} (T_{x}^{+} < \infty) < 1.$

Here $T_{x}^{+}$ is the strictly positive return time of Hitting, return, and visit times, so the initial visit at time zero does not count as a return. Since the displayed return probability lies in $[0, 1]$ , these alternatives exhaust all states. The definition concerns the specified law $P_{x}$ and does not assert that laws for every state can be selected simultaneously.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Renewal decomposition at successive returns

Statement

Assume AC (The Axiom of Choice). Let $X = (X_{n}, F_{n})_{n \geq 0}$ be a Time-homogeneous Markov chain with transition kernel on an at most countable state space $E$ with transition matrix $p$ , and use $P_{x}$ for its law started at $x \in E$ . Put $f_{x} (k) : = P_{x} (T_{x}^{+} = k) (k \geq 1), u_{x} (n) : = p^{(n)} (x, x) (n \geq 0) .$ Then $u_{x} (0) = 1$ and, for every $n \geq 1$ , $u_{x} (n) = \sum_{k = 1}^{n} f_{x} (k) u_{x} (n - k) .$

Let $R_{0} = 0$ and let $R_{k}$ be the successive return times from Hitting, return, and visit times. For each $k \geq 0$ and bounded measurable future-path functional $H : E^{N_{0}} \to R$ , define $Z_{k, H} : = \sum_{n \geq 0} 1_{{R_{k} = n}} H (X_{n}, X_{n + 1}, \dots),$ with value $0$ when $R_{k} = \infty$ . The post-return path has law $P_{x}$ independently of $F_{R_{k}}$ on the event of a finite return, in the precise sense $E_{x} [Z_{k, H} ∣ F_{R_{k}}] = 1_{{R_{k} < \infty}} E_{x} [H (X_{0}, X_{1}, \dots)] a.s.$

An excursion word from $x$ is a finite sequence $(x_{0}, \dots, x_{m})$ , $m \geq 1$ , with $x_{0} = x_{m} = x$ and $x_{j} \neq x$ for $0 < j < m$ . When $R_{k} < \infty$ , let the $k$ th completed excursion be $E_{k} = (X_{R_{k - 1}}, \dots, X_{R_{k}})$ ; set $E_{k} = \partial$ if $R_{k} = \infty$ , where $\partial \notin W_{x}$ . If $x$ is recurrent, all $R_{k}$ are finite almost surely and $(E_{k})_{k \geq 1}$ are iid. For a state that is not recurrent, the next excursion is asserted only after the preceding return is finite; no infinite sequence of completed excursions is asserted.

Facts & Assumptions

Given: AC, a countable-state Markov chain and a state $x$ .

[A1]

Every family of nonempty sets has a choice function; AC is assumed for the conditional-expectation and Markov results used below. (The Axiom of Choice)

[F1]

The return times are defined recursively, with $R_{0} = 0$ , $T_{x}^{+} = \inf {n \geq 1 : X_{n} = x}$ , and later returns set to $+ \infty$ after an infinite return. (Hitting, return, and visit times)

[F2]

A map $τ$ is a discrete stopping time when ${τ \leq n} \in F_{n}$ for every $n \geq 0$ . (Discrete stopping time)

[F3]

For a stopping time $τ$ , $F_{τ} = {A : A \cap {τ \leq n} \in F_{n} for all n \geq 0}$ . (Sigma-algebra at a stopping time)

[F4]

$p^{(n)} (x, y) = K^{n} (x, {y})$ and $p^{(0)} (x, y) = 1_{{x = y}}$ . (Transition matrices and n-step probabilities)

[F5]

For a chain with AC and bounded measurable $g$ , $E [g (X_{m + n}) ∣ F_{m}] = K^{n} g (X_{m})$ almost surely; the event version follows by taking an indicator. (Chapman-Kolmogorov equations)

[F6]

If $τ$ is a stopping time and $H$ is a bounded measurable future-path functional, then the conditional expectation of its shifted-path value is $E_{X_{τ}} H$ on ${τ < \infty}$ , with the shifted value defined as zero at $τ = \infty$ . (Discrete strong Markov property)

[F7]

The state $x$ is recurrent exactly when $P_{x} (T_{x}^{+} < \infty) = 1$ . (Recurrent and transient states)

[F8]

Under $P_{x}$ , the initial state is $X_{0} = x$ almost surely. (Initial distribution of a Markov chain)

[F9]

A time-homogeneous Markov chain is adapted to its filtration. (Time-homogeneous Markov chain with transition kernel)

[F10]

Every coordinate $X_{n}$ is a measurable random element, so finite-coordinate cylinder events are measurable. (Stochastic processes and their finite-dimensional distributions)

Proof

technique · split a return event at its first positive return, then use the strong Markov property at each finite return

1.1F4F5F8given

Since $p^{(0)} (x, x) = 1_{{x = x}}$ by [F4], $u_{x} (0) = 1$ . The conditional identity [F5] at $m = 0$ , together with $X_{0} = x$ [F8] and the definition of $p^{(n)}$ [F4], gives $P_{x} (X_{n} = x) = p^{(n)} (x, x) = u_{x} (n)$ .

1.2F1F2F9given

Every recursively defined $R_{k}$ is a stopping time: $R_{0} = 0$ is one, and if $R_{k - 1}$ is one, then for $n \geq 0$ , ${R_{k} \leq n} = ⋃_{m = 0}^{n - 1} ({R_{k - 1} = m} \cap ⋃_{j = m + 1}^{n} {X_{j} = x}),$ with the union empty when $n = 0$ . For $m \leq n$ , ${R_{k - 1} = m}$ is in $F_{m}$ because it is the difference of the stopping-time events ${R_{k - 1} \leq m}$ and ${R_{k - 1} \leq m - 1}$ (with the $m = 0$ case immediate). Adaptedness [F9] and the increasing filtration then put every displayed term in $F_{n}$ . This proves the induction using [F1, F2].

1.3F1F8F10given

Let $W_{x}$ be the set of excursion words defined in the statement. It is countable because it is a countable union of finite products of the countable set $E$ . For any $B \subseteq W_{x}$ , let $H_{B}$ be the indicator that a path starting at $x$ has a finite first-return word in $B$ , and set it to zero if there is no positive return. Its event is a countable union of finite-coordinate cylinder events [F10], so $H_{B}$ is product-measurable and bounded; write $q_{x} (B) = E_{x} H_{B} = P_{x} (E_{1} \in B)$ .

2.1F1F4F5step 1.1given

Fix $n \geq 1$ . The disjoint events ${X_{n} = x, T_{x}^{+} = k}$ , $1 \leq k \leq n$ , partition ${X_{n} = x}$ , because any path ending at $x$ has a first positive visit by time $n$ . By [F5], on ${T_{x}^{+} = k} \in F_{k}$ , $P_{x} (X_{n} = x, T_{x}^{+} = k) = E_{x} [1_{{T_{x}^{+} = k}} P_{x} (X_{n} = x ∣ F_{k})] = E_{x} [1_{{T_{x}^{+} = k}} p^{(n - k)} (X_{k}, x)] = f_{x} (k) u_{x} (n - k),$ since $X_{k} = x$ on that event. Summing these finitely many disjoint contributions and using step 1.1 gives the claimed renewal equation.

2.2F1F6F8step 1.2given

By step 1.2, $R_{k}$ is a stopping time. Apply [F6] to $H_{B}$ at $R_{k}$ . On ${R_{k} < \infty}$ , $X_{R_{k}} = x$ , and the shifted event $H_{B}$ is exactly that the next completed excursion word is in $B$ . Therefore $E_{x} [1_{{R_{k} < \infty}} 1_{{E_{k + 1} \in B}} ∣ F_{R_{k}}] = 1_{{R_{k} < \infty}} q_{x} (B),$ where the left side is interpreted as zero when $R_{k + 1} = \infty$ . The same strong Markov identity with arbitrary bounded $H$ gives the post-return formula in the statement.

3.1F1F7step 2.2given

Suppose $x$ is recurrent. Taking $B = W_{x}$ in step 2.2 gives $q_{x} (B) = P_{x} (T_{x}^{+} < \infty) = 1$ by [F7]. Induction from $R_{0} = 0$ yields $P_{x} (R_{k} < \infty) = 1$ for every $k$ ; since there are countably many $k$ , all returns are finite simultaneously almost surely.

4.1F1F3step 2.2step 3.1given

For $m \geq 1$ and arbitrary $B_{1}, \dots, B_{m} \subseteq W_{x}$ , the event $A = ⋂_{j < m} {E_{j} \in B_{j}}$ belongs to $F_{R_{m - 1}}$ : on each event ${R_{m - 1} = r}$ it is determined by $X_{0}, \dots, X_{r}$ , so $A \cap {R_{m - 1} \leq n} = ⋃_{r = 0}^{n} (A \cap {R_{m - 1} = r}) \in F_{n}$ by [F3]. Applying the conditional identity in step 2.2 at $R_{m - 1}$ and using step 3.1 gives $P_{x} (E_{1} \in B_{1}, \dots, E_{m} \in B_{m}) = q_{x} (B_{m}) P_{x} (E_{1} \in B_{1}, \dots, E_{m - 1} \in B_{m - 1}) .$ Induction in $m$ factors this joint probability as $\prod_{j = 1}^{m} q_{x} (B_{j})$ , proving that the excursion words are iid with common first-excursion law $q_{x}$ .

5.1A1F1F3F4F5F6F7step 1.1step 2.1step 2.2step 3.1step 4.1given∎

If $E = \emptyset$ , there is no state $x$ and the theorem is vacuous. If $x$ has no positive return, then $u_{x} (n) = 0$ for every $n \geq 1$ (a visit at positive time would be a return), every $f_{x} (k) = 0$ , and the convolution has both sides zero; for $n = 0$ the identity is $u_{x} (0) = 1$ . At the endpoint $n = 1$ , the formula is $u_{x} (1) = f_{x} (1) u_{x} (0)$ . In a one-state absorbing chain, $f_{x} (1) = 1$ , $f_{x} (k) = 0$ for $k > 1$ , and $u_{x} (n) = 1$ , so the equation holds directly. More generally, in a deterministic cycle of length $r$ , $f_{x} (k) = 1_{{k = r}}$ and $u_{x} (n) = 1_{{r ∣ n}}$ ; if $n < r$ the sum is empty, and if $n \geq r$ the sole possible term is $u_{x} (n - r) = 1_{{r ∣ n}}$ , as required. For a transient state the conditional identities of steps 2.2 remain restricted to finite $R_{k}$ ; if a return fails, the definition sets later returns to infinity, and no further completed excursion is claimed. AC [A1] is used through [F5] and [F6]; the cylinder measurability and event decomposition use no additional choice. The equation and iid assertion are one-way claims, not biconditionals.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Equivalent criteria for recurrence and transience

Statement

Assume AC (The Axiom of Choice). Let $X = (X_{n}, F_{n})_{n \geq 0}$ be a time-homogeneous Markov chain on an at most countable state space $E$ , with transition matrix $p$ . Fix $x \in E$ and use $P_{x}$ and $E_{x}$ for the specified law with $X_{0} = x$ almost surely. For the visit count $N_{x} = \sum_{n \geq 0} 1_{{X_{n} = x}}$ , which includes the initial visit, the following are equivalent:

$x is recurrent ⟺ P_{x} (N_{x} = \infty) = 1 ⟺ \sum_{n = 0}^{\infty} p^{(n)} (x, x) = \infty .$

If $x$ is transient and $r_{x} : = P_{x} (T_{x}^{+} < \infty) < 1$ , then for every integer $k \geq 1$ ,

$P_{x} (N_{x} = k) = (1 - r_{x}) r_{x}^{k - 1}, E_{x} N_{x} = \sum_{n = 0}^{\infty} p^{(n)} (x, x) = \frac{1}{1 - r_{x}} < \infty .$

Facts & Assumptions

Given: AC, a countable-state Markov chain, and a fixed state $x \in E$ .

[A1]

AC is assumed for the specified chain law and the finite-dimensional and strong-Markov conditional-expectation interfaces used below. (The Axiom of Choice)

[F1]

Under the fixed initial state, $X_{0} = x$ almost surely, and $P_{x}, E_{x}$ denote that specified law and expectation. (Initial distribution of a Markov chain)

[F2]

$N_{x} = \sum_{n \geq 0} 1_{{X_{n} = x}}$ counts the time-zero visit. (Hitting, return, and visit times)

[F3]

$T_{x}^{+} = \inf {n \geq 1 : X_{n} = x}$ , so a return must occur at a strictly positive time. (Hitting, return, and visit times)

[F4]

The successive returns are $R_{0} = 0$ and $R_{j} = \inf {n > R_{j - 1} : X_{n} = x}$ after a finite preceding return, with later returns set to $+ \infty$ after an infinite one. (Hitting, return, and visit times)

[F5]

$x$ is recurrent exactly when $r_{x} = P_{x} (T_{x}^{+} < \infty) = 1$ , and is transient exactly when $r_{x} < 1$ . (Recurrent and transient states)

[F6]

$p^{(n)} (x, y) = K^{n} (x, {y})$ and $p^{(0)} (x, y) = 1_{{x = y}}$ . (Transition matrices and n-step probabilities)

[F7]

The finite-dimensional law at the single time $n$ , with initial law $δ_{x}$ and test $1_{{x}}$ , gives $P_{x} (X_{n} = x) = p^{(n)} (x, x)$ . (Finite-dimensional laws of a Markov chain)

[F8]

At each finite return time $R_{j}$ , the post-return path has the $P_{x}$ law in the conditional sense: for bounded measurable future-path $H$ , $E_{x} [Z_{j, H} ∣ F_{R_{j}}] = 1_{{R_{j} < \infty}} E_{x} [H (X_{0}, X_{1}, \dots)]$ a.s. (Renewal decomposition at successive returns)

[F9]

Each coordinate $X_{n}$ is a measurable random element; hence its singleton event ${X_{n} = x}$ is measurable. (Stochastic processes and their finite-dimensional distributions)

[F10]

If nonnegative measurable $Y_{m} ↑ Y$ , then $E_{x} Y_{m} ↑ E_{x} Y$ , allowing $+ \infty$ . (Monotone convergence for the integral)

[F11]

For decreasing measurable events $A_{k}$ in the probability measure $P_{x}$ , $P_{x} (⋂_{k} A_{k}) = \lim_{k} P_{x} (A_{k})$ because $P_{x} (A_{1}) \leq 1 < \infty$ . (Continuity from above when one set has finite measure)

[F12]

If $0 \leq r < 1$ , then $r^{m} \to 0$ . (For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ )

[F13]

If $0 \leq r < 1$ , then $\sum_{m = 0}^{\infty} r^{m} = 1 / (1 - r)$ . (For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges)

[F14]

Integer powers use $r^{0} = 1$ , including when $r = 0$ . (For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges)

Proof

technique · identify visit tails with finite successive returns, iterate the return-time Markov identity, then apply monotone convergence to both the time-indexed and tail-indexed visit counts

1.1F1F2F4given

For each $k \geq 1$ , pathwise ${N_{x} \geq k} = {R_{k - 1} < \infty}$ . Since $X_{0} = x$ [F1], the first visit is already counted, and at least $k$ visits are exactly $k - 1$ further finite returns. In particular, both events are certain for $k = 1$ since $R_{0} = 0$ . Also ${N_{x} = \infty} = ⋂_{k \geq 1} {N_{x} \geq k}$ .

1.2A1F1F2F6F7F9F10given

The finite partial visit counts $V_{m} : = \sum_{n = 0}^{m} 1_{{X_{n} = x}}$ are nonnegative measurable by [F9] and increase pointwise to $N_{x}$ [F2]. Monotone convergence [F10] therefore gives, with extended values allowed, $E_{x} N_{x} = \lim_{m \to \infty} \sum_{n = 0}^{m} P_{x} (X_{n} = x) = \sum_{n = 0}^{\infty} p^{(n)} (x, x)$ , where the last equality uses the finite-dimensional law [F7] under AC [A1]. The $n = 0$ term is $1$ on each side by [F1] and [F6]; no initial visit is lost.

2.1A1F3F4F8F9step 1.1given

Define the bounded future-path functional $H_{x} (ω) = 1_{{\exists m \geq 1 : ω_{m} = x}}$ . Its event is a countable union of coordinate-cylinder events, hence measurable by [F9], and $E_{x} H_{x} = r_{x}$ by the definition of $T_{x}^{+}$ [F3]. On ${R_{j} < \infty}$ , $Z_{j, H_{x}} = 1_{{R_{j + 1} < \infty}}$ ; on ${R_{j} = \infty}$ it is zero. Applying the AC-based strong-Markov identity [F8] and taking expectations gives $P_{x} (R_{j + 1} < \infty) = r_{x} P_{x} (R_{j} < \infty)$ . Starting from $P_{x} (R_{0} < \infty) = 1$ , induction yields $P_{x} (R_{j} < \infty) = r_{x}^{j}$ . By step 1.1, $P_{x} (N_{x} \geq k) = r_{x}^{k - 1}$ for every $k \geq 1$ .

3.1F4F5F11F12step 2.1cases-exhaustivecases

The events ${N_{x} \geq k}$ decrease to ${N_{x} = \infty}$ . Continuity from above [F11] and step 2.1 give $P_{x} (N_{x} = \infty) = \lim_{k \to \infty} r_{x}^{k - 1}$ . If $x$ is recurrent, [F5] gives $r_{x} = 1$ , so this limit is $1$ . If $x$ is transient, [F5] gives $0 \leq r_{x} < 1$ , and [F12] makes the limit $0$ . These two cases exhaust all states, so $x$ is recurrent if and only if $P_{x} (N_{x} = \infty) = 1$ .

3.2F2F4F5F10F13step 2.1step 1.2cases-exhaustive

For $M \geq 1$ , let $W_{M} : = \sum_{k = 1}^{M} 1_{{N_{x} \geq k}}$ . These are nonnegative measurable variables, increase pointwise to $N_{x}$ , and [F10] together with step 2.1 gives $E_{x} N_{x} = \sum_{k = 1}^{\infty} P_{x} (N_{x} \geq k) = \sum_{j = 0}^{\infty} r_{x}^{j}$ . If $x$ is recurrent then [F5] gives $r_{x} = 1$ and this sum is $+ \infty$ . If $x$ is transient then [F5] gives $r_{x} < 1$ and [F13] gives $E_{x} N_{x} = 1 / (1 - r_{x}) < \infty$ . In view of step 1.2, the Green series diverges exactly in the recurrent case. This proves both directions of the recurrence/Green-series equivalence without subtracting extended values.

4.1F13F14step 2.1step 3.1step 3.2

In the transient case, for every $k \geq 1$ the nested tail events satisfy $P_{x} (N_{x} = k) = P_{x} (N_{x} \geq k) - P_{x} (N_{x} \geq k + 1) = (1 - r_{x}) r_{x}^{k - 1}$ by step 2.1 and finite subtraction of probabilities in $[0, 1]$ . Since $P_{x} (N_{x} = \infty) = 0$ by step 3.1, these masses account for all outcomes; their sum is $(1 - r_{x}) \sum_{j \geq 0} r_{x}^{j} = 1$ by [F13]. When $r_{x} = 0$ , the convention $0^{0} = 1$ [F14] gives $P_{x} (N_{x} = 1) = 1$ and $P_{x} (N_{x} = k) = 0$ for $k > 1$ , as expected when no positive return occurs. The mean formula is the transient case of step 3.2.

5.1A1F1F2F3F4F5F6F8step 1.1step 2.1step 3.1step 1.2step 3.2step 4.1given∎

If $E = \emptyset$ , there is no $x$ and the theorem is vacuous. For a one-state absorbing chain, $r_{x} = 1$ , $N_{x} = \infty$ almost surely, and $p^{(n)} (x, x) = 1$ for every $n$ , agreeing with both recurrence criteria. If a deterministic chain started at $x$ leaves and never returns, then $r_{x} = 0$ , $N_{x} = 1$ almost surely, and $p^{(n)} (x, x) = 0$ for $n \geq 1$ , agreeing with the transient formulas. If instead a deterministic cycle returns after a fixed positive period $d$ , then $r_{x} = 1$ and $p^{(m d)} (x, x) = 1$ for all $m \geq 0$ , so both the infinite-visit probability and Green series are infinite as asserted. The $n = 0$ Green term and $k = 1$ tail were treated explicitly in steps 1.1 and 1.2–3.2. AC [A1] is used for the specified chain law and the conditional strong-Markov identity [F8]; the return-series arithmetic itself uses no choice. Both stated equivalences have been proved in both directions in steps 3.1 and 3.2.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Green kernel of a transient chain

Definition

For any countable transition matrix $p$ , define its extended nonnegative Green kernel by

$G (x, y) : = \sum_{n \geq 0} p^{(n)} (x, y) \in [0, + \infty] .$

This matrix series is defined without Choice. Under the explicitly assumed Axiom of Choice The Axiom of Choice, for a specified chain law with initial state $x$ , the multistep Markov identity gives $P_{x} (X_{n} = y) = p^{(n)} (x, y)$ for each $n$ (Chapman-Kolmogorov equations). Applying monotone convergence to the partial sums of $N_{y} = \sum_{n \geq 0} 1_{{X_{n} = y}}$ then gives

$E_{x} N_{y} = \sum_{n \geq 0} P_{x} (X_{n} = y) = G (x, y) .$

No finiteness is asserted: $G (x, y)$ may be $+ \infty$ , including when a chain starts in a transient state and can enter a recurrent class. The expectation identity uses Hitting, return, and visit times and Monotone convergence for the integral; the matrix definition remains valid for recurrent states as well.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Green-kernel resolvent identity

Statement

Let $E$ be at most countable, let $p$ be a transition matrix on $E$ , and let $G (x, y) = \sum_{n \geq 0} p^{(n)} (x, y) \in [0, + \infty]$ . Define the extended nonnegative matrix products by the support-restricted sums

$(P G) (x, y) : = \sum_{z \in E : p (x, z) > 0} p (x, z) G (z, y), (G P) (x, y) : = \sum_{z \in E : p (z, y) > 0} G (x, z) p (z, y) .$

Zero-coefficient terms are omitted, so neither product forms the undefined $0 \cdot (+ \infty)$ . Then, for every $x, y \in E$ ,

$G (x, y) = 1_{{x = y}} + (P G) (x, y) = 1_{{x = y}} + (G P) (x, y),$

with all sums and equalities in the nonnegative extended reals.

Facts & Assumptions

Given: An at most countable state space $E$ and a transition matrix $p$ on $E$ .

[F1]

The Green kernel is $G (x, y) : = \sum_{n \geq 0} p^{(n)} (x, y) \in [0, + \infty]$ . Green kernel of a transient chain

[F2]

For $ϕ : E \to [0, + \infty]$ , the nonnegative kernel action is $P ϕ (x) : = \sum_{z \in E : p (x, z) > 0} p (x, z) ϕ (z) \in [0, + \infty]$ . Nonnegative kernel action and finite drift

[F3]

For $m, n \geq 0$ , $p^{(m + n)} (x, y) = \sum_{z \in E} p^{(m)} (x, z) p^{(n)} (z, y)$ . Matrix Chapman–Kolmogorov equations

[F4]

A nonnegative double series has the same value in either summation order: $\sum_{i} \sum_{j} a_{i j} = \sum_{j} \sum_{i} a_{i j}$ , including when the common value is $+ \infty$ . Tonelli's theorem for double series of nonnegative extended real numbers

[F5]

In the library's extended-real arithmetic, every product with one factor $0$ and the other $+ \infty$ is undefined. The extended real line $\overline{R} = R \cup {- \infty, + \infty}$ , its order, and the arithmetic that is left undefined

[F6]

A countable set is finite or is in bijection with $N$ . Finite, countably infinite, countable, uncountable

[F7]

The zero-step transition probability is $p^{(0)} (x, y) = 1_{{x = y}}$ . Transition matrices and n-step probabilities

[F8]

A nonnegative extended series is the supremum of its finite partial sums. Series in the nonnegative extended real line

Proof

technique · direct

1.1F5F8givenalgebra

If $c$ is a finite positive real and $(a_{n})_{n \geq 0}$ is nonnegative, then $c \sum_{n \geq 0} a_{n} = \sum_{n \geq 0} c a_{n}$ . For partial sums $s_{N} = \sum_{n < N} a_{n}$ , if $\sup_{N} s_{N} < \infty$ , continuity of multiplication by $c$ gives $c s_{N} ↑ c \sup_{N} s_{N}$ ; if $\sup_{N} s_{N} = + \infty$ , the $s_{N}$ are unbounded and so are $c s_{N}$ . By [F5], every product is defined because $c > 0$ .

2.1F1F3F4F5F6F8step 1.1given

Fix $x, y \in E$ . For each $z$ with $p (x, z) > 0$ , [F1, F2] and step 1.1 give $p (x, z) G (z, y) = \sum_{n \geq 0} p (x, z) p^{(n)} (z, y)$ . Terms with $p (x, z) = 0$ are omitted in $(P G) (x, y)$ ; inserting corresponding zero terms in the nonnegative double series is valid because $p^{(n)} (z, y) \leq 1$ . Apply [F4] to that double series. If $E$ is finite, use a finite listing and pad with zeros; if countably infinite, use a bijection with $N$ from [F6]. Then [F3] with $m = 1$ yields $(P G) (x, y) = \sum_{z \in E} \sum_{n \geq 0} p (x, z) p^{(n)} (z, y) = \sum_{n \geq 0} \sum_{z \in E} p (x, z) p^{(n)} (z, y) = \sum_{n \geq 0} p^{(n + 1)} (x, y) = \sum_{n \geq 1} p^{(n)} (x, y) .$

2.2F1F3F4F5F6F8step 1.1given

For each $z$ with $p (z, y) > 0$ , [F1] and step 1.1 give $G (x, z) p (z, y) = \sum_{n \geq 0} p^{(n)} (x, z) p (z, y)$ . Terms with $p (z, y) = 0$ are omitted in $(G P) (x, y)$ ; inserting their zero finite products in the double series introduces no undefined extended-real product. Tonelli [F4], now summing first over $z$ , and [F3] with $m = n$ and second time index $1$ give $(G P) (x, y) = \sum_{z \in E} \sum_{n \geq 0} p^{(n)} (x, z) p (z, y) = \sum_{n \geq 0} \sum_{z \in E} p^{(n)} (x, z) p (z, y) = \sum_{n \geq 0} p^{(n + 1)} (x, y) = \sum_{n \geq 1} p^{(n)} (x, y) .$

3.1F1F4F5F6F7F8step 2.1step 2.2given∎

By [F1, F8], separating the $n = 0$ term in the nonnegative series gives $G (x, y) = p^{(0)} (x, y) + \sum_{n \geq 1} p^{(n)} (x, y)$ . This is a split of nonnegative partial sums, not a subtraction. Using [F7] and steps 2.1 and 2.2 proves both identities. If $E = \emptyset$ , there are no $x, y$ and the claim is vacuous. For a one-state absorbing chain, $G = + \infty$ and both support-restricted products equal $+ \infty$ , so $G = 1 + \infty$ is well defined. Zero transition coefficients are always omitted; positive coefficients may multiply $+ \infty$ and produce $+ \infty$ . The argument includes deterministic rows and all zero-time endpoints. It uses no AC: the one enumeration of this fixed countable $E$ is part of [F6], and [F4] is proved using finite choice. The lemma states no biconditional.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Recurrence and transience are class properties

Statement

Assume AC (The Axiom of Choice). Let $E$ be at most countable with sigma-algebra $2^{E}$ , and let $K$ be a probability kernel with transition matrix $p (x, y) = K (x, {y})$ . For each fixed $z \in E$ , let $P_{z}$ be the canonical path-space law with initial measure $δ_{z}$ and transition kernel $K$ . Write $T_{z} = \inf {n \geq 0 : X_{n} = z}$ and $T_{z}^{+} = \inf {n \geq 1 : X_{n} = z}$ . If $x$ and $y$ communicate, then $x is recurrent ⟺ y is recurrent .$ More strongly, if $x$ is recurrent and $x \to y$ , then $P_{x} (T_{y} < \infty) = P_{y} (T_{x} < \infty) = 1.$ The communicating class $[x] : = {z \in E : z \leftrightarrow x}$ of a recurrent state is closed: if $z \in [x]$ and $p (z, w) > 0$ , then $w \in [x]$ .

Facts & Assumptions

Given: AC, an at most countable state space $E$ with its full power-set sigma-algebra, a probability kernel $K$ , its transition matrix $p$ , and the canonical law for each fixed deterministic start.

[A1]

Every family of nonempty sets has a choice function. AC is used for the canonical chain laws and the conditional Markov suppliers cited below. (The Axiom of Choice)

[F1]

An at most countable set is finite or countably infinite. (Finite, countably infinite, countable, uncountable)

[F2]

A probability kernel is a measure in its target variable and has total mass one. (Measure kernel and probability kernel)

[F3]

The transition entries are $p (x, y) = K (x, {y})$ , and matrix powers are defined from the iterated kernels. (Transition matrices and n-step probabilities)

[F4]

For each $z \in E$ , the Dirac set function $δ_{z}$ is a probability measure. (A Dirac set function is a probability measure)

[F5]

Under AC, the canonical path space has the chain law with specified initial measure and transition kernel. (Canonical Markov chain on path space)

[F6]

With initial state fixed at $z$ , $P_{z} = P_{δ_{z}}$ ; in particular $X_{0} = z$ almost surely under $P_{z}$ . (Initial distribution of a Markov chain)

[F7]

Accessibility means $x \to y$ exactly when $p^{(n)} (x, y) > 0$ for some $n \in N_{0}$ ; communication is mutual accessibility. (Accessibility, communication, and irreducibility)

[F8]

For $m, n \geq 0$ , $p^{(m + n)} (x, y) = \sum_{v \in E} p^{(m)} (x, v) p^{(n)} (v, y)$ . (Matrix Chapman–Kolmogorov equations)

[F9]

The finite-dimensional law of the coordinate chain gives the probability of every finite cylinder as the product of its successive transition probabilities when the initial state is fixed. (Finite-dimensional laws of a Markov chain)

[F10]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ and $T_{x}^{+} = \inf {n \geq 1 : X_{n} = x}$ are stopping times; the time-zero and positive return conventions are distinct. (Hitting, return, and visit times)

[F11]

A state $x$ is recurrent exactly when $P_{x} (T_{x}^{+} < \infty) = 1$ ; transience means the probability is less than one, so the two cases exhaust all states. (Recurrent and transient states)

[F12]

If $x$ is recurrent, all its successive returns are finite almost surely and the completed return excursions from $x$ are iid. (Renewal decomposition at successive returns)

[F13]

At a stopping time, the conditional law of a bounded measurable future path functional is the law started from the state at that time on the event the stopping time is finite. (Discrete strong Markov property)

[F14]

Communication is an equivalence relation, and its equivalence classes partition $E$ . (Communication is an equivalence relation)

[F15]

If $0 \leq r < 1$ , then $r^{m} \to 0$ . (For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ )

Proof

technique · choose a shortest positive route, try it on successive return excursions, and use strong Markov at the finite hitting time

1.1A1F1F2F3F4F5F6F7F8F9given

Fix distinct $x, y$ with $x \to y$ . By [F7], the set of $n$ with $p^{(n)} (x, y) > 0$ is nonempty; choose its least element. It is positive because $p^{(0)} (x, y) = 0$ by [F3]. Repeatedly decompose a positive $n$ -step entry by [F8]. At each decomposition, some summand is positive, so this gives a finite route $x = z_{0}, z_{1}, \dots, z_{n} = y$ with $α : = \prod_{i = 1}^{n} p (z_{i - 1}, z_{i}) > 0.$ This is a witness for this fixed pair only; it makes no simultaneous choice of routes. Minimality of $n$ implies $z_{i} \neq x$ and $z_{i} \neq y$ for $1 \leq i < n$ , since either repeated endpoint would leave a shorter positive route from $x$ to $y$ . The finite-dimensional law [F9], with initial state $x$ [F6], gives $P_{x} (X_{0} = z_{0}, \dots, X_{n} = z_{n}) = α .$ Call this cylinder event $C$ . In particular, on $C$ the chain reaches $y$ before any positive return to $x$ .

1.2F10F11given

If $x = y$ , recurrence of $y$ is the same assertion as recurrence of $x$ ; also $T_{x} = T_{y} = 0$ under $P_{x}$ , so both hitting probabilities in the stronger claim equal one. This separates time-zero hitting from the strictly positive return used in [F11].

2.1A1F1F11F12F15step 1.1given

Suppose $x$ is recurrent and $x \neq y$ . By [F12], the return excursions $E_{1}, E_{2}, \dots$ are iid and finite almost surely. Let $B$ be the set of completed excursion words whose first $n$ transitions follow the route in step 1.1. Since $C$ contains no return to $x$ before time $n$ , the event ${E_{1} \in B}$ agrees with $C$ except on the null event that the first return to $x$ is infinite. Hence $P_{x} (E_{1} \in B) = α$ , and the same holds for each excursion by identical distribution. For every $m \geq 1$ , the probability that none of the first $m$ excursions begins with the route is $(1 - α)^{m}$ . If $T_{y} = \infty$ , none of them can begin with it; therefore $P_{x} (T_{y} = \infty) \leq (1 - α)^{m} (m \geq 1) .$ Since $0 \leq 1 - α < 1$ , [F15] makes the right side tend to zero. Thus $P_{x} (T_{y} < \infty) = 1$ .

2.2A1F10F11F13step 1.1given

Still suppose $x$ is recurrent and $x \neq y$ . Let $H_{x}$ be the indicator of the measurable future-path event that no coordinate equals $x$ . Put $q = P_{y} (T_{x} = \infty)$ . Apply [F13] at the deterministic stopping time $n$ from step 1.1. Since $X_{n} = y$ on $C$ , the conditional future probability of avoiding $x$ is $q$ , so $P_{x} (C \cap {X_{n + j} \neq x for all j \geq 0}) = α q .$ On this event there is no positive-time return to $x$ : the route has no intermediate $x$ , its endpoint $y$ is not $x$ , and the future avoids $x$ . If $q > 0$ this contradicts [F11]. Hence $q = 0$ and $P_{y} (T_{x} < \infty) = 1$ .

3.1A1F10F11F13step 2.1step 2.2given

Under $P_{y}$ , let $τ = T_{x}$ . Step 2.2 gives $τ < \infty$ almost surely, and $τ \geq 1$ because $x \neq y$ . Apply [F13] at $τ$ to the bounded future-path indicator $1_{{T_{y} < \infty}}$ . By step 2.1, its probability from $x$ is one. Thus after the chain first reaches $x$ it reaches $y$ again almost surely. This is a positive-time return from the initial state $y$ , so $y$ is recurrent by [F11].

3.2F7F8F11F14step 2.1step 2.2given

Assume $x$ is recurrent, as required for the closure claim. Let $z \in [x]$ and suppose $p (z, w) > 0$ . By [F14], $x \leftrightarrow z$ , so some $m \geq 0$ has $p^{(m)} (x, z) > 0$ by [F7]. The one-step transition $p (z, w) > 0$ and [F8] give $p^{(m + 1)} (x, w) \geq p^{(m)} (x, z) p (z, w) > 0,$ so $x \to w$ . If $w \neq x$ , steps 2.1 and 2.2 give $w \leftrightarrow x$ ; if $w = x$ , membership is immediate. Thus $w \in [x]$ , proving the class is closed.

4.1F7F11step 1.2step 2.1step 2.2step 3.1given

Suppose $x \leftrightarrow y$ . If $x$ is recurrent, then either $x = y$ as in step 1.2 or $x \to y$ and step 3.1 shows $y$ is recurrent. If $y$ is recurrent, apply the implication of steps 2.1–3.1 to the ordered pair $(y, x)$ to get that $x$ is recurrent. This proves both directions of the equivalence. By [F11], a state that is not recurrent is transient, so the classification is shared.

5.1A1F2F3F7F8F10F11F12F13step 1.1step 1.2step 2.1step 2.2step 3.1step 3.2step 4.1given∎

If $E = \emptyset$ , there is no starting state and the assertions are vacuous. If $E$ has one state, its only transition row has probability one on itself; the state is recurrent and its class is closed. Zero transition weights cannot appear in the chosen route because every factor is positive; the Chapman–Kolmogorov sums otherwise include all states. For a deterministic transition map, recurrence of $x$ means its orbit returns to $x$ after some positive number of steps, so the orbit is a finite cycle; every state accessible from $x$ lies on that cycle and has the stated hitting and recurrence properties. The endpoint $x = y$ gives accessibility at time zero but recurrence still uses $T_{x}^{+}$ at positive time [F10, F11]; distinct communicating states use a route of length at least one. AC [A1] supplies the canonical fixed-start laws and is assumed by the renewal and strong-Markov results. The finite-route witness is selected only for each fixed pair, with no global route selection. The two recurrence implications were proved in step 4.1, so both iff cases are covered.

Source notes

Durrett, Probability: Theory and Examples, 5th ed., §5.3, Theorem 5.3.2 and its complete proof, printed p. 282/PDF p. 289 (official PDF parser lines 19113–19149). Durrett defines $ρ_{x y} = P_{x} (T_{y} < \infty)$ and proves that recurrence is contagious: recurrent $x$ and $ρ_{x y} > 0$ imply that $y$ is recurrent and $ρ_{y x} = 1$ . The proof first extracts a shortest positive route and shows $ρ_{y x} = 1$ by ruling out a positive-probability route followed by avoidance of $x$ ; it then uses Theorem 5.3.1's Green-series criterion to establish recurrence of $y$ . Here that last conclusion follows instead from the proved iid excursion law and strong Markov at $T_{x}$ . No diagonal-series comparison is used. The exact countable-state theorem is the Durrett source for the claim; its argument is not treated as a substitute for the complete local proof.

Levin–Peres–Wilmer, Markov Chains and Mixing Times, 2nd ed., §21.1, Proposition 21.3 and its complete proof, printed pp. 291–292/PDF pp. 307–308 (official PDF parser lines 22015–22090). The source assumes irreducibility and proves the equivalent all-state recurrence and hitting statements. It is relevant after restriction to a closed communicating class but is not used in this local proof. Section 1.7, printed pp. 15–17/PDF pp. 30–32, supplies finite-state communicating-class terminology only.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Irreducible recurrence/transience dichotomy

Statement

Assume AC. Let the countable-state chain, transition matrix, fixed-start canonical laws, and positive-time recurrence convention be as in Recurrence and transience are class properties. Irreducibility means that every pair of states communicates (Accessibility, communication, and irreducibility). If $E = \emptyset$ , the universal conclusions below are vacuous. Otherwise, if the chain is irreducible, then either every state is recurrent or every state is transient.

Facts & Assumptions

Given: AC and a chain in the countable-state setup of the class-property theorem.

[A1]

AC supplies the fixed-start canonical laws and is an explicit hypothesis of the class-property theorem used here. (The Axiom of Choice)

[F1]

Irreducibility means $x \leftrightarrow y$ for every pair $x, y \in E$ . (Accessibility, communication, and irreducibility)

[F2]

Communicating states have the same recurrence status. In particular, recurrence of one state transfers to every state that communicates with it. (Recurrence and transience are class properties)

[F3]

A state is recurrent when its positive-time return probability is one and transient when that probability is less than one; these alternatives exhaust all states because the probability lies in $[0, 1]$ . (Recurrent and transient states)

[F4]

Every probability-kernel row has total mass one. On a one-state space, this forces the sole transition probability to equal one. (Measure kernel and probability kernel)

Proof

technique · in a nonempty irreducible chain, fix one state and use the class-property theorem to transfer its exhaustive recurrence/transience case to every state

1.1given

If $E = \emptyset$ , there are no states to classify. Both universal conclusions in the disjunction hold vacuously.

1.2F1given

Now suppose $E \neq \emptyset$ and fix one state $x \in E$ . For every $y \in E$ , irreducibility [F1] gives $x \leftrightarrow y$ . This fixes one witness state only; no family of choices is made.

2.1F2step 1.2given

If $x$ is recurrent, [F2] and step 1.2 imply that every $y \in E$ is recurrent. Hence the first alternative holds.

2.2F2F3step 1.2given

If $x$ is not recurrent, consider any $y \in E$ . If $y$ were recurrent, [F2] and step 1.2 would imply that $x$ is recurrent, a contradiction. Thus no state is recurrent. By [F3], every state is transient, so the second alternative holds.

3.1F3step 2.1step 2.2given

By [F3], the fixed state $x$ is either recurrent or transient. Step 2.1 handles the recurrent case and step 2.2 handles the transient case. Therefore one of the two asserted universal alternatives always holds.

4.1A1F1F2F3F4step 1.2step 2.1step 2.2given∎

If $E$ has one state $x$ , [F4] gives $p (x, x) = 1$ , so its positive-time return probability is one. If $E$ has more than one state, an absorbing row at any state would make the chain reducible; zero one-step weights are allowed, since irreducibility requires communication by some positive-probability finite path, not a positive one-step transition. The zero-step accessibility $x \to x$ alone does not establish recurrence, which requires a positive-time return [F3]. For a deterministic transition map on a nonempty irreducible state space with more than one state, fix $x$ and choose $y \neq x$ . The unique forward orbit from $x$ reaches $y$ and then returns to $x$ by irreducibility. It therefore contains a finite cycle through $x$ ; every state is reachable from $x$ , so every state lies on this cycle and returns to itself. Steps 2.1 and 2.2 prove the forward and reverse uses of the class-property equivalence. AC [A1] is inherited by the canonical laws and class-property theorem; fixing one state in step 1.2 uses no choice principle.

Source notes

Durrett, Probability: Theory and Examples, 5th ed., §5.3, Theorem 5.3.2 and its complete proof, printed p. 282/PDF p. 289 (official PDF parser lines 19113–19149), proves the stronger countable-chain statement that recurrence is contagious along accessibility and that the reverse hitting probability is one. Example 5.3.6 explicitly says that an infinite irreducible chain is either wholly recurrent or wholly transient, printed p. 284/PDF p. 291 (official parser lines 19241–19243). The example alone has an infinite-state hypothesis; this item's finite and empty cases are handled locally. The proof here uses the pair's completed class-property theorem and the definition that recurrence and transience exhaust the return-probability alternatives.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Hitting probability as minimal harmonic extension

Statement

Assume AC (The Axiom of Choice). Let $X$ be a Markov chain with transition kernel $K$ on an at most countable state space $E$ , transition matrix $p (x, y) = K (x, {y})$ , and let $A \subseteq E$ . Define $h (x) : = P_{x} (T_{A} < \infty)$ . Then $h (x) = 1 (x \in A), h (x) = P h (x) (x \in A^{c}),$ where $P ϕ (x) = \sum_{y \in E : p (x, y) > 0} p (x, y) ϕ (y)$ is the support-restricted nonnegative kernel action. Moreover, for every finite-valued $g : E \to [0, \infty)$ satisfying $g = 1$ on $A$ and $g = P g$ on $A^{c}$ , one has $h (x) \leq g (x)$ for every $x \in E$ .

Facts & Assumptions

Given: AC, a countable-state Markov chain, $A \subseteq E$ , and for the minimality claim a finite-valued nonnegative $g$ with $g = 1$ on $A$ and $g = P g$ on $A^{c}$ .

[A1]

The Axiom of Choice states that every family of nonempty sets has a choice function; it is assumed by the canonical-law and conditional-expectation/Markov suppliers used below. (The Axiom of Choice)

[F1]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ , so $T_{A} = 0$ at a start in $A$ . (Hitting, return, and visit times)

[F17]

The infimum of the empty set is $+ \infty$ . (Hitting, return, and visit times)

[F2]

$p (x, y) = K (x, {y})$ . (Transition matrices and n-step probabilities)

[F3]

For nonnegative $ϕ$ , $P ϕ (x) = \sum_{y : p (x, y) > 0} p (x, y) ϕ (y)$ , omitting zero transition weights. (Nonnegative kernel action and finite drift)

[F4]

A measure on a countable discrete space is the sum of its singleton weights; for $K (x, \cdot)$ those weights are $p (x, y)$ . (Every measure on a countable discrete space is its weighted sum of Dirac measures)

[F5]

For bounded product-measurable $H$ , $h_{H} (x) = E_{x} H (X_{0}, X_{1}, \dots)$ is measurable and $E [H (X_{n}, X_{n + 1}, \dots) ∣ F_{n}] = h_{H} (X_{n})$ almost surely. (Markov property for bounded future path functionals)

[F6]

For bounded measurable $q$ , $E [q (X_{n + 1}) ∣ F_{n}] = K q (X_{n})$ almost surely. (Bounded-function form of the Markov property)

[F7]

Under $P_{x} = P_{δ_{x}}$ , one has $X_{0} = x$ almost surely. (Initial distribution of a Markov chain)

[F8]

For nonnegative measurable $Z$ , $E [Z ∣ G]$ is characterized by its event integrals, and increasing nonnegative limits pass through conditional expectation almost surely. (Conditional monotone convergence)

[F9]

For bounded real $Y$ , $E [E (Y ∣ G)] = E [Y]$ . (Basic algebra and order properties of conditional expectation)

[F10]

Fatou's lemma gives $\int lim inf Y_{n} d P \leq {lim inf}_{n} \int Y_{n} d P$ for nonnegative measurable $Y_{n}$ . (Fatou's lemma)

[F11]

Increasing sequences of nonnegative measurable functions pass to the limit under the nonnegative integral. (Monotone convergence for the integral)

[F12]

A nonnegative simple measurable function has finite range. (Nonnegative simple measurable functions)

[F13]

The nonnegative Lebesgue integral is defined as the supremum of the simple integrals of nonnegative simple minorants. (The nonnegative Lebesgue integral)

[F14]

For $s = \sum_{j} c_{j} χ_{E_{j}}$ on disjoint measurable sets, its simple integral is $\sum_{j} c_{j} μ (E_{j})$ . (The integral of a nonnegative simple function)

[F15]

For every nonnegative simple measurable $s$ , its nonnegative Lebesgue integral equals its simple integral. (The nonnegative integral agrees with the simple integral on simple functions)

[F16]

A nonnegative extended series is the supremum of its increasing finite partial sums. (Series in the nonnegative extended real line)

Proof

technique · identify the countable kernel integral by finite-support truncations, extend the one-step Markov identity by conditional monotone convergence, and apply Fatou to the stopped candidate

1.1F2F3F4F11F12F13F14F15F16given

If $E$ is finite or countably infinite, fix an increasing finite exhaustion $E_{j} ↑ E$ (using a fixed enumeration when $E$ is infinite), and for $ϕ : E \to [0, + \infty]$ put $ϕ_{j} (y) = 1_{E_{j}} (y) (ϕ (y) \land j)$ . Each $ϕ_{j}$ is bounded and simple by [F12]; the nonnegative integral [F13], its simple-function agreement [F15], the simple integral formula [F14], the atomic weights [F4] and [F2] give $K ϕ_{j} (x) = \int_{E} ϕ_{j} (y) K (x, d y) = \sum_{y \in E_{j}} p (x, y) (ϕ (y) \land j)$ . As $j ↑ \infty$ , [F11] passes the integrals to $K ϕ (x)$ , while the finite sums increase to the support-restricted extended row sum by [F16] and [F3]; thus $K ϕ (x) = P ϕ (x)$ , with zero weights omitted and no $0 \cdot (+ \infty)$ formed.

1.2F1F7F17given

If $E = \emptyset$ , there is no state or initial law to check; if $A = \emptyset$ , then $T_{A} = \infty$ by [F1, F17], so $h = 0$ and $h \leq g$ follows from $g \geq 0$ ; if $A = E$ , every start has $T_{A} = 0$ and $h = 1$ , while every admissible $g$ is also $1$ ; in general, [F1, F7] give $h (x) = 1$ whenever $x \in A$ .

2.1F5F6F7F9step 1.1given

Define $H (ω) = 1_{{\exists n \geq 0 : ω_{n} \in A}}$ , a bounded product-measurable path functional. By [F5], $h$ is measurable and $E_{x} [H (X_{1}, X_{2}, \dots) ∣ F_{1}] = h (X_{1})$ ; for $x \in A^{c}$ , hitting $A$ is equivalent to the shifted path hitting it, so [F9] gives $h (x) = E_{x} h (X_{1})$ . The bounded one-step identity [F6], $X_{0} = x$ [F7], and expectation preservation [F9] identify this as $K h (x)$ ; step 1.1 then gives $K h (x) = P h (x)$ .

2.2F3F6F8step 1.1given

For any finite-valued nonnegative $g$ and each $n$ , use the finite-support truncations $g_{j}$ from step 1.1. The bounded one-step identity [F6] and step 1.1 give $E [g_{j} (X_{n + 1}) ∣ F_{n}] = K g_{j} (X_{n}) = P g_{j} (X_{n})$ ; since $g_{j} ↑ g$ , conditional monotone convergence [F8] and the row-sum limit in step 1.1 yield $E [g (X_{n + 1}) ∣ F_{n}] = P g (X_{n})$ almost surely, with its event-integral characterization available even when the conditional value is infinite.

3.1F1F7F8step 2.2given

Fix $x \in A^{c}$ , put $T = T_{A}$ , $Y_{n} = g (X_{n \land T})$ , and $S_{n} = {T > n} \in F_{n}$ by [F1]. If $E_{x} Y_{n} = g (x) < \infty$ , then on $S_{n}$ one has $X_{n} \in A^{c}$ and $P g (X_{n}) = g (X_{n})$ ; [F8] and step 2.2 give $E_{x} [1_{S_{n}} g (X_{n + 1})] = E_{x} [1_{S_{n}} P g (X_{n})] = E_{x} [1_{S_{n}} g (X_{n})]$ . On $S_{n}^{c}$ , $Y_{n + 1} = Y_{n} = 1$ , and on $S_{n}$ , $Y_{n} = g (X_{n})$ and $Y_{n + 1} = g (X_{n + 1})$ . Since $X_{0} = x$ by [F7], induction from $Y_{0} = g (x)$ proves $E_{x} Y_{n} = g (x)$ and integrability for every finite $n$ .

4.1A1F1F5F6F7F8F10step 1.1step 1.2step 3.1given∎

On ${T < \infty}$ , $Y_{n} = 1$ for every $n \geq T$ , while on ${T = \infty}$ all $Y_{n} \geq 0$ ; hence $1_{{T < \infty}} \leq {lim inf}_{n} Y_{n}$ . Fatou [F10] and step 3.1 give $h (x) \leq E_{x} {lim inf}_{n} Y_{n} \leq {lim inf}_{n} E_{x} Y_{n} = g (x)$ for $x \in A^{c}$ , and step 1.2 covers $x \in A$ , $A = \emptyset$ , and $A = E$ . A one-state absorbing chain is included by those same two set cases, and the finite-row argument in step 1.1 covers deterministic transitions. AC [A1] is used for the canonical laws and the conditional-expectation/Markov suppliers; the row exhaustion uses the supplied countability witness, with no extra choice. The result asserts minimality and no biconditional.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Geometric tail for hitting in a finite irreducible chain

Statement

Assume AC. Let $E$ be finite, let $p$ be an irreducible transition matrix on $E$ , and let $A \subseteq E$ be nonempty. There exist an integer $m \geq 1$ and $ε \in (0, 1)$ such that, for every $x \in E$ and $k \in N_{0}$ ,

$P_{x} (T_{A} > k m) \leq (1 - ε)^{k} .$

In particular, $E_{x} T_{A} < \infty$ for every $x \in E$ . Moreover, in any countable-state chain with transition matrix $p$ , if $C$ is a finite nonempty subset satisfying $\sum_{y \in C} p (x, y) = 1$ for each $x \in C$ and the restricted matrix on $C$ is irreducible, then every state of $C$ is recurrent for $p$ .

Facts & Assumptions

Given: AC. The geometric-tail clause assumes a finite state space $E$ , an irreducible transition matrix $p$ , and a nonempty target $A \subseteq E$ . The recurrence clause assumes a countable state space $E$ , a transition matrix $p$ , and a finite nonempty $C \subseteq E$ that is closed under $p$ and irreducible for the restricted matrix.

[F1]

Irreducibility means every pair of states communicates, with accessibility witnessed by some finite matrix power. Accessibility, communication, and irreducibility

[F2]

The transition probabilities are $p^{(n)} (x, y) = K^{n} (x, {y})$ , where $K$ is the one-step kernel. Transition matrices and n-step probabilities

[F3]

The hitting time is $T_{A} = \inf {n \geq 0 : X_{n} \in A}$ and is a stopping time; in particular ${T_{A} \leq n} = ⋃_{j = 0}^{n} {X_{j} \in A}$ . Hitting, return, and visit times

[F4]

Under the deterministic initial state $x$ , the chain law and expectation are denoted $P_{x}$ and $E_{x}$ . Initial distribution of a Markov chain

[F5]

For bounded measurable future path functionals $H$ , $E [H (X_{n}, X_{n + 1}, \dots) ∣ F_{n}] = h (X_{n})$ with $h (y) = E_{y} H (X_{0}, X_{1}, \dots)$ . Markov property for bounded future path functionals

[F6]

Finite-dimensional chain laws give $P_{x} (X_{n} = y) = K^{n} (x, {y})$ . Finite-dimensional laws of a Markov chain

[F7]

For a nonnegative random variable, expectation is the integral of its strict tail probabilities. Layer-cake formulas for random variables

[F8]

A state $x$ is recurrent when $P_{x} (T_{x}^{+} < \infty) = 1$ . Recurrent and transient states

[F9]

Full AC supplies a choice function for a family of nonempty sets; here it is assumed for the canonical chain-law and conditional-Markov interfaces in [F5] and [F6]. The Axiom of Choice

Proof

technique · direct

1.1F1F2F4F6given

Fix one $a \in A$ . For $x \notin A$ , irreducibility gives a nonempty set ${n \geq 1 : p^{(n)} (x, a) > 0}$ ; let $n_{x}$ be its least element. Set $n_{x} = 0$ for $x \in A$ . By [F2] and [F6], $P_{x} (T_{A} \leq n_{x}) > 0$ for every $x$ : it is $1$ on $A$ , and off $A$ the event ${X_{n_{x}} = a}$ has positive probability. Since $E$ is finite, $m : = \max (1, \max_{x \in E} n_{x})$ is finite and $q_{x} : = P_{x} (T_{A} \leq m) > 0$ for every $x$ . Thus $ε : = \min (1 / 2, \min_{x \in E} q_{x})$ lies in $(0, 1)$ and $q_{x} \geq ε$ uniformly. The witness lengths are least natural numbers, so this finite construction makes no choice-function assumption.

2.1F3F4F5step 1.1given

Define the bounded path functional $H_{m} (ω) = 1_{{ω_{j} \notin A for 0 \leq j \leq m}}$ and $r_{m} (x) : = E_{x} H_{m} (X_{0}, X_{1}, \dots) = P_{x} (T_{A} > m)$ . Step 1.1 gives $r_{m} (x) = 1 - q_{x} \leq 1 - ε$ for every $x$ . For $k \geq 0$ let $B_{k} = {T_{A} > k m} \in F_{k m}$ by [F3]. The event $B_{k + 1}$ is $B_{k}$ intersected with avoidance of $A$ during the next $m$ steps. Applying [F5] at time $k m$ and integrating over $B_{k}$ yields $P_{x} (B_{k + 1}) = E_{x} [1_{B_{k}} r_{m} (X_{k m})] \leq (1 - ε) P_{x} (B_{k})$ . This unconditional recursion also holds when a survival event has probability zero.

3.1F4F7step 2.1algebra

Since $P_{x} (B_{0}) \leq 1$ , induction in step 2.1 gives $P_{x} (T_{A} > k m) \leq (1 - ε)^{k}$ for every $k \geq 0$ . Since $T_{A}$ is integer-valued (with $+ \infty$ allowed), its strict tail is constant on each interval $[j, j + 1)$ ; integrating that tail in [F7] gives $E_{x} T_{A} = \sum_{j \geq 0} P_{x} (T_{A} > j)$ . Writing $j = k m + s$ with $0 \leq s < m$ and using monotonicity of the tail, $E_{x} T_{A} \leq m \sum_{k \geq 0} (1 - ε)^{k} = \frac{m}{ε} < \infty .$ This bound is uniform in $x$ .

4.1F2F4F5F6F7F8step 1.1step 2.1step 3.1given

The same estimate gives the scaffold's finite-class return consequence. For this clause, let $E$ be countable and let $C \subseteq E$ be finite and nonempty, satisfy $\sum_{z \in C} p (y, z) = 1$ for each $y \in C$ , and have an irreducible restricted matrix. For each $y \in C$ , closure and the finite-dimensional iterated law [F6] imply $P_{y} (X_{0}, \dots, X_{n} \in C) = 1$ for every $n$ and identify the joint law of $(X_{0}, \dots, X_{n})$ with that of the restricted matrix on $C$ . In particular, each event ${T_{{a}} > n}$ has the same probability under the ambient and restricted chains; summing these integer tails by [F7] shows their hitting-time expectations agree. Fix $a \in C$ and put $M = \max_{y \in C} E_{y} T_{{a}} < \infty$ by applying the argument of steps 1.1–3.1 to this finite restricted chain. For every $n \geq 0$ , the bounded future-path Markov identity at time $1$ , applied to avoidance of $a$ in the next $n + 1$ coordinates, gives $P_{a} (T_{a}^{+} > n + 1) = \sum_{y \in C} p (a, y) P_{y} (T_{{a}} > n) .$ Summing this identity over $n \geq 0$ and using the same integer-valued tail identity from [F7] as in step 3.1 gives $E_{a} T_{a}^{+} = 1 + \sum_{y \in C} p (a, y) E_{y} T_{{a}} \leq 1 + M < \infty$ . Hence $P_{a} (T_{a}^{+} < \infty) = 1$ , so [F8] makes $a$ recurrent. Since $a$ was arbitrary, every state of $C$ is recurrent.

5.1F3F5F6step 1.1step 2.1step 3.1step 4.1F9given∎

The nonempty-target hypothesis is necessary: for $A = \emptyset$ , $T_{A} = \infty$ and the finite-mean conclusion fails. If $A = E$ or the starting state lies in $A$ , then $T_{A} = 0$ and the tail bound holds immediately; for a one-state chain these are the only target cases. Deterministic and other degenerate rows are covered by the same positive accessibility witnesses and the uniform block estimate. At $k = 0$ the asserted bound is just $P_{x} (T_{A} > 0) \leq 1$ . AC is used only through [F5] and [F6]; all path-length witnesses above are least natural numbers. The theorem is not an iff statement.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Bounded Dirichlet problem for hitting probabilities

Statement

Assume AC (The Axiom of Choice). Let $X$ be a Markov chain with transition kernel $K$ on an at most countable state space $E$ and transition matrix $p (x, y) = K (x, {y})$ . If $E = \emptyset$ , the assertion is vacuous. For $A \subseteq E$ , suppose $P_{x} (T_{A} < \infty) = 1$ for every $x \in E$ . For bounded real boundary data $f : A \to R$ , define the payoff before any random-time evaluation by $F_{A} = {\begin{cases} f (X_{T_{A}}), & T_{A} < \infty, \\ 0, & T_{A} = \infty, \end{cases} u (x) : = E_{x} F_{A} .$ Then $u$ is the unique bounded $v : E \to R$ satisfying $v = f on A, v = P v on A^{c},$ where for bounded real $q$ , $P q (x) : = \sum_{y \in E} p (x, y) q (y)$ is absolutely convergent. In particular, the almost-sure hitting hypothesis holds when $E$ is finite, $p$ is irreducible, and $A$ is nonempty. For $f \equiv 1$ on $A$ , $u (x) = P_{x} (T_{A} < \infty)$ .

Facts & Assumptions

Given: AC; a Markov chain on an at most countable discrete state space with transition matrix $p$ ; a set $A \subseteq E$ ; bounded real data $f$ on $A$ ; and $P_{x} (T_{A} < \infty) = 1$ for every deterministic start $x$ .

[A1]

AC is the axiom that every family of nonempty sets has a choice function; the canonical chain-law and conditional-expectation Markov interfaces below assume it. (The Axiom of Choice)

[F1]

The transition probabilities satisfy $p (x, y) = K (x, {y})$ and every kernel row is a probability measure; in particular its singleton weights sum to one. (Transition matrices and n-step probabilities)

[F2]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ , with ${T_{A} \leq n} = ⋃_{j = 0}^{n} {X_{j} \in A}$ ; hence $T_{A}$ is a stopping time and $X_{n \land T_{A}}$ is defined for finite $n$ . (Hitting, return, and visit times)

[F3]

Under the deterministic start, $P_{x} = P_{δ_{x}}$ , $E_{x}$ is its expectation, and $X_{0} = x$ almost surely. (Initial distribution of a Markov chain)

[F4]

For bounded measurable $q$ , $E [q (X_{n + 1}) ∣ F_{n}] = K q (X_{n}) a.s., K q (x) : = \int_{E} q (y) K (x, d y) .$ (Bounded-function form of the Markov property)

[F5]

For bounded product-measurable path functionals $H$ , $h (x) : = E_{x} H (X_{0}, X_{1}, \dots)$ is measurable and $E [H (X_{n}, X_{n + 1}, \dots) ∣ F_{n}] = h (X_{n}) a.s.$ (Markov property for bounded future path functionals)

[F6]

On bounded real functions, $P q (x) = \sum_{y} p (x, y) q (y)$ ; the series is absolutely convergent since $\sum_{y} p (x, y) = 1$ . (Discrete generator of a countable-state transition matrix)

[F7]

A nonnegative function with finite range is simple; its simple integral is the finite sum of its values times the measures of its disjoint level sets, and this equals its nonnegative Lebesgue integral. (Nonnegative simple measurable functions, The integral of a nonnegative simple function, The nonnegative integral agrees with the simple integral on simple functions)

[F8]

For an integrable real $q$ , its integral is $\int q d μ = \int q^{+} d μ - \int q^{-} d μ$ . (Integrable real and complex functions, and their integrals)

[F9]

Dominated convergence passes limits through integrals when the functions converge almost everywhere and are bounded by one integrable majorant. (Dominated convergence)

[F10]

Conditional expectation preserves order and constants and satisfies $E (E [Y ∣ G]) = E Y$ for integrable real $Y$ . (Basic algebra and order properties of conditional expectation)

[F11]

If $E$ is finite, $p$ is irreducible, and $A$ is nonempty, there are $m \geq 1$ and $ε \in (0, 1)$ such that $P_{x} (T_{A} > k m) \leq (1 - ε)^{k}$ for every $x$ and $k \geq 0$ . (Geometric tail for hitting in a finite irreducible chain)

Source scope

LPW Proposition 9.1 and its proof [S1] give context for the boundary-payoff construction and the first-step decomposition. Its uniqueness argument uses a global maximum, and its displayed assumptions do not supply the almost-sure boundary-hit and bounded-data hypotheses used here; that argument is not invoked for the countable bounded result. Roch Theorem 24.4 [S2] proves the first-step equations for bounded nonnegative exit data on a proper domain. The bounded real-data equations and the uniqueness statement below are derived locally under the stated almost-sure hitting assumption.

Proof

Proof technique: establish the bounded row-integral identity by finite support truncations, derive the boundary and harmonic equations from bounded Markov identities, and identify every bounded solution by a stopped martingale and dominated convergence.

1.1F1F6F7F8F9given

Fix $x \in E$ and a bounded real $q : E \to R$ , with $∣ q ∣ \leq M$ . Take an increasing sequence of finite sets $E_{j} ↑ E$ (eventually $E_{j} = E$ if $E$ is finite) and put $q_{j} = q 1_{E_{j}}$ . The positive and negative parts of $q_{j}$ are finite-range nonnegative simple functions. By [F1], [F7] and [F8], $K q_{j} (x) = \int_{E} q_{j} d K (x, \cdot) = \sum_{y \in E_{j}} p (x, y) q (y) .$ The constant $M$ is integrable for the probability measure $K (x, \cdot)$ , so [F9] gives $K q_{j} (x) \to K q (x)$ . Also $\sum_{y} p (x, y) ∣ q (y) ∣ \leq M \sum_{y} p (x, y) = M$ by [F1], so the finite sums converge to the absolutely convergent row sum $P q (x)$ from [F6]. Therefore $K q (x) = P q (x) .$ This identity holds for every bounded real $q$ and each row; no positivity of the individual entries beyond being transition weights is required.

2.1F2F3F4F5F10step 1.1given

Choose $M < \infty$ with $∣ f (a) ∣ \leq M$ on $A$ , extend $f$ by zero off $A$ , and define $H (ω)$ to be $f (ω_{T_{A} (ω)})$ when the first-hit time of $A$ is finite, and zero otherwise. Each event that the first hit is at time $n$ is cylinder-measurable; $H$ is the pointwise limit of its finite sums over these disjoint events, so it is product-measurable and $∣ H ∣ \leq M$ . By [F5], $h (x) : = E_{x} H (X_{0}, X_{1}, \dots)$ is measurable; [F10] gives $∣ h (x) ∣ \leq M$ . The payoff in the Statement equals $H (X_{0}, X_{1}, \dots)$ pathwise, including its zero value on nonhit paths, so $h = u$ . If $x \in A$ , [F2] and [F3] give $T_{A} = 0$ and $h (x) = f (x)$ . If $x \notin A$ , deleting the first coordinate does not change $H$ , including when the path never hits $A$ . Thus [F5] at time $1$ and [F10] give $h (x) = E_{x} H (X_{1}, X_{2}, \dots) = E_{x} h (X_{1}) .$ Apply [F4] at time $0$ to the bounded function $h$ , use [F3] and [F10] to take expectations, and then use step 1.1 to obtain $u (x) = h (x) = K h (x) = P h (x) = P u (x) .$ This proves existence and both equations.

2.2F2F3F4F9F10step 1.1given

Let $v : E \to R$ be any bounded solution of the stated boundary and harmonic equations, fix $x \in E$ , set $T = T_{A}$ , and define $Y_{n} = v (X_{n \land T})$ . By [F2] this is adapted, and it is bounded by $∥ v ∥_{\infty}$ . On ${T \leq n}$ , $Y_{n + 1} = Y_{n}$ ; on ${T > n}$ , $X_{n} \in A^{c}$ and $Y_{n + 1} = v (X_{n + 1})$ . The one-step identity [F4], the row identity in step 1.1, and $v = P v$ on $A^{c}$ imply $E_{x} [Y_{n + 1} ∣ F_{n}] = Y_{n} a.s.$ Consequently $Y_{n}$ is a bounded martingale and [F3], [F10] give $E_{x} Y_{n} = v (x)$ for every $n$ . The hypothesis makes $T < \infty$ $P_{x}$ -almost surely, so eventually $Y_{n} = v (X_{T}) = f (X_{T}) = F_{A}$ almost surely. Since $∣ Y_{n} ∣ \leq ∥ v ∥_{\infty}$ is an integrable majorant, [F9] yields $v (x) = \lim_{n} E_{x} Y_{n} = E_{x} F_{A} = u (x) .$ As $x$ was arbitrary, every bounded solution equals $u$ ; this proves uniqueness.

3.1F3F11step 2.1step 2.2given

If $E$ is finite, $p$ is irreducible and $A \neq \emptyset$ , [F11] gives $P_{x} (T_{A} = \infty) \leq P_{x} (T_{A} > k m) \leq (1 - ε)^{k} ⟶ 0$ , so the almost-sure hitting hypothesis holds for every start. The preceding steps give the finite irreducible instance. When $f \equiv 1$ on $A$ , the pathwise payoff is $1_{{T_{A} < \infty}}$ , hence its expectation is the hitting probability; under the theorem's hypothesis it equals $1$ .

4.1A1F1F2F3F4F5F6F10F11step 1.1step 2.1step 2.2step 3.1given∎

If $E = \emptyset$ , there is no state or deterministic-start law and all assertions are vacuous. If $E \neq \emptyset$ and $A = \emptyset$ , then $T_{A} = \infty$ everywhere, contradicting the hypothesis; thus every nonvacuous instance has $A \neq \emptyset$ . If $A = E$ , then $T_{A} = 0$ , the boundary equation determines $u$ and every solution directly. For a one-state chain these are the only admissible cases. If $f = 0$ , then $H = u = 0$ and the uniqueness proof still applies. Deterministic rows are covered by the row identity and the same martingale calculation; a finite irreducible deterministic chain reaches every nonempty $A$ by the finite-tail argument. The endpoint $T_{A} = 0$ is handled in step 2.1, while a first hit at time $1$ is included in the shifted-path and stopped-process identities in steps 2.1 and 2.2. AC [A1] is used through the canonical chain laws and conditional-expectation Markov identities [F4], [F5] and [F10]; choosing one enumeration of a countable $E$ adds no family-wise choice. The equations and uniqueness claim are not an iff statement.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Period of a state

Definition

For $x \in E$ , let

$R_{x} : = {n \in N : n \geq 1 and p^{(n)} (x, x) > 0} .$

If $R_{x} = \emptyset$ , set $d (x) : = 0$ . If $R_{x} \neq \emptyset$ , define $d (x)$ to be the greatest positive integer dividing every element of $R_{x}$ (the gcd convention of Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ). This greatest divisor exists: fix one $t \in R_{x}$ ; every common positive divisor of $R_{x}$ is a divisor of $t$ , so the set of such divisors is a nonempty finite subset of the positive divisors of $t$ , and therefore has a greatest element. The set being maximized is intrinsic to $R_{x}$ , so the result is independent of the auxiliary $t$ . Only positive return times enter; $p^{(0)} (x, x) = 1$ does not force $d (x) = 1$ .

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Period is constant on communicating classes

Statement

If $x$ and $y$ communicate, then $d (x) = d (y)$ , including $x = y$ and the convention $d (x) = 0$ when no positive return exists.

Facts & Assumptions

Given: A countable transition matrix $p$ and communicating states $x, y$ .

[F1]

Communication means $x \to y$ and $y \to x$ , where accessibility is witnessed by some $n \in N_{0}$ with $p^{(n)} (x, y) > 0$ . Accessibility, communication, and irreducibility

[F2]

$R_{x} = {n \geq 1 : p^{(n)} (x, x) > 0}$ ; $d (x) = 0$ if $R_{x} = \emptyset$ , and otherwise $d (x)$ is the greatest positive integer dividing every element of $R_{x}$ . Period of a state

[F3]

For $m, n \geq 0$ , $p^{(m + n)} (u, v) = \sum_{z \in E} p^{(m)} (u, z) p^{(n)} (z, v)$ . Matrix Chapman–Kolmogorov equations

[F4]

$p^{(0)} (u, v) = 1_{{u = v}}$ . Transition matrices and n-step probabilities

Proof

technique · direct

1.1F1F3F4given

If $x = y$ , the conclusion is the identity $d (x) = d (x)$ , whether or not $R_{x}$ is empty. Suppose $x \neq y$ . By [F1], choose route lengths $r, s \in N_{0}$ with $p^{(r)} (x, y) > 0$ and $p^{(s)} (y, x) > 0$ . By [F4], neither length is zero, so $r, s \geq 1$ . Twice applying [F3] and retaining the route terms gives $p^{(r + s)} (x, x) \geq p^{(r)} (x, y) p^{(s)} (y, x) > 0$ and $p^{(r + s)} (y, y) \geq p^{(s)} (y, x) p^{(r)} (x, y) > 0$ . Thus both return-time sets are nonempty and both periods are positive.

2.1F2F3step 1.1givenalgebra

Fix any $t \in R_{x}$ . By [F3], the route from $y$ to $x$ , a $t$ -step return at $x$ , and the route from $x$ to $y$ give $p^{(s + t + r)} (y, y) \geq p^{(s)} (y, x) p^{(t)} (x, x) p^{(r)} (x, y) > 0$ . Step 1.1 also shows $r + s \in R_{y}$ . Hence the positive integer $d (y)$ divides both $r + s$ and $r + t + s$ , so it divides their difference $t$ . As this holds for every $t \in R_{x}$ , $d (y)$ is a common positive divisor of $R_{x}$ and therefore $d (y) \leq d (x)$ by [F2].

3.1F1F2F3step 1.1step 2.1givenalgebra

Interchanging $x$ and $y$ in step 2.1 shows that every $t \in R_{y}$ is divisible by $d (x)$ ; hence $d (x)$ is a common positive divisor of $R_{y}$ and $d (x) \leq d (y)$ . Together with step 2.1 this proves equality for distinct communicating states. The case $x = y$ was settled in step 1.1.

4.1F1F2F4step 1.1step 2.1step 3.1given∎

If $E = \emptyset$ , there are no communicating states and the assertion is vacuous. If $x = y$ and there is no positive return, both sides equal the stipulated zero; if $x \neq y$ communicate, step 1.1 proves positive returns exist, so neither period is zero. One-state, deterministic, and absorbing cases are covered by the same alternatives. The accessibility witnesses are positive for distinct states because [F4] makes a zero-step transition possible only from a state to itself. The proof chooses routes only for this fixed pair, so it uses no choice function. This one-way equality statement is not an iff.

DefinitionDefinition: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-09-30Open item page →

Aperiodic irreducible chain

Definition

Let $p$ be an irreducible transition matrix on a nonempty countable state space $E$ . The periods $d (x)$ are independent of $x$ by Period is constant on communicating classes, and the verification below shows their common value is positive. Define the period of the chain by $per (p) : = d (x)$ for any $x \in E$ . The chain is aperiodic when $per (p) = 1$ .

Facts & Assumptions

Given: A nonempty countable state space $E$ and an irreducible transition matrix $p$ on $E$ .

[F1]

Every transition-matrix power has a stochastic row: $\sum_{y \in E} p^{(n)} (x, y) = 1$ . (Transition matrices and n-step probabilities)

[F2]

The zero-step matrix is $p^{(0)} (x, y) = 1_{{x = y}}$ . (Transition matrices and n-step probabilities)

[F3]

Irreducibility means every pair of states communicates. (Accessibility, communication, and irreducibility)

[F4]

Accessibility is witnessed by a finite $n \in N_{0}$ with $p^{(n)} (x, y) > 0$ . (Accessibility, communication, and irreducibility)

[F5]

The positive return set is $R_{x} = {n \geq 1 : p^{(n)} (x, x) > 0}$ ; if it is nonempty, $d (x)$ is its greatest common positive divisor, while $d (x) = 0$ if $R_{x} = \emptyset$ . (Period of a state)

[F6]

For $r, s \geq 0$ , $p^{(r + s)} (x, z) = \sum_{w \in E} p^{(r)} (x, w) p^{(s)} (w, z)$ . (Matrix Chapman–Kolmogorov equations)

[F7]

Communicating states have equal periods, including the convention that a state with no positive return has period zero. (Period is constant on communicating classes)

Verification

technique · verify that the common state period exists and is positive, then use it to define aperiodicity

1.1F1F2F3F4F5F6given

For each $x \in E$ , $R_{x}$ is nonempty. If $E = {x}$ , [F1] gives $p (x, x) = 1$ , so $p^{(1)} (x, x) > 0$ . If $E$ has at least two states, fix an arbitrary $x$ and take $y \neq x$ ; by [F3]–[F4], there are $r, s \in N_{0}$ with $p^{(r)} (x, y) > 0$ and $p^{(s)} (y, x) > 0$ . Since $x \neq y$ , [F2] forces $r, s \geq 1$ , and [F6] gives $p^{(r + s)} (x, x) \geq p^{(r)} (x, y) p^{(s)} (y, x) > 0$ . Thus $d (x)$ is a positive integer by [F5] in either case.

2.1F3F5F7step 1.1given

For any $x, y \in E$ , irreducibility [F3] makes them communicate, so [F7] gives $d (x) = d (y)$ . Step 1.1 shows this common value is positive. It is therefore independent of the chosen state and defines $per (p)$ ; declaring aperiodicity by the condition $per (p) = 1$ is well-defined.

3.1F1F2F3F5F6F7step 1.1step 2.1given∎

The empty state space is excluded in the definition because no state period could be chosen as a common value. For a one-state chain, step 1.1 gives period one and hence aperiodicity. On a deterministic cycle of length $k \geq 1$ , label the states $x_{0}, \dots, x_{k - 1}$ and let the transition from $x_{j}$ go to $x_{(j + 1) m o d k}$ with probability one. Iteration gives $p^{(n)} (x_{j}, x_{j}) = 1$ when $k$ divides $n$ and zero otherwise, so positive return times are precisely the positive multiples of $k$ and the period is $k$ ; a one-state absorbing chain is the case $k = 1$ . The return set begins at $n = 1$ , so $p^{(0)} (x, x) = 1$ does not make every chain aperiodic. The proof uses only fixed-pair routes and finite row sums, with no choice function or AC. This is a definition, not an iff theorem.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Simple symmetric walk on the integer lattice

Definition

For an integer $d \geq 1$ , the simple symmetric nearest-neighbor transition matrix on $Z^{d}$ is

$p (z, z + e_{j}) = p (z, z - e_{j}) = \frac{1}{2 d} (j = 1, \dots, d),$

with every other entry zero. Here $e_{j}$ is the $j$ th standard basis vector. The $2 d$ neighbors $z \pm e_{j}$ are distinct when $d \geq 1$ , so each row sums to $2 d / (2 d) = 1$ ; this is a transition matrix in the sense of Transition matrices and n-step probabilities. The definition uses no Choice.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

One-dimensional simple symmetric walk is recurrent

Statement

Assume AC. Identify $Z$ with $Z^{1}$ and define, for $A \subseteq Z$ , $K (z, A) : = \frac{1}{2} δ_{z + 1} (A) + \frac{1}{2} δ_{z - 1} (A) .$ For each fixed $z \in Z$ , use the canonical chain law $P_{z}$ with initial measure $δ_{z}$ and kernel $K$ . This is the simple symmetric nearest-neighbor walk in dimension one (Simple symmetric walk on the integer lattice). With $T_{z}^{+} : = \inf {n \geq 1 : X_{n} = z}$ , every state is recurrent: $P_{z} (T_{z}^{+} < \infty) = 1 (z \in Z) .$

Facts & Assumptions

Given: AC, the state space $Z$ with its full power-set sigma-algebra, the one-dimensional simple symmetric walk, and a fixed start $z$ .

[A1]

AC is assumed by the canonical path-law and finite-dimensional-law suppliers used here. (The Axiom of Choice)

[F1]

In dimension one, the simple symmetric transition row has mass $1 / 2$ at each of the two distinct neighbors $z - 1, z + 1$ , and zero elsewhere. (Simple symmetric walk on the integer lattice)

[F2]

For each point $w$ , $δ_{w}$ is a probability measure. (A Dirac set function is a probability measure)

[F3]

A finite nonnegative weighted sum of measures is a measure. (Nonnegative scalar multiples and countable weighted sums of measures are measures)

[F4]

A probability kernel is a measure in its target variable for each source point, has total mass one, and is measurable in the source point for each measurable target set. (Measure kernel and probability kernel)

[F5]

A function is measurable when the preimage of each measurable target set is measurable in the source space. (A measurable function between measurable spaces)

[F6]

Under AC, the path space carries the canonical law for a specified probability initial measure and probability kernel. (Canonical Markov chain on path space)

[F7]

With initial measure $δ_{z}$ , the fixed-start notation is $P_{z} = P_{δ_{z}}$ and $X_{0} = z$ almost surely. (Initial distribution of a Markov chain)

[F8]

Under the finite-dimensional law, the probability of a finite cylinder is the iterated product of its initial and transition probabilities. (Finite-dimensional laws of a Markov chain)

[F9]

The matrix entries are $p (z, w) = K (z, {w})$ and $p^{(n)} (z, w) = K^{n} (z, {w})$ , with $p^{(0)} (z, w) = 1_{{z = w}}$ . (Transition matrices and n-step probabilities)

[F10]

$(\binom{m}{k})$ is the number of $k$ -element subsets of an $m$ -element set. (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ )

[F11]

For a fixed state, recurrence is equivalent to divergence of its return Green series: $z$ is recurrent iff $\sum_{n \geq 0} p^{(n)} (z, z) = \infty$ . (Equivalent criteria for recurrence and transience)

[F12]

Recurrence means that the positive-time return probability is one. (Recurrent and transient states)

[F13]

$T_{z}^{+} = \inf {n \geq 1 : X_{n} = z}$ is the strictly positive return time. (Hitting, return, and visit times)

[F14]

For $n \geq 1$ , $4^{- n} (\binom{2 n}{n}) \sim (π n)^{- 1 / 2}$ . (The central binomial coefficient is asymptotic to 4^n divided by the square root of pi n)

[F15]

A set in bijection with $N$ is countably infinite and hence at most countable. (Finite, countably infinite, countable, uncountable)

Proof

technique · count the finite return words, use the central-binomial asymptotic to make their Green series diverge, and apply the statewise recurrence criterion at each fixed start

1.1F15given

Define $e : N \to Z$ by $e (0) = 0$ , $e (2 k - 1) = k$ , and $e (2 k) = - k$ for $k \geq 1$ . Every integer occurs exactly once, so this is a bijection and $Z$ is countably infinite, hence at most countable as required by the chain-law and recurrence suppliers.

1.2F1F2F3F4F5given

For each fixed $z$ , the two Dirac measures in the displayed definition of $K (z, \cdot)$ are probability measures [F2]; their weighted sum is a measure by [F3], and its total mass is $1 / 2 + 1 / 2 = 1$ . For each fixed $A \subseteq Z$ , the map $z \mapsto K (z, A)$ is measurable because every subset of the discrete source $Z$ is measurable [F5]. Thus [F4] makes $K$ a probability kernel. Its singleton entries agree with [F1], so this is exactly the d=1 simple symmetric walk kernel.

1.3A1F6F7F8F9given

Under AC [A1], [F6] supplies the canonical law with initial measure $δ_{z}$ for each fixed $z$ ; [F7] names it $P_{z}$ , and [F8] gives the probabilities of its finite path cylinders. The transition matrix of this chain is the matrix in [F9].

1.4F1F7F8F9F10given

Fix $z \in Z$ and $n \geq 0$ . A sign word $(ε_{1}, \dots, ε_{2 n}) \in {- 1, 1}^{2 n}$ determines the path $X_{j} = z + \sum_{i = 1}^{j} ε_{i}$ for $0 \leq j \leq 2 n$ . Each such cylinder has probability $2^{- 2 n}$ by [F1], [F7], and [F8]. Distinct sign words give disjoint cylinders, and their endpoint equals $z$ exactly when the word has equally many $+ 1$ and $- 1$ entries. By [F10] there are $(\binom{2 n}{n})$ such words. Consequently $p^{(2 n)} (z, z) = P_{z} (X_{2 n} = z) = 4^{- n} (\binom{2 n}{n}) .$ For $n = 0$ , this says $p^{(0)} (z, z) = 1$ , as required by [F9].

1.5F1F8F9given

A sum of an odd number of $\pm 1$ increments is odd and cannot be zero. Thus $p^{(2 n + 1)} (z, z) = 0$ for every $n \geq 0$ .

2.1F14step 1.4given

Put $a_{n} : = p^{(2 n)} (z, z)$ . By step 1.4 and [F14], $\sqrt{π n} a_{n} \to 1$ as $n \to \infty$ . Hence there is $N \geq 1$ such that for $n \geq N$ , $a_{n} \geq \frac{1}{2 \sqrt{π} \sqrt{n}} .$

3.1step 1.5step 2.1given

For each integer $m \geq 1$ , there are $2 m + 1$ integers in $[m^{2}, (m + 1)^{2})$ , and for each one $n^{- 1 / 2} \geq (m + 1)^{- 1}$ . Therefore $\sum_{n = m^{2}}^{(m + 1)^{2} - 1} n^{- 1 / 2} \geq \frac{2 m + 1}{m + 1} > 1.$ Infinitely many such disjoint blocks show $\sum_{n \geq N} n^{- 1 / 2} = \infty$ ; [step 2.1] then gives $\sum_{n \geq 0} p^{(2 n)} (z, z) = \infty$ . The odd-time terms are zero by step 1.5, so the full Green series $\sum_{n \geq 0} p^{(n)} (z, z)$ diverges. The initial $n = 0$ term is $1$ and is included.

4.1F11F12F13step 3.1given

By [F11], divergence of the Green series implies that this fixed state $z$ is recurrent; by [F12] and [F13], this means exactly $P_{z} (T_{z}^{+} < \infty) = 1$ . Since $z$ was arbitrary, the conclusion holds for every state of $Z$ . This uses only the forward implication of [F11], and no converse to the corollary is asserted.

5.1A1F1F6F8F9F11F12F13step 1.1step 1.3step 1.5step 3.1step 4.1given∎

The state space is fixed as $Z$ , which contains $0$ and infinitely many integers, so the empty-space and one-state cases are inapplicable. Every row has two distinct positive transitions, so the walk is neither absorbing nor deterministic. Zero return weights occur at every odd time by step 1.5; the time-zero Green term is $1$ but is not a positive-time return [F12, F13]. AC [A1] is used exactly for the canonical path law and the stated finite-dimensional and recurrence suppliers. The enumeration of $Z$ , the finite path count, and the square-block divergence require no choice. The only iff input is [F11]; the proof uses its divergence-to-recurrence direction, so the reverse direction is not part of the claim.

Source notes

Durrett, Probability: Theory and Examples, 5th ed., §5.4, Theorem 5.4.3 and complete proof (printed pp. 288–289/PDF pp. 295–296, official parser lines 19430–19460) gives the general return-series criterion for random walks. The d=1 part of Theorem 5.4.4 (printed p. 289/PDF p. 296, lines 19461–19469) uses odd-time parity and the central-order return probability to conclude recurrence. Its asymptotic is cited there from Theorem 3.1.3; here the published central-binomial asymptotic is used and the divergence is proved by square blocks. Durrett's source proof supports the result but does not replace the local kernel construction, finite-word calculation, or statewise Green-series argument above.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Two-dimensional simple symmetric walk is recurrent

Statement

Assume the Axiom of Choice (The Axiom of Choice). Put $E = Z^{2}$ with its full power-set sigma-algebra. For $z \in E$ and $A \subseteq E$ , define $K (z, A) : = \frac{1}{4} (δ_{z + e_{1}} (A) + δ_{z - e_{1}} (A) + δ_{z + e_{2}} (A) + δ_{z - e_{2}} (A)),$ where $e_{1} = (1, 0)$ and $e_{2} = (0, 1)$ . For each fixed $z$ , let $P_{z}$ be the canonical path-space law with initial measure $δ_{z}$ and kernel $K$ , and let $p$ be its transition matrix. Then every state is recurrent: $P_{z} (T_{z}^{+} < \infty) = 1 (z \in Z^{2}),$ where $T_{z}^{+} : = \inf {n \geq 1 : X_{n} = z}$ .

Facts & Assumptions

Given: AC, $E = Z^{2}$ , its full power-set sigma-algebra, and the four-neighbor kernel $K$ in the Statement.

[A1]

AC is the axiom that every family of nonempty sets has a choice function; the canonical-chain construction and recurrence criterion below explicitly assume it. (The Axiom of Choice)

[F1]

$Z$ is the quotient $(N \times N) / \sim$ and its quotient map is onto. (The integers as equivalence classes of pairs of naturals)

[F2]

$N \times N \approx N$ ; a nonempty set is at most countable when a surjection from $N$ onto it exists; bijections invert and surjections compose. ( $N \times N \approx N$ , Equinumerous sets, $A \approx B$ and $A ⪯ B$ , A nonempty set is at most countable iff it is a surjective image of $N$ , Injection, surjection, bijection, Finite, countably infinite, countable, uncountable)

[F3]

The product of two at-most-countable sets is at most countable. (A product of two at most countable sets is at most countable)

[F4]

A Dirac measure is a probability measure, and a finite nonnegative weighted sum of measures is a measure. (The Dirac set function at a point, A Dirac set function is a probability measure, Nonnegative scalar multiples and countable weighted sums of measures are measures)

[F5]

A probability kernel is pointwise a measure of total mass one and is measurable in its source variable for each measurable target set. The measurability test is preimages of Borel sets. (Measure kernel and probability kernel, A measurable function between measurable spaces)

[F6]

For $d \geq 1$ , the simple symmetric lattice matrix has mass $1 / (2 d)$ at each distinct neighbor $z \pm e_{j}$ and zero elsewhere. (Simple symmetric walk on the integer lattice)

[F7]

Under AC, the canonical path space carries a Markov chain with specified initial probability measure and probability kernel; for initial $δ_{z}$ , the notation is $P_{z}$ . (Canonical Markov chain on path space, Initial distribution of a Markov chain)

[F8]

The transition entries and their iterates are $p (x, y) = K (x, {y})$ and $p^{(n)} (x, y) = K^{n} (x, {y})$ , with the identity at $n = 0$ . (Transition matrices and n-step probabilities)

[F9]

For a countable transition matrix, $p^{(m + n)} (x, y) = \sum_{w} p^{(m)} (x, w) p^{(n)} (w, y)$ . (Matrix Chapman–Kolmogorov equations)

[F10]

$(\binom{N}{k})$ counts $k$ -element subsets of an $N$ -element set, and for $k \leq N$ its real value is $N! / (k! (N - k)!)$ ; Vandermonde gives $\sum_{m = 0}^{n} (\binom{n}{m}) (\binom{n}{n - m}) = (\binom{2 n}{n})$ . (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ , Vandermonde's identity $(\binom{m + n}{k}) = \sum_{i < k + 1} (\binom{m}{i}) (\binom{n}{k - i})$ )

[F11]

For $n \geq 1$ , $\sqrt{π n} (\binom{2 n}{n}) / 4^{n} \to 1$ , and $π > 0$ . (The central binomial coefficient is asymptotic to 4^n divided by the square root of pi n, Pi as twice the smallest positive zero of cosine)

[F12]

The harmonic series $\sum_{n \geq 1} 1 / n$ diverges, and positive sequences whose ratio converges to a finite positive number have the same series behavior. (For rational $p > 0$ , $\sum 1 / k^{p}$ converges iff $p > 1$ , For $a_{k}, b_{k} > 0$ with $a_{k} / b_{k} \to L$ : if $L \in (0, \infty)$ the two series share their behaviour, while $L = 0$ and $L = \infty$ give one implication each)

[F13]

A nonnegative series is the supremum of its finite partial sums; a state is recurrent exactly when its positive-time return probability is one, and the return time starts at $n \geq 1$ . (Series in the nonnegative extended real line, Recurrent and transient states, Hitting, return, and visit times)

[F14]

Under AC, for a fixed state $z$ of a countable-state chain, $z is recurrent ⟺ \sum_{n = 0}^{\infty} p^{(n)} (z, z) = \infty .$ (Equivalent criteria for recurrence and transience)

Proof

Proof technique: count finite move words using the matrix Chapman–Kolmogorov equations, then apply the statewise Green-series criterion.

1.1F1F2F3given

The quotient map $q : N \times N \to Z$ from [F1] is onto. By [F2] there is a bijection $b : N \times N \to N$ ; for each $n$ , injectivity and surjectivity give a unique pair $u$ with $b (u) = n$ , so assigning that unique pair defines a map $b^{- 1} : N \to N \times N$ . The composite $q \circ b^{- 1}$ is onto: for $z \in Z$ , choose a pair $u$ with $q (u) = z$ , and then $q (b^{- 1} (b (u))) = z$ . Hence [F2] makes $Z$ at most countable, and [F3] makes $E = Z \times Z$ at most countable. It is nonempty, since $(0, 0) \in E$ .

1.2F4F5F6given

For each $z$ , the four summands in $K (z, \cdot)$ are probability measures by [F4]; their weighted sum is a measure, has total mass $4 \cdot \frac{1}{4} = 1$ , and is measurable in $z$ because the source sigma-algebra is the full power set [F5]. Hence $K$ is a probability kernel. Its four neighbors are distinct and its singleton entries are $1 / 4$ at those neighbors and zero elsewhere, agreeing with the $d = 2$ matrix in [F6].

2.1A1F7F8F14step 1.1

For each fixed $z$ , AC [A1] and [F7] therefore give the canonical chain law $P_{z}$ with $X_{0} = z$ and kernel $K$ ; [F8] identifies its transition matrix and iterates. This verifies the chain hypotheses for [F14].

2.2F6F8F9step 1.2

Let $S = {e_{1}, - e_{1}, e_{2}, - e_{2}}$ . For any $x, y \in E$ and $n \geq 0$ , $p^{(n)} (x, y) = 4^{- n}$ times the number of words $(s_{1}, \dots, s_{n}) \in S^{n}$ with $x + s_{1} + \dots + s_{n} = y$ . At $n = 0$ this is the identity-matrix statement [F8]. If it holds at $n$ , [F9] writes $p^{(n + 1)} (x, y) = \sum_{w} p^{(n)} (x, w) p (w, y)$ . By [F6] only the four possible predecessors $w = y - s$ , $s \in S$ , contribute; grouping $n$ -step words by their endpoint $w$ and appending the unique final step $s$ counts each $(n + 1)$ -step word exactly once. Each added factor is $1 / 4$ , proving the formula by induction.

3.1F10step 2.2given

Fix $n \geq 0$ . A word of length $2 n$ returns to its starting point exactly when, for some $m \in {0, \dots, n}$ , it contains $m$ up-steps, $m$ down-steps, and $n - m$ steps in each horizontal direction. For this $m$ , choose the up, down, and left positions in succession; [F10] gives $(\binom{2 n}{m}) (\binom{2 n - m}{m}) (\binom{2 n - 2 m}{n - m}) = \frac{(2 n)!}{m!^{2} (n - m)!^{2}} = (\binom{2 n}{n}) (\binom{n}{m}) (\binom{n}{n - m}) .$ The equalities follow by applying the real closed formula in [F10] to each coefficient.

4.1F6F8F9F10step 2.2step 3.1

Summing the counts from step 3.1 over $m = 0, \dots, n$ , Vandermonde [F10] gives $p^{(2 n)} (z, z) = 4^{- 2 n} (\binom{2 n}{n}) \sum_{m = 0}^{n} (\binom{n}{m}) (\binom{n}{n - m}) = 4^{- 2 n} {(\binom{2 n}{n})}^{2} .$ The formula includes $n = 0$ , where the empty word has weight one. It is independent of $z$ . For odd length, each move flips the parity of the sum of the two coordinates, so $p^{(2 n + 1)} (z, z) = 0$ .

5.1F11step 4.1given

Set $a_{k} : = p^{(2 k + 2)} (z, z)$ and $b_{k} : = 1 / (k + 1)$ for $k \geq 0$ . By step 4.1 and [F11], $\frac{a_{k}}{b_{k}} = (k + 1) 4^{- 2 (k + 1)} {(\binom{2 k + 2}{k + 1})}^{2} ⟶ \frac{1}{π} > 0.$ Indeed, writing $u_{n} = 4^{- n} (\binom{2 n}{n})$ gives $n u_{n}^{2} = (\sqrt{π n} u_{n})^{2} / π \to 1 / π$ . All $a_{k}, b_{k}$ are positive by step 4.1.

6.1F12step 5.1

The harmonic series is $\sum_{k \geq 0} b_{k}$ after the index shift $n = k + 1$ , and diverges by [F12]. The positive finite limit in step 5.1 and the limit-comparison theorem [F12] imply $\sum_{k \geq 0} p^{(2 k + 2)} (z, z) = \sum_{k \geq 0} a_{k} = \infty$ .

7.1F13step 6.1

Every return term is nonnegative. Therefore the full partial sum $\sum_{j = 0}^{2 M + 2} p^{(j)} (z, z)$ dominates $\sum_{k = 0}^{M} p^{(2 k + 2)} (z, z)$ ; the latter is unbounded by step 6.1. By [F13] the full Green series diverges. This argument does not mistake the $n = 0$ identity term for a positive-time return.

8.1F6F8F13F14step 4.1step 7.1given

The fixed state space $E = Z^{2}$ contains $(0, 0)$ and at least the distinct states $(1, 0)$ and $(0, 1)$ , so empty and one-state cases do not occur. Every row has four positive entries; off-neighbor entries are zero, odd-time return entries vanish by step 4.1, and $p^{(0)} (z, z) = 1$ is included only in the Green series, not in $T_{z}^{+}$ . There is no boundary parameter, absorbing state, deterministic row, or iff claim. The one-way recurrence conclusion uses only the Green-divergence-to-recurrence direction of [F14].

9.1A1F13F14step 2.1step 7.1given∎

For each fixed $z$ , the statewise recurrence criterion [F14] and step 7.1 show that $z$ is recurrent. By [F13] this means exactly $P_{z} (T_{z}^{+} < \infty) = 1$ . Since $z$ was arbitrary, every state of the two-dimensional simple symmetric walk is recurrent. AC is used to obtain the canonical laws and to apply the recurrence criterion; the finite word count, Vandermonde identity, asymptotic comparison, and parity argument require no choice.

Source notes

Durrett, Probability: Theory and Examples, 5th ed., §5.4 Example 5.4.2, Theorem 5.4.3 and complete proof, and the $d = 2$ part of Theorem 5.4.4, printed pp. 288–289/PDF pp. 295–296 (official PDF parser lines 19421–19505), gives the return-series criterion, four-direction path count, Vandermonde reduction, and harmonic-order asymptotic. Its random-walk setup uses iid uniform increments; the item constructs the corresponding matrix chain and its canonical laws locally.

Levin–Peres–Wilmer, Markov Chains and Mixing Times, 2nd ed., §21.1 Proposition 21.3 and complete proof, and Example 21.5, printed p. 292/PDF p. 308, give the Green-series criterion and an alternate corner-walk proof. Proposition 21.3 assumes irreducibility; the corner walk's communicating-class issue is resolved in the source by the rotation/dilation observation. This item does not depend on that result: it uses the library's statewise criterion and directly computes the same return series from every starting state.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Higher-dimensional simple symmetric walks are transient

Statement

Assume AC (The Axiom of Choice). For every integer $d \geq 3$ , define the probability kernel on $(Z^{d}, 2^{Z^{d}})$ by $K_{d} (z, A) = \frac{1}{2 d} \sum_{j = 1}^{d} (δ_{z + e_{j}} (A) + δ_{z - e_{j}} (A)),$ where $e_{1}, \dots, e_{d}$ are the standard basis vectors of $Z^{d}$ . For each $x \in Z^{d}$ , let $P_{x}$ be the canonical path-space chain law with initial measure $δ_{x}$ and transition kernel $K_{d}$ . Then every state $x \in Z^{d}$ is transient for this simple symmetric nearest-neighbor walk.

Facts & Assumptions

Given: AC, an integer $d \geq 3$ , the lattice $Z^{d}$ , the kernel $K_{d}$ , and a fixed initial state $x \in Z^{d}$ .

[A1]

AC is assumed for the canonical path-space law and the statewise recurrence criterion used below. (The Axiom of Choice)

[F1]

A Dirac set function is a probability measure; finite nonnegative weighted sums of measures are measures. (A Dirac set function is a probability measure, Nonnegative scalar multiples and countable weighted sums of measures are measures)

[F2]

A probability kernel is a measure in the target variable for each source point, has total mass one, and is measurable in the source point for each measurable target set. (Measure kernel and probability kernel)

[F3]

From any probability measure and probability kernel, AC supplies a unique canonical path-space law whose coordinates form the corresponding homogeneous Markov chain. (Canonical Markov chain on path space)

[F4]

With initial measure $δ_{x}$ , write $P_{x}$ for the specified deterministic-start chain law. (Initial distribution of a Markov chain)

[F5]

The simple symmetric walk has one-step matrix $p (z, z + e_{j}) = p (z, z - e_{j}) = 1 / (2 d)$ for $j = 1, \dots, d$ and zero elsewhere; each row sums to one. (Simple symmetric walk on the integer lattice)

[F6]

The matrix probabilities are $p (z, w) = K_{d} (z, {w})$ and $p^{(n)} (z, w) = K_{d}^{n} (z, {w})$ , with $p^{(0)} (z, w) = 1_{{z = w}}$ . (Transition matrices and n-step probabilities)

[F7]

Matrix Chapman–Kolmogorov holds: $p^{(m + n)} (z, w) = \sum_{v \in Z^{d}} p^{(m)} (z, v) p^{(n)} (v, w) .$ (Matrix Chapman–Kolmogorov equations)

[F8]

$Z$ is at most countable: it is a surjective image of $N \times N$ . ( $Q$ is countably infinite, Remark)

[F9]

Every finite power of an at most countable set is at most countable. (Every finite power of an at most countable set is at most countable)

[F10]

For $a = (a_{1}, \dots, a_{d}) \in W (n, d)$ , the multinomial coefficient counts ordered blocks of sizes $a_{1}, \dots, a_{d}$ , and $(\binom{n}{a_{1}, \dots, a_{d}}) \prod_{j = 1}^{d} a_{j}! = n! .$ The multinomial expansion holds for real variables. (The multinomial coefficient $(\binom{n}{k_{0}, \dots, k_{m - 1}})$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes, The multinomial coefficient equals $n! / \prod_{i < m} k_{i}!$ , and $(x_{0} + \dots + x_{m - 1})^{n} = \sum ι ⁣ (\binom{n}{k}) \prod_{i < m} x_{i}^{k_{i}}$ in $R$ )

[F11]

If positive reals $u_{j}$ have nonnegative real weights $r_{j}$ summing to one, then $\prod_{j} u_{j}^{r_{j}} \leq \sum_{j} r_{j} u_{j}$ . (The weighted arithmetic-geometric mean inequality for real weights)

[F12]

Stirling's formula gives $\frac{m!}{\sqrt{2 π m} (m / e)^{m}} ⟶ 1 (m \to \infty) .$ (Stirling's formula for factorials)

[F13]

For $n \geq 1$ , if $b_{n} = 4^{- n} (\binom{2 n}{n})$ , then $\sqrt{π n} b_{n} \to 1$ . (The central binomial coefficient is asymptotic to 4^n divided by the square root of pi n)

[F14]

Every nonempty finite subset of $R$ has a maximum and minimum. (The nonempty finite subsets of $R$ are exactly the listable ones)

[F15]

For rational $s > 1$ , the series $\sum_{n \geq 1} n^{- s}$ converges. (For rational $p > 0$ , $\sum 1 / k^{p}$ converges iff $p > 1$ )

[F16]

If nonnegative terms are eventually bounded above by terms of a convergent series, their series converges. (If $0 \leq a_{k} \leq b_{k}$ eventually, convergence of $\sum b_{k}$ gives convergence of $\sum a_{k}$ , and divergence of $\sum a_{k}$ gives divergence of $\sum b_{k}$ )

[F17]

For every specified chain law, $P_{x} (T_{x}^{+} < \infty) = 1$ means $x$ is recurrent, while $P_{x} (T_{x}^{+} < \infty) < 1$ means it is transient; these alternatives exhaust all states. (Recurrent and transient states)

[F18]

Under AC, recurrence of a fixed state is equivalent to divergence of its return Green series: $x recurrent ⟺ \sum_{n = 0}^{\infty} p^{(n)} (x, x) = \infty .$ (Equivalent criteria for recurrence and transience)

Proof

technique · count return paths, estimate the maximum multinomial probability by Stirling's formula, and apply the Green-series criterion

1.1A1F3F6F17F18step 1.1step 1.2step 1.3step 2.1step 3.1step 2.2step 4.1step 5.1step 6.1given∎

For fixed $z$ , $K_{d} (z, \cdot)$ is the finite weighted sum of the $2 d$ Dirac probability measures at $z \pm e_{j}$ , $1 \leq j \leq d$ , with coefficient $1 / (2 d)$ . By [F1] it is a measure, and its total mass is $2 d / (2 d) = 1$ . For fixed $A \subseteq Z^{d}$ , the function $z \mapsto K_{d} (z, A)$ is measurable because the source sigma-algebra is the full power set. Thus [F2] makes $K_{d}$ a probability kernel. The vectors $z \pm e_{j}$ are pairwise distinct, so its transition matrix is exactly [F5]. [F1, F2, F5, given] 1.2 By [F3], [F4], and [A1], for each fixed $x$ there is a canonical Markov chain law with this matrix and initial state $x$ . Also [F8] and [F9] show that its state space $Z^{d}$ is at most countable, as required by [F18]. The law is unique for each $x$ , so no family of laws is selected by choice. [A1, F3, F4, F8, F9, given] 1.3 Repeatedly apply [F7] to the finite-support one-step rows. Induction on the number of steps expands $p^{(n)} (0, 0)$ as the sum of the probabilities of all length- $n$ move words that start and end at $0$ ; each such word has probability equal to the product of its one-step entries [F5]. At every finite time only finitely many words occur, since there are $2 d$ choices at each step. In particular, a return after an odd number of steps is impossible: each move changes the parity of the sum of the coordinates. [F5, F6, F7, given] 1.4 Fix $n \geq 1$ and let $W_{n, d} = {a = (a_{1}, \dots, a_{d}) \in N^{d} : \sum_{j = 1}^{d} a_{j} = n} .$ For $a \in W_{n, d}$ define $q_{n} (a) = d^{- n} (\binom{n}{a_{1}, \dots, a_{d}}) = \frac{n!}{d^{n} \prod_{j = 1}^{d} a_{j}!},$ where the second equality follows from [F10]. By the real multinomial expansion [F10], evaluating all $d$ variables at $1 / d$ gives $\sum_{a \in W_{n, d}} q_{n} (a) = 1.$ The index set is finite by [F10], and each $q_{n} (a) > 0$ . [F10, given] 2.1 The maximum $M_{n} : = \max_{a \in W_{n, d}} q_{n} (a)$ exists by [F10] and [F14]; the set is nonempty, for example $(n, 0, \dots, 0)$ belongs to it. If $a_{i} \geq a_{j} + 2$ for coordinates $1 \leq i, j \leq d$ , transferring one unit from coordinate $i$ to coordinate $j$ produces $a^{'} = a - e_{i} + e_{j} \in W_{n, d}$ and $\frac{q_{n} (a^{'})}{q_{n} (a)} = \frac{a_{i}}{a_{j} + 1} > 1.$ Consequently any maximizing tuple has coordinates differing by at most one. Writing $n = d m + r$ with $0 \leq r < d$ , such a tuple has $r$ coordinates equal to $m + 1$ and the others equal to $m$ ; all such tuples have the same value. [F10, F14, step 1.4, given] 2.2 A $2 n$ -step word returns to zero exactly when, for each coordinate $1 \leq j \leq d$ , it uses $+ e_{j}$ and $- e_{j}$ equally often. Write their common count as $a_{j}$ ; then $a \in W_{n, d}$ . For fixed $a$ , the number of words is the multinomial coefficient with the $2 d$ category counts $(a_{1}, a_{1}, \dots, a_{d}, a_{d})$ , so [F10] and [F5] give its return probability as $\frac{(2 n)!}{(2 d)^{2 n} \prod_{j = 1}^{d} (a_{j}!)^{2}} .$ Summing over $a$ and using the definition of $q_{n}$ yields $p^{(2 n)} (0, 0) = b_{n} \sum_{a \in W_{n, d}} q_{n} (a)^{2}, b_{n} = 4^{- n} (\binom{2 n}{n}) .$ Indeed, each summand on the right is $4^{- n} \frac{(2 n)!}{(n!)^{2}} \frac{(n!)^{2}}{d^{2 n} \prod_{j = 1}^{d} (a_{j}!)^{2}} = \frac{(2 n)!}{(2 d)^{2 n} \prod_{j = 1}^{d} (a_{j}!)^{2}},$ the word probability just computed. [F5, F7, F10, step 1.3, step 1.4, given, algebra] 3.1 The limit in [F12], and positivity of its terms for $m \geq 1$ , imply constants $c, C > 0$ such that for every integer $m \geq 1$ , $c \sqrt{m} (m / e)^{m} \leq m! \leq C \sqrt{m} (m / e)^{m} .$ For fixed $d$ and $n \geq 2 d$ , a balanced tuple has every coordinate $a_{j} \geq n / (2 d) > 0$ . Put $r_{j} = a_{j} / n$ for $1 \leq j \leq d$ . These positive weights sum to one; applying weighted AM–GM [F11] to $u_{j} = 1 / (d r_{j})$ gives $\prod_{j = 1}^{d} {(\frac{1}{d r_{j}})}^{r_{j}} \leq \sum_{j = 1}^{d} \frac{r_{j}}{d r_{j}} = 1,$ and raising to the $n$ th power yields $\frac{n^{n}}{d^{n} \prod_{j = 1}^{d} a_{j}^{a_{j}}} = \prod_{j = 1}^{d} {(\frac{1}{d r_{j}})}^{a_{j}} \leq 1.$ Use the upper Stirling bound for $n!$ and the lower one for each $a_{j}!$ in the factorial formula for $q_{n}$ . Since $\sum_{j = 1}^{d} a_{j} = n$ , the exponential factors cancel, and the last display gives $M_{n} \leq \frac{C}{c^{d}} \frac{\sqrt{n}}{\prod_{j = 1}^{d} \sqrt{a_{j}}} \leq \frac{C}{c^{d}} (2 d)^{d / 2} n^{- (d - 1) / 2} .$ For $1 \leq n < 2 d$ , [F10] gives $M_{n} \leq 1$ ; increasing the constant therefore produces $C_{d} > 0$ with $M_{n} \leq C_{d} n^{- (d - 1) / 2} (n \geq 1) .$ Here $C_{d}$ may depend on the fixed dimension $d$ . [F10, F11, F12, step 2.1, step 1.4, given, algebra] 4.1 Since $0 \leq q_{n} (a) \leq M_{n}$ , normalization [step 1.4] gives $\sum_{a \in W_{n, d}} q_{n} (a)^{2} \leq M_{n} \sum_{a \in W_{n, d}} q_{n} (a) = M_{n} .$ By [F13] there is a constant $C_{0}$ with $b_{n} \leq C_{0} n^{- 1 / 2}$ for all $n \geq 1$ . Combining the return factorization, the bound from step 3.1, and the square-sum estimate just proved, there is a constant $D_{d} > 0$ such that $0 \leq p^{(2 n)} (0, 0) \leq D_{d} n^{- d / 2} (n \geq 1) .$ The odd-time return probabilities vanish by step 1.3. [F13, step 1.3, step 1.4, step 3.1, step 2.2, algebra] 5.1 For fixed integer $d \geq 3$ , the rational exponent $d / 2$ exceeds one, so [F15] gives convergence of $\sum_{n \geq 1} n^{- d / 2}$ . The comparison theorem [F16] and step 4.1 show that $\sum_{n = 0}^{\infty} p^{(n)} (0, 0) = 1 + \sum_{n = 1}^{\infty} p^{(2 n)} (0, 0) < \infty .$ The initial term is one by [F6]. [F6, F15, F16, step 1.3, step 4.1, algebra] 6.1 The Green-series criterion [F18] implies that $0$ is not recurrent; [F17] gives the exhaustive recurrent/transient alternatives, so $0$ is transient. For every $x \in Z^{d}$ , translation by $x$ is a probability-preserving bijection from the finite move words from $0$ back to $0$ to the words from $x$ back to $x$ . Therefore $p^{(n)} (x, x) = p^{(n)} (0, 0)$ for every $n$ , and the same finite Green-series criterion makes each $x$ transient. [F5, F6, F17, F18, step 1.3, step 5.1, given] 7.1 The time-zero return contributes exactly one; all odd positive returns have probability zero; and the estimates apply at the threshold $d = 3$ , where the bounding exponent is $3 / 2$ . The constant $D_{d}$ is allowed to depend on fixed $d$ , so no uniform-in-d claim is made. AC [A1] is used for the canonical chain law and recurrence criterion; the path counting, finite maximization, and translation argument require no choice. The assertion is one-way, not an iff statement.

Source notes

Durrett, §5.4, Example 5.4.2 and the complete proof of Theorem 5.4.4, printed pp. 288–290 (official fifth-edition PDF at https://sites.math.duke.edu/~rtd/PTE/PTE5_011119.pdf). The theorem states the same transience classification. Its proof counts the d=3 return words, writes the return probability as a central-binomial factor times a sum of squared multinomial masses, bounds that sum by the largest mass, locates the maximum at balanced counts, and uses Stirling's formula for an $O (n^{- 1})$ maximum mass. It then handles $d > 3$ using the embedded three-coordinate walk. The proof here extends the coefficient calculation to each fixed $d \geq 3$ by weighted AM–GM and the Stirling ratio, and applies the already authored statewise Green-series criterion. The source passage does not prove this all-d coefficient estimate, and no local central limit theorem is used.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Nonnegative kernel action and finite drift

Definition

Let $p$ be a transition matrix on countable $E$ and let $ϕ : E \to [0, + \infty]$ . Define the nonnegative kernel action

$P ϕ (x) : = \sum_{y \in E : p (x, y) > 0} p (x, y) ϕ (y) \in [0, + \infty],$

using the extended nonnegative sum of Series in the nonnegative extended real line. Terms with zero transition weight are omitted: The extended real line $\overline{R} = R \cup {- \infty, + \infty}$ , its order, and the arithmetic that is left undefined leaves $0 \cdot (+ \infty)$ undefined, while each displayed product has positive finite first factor and is defined even when $ϕ (y) = + \infty$ . If $ϕ$ is finite-valued and $P ϕ (x) < \infty$ , its drift is the finite real number

$L ϕ (x) : = P ϕ (x) - ϕ (x) .$

This agrees with the published discrete generator Discrete generator of a countable-state transition matrix on bounded functions. For an extended-valued $u$ , write a first-step relation as $u = P u + c$ in extended nonnegative arithmetic; do not define a drift by subtracting $+ \infty$ from $+ \infty$ .

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

First-step equations for nonnegative exit costs

Statement

Assume AC (The Axiom of Choice). Let $X$ be a Markov chain on an at most countable state space $E$ with transition kernel $K$ and transition matrix $p (x, y) = K (x, {y})$ . Let $D \subseteq E$ , put $T = T_{D^{c}}$ , and let $f : D^{c} \to [0, \infty)$ and $c : D \to [0, \infty)$ be bounded. Define the boundary payoff $B$ by $B = f (X_{T})$ when $T < \infty$ and $B = 0$ when $T = \infty$ , so no value $X_{\infty}$ is used. For $x \in E$ , let $u (x) : = E_{x} ⁣ [B + \sum_{0 \leq m < T} c (X_{m})] \in [0, + \infty],$ with the empty sum equal to $0$ . Then $u (x) = f (x) (x \in D^{c}), u (x) = c (x) + P u (x) (x \in D),$ where $P ϕ (x) = \sum_{y \in E : p (x, y) > 0} p (x, y) ϕ (y)$ is the support-restricted nonnegative kernel action of Nonnegative kernel action and finite drift. The equation on $D$ is in extended nonnegative arithmetic and may have value $+ i n f t y$ .

Facts & Assumptions

Given: AC, a countable-state Markov chain with kernel $K$ , $D \subseteq E$ , bounded nonnegative $f$ and $c$ , and $T = T_{D^{c}}$ .

[A1]

The Axiom of Choice states that every family of nonempty sets has a choice function; it is assumed here for the canonical laws and conditional-expectation/Markov suppliers cited below. (The Axiom of Choice)

[F1]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ , so $T = 0$ when the initial state is in $D^{c}$ . (Hitting, return, and visit times)

[F17]

The infimum of the empty set is $+ \infty$ . (Hitting, return, and visit times)

[F2]

$p (x, y) = K (x, {y})$ for the transition matrix. (Transition matrices and n-step probabilities)

[F18]

$P ϕ (x) = \sum_{y : p (x, y) > 0} p (x, y) ϕ (y)$ for nonnegative $ϕ$ , with zero weights omitted. (Nonnegative kernel action and finite drift)

[F3]

[F4]

For bounded measurable $g$ , $E [g (X_{n + 1}) ∣ F_{n}] = K g (X_{n})$ almost surely, where $K g (x) = \int g (y) K (x, d y)$ . (Bounded-function form of the Markov property)

[F5]

When the initial state is fixed at $x$ , $P_{x} = P_{δ_{x}}$ and $E_{x} = E_{δ_{x}}$ ; hence $X_{0} = x$ almost surely under $P_{x}$ . (Initial distribution of a Markov chain)

[F6]

On a countable discrete space, a measure is the sum of its singleton weights; for $K (x, \cdot)$ they are $p (x, y)$ . (Every measure on a countable discrete space is its weighted sum of Dirac measures)

[F7]

Increasing sequences of nonnegative measurable functions pass to the limit under the nonnegative integral. (Monotone convergence for the integral)

[F8]

The nonnegative integral is additive, including when one or both integrals are infinite. (Additivity of the nonnegative Lebesgue integral)

[F9]

Restricting a nonnegative measurable function to a measurable event by setting it to zero off the event preserves measurability. (Closure properties of measurable functions used by the integral)

[F10]

A nonnegative extended series is the supremum of its increasing finite partial sums. (Series in the nonnegative extended real line)

[F11]

Pointwise increasing limits of measurable functions are measurable. (Closure properties of measurable functions used by the integral)

[F12]

Every nonnegative measurable function is the pointwise increasing limit of nonnegative simple functions. (Every nonnegative measurable function is the increasing limit of simple measurable functions)

[F13]

For a nonnegative simple $s = \sum_{i = 1}^{r} a_{i} 1_{A_{i}}$ on disjoint measurable sets, its simple integral is $\sum_{i = 1}^{r} a_{i} μ (A_{i})$ . (The integral of a nonnegative simple function)

[F14]

For a nonnegative double sequence, the two iterated sums agree, including when their common value is $+ \infty$ . (Tonelli's theorem for double series of nonnegative extended real numbers)

[F15]

For bounded real $Y$ , $E [E (Y ∣ G)] = E [Y]$ . (Basic algebra and order properties of conditional expectation)

[F16]

Sums of measurable extended-real functions are measurable whenever the sum is defined pointwise. (Closure properties of measurable functions used by the integral)

[F19]

For a nonnegative simple measurable function, its nonnegative Lebesgue integral equals its simple integral. (The nonnegative integral agrees with the simple integral on simple functions)

[F20]

The nonnegative Lebesgue integral is the supremum of the simple integrals of all nonnegative simple minorants. (The nonnegative Lebesgue integral)

[F21]

A nonnegative simple measurable function has finite range. (Nonnegative simple measurable functions)

[F22]

For every $A$ and $n \geq 0$ , ${T_{A} \leq n} = ⋃_{j = 0}^{n} {X_{j} \in A}$ , so the hitting events used here are measurable. (Hitting, return, and visit times)

Proof

technique · define the path reward before any random-time evaluation, then use bounded truncations and monotone convergence

1.1F1F9F10F16F17F22given

On $E^{N_{0}}$ , put $T (ω) = \inf {n \geq 0 : ω_{n} \in D^{c}}$ , extend $f$ by zero on $D$ and $c$ by zero on $D^{c}$ , and define $B (ω) = \sum_{n \geq 0} f (ω_{n}) 1_{{T (ω) = n}}$ , $C (ω) = \sum_{m \geq 0} c (ω_{m}) 1_{{m < T (ω)}}$ , and $R = B + C$ . The hitting events are measurable by [F22], the restrictions by [F9], the nonnegative series by [F10], and their sum by [F16]; thus $R$ is measurable, $B = 0$ on $T = \infty$ by [F17], and no coordinate at infinity is evaluated.

1.2F1F5given

If $x \in D^{c}$ , then $X_{0} = x$ almost surely under $P_{x}$ by [F5], so $T = 0$ by [F1], $B = f (x)$ and $C = 0$ ; hence $u (x) = E_{x} R = f (x)$ . This includes an empty $D$ and a start already on the boundary.

1.3F1F8F17given

If $x \in D$ , then every path starting at $x$ has $T \geq 1$ ; its shifted path exits at time $T - 1$ when $T < \infty$ and never exits when $T = \infty$ , so $R (ω) = c (x) + R (ω_{1}, ω_{2}, \dots)$ in extended nonnegative arithmetic. Additivity [F8] gives $u (x) = c (x) + E_{x} R (X_{1}, X_{2}, \dots)$ without subtraction, also when the tail expectation is infinite.

1.4F3F15given

For $N \geq 1$ , let $H_{N} = R \land N$ and $h_{N} (y) = E_{y} H_{N} (X_{0}, X_{1}, \dots)$ ; then $h_{N}$ is measurable and bounded by $N$ by [F3], and its conditional future-path identity at time $1$ , followed by [F15], gives $E_{x} H_{N} (X_{1}, X_{2}, \dots) = E_{x} h_{N} (X_{1})$ .

1.5F4F5F15given

The bounded one-step identity [F4], expectation preservation [F15], and $X_{0} = x$ under $P_{x}$ [F5] give $E_{x} h_{N} (X_{1}) = K h_{N} (x) : = \int_{E} h_{N} (y) K (x, d y)$ .

1.6F2F6F7F10F12F13F14F18F19F20F21given

For a nonnegative simple $s = \sum_{i = 1}^{r} a_{i} 1_{A_{i}}$ with disjoint measurable $A_{i}$ , [F19] identifies its nonnegative integral with its simple integral [F13], and countable singleton weights [F6] give $\int_{E} s (y) K (x, d y) = \sum_{i} a_{i} K (x, A_{i}) = \sum_{i} a_{i} \sum_{y \in A_{i}} p (x, y) = \sum_{y : p (x, y) > 0} p (x, y) s (y)$ . For general nonnegative measurable $g$ , choose simple $s_{j} ↑ g$ by [F12]; MCT [F7] passes the integrals to the limit, while [F20] fixes the nonnegative integral and [F21] ensures the increments $s_{i + 1} - s_{i}$ are finite-valued nonnegative simple functions. Thus $s_{j} = \sum_{i < j} (s_{i + 1} - s_{i})$ with $s_{0} = 0$ ; Tonelli [F14] interchanges the increment and state sums when $E$ is countably infinite, using its fixed enumeration, while for finite $E$ the limit passes through the finite sum. It follows that $\int_{E} g (y) K (x, d y) = \sum_{y : p (x, y) > 0} p (x, y) g (y)$ , the support-restricted action [F18].

2.1F2F7F11F18step 1.3step 1.4step 1.5step 1.6given

As $N \to \infty$ , $H_{N} (X_{1}, X_{2}, \dots) ↑ R (X_{1}, X_{2}, \dots)$ and $h_{N} (y) ↑ u (y)$ for every $y$ ; [F7] and measurability of the increasing limit [F11] give $E_{x} R (X_{1}, X_{2}, \dots) = \int_{E} u (y) K (x, d y) = \sum_{y : p (x, y) > 0} p (x, y) u (y) = P u (x)$ by steps 1.4–1.6 and [F2]. Combining with step 1.3 proves $u (x) = c (x) + P u (x)$ on $D$ , including the value $+ \infty$ .

3.1A1F1F2F3F4F5F6F15F17F18step 1.2step 1.3step 2.1given∎

If $E = \emptyset$ , there is no probability law of an $E$ -valued chain and no state to check; if $D = \emptyset$ , step 1.2 covers every state; if $D = E$ , the boundary payoff is zero and the equation still holds when $T = \infty$ and $u = + \infty$ . If $f = c = 0$ , then $u = 0$ ; a one-state absorbing chain in $D$ with positive cost has $u = + \infty = c + P u$ , and deterministic rows obey the same shift calculation. The endpoint $T = 0$ is handled in step 1.2, whereas on $D$ one has $T \geq 1$ and the exit-time cost is excluded by $m < T$ . AC [A1] is used for the canonical laws and conditional-expectation/Markov identities [F3]–[F5], [F15]; countability supplies the fixed row representation, with no additional choice principle. The two equations form no biconditional.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Superharmonic majorants bound exit costs

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$ , let $D \subseteq E$ , and put $T = T_{D^{c}}$ . Let $f : D^{c} \to [0, \infty)$ and $c : D \to [0, \infty)$ be bounded. Define $B = f (X_{T})$ on ${T < \infty}$ and $B = 0$ on ${T = \infty}$ , and put $u (x) : = E_{x} ⁣ [B + \sum_{0 \leq m < T} c (X_{m})] (x \in E),$ as in First-step equations for nonnegative exit costs. Suppose $ψ : E \to [0, \infty)$ is finite-valued, $P ψ (x) < \infty$ for every $x$ , $ψ (x) \geq f (x)$ on $D^{c}$ , and $L ψ (x) \leq - c (x)$ on $D$ , where $P ψ (x) = \sum_{y \in E : p (x, y) > 0} p (x, y) ψ (y), L ψ (x) = P ψ (x) - ψ (x)$ are the kernel action and finite drift from Nonnegative kernel action and finite drift. Then $u (x) \leq ψ (x) for every x \in E .$

Facts & Assumptions

Given: AC, a countable-state Markov chain, $D, f, c, T, B, u$ , and a finite-valued nonnegative $ψ$ satisfying the displayed boundary and drift inequalities and $P ψ (x) < \infty$ at each state.

[A1]

AC supplies the canonical chain laws and the conditional-expectation versions used by the Markov and conditional-monotone-convergence results. (The Axiom of Choice)

[F1]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ ; in particular $T = 0$ for an initial state in $D^{c}$ , and ${T \leq n}$ is measurable from the first $n + 1$ states. (Hitting, return, and visit times)

[F2]

For the transition kernel $K$ , $p (x, y) = K (x, {y})$ . (Transition matrices and n-step probabilities)

[F3]

Under the deterministic-start law, $X_{0} = x$ almost surely and its expectation is denoted by $E_{x}$ . (Initial distribution of a Markov chain)

[F4]

The exit reward is $B + \sum_{0 \leq m < T} c (X_{m})$ , with boundary payoff zero when $T = \infty$ ; its expectation is $u (x)$ . (First-step equations for nonnegative exit costs)

[F5]

$P ϕ (x)$ is the sum over positive transition weights, and if $ϕ$ is finite-valued with finite $P ϕ (x)$ , then $L ϕ (x) = P ϕ (x) - ϕ (x)$ . (Nonnegative kernel action and finite drift)

[F6]

Bounded measurable $g$ satisfies $E [g (X_{n + 1}) ∣ F_{n}] = K g (X_{n})$ almost surely. (Bounded-function form of the Markov property)

[F7]

Increasing nonnegative conditional expectations converge to the conditional expectation of their pointwise limit, whose defining event integrals hold for every event in the conditioning sigma-algebra. (Conditional monotone convergence)

[F8]

A nonnegative integral passes through an increasing pointwise limit. (Monotone convergence for the integral)

[F9]

A finite-range nonnegative function has its simple integral given by its finite sum of values times the measures of their level sets; that is its nonnegative integral. (Nonnegative simple measurable functions, The integral of a nonnegative simple function, The nonnegative integral agrees with the simple integral on simple functions)

[F10]

The nonnegative integral is the supremum of the simple integrals of nonnegative simple minorants. (The nonnegative Lebesgue integral)

[F11]

The integral of a pointwise lower limit of nonnegative measurable functions is at most the lower limit of their integrals. (Fatou's lemma)

[F12]

Nonnegative integrals are additive, including extended values. (Additivity of the nonnegative Lebesgue integral)

[F13]

An at most countable set is finite or admits a listing by $N$ . (Finite, countably infinite, countable, uncountable)

[F14]

A nonnegative extended series is the supremum of its finite partial sums. (Series in the nonnegative extended real line)

Proof

technique · define the path reward before any random-time evaluation, then use bounded truncations and monotone convergence

1.1F2F5F8F9F10F13F14given

Fix $x \in E$ and a finite-valued nonnegative $g$ . Exhaust finite $E$ by its finite initial subsets, or, for countably infinite $E$ , fix an enumeration $e_{0}, e_{1}, \dots$ and put $F_{j} = {e_{0}, \dots, e_{j - 1}}$ . Each $g 1_{F_{j}}$ is a finite-range simple function, and the simple-integral formula plus $p (x, y) = K (x, {y})$ gives $\int_{E} g (y) 1_{F_{j}} (y) K (x, d y) = \sum_{y \in F_{j}} p (x, y) g (y)$ , with zero weights omitted from the row action. These functions increase to $g$ , so monotone convergence and the definition of the nonnegative row series give $K g (x) : = \int_{E} g (y) K (x, d y) = P g (x)$ , also for finite $E$ .

1.2F1given

For each finite $n$ , define $M_{n} : = ψ (X_{n \land T}) + \sum_{m < n \land T} c (X_{m})$ . By [F1], this is a finite sum of measurable nonnegative terms, equivalently using $\sum_{m < n} 1_{{T > m}} c (X_{m})$ , so $M_{n}$ is measurable and finite pathwise. On ${T \leq n}$ , $M_{n + 1} = M_{n}$ ; on $S_{n} : = {T > n} \in F_{n}$ , one has $X_{n} \in D$ , $M_{n} = ψ (X_{n}) + \sum_{m < n} c (X_{m})$ , and $M_{n + 1} = ψ (X_{n + 1}) + \sum_{m \leq n} c (X_{m})$ .

2.1F5F6F7F14step 1.1given

For $N \geq 1$ , let $ψ_{N} = \min (ψ, N)$ . It is bounded and measurable, so [F6] and step 1.1 give $E [ψ_{N} (X_{n + 1}) ∣ F_{n}] = P ψ_{N} (X_{n})$ almost surely. As $N ↑ \infty$ , both $ψ_{N} (X_{n + 1})$ and $P ψ_{N} (X_{n})$ increase to their untruncated values: for the row action, its supremum over $N$ and over finite row partial sums commute, and each finite partial sum converges termwise. Conditional monotone convergence [F7] therefore yields $E [ψ (X_{n + 1}) ∣ F_{n}] = P ψ (X_{n})$ almost surely, with the right side finite at every state by hypothesis.

3.1F3F5F7F12step 2.1step 1.2given

Fix $x \in E$ under $P_{x}$ . Since $M_{0} = ψ (x)$ , suppose inductively that $E_{x} M_{n} \leq ψ (x)$ , which makes $M_{n}$ integrable. Integrating the conditional identity from step 2.1 over $S_{n}$ by the defining event-integral property [F7] gives $E_{x} [1_{S_{n}} ψ (X_{n + 1})] = E_{x} [1_{S_{n}} P ψ (X_{n})]$ . On $S_{n}$ , $P ψ (X_{n}) + c (X_{n}) \leq ψ (X_{n})$ by the drift hypothesis, and $E_{x} [1_{S_{n}} ψ (X_{n})] \leq E_{x} M_{n} < \infty$ ; thus $E_{x} [1_{S_{n}} (ψ (X_{n + 1}) + c (X_{n}))] \leq E_{x} [1_{S_{n}} ψ (X_{n})]$ . Off $S_{n}$ the stopped quantities agree, while on $S_{n}$ their earlier cost sums agree; nonnegative additivity [F12] now yields $E_{x} M_{n + 1} \leq E_{x} M_{n} \leq ψ (x)$ . Induction proves finite stopped expectations without assuming global integrability of $ψ (X_{n})$ .

4.1F4F11step 3.1given

Put $Z : = B + \sum_{0 \leq m < T} c (X_{m})$ , so $E_{x} Z = u (x)$ by [F4]. On ${T < \infty}$ , for every $n \geq T$ , $M_{n} = ψ (X_{T}) + \sum_{m < T} c (X_{m}) \geq f (X_{T}) + \sum_{m < T} c (X_{m}) = Z$ . On ${T = \infty}$ , $B = 0$ and $M_{n} \geq \sum_{m < n} c (X_{m})$ , whose partial costs increase to $Z$ . Hence $Z \leq {lim inf}_{n \to \infty} M_{n}$ pointwise without evaluating $X_{\infty}$ ; Fatou [F11] and step 3.1 give $u (x) = E_{x} Z \leq E_{x} [{lim inf}_{n} M_{n}] \leq {lim inf}_{n} E_{x} M_{n} \leq ψ (x)$ . Since $x$ was arbitrary, the claim holds at every state.

5.1A1F1F3F4F6F7step 1.2step 2.1step 4.1given∎

If $E = \emptyset$ , there is no state to check. If $D = \emptyset$ , then $T = 0$ and the conclusion is $f \leq ψ$ ; if $D = E$ , step 4.1 applies with $B = 0$ . When $f = c = 0$ , $u = 0 \leq ψ$ . For a one-state chain, a boundary start has $T = 0$ , and if its state is in $D$ then $P ψ = ψ$ forces $c = 0$ and $u = 0$ . Deterministic transitions are covered by the one-step identity. A hit at $T = n + 1$ incurs $c (X_{n})$ and then the boundary value at $X_{n + 1}$ . AC [A1] supports the canonical laws, bounded conditional Markov identities, and conditional monotone convergence; the pathwise comparison itself uses no choice. This is a one-way bound, with no iff claim.

Source notes

Roch, Note 24 §2 equation (4), printed/PDF p. 3, defines the same exit payoff and pre-exit running cost. In §3, Lemma 24.6 and its proof state the stopped supermartingale construction, and Theorem 24.7 and its proof state the majorant conclusion. In the proof of Theorem 24.7, the displayed identity for the stopped limit at $T = \infty$ is not justified and need not hold: the limit can retain a nonzero $ψ (X_{n})$ contribution. This proof does not use that identity or the source's supermartingale convergence step. It derives finite stopped-expectation bounds with conditional truncations and obtains the result from pointwise domination and Fatou. The source's generator was initially defined for bounded functions; this item states $P ψ (x) < \infty$ at every state and proves the unbounded one-step conditional identity locally.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

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 \subseteq E$ , put $T = T_{D^{c}}$ and $v (x) : = E_{x} T, x \in E .$ If $v (x) < \infty$ for every $x \in E$ , then $v (x) = 0 (x \in D^{c}), L v (x) = - 1 (x \in 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 \subseteq E$ ; and $T = T_{D^{c}}$ .

[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]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ , with the empty infimum equal to $+ \infty$ . (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$ , $P_{x}$ is the law with initial distribution $δ_{x}$ and $E_{x}$ 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 $D^{c}$ and $u = c + P u$ on $D$ in extended nonnegative arithmetic. (First-step equations for nonnegative exit costs)

[F5]

The nonnegative kernel action is $P ϕ (x) = \sum_{y : p (x, y) > 0} p (x, y) ϕ (y)$ . (Nonnegative kernel action and finite drift)

[F6]

If $ϕ$ is finite-valued and $P ϕ (x) < \infty$ , 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 $E_{x} T_{A} < \infty$ 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, $\sum_{m \geq 0} 1_{{m < T}} = T$ : if $T = t \in N_{0}$ , exactly the indices $m = 0, \dots, t - 1$ contribute, while if $T = \infty$ , every index contributes and both sides are $+ \infty$ . 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 $D^{c}$ and $v (x) = 1 + P v (x)$ for $x \in 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 + P v (x) (x \in D)$

3.1

If $v$ is finite at every state, then for each $x \in D$ the first-step relation forces $P v (x) < \infty$ and hence $L v (x) = - 1$ . [F5, F6, step 2.1, given] Indeed, step 2.1 gives $v (x) = 1 + P v (x) < \infty$ , so $P v (x) < \infty$ . Since $v$ is finite-valued, [F6] defines $L v (x)$ , and the finite-real equation gives $L v (x) = P v (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 = D^{c}$ is nonempty. Thus [F7] holds with this target, and [F8] gives $E_{x} T_{A} < \infty$ for every $x \in 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_{\emptyset} = \infty$ , so the global finite-mean premise fails.

5.1A1F1F2F3F4F5F6F7F8step 1.1step 2.1step 3.1given∎

If $E = \emptyset$ , the initial-distribution definition supplies no probability law of an $E$ -valued chain; there are no states to check. If $D = \emptyset$ , 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 = \infty$ 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 $L v (x) = - 1$ . The endpoint $T = 0$ is counted by the empty path sum, and for $x \in D$ one has $T \geq 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.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30Open item page →

Lyapunov drift bound for hitting times

Statement

Assume AC (The Axiom of Choice). Let $E$ be at most countable with sigma-algebra $2^{E}$ , let $K$ be a probability kernel, and set $p (x, y) = K (x, {y})$ . For each $x \in E$ , let $P_{x}$ be the canonical path-space chain law with initial measure $δ_{x}$ and transition kernel $K$ , and let $E_{x}$ be its expectation. For $A \subseteq E$ , define $T_{A} = \inf {n \geq 0 : X_{n} \in A}$ . If $ψ : E \to [0, \infty)$ is finite-valued with $P ψ (x) < \infty$ for every $x$ and $L ψ (x) \leq - 1$ on $E ∖ A$ , using the support-restricted kernel action and finite drift, then $E_{x} [T_{A}] \leq ψ (x)$ for every $x$ . Consequently $P_{x} (T_{A} < \infty) = 1$ .

Facts & Assumptions

Given: AC, an at most countable state space $E$ , a probability kernel $K$ with transition matrix $p$ , a target $A \subseteq E$ , and a finite-valued nonnegative $ψ$ satisfying $P ψ < \infty$ everywhere and $L ψ \leq - 1$ on $A^{c}$ .

[A1]

AC is the assumption available to construct each fixed-start canonical law and is assumed by the prior first-step and superharmonic-majorant theorems. (The Axiom of Choice)

[F1]

An at most countable set is finite or countably infinite. (Finite, countably infinite, countable, uncountable)

[F2]

A probability kernel is a probability measure in the target variable and has total mass one. (Measure kernel and probability kernel)

[F3]

For $x \in E$ , the Dirac set function $δ_{x}$ is a probability measure. (A Dirac set function is a probability measure)

[F4]

AC gives the canonical path-space law for a probability initial measure and a probability kernel; its coordinate process is the corresponding Markov chain. (Canonical Markov chain on path space)

[F5]

With initial state fixed at $x$ , write $P_{x}$ for the law with initial distribution $δ_{x}$ and $E_{x}$ for its expectation. (Initial distribution of a Markov chain)

[F6]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ , the infimum of the empty set is $+ \infty$ , and $T_{A} = 0$ when the start is in $A$ . (Hitting, return, and visit times)

[F7]

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

[F8]

For finite-valued $ψ$ , $P ψ (x) = \sum_{y : p (x, y) > 0} p (x, y) ψ (y)$ ; when this is finite, $L ψ (x) = P ψ (x) - ψ (x)$ . Zero transition weights are omitted. (Nonnegative kernel action and finite drift)

[F9]

For bounded nonnegative boundary payoff $f$ and running cost $c$ , the first-step exit cost is $u (x) = E_{x} [B + \sum_{0 \leq m < T} c (X_{m})]$ , where $B = f (X_{T})$ on $T < \infty$ and $B = 0$ on $T = \infty$ . (First-step equations for nonnegative exit costs)

[F10]

If $D \subseteq E$ , $f : D^{c} \to [0, \infty)$ and $c : D \to [0, \infty)$ are bounded, and finite-valued $ψ \geq 0$ satisfies $P ψ < \infty$ everywhere, $ψ \geq f$ on $D^{c}$ , and $L ψ \leq - c$ on $D$ , then the corresponding exit cost obeys $u (x) \leq ψ (x)$ . (Superharmonic majorants bound exit costs)

[F11]

Expectation of a nonnegative measurable random variable is its extended nonnegative integral, and the nonnegative integral preserves pointwise order. (Expectation of a nonnegative or integrable random variable, Monotonicity and nonnegative homogeneity of the nonnegative integral)

Proof

technique · identify $T_A$ with the unit running cost up to first exit from $A^c$, then apply the superharmonic-majorant bound

1.1A1F2F3F4F5given

Fix $x \in E$ . By [F2] and [F3], $K$ and $δ_{x}$ satisfy the kernel and initial-measure hypotheses of [F4]; AC [A1] therefore supplies the canonical law $P_{x}$ , and [F5] fixes the notation $E_{x}$ . This is done for each $x$ separately, without selecting path-space realizations as a family.

1.2F6given

Pathwise, if $T_{A} = k < \infty$ then exactly the indices $m = 0, \dots, k - 1$ satisfy $m < T_{A}$ , while if $T_{A} = \infty$ every $m \geq 0$ does; hence $\sum_{m \geq 0} 1_{{m < T_{A}}} = T_{A}$ in $[0, + \infty]$ . In particular the sum is empty and equals zero when the starting state is in $A$ .

1.3F1F2F7F8given

Set $D = A^{c}$ , let $f$ be the zero function on $A = D^{c}$ , and let $c$ be the constant one function on $D$ . Both are bounded and nonnegative, $ψ \geq f$ on $A$ , and [F8] identifies the given drift condition with $L ψ \leq - c$ on $D$ . Countability and the matrix-kernel relationship are [F1], [F2], and [F7].

2.1F6F9step 1.2step 1.3given

For the exit problem in step 1.3, the boundary payoff is zero on both $T_{A} < \infty$ and $T_{A} = \infty$ , and the accumulated running cost is $\sum_{m < T_{A}} 1$ . By [F9] and the pathwise identity in step 1.2, its value is $u (x) = E_{x} [T_{A}]$ , including the value $+ \infty$ if the target is never hit.

3.1A1F1F8F10step 1.3step 2.1given

The hypotheses of [F10] hold for $D = A^{c}$ , $f = 0$ , and $c = 1$ : the chain is countable by [F1], AC [A1] is assumed, step 1.3 verifies the boundary and drift inequalities, and $P ψ$ is finite everywhere by hypothesis. Therefore step 2.1 and [F10] give $E_{x} [T_{A}] = u (x) \leq ψ (x)$ .

4.1F11step 3.1given

For each integer $N \geq 1$ , pointwise $N 1_{{T_{A} = \infty}} \leq T_{A} \land N \leq T_{A}$ . By [F11] and step 3.1, $N P_{x} (T_{A} = \infty) \leq E_{x} [T_{A} \land N] \leq E_{x} [T_{A}] \leq ψ (x) < \infty$ ; letting $N$ grow forces $P_{x} (T_{A} = \infty) = 0$ . Thus the stated expectation bound also gives almost-sure hitting.

5.1A1F6F7F8step 1.2step 2.1step 3.1given∎

If $A = E$ , then $T_{A} = 0$ and the bound is immediate. If $A = \emptyset$ and $E \neq \emptyset$ , step 2.1 would give $+ \infty = E_{x} [T_{A}] \leq ψ (x) < \infty$ , so no $ψ$ can satisfy the hypotheses; the implication is vacuous in this case. For a one-state chain, $A = E$ is the first case, while for $A = \emptyset$ its sole row has $p (x, x) = 1$ and $L ψ (x) = 0$ , contradicting the drift assumption. On a deterministic row $p (x, y) = 1$ , the drift inequality gives $ψ (y) \leq ψ (x) - 1$ until the hit, so nonnegativity prevents an infinite path outside $A$ ; zero-weight terms are omitted by [F8]. The endpoints $T_{A} = 0$ and $T_{A} = \infty$ were handled in steps 1.2 and 2.1. AC is used for the canonical laws and the two prior theorems, not for the pathwise identity or deterministic calculation. This is a one-way bound, not an iff claim.

Source notes

Roch, Note 24 §2 equation (4), printed/PDF p. 3, defines the boundary payoff and accumulated pre-exit cost; the complete proof of Theorem 24.4, printed/PDF p. 4, supplies the first-step cost identity. Section 3 Theorem 24.8 and its complete proof, printed/PDF p. 7 (official PDF parser lines 312–336), state the Lyapunov hitting-time bound and reduce it to Theorem 24.7 with $D = A^{c}$ , $f = 0$ , and $c = 1$ . Roch assumes $A$ proper and states a nonnegative $ψ$ without separately requiring finite $P ψ$ ; §1 initially defines the generator for bounded functions. This item uses the earlier library superharmonic-majorant theorem, whose explicit finite- $P ψ$ condition makes the action and drift well-defined, and handles $A = E$ directly. No source uncertainty remains for the stated library claim.

5 · Examples, counterexamples and false statements

None yet.