CorollaryStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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

Sources

Durrett, Probability: Theory and Examples, fifth edition (standard reference, not scraped)
Levin, Peres and Wilmer, Markov Chains and Mixing Times, second edition (standard reference, not scraped)