TheoremStatement: AI-adaptedProof: 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.

Kac return-time formula for a positive-mass set

Statement

Assume AC (The Axiom of Choice). Let $p$ be an irreducible transition matrix on a countable state space $E$ with invariant probability $π$ , and let $A \subseteq E$ be nonempty. With $T_{A}^{+} : = \inf {n \geq 1 : X_{n} \in A}$ (Hitting, return, and visit times), one has $π (A) > 0$ and

$\sum_{x \in A} π (x) E_{x} T_{A}^{+} = 1,$

where the terms are extended nonnegative numbers; equivalently $E_{π (\cdot ∣ A)} T_{A}^{+} = 1 / π (A)$ . For a singleton $A = {b}$ this recovers the state Kac identity $π (b) E_{b} T_{b}^{+} = 1$ (Kac return-time formula for a state).

Facts & Assumptions

Given: AC, an irreducible countable transition matrix $p$ with invariant probability $π$ , and a nonempty $A \subseteq E$ .

[A1]

Every family of nonempty sets has a choice function; AC is assumed and is used through the positive-recurrence, reversal, and recurrent-class/hitting suppliers [F3]–[F5]. (The Axiom of Choice)

[F1]

$T_{A} = \inf {n \geq 0 : X_{n} \in A}$ and $T_{A}^{+} = \inf {n \geq 1 : X_{n} \in A}$ , with value $+ \infty$ on the event that the infimum is empty; the initial visit at time zero is not counted by $T_{A}^{+}$ . (Hitting, return, and visit times)

[F2]

On a countable state space $π$ is invariant exactly when $π (y) = \sum_{x} π (x) p (x, y)$ for every $y$ ; a $p$ -chain started in $π$ has $X_{0}$ distributed as $π$ . (Invariant and stationary distribution for a Markov kernel)

[F3]

Assume AC. For an irreducible countable chain with invariant probability $π$ : every state is positive recurrent and hence recurrent, all one-step and $n$ -step transition probabilities are determined by $p$ , and $π (x) > 0$ for every $x \in E$ . (Positive recurrence and stationary probability for irreducible countable chains)

[F4]

Assume AC. For a stationary countable chain with law $π$ : the reverse kernel $p_{*} (x, y) = π (y) p (y, x) / π (x)$ is a transition matrix on $E_{+} = {x : π (x) > 0}$ with $π$ invariant, and every finite segment read backward is distributed as a stationary $p_{*}$ -chain; for every $r \geq 1$ and $0 \leq n_{0} < \dots < n_{r}$ , a stationary $p_{*}$ -chain $X^{*}$ with initial law $π$ satisfies $L (X_{n_{r}}, \dots, X_{n_{0}}) = L (X_{0}^{*}, X_{n_{r} - n_{r - 1}}^{*}, \dots, X_{n_{r} - n_{0}}^{*})$ . (Time reversal of a stationary Markov chain)

[F5]

Assume AC. If $x$ is recurrent and $x \to y$ , then $P_{x} (T_{y} < \infty) = 1$ ; recurrence is a class property. (Recurrence and transience are class properties)

[F6]

For a random variable $T$ with values in ${0, 1, 2, \dots} \cup {+ \infty}$ , $E T = \sum_{n \geq 0} P (T > n)$ , both sides extended nonnegative; this follows by monotone convergence applied to $T = \sum_{n \geq 0} 1_{{T > n}}$ . (Monotone convergence for the integral)

[F7]

