CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-02

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.

A null recurrent chain has no stationary probability

Statement refuted

Assume AC for the canonical walk law. Simple symmetric nearest-neighbor random walk on $Z$ (Simple symmetric walk on the integer lattice) is recurrent, but it has no invariant probability distribution. Consequently every state is null recurrent (Positive and null recurrence of a state) and $E_{k} T_{k}^{+} = + \infty$ for every $k \in Z$ . Thus positive recurrence is strictly stronger than recurrence, and a recurrent chain need not admit a stationary probability.

Facts & Assumptions

Given: AC and the simple symmetric nearest-neighbor walk on $Z$ , with canonical laws $P_{z}$ and transition matrix $p$ .

[A1]

Every family of nonempty sets has a choice function; AC is assumed and is used through the recurrence and positive-recurrence suppliers [F2] and [F4]. (The Axiom of Choice)

[F1]

For $d = 1$ , $p (z, z + 1) = p (z, z - 1) = \frac{1}{2}$ and all other entries vanish; each row sums to one. (Simple symmetric walk on the integer lattice)

[F2]

Assume AC. With $T_{z}^{+} = \inf {n \geq 1 : X_{n} = z}$ , every state of the one-dimensional simple symmetric walk is recurrent: $P_{z} (T_{z}^{+} < \infty) = 1$ . (One-dimensional simple symmetric walk is recurrent)

[F3]

$x \to y$ means $p^{(n)} (x, y) > 0$ for some $n \geq 0$ , and a chain is irreducible when every pair communicates. (Accessibility, communication, and irreducibility)

[F4]

Assume AC. For an irreducible countable chain, some state positive recurrent, every state positive recurrent, and existence of an invariant probability are equivalent; an invariant probability satisfies $π (b) > 0$ and $E_{b} T_{b}^{+} \leq 1 / π (b)$ for every state $b$ . (Positive recurrence and stationary probability for irreducible countable chains)

[F5]

On a countable state space a probability vector $π$ is invariant exactly when $π (y) = \sum_{x \in E} π (x) p (x, y)$ for every $y \in E$ . (Invariant and stationary distribution for a Markov kernel)

[F6]

A recurrent state is positive recurrent when $E_{x} T_{x}^{+} < + \infty$ and null recurrent when $E_{x} T_{x}^{+} = + \infty$ ; the two cases exhaust the recurrent states. (Positive and null recurrence of a state)

Counterexample

Given: AC and the simple symmetric walk on $Z$ with transition matrix $p (z, z \pm 1) = \frac{1}{2}$ .

Proof technique: suppose an invariant probability exists, show that its successive differences are constant, and contradict summability; then invoke the positive-recurrence equivalence.

1.1F1F3given

The walk is irreducible: for $z, w \in Z$ with $m = w - z$ , following the $∣ m ∣$ nearest-neighbor steps from $z$ toward $w$ has probability $2^{- ∣ m ∣} > 0$ , so $p^{(∣ m ∣)} (z, w) > 0$ ; hence every pair of states communicates in the sense of [F3].

1.2A1F2given

By [F2] every state $k$ is recurrent, $P_{k} (T_{k}^{+} < \infty) = 1$ .

1.3F5given

Suppose $π$ is an invariant probability. By [F5], $2 π (k) = π (k - 1) + π (k + 1)$ for every $k \in Z$ ; rearranging gives $π (k + 1) - π (k) = π (k) - π (k - 1)$ for every $k$ , so the successive difference $c : = π (k + 1) - π (k)$ is the same real number for all $k$ .

2.1step 1.3algebragiven

If $c > 0$ then $π (k) = π (0) + k c \to + \infty$ , so the nonnegative series $\sum_{k} π (k)$ diverges, contradicting $\sum_{k} π (k) = 1$ ; if $c < 0$ then $π (k) \to + \infty$ as $k \to - \infty$ along nonpositive indices, contradicting $π (k) \leq 1$ , which follows from $π$ being a probability; hence $c = 0$ and $π$ is constant on $Z$ .

3.1step 2.1given

A constant probability mass on the countably infinite set $Z$ sums to $0$ when the constant is $0$ and diverges otherwise, so it cannot satisfy $\sum_{k} π (k) = 1$ ; this contradicts the assumed invariant probability, so the walk admits no invariant probability distribution.

4.1step 1.3step 3.1given

Steps 1.3–3.1 derive nonexistence of an invariant probability from the finite-row stationarity equation and summability; this calculation does not assume recurrence.

4.2A1F4F6step 1.1step 1.2step 3.1given

By steps 1.1–1.2 the chain is irreducible and recurrent, and by step 3.1 it has no invariant probability; the equivalence [F4] then rules out positive recurrence of every state, so each recurrent state $k$ satisfies $E_{k} T_{k}^{+} = + \infty$ and is null recurrent by [F6].

4.3step 1.3step 3.1given

Step 3.1 reaches a contradiction from the assumed probability $π$ , so no other constructed object requires a well-definedness check; the stationarity equation used in step 1.3 is a finite row computation.

5.1A1step 1.2step 4.2given∎

AC [A1] is used exactly at the AC-qualified supplier applications in steps 1.2 and 4.2; the difference calculation in step 1.3 uses no Choice.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

28 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Levin–Peres–Wilmer, Markov Chains and Mixing Times, second edition, §21.3 and Appendix C.1, recurrence without a stationary probability (standard reference, not scraped)
Aldous–Chewi, Probability Theory, Lectures 13–15 (standard reference, not scraped)