ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

Empirical state frequencies converge to stationary masses

Example

Assume AC (The Axiom of Choice). Let $p$ be an irreducible positive-recurrent transition matrix on a countable state space $E$ with invariant probability $π$ , let $y \in E$ , and let $P_{x}$ be the law of the $p$ -chain started at the deterministic state $x \in E$ . Then the empirical frequency of visits to $y$ converges,

$\frac{1}{n} # {0 \leq k < n : X_{k} = y} ⟶ π (y) P_{x} -almost surely,$

and the expectation of that frequency converges to the same number,

$E_{x} [\frac{1}{n} # {0 \leq k < n : X_{k} = y}] ⟶ π (y) .$

No aperiodicity is used, and the statements hold for every fixed pair of states $x, y$ ; the second is a convergence statement about real numbers, with no almost-sure qualifier.

Facts & Assumptions

Given: AC; an irreducible positive-recurrent $p$ on the countable state space $E$ with invariant probability $π$ , and states $x, y \in E$ .

[A1]

Every family of nonempty sets has a choice function; AC is assumed and is used through the ergodic theorem supplier [F2], the Cesàro supplier [F3] and the chain-law supplier [F4]. (The Axiom of Choice)

[F1]

A recurrent state $z$ is positive recurrent when $E_{z} T_{z}^{+} < + \infty$ and null recurrent when $E_{z} T_{z}^{+} = + \infty$ ; positive recurrence of the chain means that every state is positive recurrent. (Positive and null recurrence of a state)

[F2]

Assume AC. For an irreducible positive-recurrent countable chain with invariant probability $π$ and a function $f$ with $\sum_{z} π (z) ∣ f (z) ∣ < \infty$ , $\frac{1}{n} \sum_{k = 0}^{n - 1} f (X_{k}) \to \sum_{z} π (z) f (z)$ almost surely under $P_{x}$ , for every starting state $x$ . (Ergodic theorem for an irreducible positive-recurrent Markov chain)

[F3]

Assume AC. For an irreducible positive-recurrent $p$ on countable $E$ with invariant probability $π$ , $\frac{1}{n} \sum_{k = 0}^{n - 1} p^{(k)} (x, y) \to π (y)$ for all $x, y \in E$ . (Cesaro convergence for irreducible positive-recurrent chains)

[F4]

Assume Choice. For a Markov chain with kernel $K$ and bounded measurable real $f$ , $E [f (X_{m + n}) ∣ F_{m}] = K^{n} f (X_{m})$ almost surely, with $m = 0$ included, so that $E_{x} [f (X_{n})] = K^{n} f (x)$ ; equivalently $P (X_{n} \in A ∣ F_{0}) = K^{n} (X_{0}, A)$ almost surely. (Chapman-Kolmogorov equations)

[F5]

On a finite measure space, if measurable $f_{n} \to f$ almost everywhere and $∣ f_{n} ∣ \leq M$ almost everywhere for one real $M \geq 0$ , then $\int f_{n} \to \int f$ . (Bounded convergence on a finite measure space)

[F6]

The $k$ -step transition probabilities are $p^{(k)} (x, y) = K^{k} (x, {y})$ for $k \geq 0$ . (Transition matrices and n-step probabilities)

Verification

Given: AC; an irreducible positive-recurrent $p$ on countable $E$ with invariant probability $π$ , and fixed states $x, y \in E$ .

Proof technique: apply the chain ergodic theorem to the indicator of the target state, then evaluate the expectation of the empirical frequency both by linearity with the Cesàro theorem and by bounded convergence.

1.1F2given

Let $f : = 1_{{y}}$ . Then $0 \leq f \leq 1$ and $\sum_{z \in E} π (z) ∣ f (z) ∣ = π (y) \leq 1 < + \infty$ , so the ergodic theorem [F2] applies to $f$ and the fixed starting state $x$ ; for every $n \geq 1$ and every path, $\sum_{k = 0}^{n - 1} 1_{{X_{k} = y}} = # {0 \leq k < n : X_{k} = y}$ by the definition of the counting notation.

1.2F4F6given

For every $k \geq 0$ , $E_{x} [1_{{X_{k} = y}}] = P_{x} (X_{k} = y) = K^{k} (x, {y}) = p^{(k)} (x, y)$ : the second equality is the $m = 0$ case of [F4] applied to the singleton event ${y}$ , and the third is [F6].

2.1F2step 1.1given

Dividing the identity of step 1.1 by $n \geq 1$ and applying the almost-sure conclusion of [F2] to $f$ gives $\frac{1}{n} # {0 \leq k < n : X_{k} = y} = \frac{1}{n} \sum_{k = 0}^{n - 1} f (X_{k}) \to \sum_{z} π (z) f (z) = π (y)$ almost surely under $P_{x}$ , which is the first displayed assertion.

2.2F3step 1.2given

Expectation by linearity: $E_{x} [\frac{1}{n} # {0 \leq k < n : X_{k} = y}] = \frac{1}{n} \sum_{k = 0}^{n - 1} E_{x} [1_{{X_{k} = y}}] = \frac{1}{n} \sum_{k = 0}^{n - 1} p^{(k)} (x, y)$ , and [F3] makes this tend to $π (y)$ , which is the second displayed assertion.

3.1F5step 2.1step 2.2

Consistency by bounded convergence: the averages of step 2.1 are measurable, converge $P_{x}$ -almost everywhere to the constant $π (y)$ , and satisfy $0 \leq \frac{1}{n} # {0 \leq k < n : X_{k} = y} \leq 1$ for every $n \geq 1$ ; since $P_{x}$ is a probability measure, [F5] gives $E_{x} [\frac{1}{n} # {0 \leq k < n : X_{k} = y}] \to π (y)$ , the same limit as in step 2.2, and the two expressions for the expectation agree term by term by step 1.2.

4.1A1F1F2F3F4F5step 2.1step 2.2step 3.1given∎

The averages are formed for $n \geq 1$ . For the periodic two-cycle started at $0$ with $y = 0$ , the frequency is $⌈ n / 2 ⌉ / n$ , which tends to $1 / 2$ despite periodicity. The indicator remains bounded and integrable on an infinite state space; the almost-sure and expectation limits were proved separately in steps 2.1 and 2.2. AC [A1] enters through [F2]–[F4].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

23 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.