[proofplan] The argument proceeds through the renewal structure induced by successive returns to state $k$. By the [Strong Markov Property](/theorems/2208), the inter-return times to $k$ form an i.i.d. sequence with finite mean $\mu_k$. The Strong Law of Large Numbers then implies that the $r$-th return time $T_k^{(r)}$ satisfies $T_k^{(r)}/r \to \mu_k$ a.s. Since $V_k(n)$ is the counting process that inverts the return-time sequence — counting how many returns have occurred by time $n$ — inverting the SLLN gives $V_k(n)/n \to 1/\mu_k = \pi_k$ a.s. [/proofplan] [step:Establish that $k$ is visited infinitely often and define the successive return times] Since $(X_n)$ is irreducible and positive recurrent, every state is recurrent. By [Recurrence and Infinitely Many Returns](/theorems/2219), starting from $X_0 = i$, the chain visits state $k$ infinitely often, $\mathbb{P}_i$-a.s. In particular, the first hitting time of $k$, \begin{align*} T_k := \inf\{n \geq 1 : X_n = k\}, \end{align*} is finite $\mathbb{P}_i$-a.s. Define the successive return times to $k$ recursively. Set $T_k^{(0)} := T_k$ (the first time the chain reaches $k$), and for each $r \in \mathbb{N}$, define \begin{align*} T_k^{(r)} := \inf\{n > T_k^{(r-1)} : X_n = k\}. \end{align*} Each $T_k^{(r)}$ is the time of the $(r+1)$-th visit to $k$ (counting from the first arrival). Since $k$ is visited infinitely often a.s., every $T_k^{(r)}$ is finite $\mathbb{P}_i$-a.s. Define the inter-return times \begin{align*} \tau_r := T_k^{(r)} - T_k^{(r-1)}, \qquad r \in \mathbb{N}, \end{align*} where each $\tau_r$ records the number of steps between the $r$-th and $(r+1)$-th visits to $k$. [guided] The goal of this step is to set up the renewal framework that will drive the rest of the proof. We need the chain to visit $k$ infinitely often — without this, $V_k(n)$ would eventually stop growing and $V_k(n)/n \to 0$, which would contradict $\pi_k > 0$. Why does $k$ get visited infinitely often? The chain is irreducible, so every state communicates with every other state — in particular, starting from $X_0 = i$, the chain reaches $k$ in finite time a.s. Once at $k$, recurrence (which follows from positive recurrence) guarantees that the chain returns to $k$ again and again. Formally, by [Recurrence and Infinitely Many Returns](/theorems/2219), a recurrent state is visited infinitely often a.s. from any starting state in the same communicating class. With infinitely many visits guaranteed, we define the successive return times. The first hitting time of $k$ is \begin{align*} T_k := \inf\{n \geq 1 : X_n = k\}, \end{align*} which is finite $\mathbb{P}_i$-a.s. We set $T_k^{(0)} := T_k$ and define inductively \begin{align*} T_k^{(r)} := \inf\{n > T_k^{(r-1)} : X_n = k\}, \qquad r \in \mathbb{N}. \end{align*} Since $k$ is visited infinitely often, each $T_k^{(r)}$ is finite a.s. The inter-return times \begin{align*} \tau_r := T_k^{(r)} - T_k^{(r-1)}, \qquad r \in \mathbb{N}, \end{align*} measure the gap between consecutive visits to $k$. Notice that $\tau_r \geq 1$ for every $r$, since we require $n > T_k^{(r-1)}$ (the chain must take at least one step to return). The first passage time $T_k^{(0)}$ from $i$ to $k$ may have a different distribution from the subsequent inter-return times — this is the reason we separate the initial arrival from the renewal structure that follows. [/guided] [/step] [step:Apply the Strong Markov Property to show the inter-return times $(\tau_r)_{r \geq 1}$ are i.i.d.] Each $T_k^{(r)}$ is a stopping time with respect to the natural filtration $\mathcal{F}_n := \sigma(X_0, X_1, \ldots, X_n)$, and $X_{T_k^{(r)}} = k$ at each of these stopping times. By the [Strong Markov Property](/theorems/2208), the post-$T_k^{(r)}$ process $(X_{T_k^{(r)} + m})_{m \geq 0}$ is a Markov chain started at $k$, independent of $\mathcal{F}_{T_k^{(r)}}$. Since each $\tau_{r+1} = T_k^{(r+1)} - T_k^{(r)}$ is determined entirely by the post-$T_k^{(r)}$ process (it is the first return time to $k$ from the restart at $k$), and this restarted chain always begins in state $k$, the random variables $\tau_1, \tau_2, \tau_3, \ldots$ are independent. Moreover, for every $r \geq 1$, the random variable $\tau_r$ has the same distribution as $T_k^+ := \inf\{n \geq 1 : X_n = k\}$ under $\mathbb{P}_k$ — the first return time to $k$ when starting from $k$. Since $k$ is positive recurrent, the mean return time is finite: \begin{align*} \mu_k := \mathbb{E}_k[T_k^+] < \infty. \end{align*} Therefore $(\tau_r)_{r \geq 1}$ is an i.i.d. sequence with common mean $\mu_k < \infty$. [guided] This is the core probabilistic step. We want to apply the law of large numbers to the return times, but the LLN requires independence — where does it come from? The key is the [Strong Markov Property](/theorems/2208): at a stopping time $\tau$, the chain "restarts fresh." We verify the hypotheses. Each $T_k^{(r)}$ is a stopping time with respect to the natural filtration $\mathcal{F}_n = \sigma(X_0, X_1, \ldots, X_n)$ because the event $\{T_k^{(r)} \leq n\}$ depends only on $X_0, \ldots, X_n$ (we can determine whether the chain has made its $(r+1)$-th visit to $k$ by time $n$ solely from the trajectory up to time $n$). Furthermore, $T_k^{(r)} < \infty$ a.s. as established in the previous step, and $X_{T_k^{(r)}} = k$ by construction. The Strong Markov Property then gives: conditional on $\mathcal{F}_{T_k^{(r)}}$, the process $(X_{T_k^{(r)} + m})_{m \geq 0}$ is a Markov chain with the same transition matrix, started at state $k$. The inter-return time $\tau_{r+1} = T_k^{(r+1)} - T_k^{(r)}$ depends only on this restarted process — specifically, it equals $\inf\{m \geq 1 : X_{T_k^{(r)} + m} = k\}$. Since the restarted chain is independent of $\mathcal{F}_{T_k^{(r)}}$ (and hence of $\tau_1, \ldots, \tau_r$, which are $\mathcal{F}_{T_k^{(r)}}$-measurable), the variable $\tau_{r+1}$ is independent of $(\tau_1, \ldots, \tau_r)$. Since the restarted chain always begins at $k$ with the same transition probabilities, every $\tau_r$ (for $r \geq 1$) has the same distribution — namely, the distribution of $T_k^+$ under $\mathbb{P}_k$. The fact that $k$ is positive recurrent gives $\mu_k = \mathbb{E}_k[T_k^+] < \infty$, which is the finite-mean condition needed for the Strong Law. Note: the initial passage time $T_k^{(0)} = T_k$ under $\mathbb{P}_i$ may have a *different* distribution from $\tau_1, \tau_2, \ldots$ when $i \neq k$. This does not affect the argument because a single non-identically distributed term does not alter the almost sure limit in the law of large numbers. [/guided] [/step] [step:Apply the Strong Law of Large Numbers to obtain $T_k^{(r)}/r \to \mu_k$ a.s.] Write the $r$-th return time as a telescoping sum: \begin{align*} T_k^{(r)} = T_k^{(0)} + \sum_{j=1}^{r} \tau_j. \end{align*} Since $(\tau_j)_{j \geq 1}$ is an i.i.d. sequence with $\mathbb{E}[\tau_j] = \mu_k < \infty$, the Strong Law of Large Numbers gives \begin{align*} \frac{1}{r}\sum_{j=1}^{r} \tau_j \xrightarrow{a.s.} \mu_k \quad \text{as } r \to \infty. \end{align*} Since $T_k^{(0)}$ is finite a.s., the additive correction $T_k^{(0)}/r \to 0$ a.s. Therefore \begin{align*} \frac{T_k^{(r)}}{r} = \frac{T_k^{(0)}}{r} + \frac{1}{r}\sum_{j=1}^{r} \tau_j \xrightarrow{a.s.} 0 + \mu_k = \mu_k \quad \text{as } r \to \infty. \end{align*} [guided] We want to show $T_k^{(r)}/r \to \mu_k$ a.s. The idea is to express the $r$-th return time as a sum of i.i.d. increments, then apply the Strong Law. Write \begin{align*} T_k^{(r)} = T_k^{(0)} + \sum_{j=1}^{r} \tau_j, \end{align*} where $\tau_j = T_k^{(j)} - T_k^{(j-1)}$ is the $j$-th inter-return time. By the previous step, the sequence $(\tau_j)_{j \geq 1}$ is i.i.d. with $\mathbb{E}[\tau_j] = \mu_k$. The hypothesis of positive recurrence gives $\mu_k = \mathbb{E}_k[T_k^+] < \infty$. These are exactly the conditions required by the Strong Law of Large Numbers: an i.i.d. sequence with finite first moment. The SLLN therefore gives \begin{align*} \frac{1}{r}\sum_{j=1}^{r} \tau_j \xrightarrow{a.s.} \mathbb{E}[\tau_1] = \mu_k \quad \text{as } r \to \infty. \end{align*} What about the initial passage time $T_k^{(0)}$? This is the time to first reach $k$ starting from $X_0 = i$. It is finite $\mathbb{P}_i$-a.s. (by [Recurrence and Infinitely Many Returns](/theorems/2219) and irreducibility, since $k$ is recurrent and communicates with $i$). Since $T_k^{(0)}$ is a fixed finite random variable, $T_k^{(0)}/r \to 0$ a.s. as $r \to \infty$. Combining: \begin{align*} \frac{T_k^{(r)}}{r} = \frac{T_k^{(0)}}{r} + \frac{1}{r}\sum_{j=1}^{r} \tau_j \xrightarrow{a.s.} 0 + \mu_k = \mu_k. \end{align*} This says: the average time per return converges to the mean return time $\mu_k$. The next step inverts this to obtain the visit frequency. [/guided] [/step] [step:Relate $V_k(n)$ to the return times and invert the SLLN to conclude $V_k(n)/n \to 1/\mu_k$ a.s.] The visit count from the theorem statement is \begin{align*} V_k(n) := \sum_{m=0}^{n-1} \mathbb{1}_{\{X_m = k\}} \end{align*} counts the number of visits to state $k$ during times $0, 1, \ldots, n-1$. The visit count $V_k(n)$ and the return times are linked by the equivalence: $V_k(n) \geq r+1$ if and only if the chain has completed at least $r+1$ visits to $k$ by time $n-1$, which occurs if and only if $T_k^{(r)} \leq n-1$. More precisely, for every $n \geq 1$, \begin{align*} V_k(n) = \sup\{r \geq 0 : T_k^{(r)} \leq n - 1\} + 1 \end{align*} on the event that $k$ is visited at least once by time $n-1$, with the convention $V_k(n) = 0$ when $T_k^{(0)} > n-1$. Since $T_k^{(0)} < \infty$ a.s., for all sufficiently large $n$ we have $V_k(n) \geq 1$, and $V_k(n) \to \infty$ a.s. because $k$ is visited infinitely often. We now invert the SLLN. Fix $\omega$ in the a.s. event on which $T_k^{(r)}/r \to \mu_k$ and $V_k(n) \to \infty$. For each $n$, set $r_n := V_k(n) - 1$, so that $T_k^{(r_n)} \leq n - 1 < T_k^{(r_n + 1)}$. Dividing through by $r_n + 1$ (which is $V_k(n) \geq 1$ for $n$ large): \begin{align*} \frac{T_k^{(r_n)}}{r_n + 1} \;\leq\; \frac{n-1}{r_n + 1} \;<\; \frac{T_k^{(r_n + 1)}}{r_n + 1}. \end{align*} As $n \to \infty$, we have $r_n \to \infty$ and $r_n + 1 \to \infty$, so \begin{align*} \frac{T_k^{(r_n)}}{r_n + 1} = \frac{T_k^{(r_n)}}{r_n} \cdot \frac{r_n}{r_n + 1} \to \mu_k \cdot 1 = \mu_k, \end{align*} and similarly \begin{align*} \frac{T_k^{(r_n + 1)}}{r_n + 1} = \frac{T_k^{(r_n + 1)}}{r_n + 1} \to \mu_k, \end{align*} where the second limit uses $T_k^{(r_n+1)}/(r_n+1) \to \mu_k$ because the SLLN convergence $T_k^{(r)}/r \to \mu_k$ holds along every subsequence tending to infinity. By the squeeze inequality, \begin{align*} \frac{n - 1}{r_n + 1} = \frac{n-1}{V_k(n)} \to \mu_k. \end{align*} Since $(n-1)/n \to 1$, we obtain \begin{align*} \frac{V_k(n)}{n} = \frac{V_k(n)}{n-1} \cdot \frac{n-1}{n} \to \frac{1}{\mu_k} \cdot 1 = \frac{1}{\mu_k}. \end{align*} By the [Existence and Uniqueness of Invariant Distribution](/theorems/2223), $\pi_k = 1/\mu_k$. Therefore \begin{align*} \frac{V_k(n)}{n} \xrightarrow{a.s.} \pi_k, \end{align*} confirming that the long-run fraction of time spent in state $k$ equals its invariant probability, and that this invariant weight is the reciprocal of the mean return time. [guided] This is the counting-process inversion argument. The intuition is: if the $r$-th return occurs at time roughly $r \mu_k$, then by time $n$ there should be roughly $n/\mu_k$ returns. We make this rigorous via a squeeze. Recall the visit count $V_k(n) = \sum_{m=0}^{n-1} \mathbb{1}_{\{X_m = k\}}$. The relationship between $V_k(n)$ and the return-time sequence is that $V_k(n)$ counts how many of the times $T_k^{(0)}, T_k^{(1)}, T_k^{(2)}, \ldots$ fall in the interval $\{0, 1, \ldots, n-1\}$. More precisely, if $r_n := V_k(n) - 1$ (the index of the last completed return by time $n-1$), then \begin{align*} T_k^{(r_n)} \leq n - 1 < T_k^{(r_n + 1)}. \end{align*} The left inequality says the $(r_n + 1)$-th visit to $k$ has occurred by time $n-1$; the right says the $(r_n + 2)$-th visit has not yet occurred. Now we squeeze. Divide all three expressions by $r_n + 1 = V_k(n)$: \begin{align*} \frac{T_k^{(r_n)}}{r_n + 1} \;\leq\; \frac{n-1}{r_n + 1} \;<\; \frac{T_k^{(r_n + 1)}}{r_n + 1}. \end{align*} As $n \to \infty$, the visit count $V_k(n) \to \infty$ a.s. (because $k$ is visited infinitely often), so $r_n \to \infty$. We compute the limits of the outer terms. For the left bound: \begin{align*} \frac{T_k^{(r_n)}}{r_n + 1} = \frac{T_k^{(r_n)}}{r_n} \cdot \frac{r_n}{r_n + 1}. \end{align*} The first factor converges to $\mu_k$ by the SLLN result from the previous step (the convergence $T_k^{(r)}/r \to \mu_k$ holds along any subsequence $r = r_n \to \infty$). The second factor converges to $1$. So the product converges to $\mu_k$. For the right bound: $T_k^{(r_n + 1)}/(r_n + 1) \to \mu_k$ directly from the SLLN applied along the subsequence $r = r_n + 1 \to \infty$. By the squeeze theorem, the middle term converges: \begin{align*} \frac{n-1}{V_k(n)} \to \mu_k \quad \text{a.s.} \end{align*} Taking reciprocals (valid since $\mu_k > 0$ for a positive recurrent state and $V_k(n) \geq 1$ for large $n$): \begin{align*} \frac{V_k(n)}{n-1} \to \frac{1}{\mu_k} \quad \text{a.s.} \end{align*} Finally, since $(n-1)/n \to 1$, we multiply: \begin{align*} \frac{V_k(n)}{n} = \frac{V_k(n)}{n-1} \cdot \frac{n-1}{n} \to \frac{1}{\mu_k} \cdot 1 = \frac{1}{\mu_k}. \end{align*} By the [Existence and Uniqueness of Invariant Distribution](/theorems/2223), which establishes that the unique invariant distribution of an irreducible positive recurrent chain satisfies $\pi_k = 1/\mu_k$, we conclude \begin{align*} \frac{V_k(n)}{n} \xrightarrow{a.s.} \pi_k = \frac{1}{\mu_k}. \end{align*} This completes the proof. The result says that time averages along the sample path converge to the spatial average $\pi_k$ — the ergodic property of the chain. The positive recurrence hypothesis is consumed in two places: it guarantees $\mu_k < \infty$ (needed for the SLLN to produce a finite limit) and it guarantees the existence of $\pi$ via the invariant distribution theorem. [/guided] [/step]