DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-generatedjudge 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.

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.

Depends on

Used by

Expected exit time solves the Poisson equation Corollary
Higher-dimensional simple symmetric walks are transient Corollary
One-dimensional simple symmetric walk is recurrent Corollary
Two-dimensional simple symmetric walk is recurrent Corollary
Different classes can have different recurrence types Counterexample
Accessibility, communication, and irreducibility Definition
Aperiodic irreducible chain Definition
Green kernel of a transient chain Definition
Nonnegative kernel action and finite drift Definition
Period of a state Definition
Recurrent and transient states Definition
Simple symmetric walk on the integer lattice Definition
Birth–death recurrence through scale products Example
Communicating classes in a four-state chain Example
Gambler’s ruin from harmonicity Example
Green kernel of a biased integer walk Example
Laziness makes an irreducible chain aperiodic Example
Negative drift gives a finite mean small-set hit Example
Period two on a bipartite graph Example
Geometric tail for hitting in a finite irreducible chain Lemma
Green-kernel resolvent identity Lemma
Matrix Chapman–Kolmogorov equations Lemma
Period is constant on communicating classes Lemma
Bounded Dirichlet problem for hitting probabilities Theorem
Equivalent criteria for recurrence and transience Theorem
First-step equations for nonnegative exit costs Theorem
Hitting probability as minimal harmonic extension Theorem
Lyapunov drift bound for hitting times Theorem
Recurrence and transience are class properties Theorem
Renewal decomposition at successive returns Theorem
Superharmonic majorants bound exit costs Theorem

Dependency tree · two levels

10 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)