ExampleConstruction: Literature-sourcedVerification: 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.

Laziness makes an irreducible chain aperiodic

Example

Let $E$ be a nonempty at most countable state space and let $p$ be an irreducible transition matrix on $E$ . Define the identity matrix by $I (x, y) = 1_{{x = y}}$ and put $q = (I + p) / 2$ , entrywise. Then $q$ is an irreducible aperiodic transition matrix on $E$ .

The finite-state discussion in Levin–Peres–Wilmer §1.3 motivates this lazification: the identity contribution gives every state a positive one-step self-loop. The countable-state argument below checks directly that $q$ is stochastic, preserves every positive accessibility route, and has period one at every state.

Verification

Given: A nonempty at most countable set $E$ and an irreducible transition matrix $p$ on $E$ .

[F1] Transition-matrix iterates have nonnegative entries and stochastic rows; in particular, each row sums to one. (Transition matrices and n-step probabilities)

[F2] For any countable transition matrix $s$ and $m, n \geq 0$ , $s^{(m + n)} (x, y) = \sum_{z \in E} s^{(m)} (x, z) s^{(n)} (z, y)$ . (Matrix Chapman–Kolmogorov equations)

[F3] Accessibility means $x \to y$ exactly when $p^{(n)} (x, y) > 0$ for some $n \in N_{0}$ ; irreducibility means every ordered pair is accessible. (Accessibility, communication, and irreducibility)

[F4] The positive return set is $R_{x} = {n \geq 1 : p^{(n)} (x, x) > 0}$ , and when nonempty the state period is its greatest common positive divisor. (Period of a state)

[F5] For an irreducible transition matrix on a nonempty countable state space, the chain is aperiodic when its common state period is one. (Aperiodic irreducible chain)

[F6] A nonnegative countable sum is the supremum of its finite partial sums; termwise inequalities and multiplication by a fixed positive constant therefore preserve the corresponding sum inequality. (Series in the nonnegative extended real line)

[F7] The n-step entries are $p^{(n)} (x, y) = K^{n} (x, {y})$ , with $p^{(0)} (x, y) = 1_{{x = y}}$ . (Transition matrices and n-step probabilities)

Proof technique: prove the lazy matrix is stochastic, compare its powers with those of the original matrix, and use the added one-step returns.

1.1F1F6given

For every $x, y \in E$ , $q (x, y) = \frac{1}{2} 1_{{x = y}} + \frac{1}{2} p (x, y) \geq 0$ and $\sum_{y \in E} q (x, y) = \frac{1}{2} \sum_{y} 1_{{x = y}} + \frac{1}{2} \sum_{y} p (x, y) = \frac{1}{2} + \frac{1}{2} = 1$ by [F1]. Thus $q$ is a transition matrix.

2.1F1F4step 1.1given

For each $x \in E$ , $q (x, x) = \frac{1}{2} + \frac{1}{2} p (x, x) \geq \frac{1}{2} > 0$ . Hence $q^{(1)} (x, x) > 0$ , so $1 \in R_{x} (q)$ by [F4]; the only positive integer dividing $1$ is $1$ , and therefore $d_{q} (x) = 1$ for every state.

2.2F2F6F7step 1.1given

For every $n \in N_{0}$ and $x, y \in E$ , $q^{(n)} (x, y) \geq 2^{- n} p^{(n)} (x, y)$ . This is equality for $n = 0$ by [F7]. If it holds at $n$ , then $q (z, y) \geq \frac{1}{2} p (z, y)$ and Chapman–Kolmogorov [F2] give $q^{(n + 1)} (x, y) = \sum_{z} q^{(n)} (x, z) q (z, y) \geq 2^{- (n + 1)} \sum_{z} p^{(n)} (x, z) p (z, y) = 2^{- (n + 1)} p^{(n + 1)} (x, y)$ ; the sum comparison follows from [F6]. Induction proves the bound.

3.1F3step 2.2given

Fix any ordered pair $x, y \in E$ . By irreducibility and [F3], some $n \geq 0$ satisfies $p^{(n)} (x, y) > 0$ . If $x = y$ and $n = 0$ , then $q^{(0)} (x, x) = 1$ ; otherwise step 2.2 gives $q^{(n)} (x, y) \geq 2^{- n} p^{(n)} (x, y) > 0$ . Thus every ordered pair is accessible for $q$ , so $q$ is irreducible.

4.1F1F4step 1.1step 2.1step 2.2step 3.1given

The empty space is excluded by the nonempty hypothesis. If $E$ has one state, [F1] forces its sole entry to be $1$ , and step 2.1 gives period one. Zero entries of $p$ are allowed: off-diagonal zeros remain zero in $q$ , while each originally positive entry stays positive by step 2.2; deterministic cycles also gain the positive one-step return from step 2.1. The period uses positive return times $n \geq 1$ , so the identity at $n = 0$ is not the reason for period one. There is no boundary or endpoint parameter in this matrix statement. The proof uses only pointwise matrix arithmetic and a finite induction, so it requires no choice function or AC; the claim is not an iff statement.

5.1F5step 2.1step 3.1step 4.1given∎

Step 3.1 proves that $q$ is irreducible, and step 2.1 proves that every one of its state periods equals $1$ . Thus the periods are common and the chain has period one; by [F5], $q$ is aperiodic.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

16 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 and Wilmer, Markov Chains and Mixing Times, second edition (standard reference, not scraped)