For every double sequence $(a_{i j})$ in $[0, + \infty]$ the order of summation may be interchanged, the two iterated sums being equal even when the common value is $+ \infty$ . (Tonelli's theorem for double series of nonnegative extended real numbers)

[F8]

Under the present irreducibility and invariance hypotheses, the state Kac identity is $π (b) E_{b} T_{b}^{+} = 1$ . (Kac return-time formula for a state)

Proof

Given: AC, an irreducible $p$ on countable $E$ , an invariant probability $π$ , a nonempty $A \subseteq E$ , and a $p$ -chain started in $π$ .

Proof technique: identify the probability that the chain starts in $A$ and avoids it up to time $n$ with the probability that the reversed stationary chain first hits $A$ at time $n$ , then sum the identity over $n$ .

1.1A1F3F4algebra

By [F3] every state satisfies $π (x) > 0$ , so $E_{+} = {x : π (x) > 0} = E$ ; by [F4] the reverse kernel $p_{*} (x, y) = π (y) p (y, x) / π (x)$ is a transition matrix on $E$ with $π$ invariant. The $n$ -step reverse identity $p_{*}^{(n)} (x, y) = π (y) p^{(n)} (y, x) / π (x)$ follows by induction on $n$ from this definition and the invariance of $π$ .

1.2A1F3given

For a nonempty $A$ , $π (A) = \sum_{x \in A} π (x) > 0$ , since every term is positive by [F3] and the sum is over a nonempty set.

1.3F1F2given

For every $n \geq 0$ , $P_{π} (X_{0} \in A, X_{1} \notin A, \dots, X_{n} \notin A) = \sum_{x \in A} π (x) P_{x} (T_{A}^{+} > n)$ : the events ${X_{0} = x}$ for $x \in A$ are disjoint, each carries probability $π (x)$ by [F2], and conditional on $X_{0} = x$ with $x \in A$ the event that $X_{1}, \dots, X_{n}$ avoid $A$ is exactly ${T_{A}^{+} > n}$ by [F1].

1.4F1given

If $A = E$ , then $T_{A}^{+} = 1$ and the formula reduces to $\sum_{x} π (x) = 1$ .

2.1step 1.1given

The reverse chain is irreducible: for $x, y \in E$ irreducibility of $p$ gives $n$ with $p^{(n)} (y, x) > 0$ , and then the identity of step 1.1 gives $p_{*}^{(n)} (x, y) = π (y) p^{(n)} (y, x) / π (x) > 0$ .

2.2A1F2F4step 1.3given

If $n \geq 1$ , [F4] gives $L (X_{n}, \dots, X_{0}) = L (X_{0}^{*}, \dots, X_{n}^{*})$ ; if $n = 0$ , both $X_{0}$ and $X_{0}^{*}$ have law $π$ . Thus the event in step 1.3 has probability $P_{π}^{*} (X_{0}^{*} \notin A, \dots, X_{n - 1}^{*} \notin A, X_{n}^{*} \in A) = P_{π}^{*} (T_{A}^{*} = n)$ , where $T_{A}^{*} : = \inf {k \geq 0 : X_{k}^{*} \in A}$ .

3.1A1F3F5step 2.1given

Since $p_{*}$ is irreducible and has the invariant probability $π$ , [F3] applied to $p_{*}$ makes it positive recurrent and recurrent; then [F5] gives $P_{z}^{*} (T_{a} < \infty) = 1$ for all $z \in E$ and every fixed $a \in E$ .

3.2F6F7step 1.3step 2.2given

Summing the identities of steps 1.3 and 2.2 over $n \geq 0$ and using the tail formula [F6] for each nonnegative integer valued $T_{A}^{+}$ gives $\sum_{x \in A} π (x) E_{x} T_{A}^{+} = \sum_{n \geq 0} \sum_{x \in A} π (x) P_{x} (T_{A}^{+} > n) = \sum_{n \geq 0} P_{π}^{*} (T_{A}^{*} = n)$ , the interchange of the two nonnegative sums being [F7].

3.3F1F4step 2.2given

The value $T_{A}^{+} = + \infty$ is never evaluated as $X_{\infty}$ : it occurs only in the nonnegative expectations and tail probabilities, and step 2.2 reverses a finite segment rather than an infinite path.

4.1step 3.1step 3.2given

The last series is $P_{π}^{*} (T_{A}^{*} < \infty) = 1$ : choosing any $a \in A$ , step 3.1 gives $P_{z}^{*} (T_{a} < \infty) = 1$ for every $z$ , hence $P_{π}^{*} (T_{a} < \infty) = \sum_{z} π (z) P_{z}^{*} (T_{a} < \infty) = 1$ , and $T_{A}^{*} \leq T_{a}$ . Therefore $\sum_{x \in A} π (x) E_{x} T_{A}^{+} = 1$ , which in particular shows that the weighted sum is finite.

5.1F8step 1.2step 4.1given

Dividing by the positive number $π (A)$ from step 1.2 gives $E_{π (\cdot ∣ A)} T_{A}^{+} = \sum_{x \in A} \frac{π (x)}{π (A)} E_{x} T_{A}^{+} = \frac{1}{π (A)}$ . For $A = {b}$ the sum has the single term $π (b) E_{b} T_{b}^{+} = 1$ , agreeing with [F8].

5.2F6F7step 3.2step 4.1given

The sum in step 3.2 is over nonnegative extended terms, so it assumes no integrability beforehand; finiteness of the weighted sum follows in step 4.1.

6.1step 5.1step 1.4given

A one-state chain is covered by the case $A = E$ in step 1.4, and the singleton formula is the specialization in step 5.1.

7.1A1step 1.1step 2.2step 3.1given∎

AC [A1] is used exactly at the AC-qualified supplier applications in steps 1.1, 2.2, and 3.1; the subsequent nonnegative summation is choice-free.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

43 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, Lemma 21.12 and §21.3 / Appendix C.1 (standard reference, not scraped)