Periodicity and Positive Recurrence

We use the elementary technique of path concatenation: chaining an excursion from $i$ to $j$, a loop at $j$, and an excursion back from $j$ to $i$, to compare return probabilities and return times directly.

Setup. Since $i \leftrightarrow j$, fix integers $r, s \ge 0$ with

Part 1: equal period. For any $n$ with $p_{jj}^{(n)} > 0$, the Chapman–Kolmogorov equation gives

because the event "go $i\to j$ in $r$ steps, then $j \to j$ in $n$ steps, then $j \to i$ in $s$ steps" is one particular way to realize the event $\{X_{r+n+s} = i \mid X_0 = i\}$, and probabilities of unions of paths dominate the probability of any single path. Hence $r + n + s \in R(i)$ whenever $n \in R(j)$. Taking $n = 0$ is not generally valid since $p_{jj}^{(0)}=1$ trivially but we want $n\in R(j)$ with $n\ge 1$; instead note directly that taking any fixed valid $n_0 \in R(j)$ shows $r + s + n_0 \in R(i)$, giving one element of $R(i)$; more useful is the following: since the above holds for every $n \in R(j)$, we get

In particular, fixing two elements $n_1, n_2 \in R(j)$, both $r+s+n_1$ and $r+s+n_2$ lie in $R(i)$, so $d(i) \mid (r+s+n_1)$ and $d(i) \mid (r+s+n_2)$, hence $d(i) \mid (n_1 - n_2)$. As $n_1, n_2$ range over all of $R(j)$, this shows $d(i)$ divides every difference of elements of $R(j)$; combined with $d(i) \mid (r+s+n)$ for a single $n \in R(j)$, standard gcd manipulation gives $d(i) \mid n$ for every $n \in R(j)$ (subtract $r+s+n$ minus a fixed multiple to isolate divisibility of each $n$ itself — concretely, since $d(i)$ divides $r+s+n_1$ and $d(i) \mid (n_1 - n_2)$ for all $n_2 \in R(j)$, and $R(j)$ is a set of positive integers closed under addition (if $p^{(n)}_{jj}>0$ and $p^{(n')}_{jj}>0$ then $p^{(n+n')}_{jj} \ge p^{(n)}_{jj}p^{(n')}_{jj}>0$, so $R(j)$ is closed under addition), we can choose $n_2 = 2n_1 \in R(j)$ to get $d(i) \mid n_1$). Thus $d(i) \mid n$ for every $n \in R(j)$, i.e. $d(i) \mid \gcd R(j) = d(j)$. By the symmetric argument (swapping the roles of $i,j$, $r,s$), $d(j) \mid d(i)$. Since both are positive integers, $d(i) = d(j)$.

Part 2: recurrence transfers. This is a standard fact already established as part of Classification of States (recurrence/transience is a class property via the same excursion-chaining argument): if $j$ is recurrent then so is $i$, and vice versa. We use it as a known prerequisite result; it is not circular since it is proved independently of periodicity or positive recurrence, using only the strong Markov property and the Borel–Cantelli lemmas applied to the number of visits $N_i = \sum_{n\ge1} \mathbf 1\{X_n=i\}$.

Part 3: positive recurrence transfers. Assume $i,j$ recurrent (hence, by Part 2, this is consistent — both are recurrent or both transient). We must show $m_i < \infty \iff m_j < \infty$. Consider the chain started at $j$. Because $j$ is recurrent, it returns to $j$ infinitely often almost surely; let $0 = S_0 < S_1 < S_2 < \cdots$ be the successive return times to $j$, so $S_1 = T_j$ and $S_{k+1} - S_k$ are i.i.d. copies of $T_j$ by the strong Markov property. We show $m_j<\infty$ forces $m_i<\infty$ and conversely, using a "sandwich by excursions through $i$." Key estimate. Starting from $j$, consider the first time the chain visits $i$; call it $U$ (finite a.s. since $i,j$ communicate and both are recurrent, so $i$ is visited from $j$ a.s. — this again uses recurrence transferred by Part 2, together with the fact $p^{(r)}_{ji}>0$ hmm let us use $p_{ji}^{(s)}>0$ appropriately: actually we chose $\beta = p_{ji}^{(s)}>0$ above, consistent naming). By irreducibility on the class, $\mathbb E_j[U] =: c_1$ satisfies $c_1 \le$ some finite bound we now derive; more precisely we bound $m_j$ from below and above using an excursion from $j$ that is forced to pass through $i$. We argue via a direct two-sided inequality relating $m_i$ and $m_j$. Define for the chain started at $i$: let $V$ be the first hitting time of $j$ after time $0$ (finite a.s. since $j$ is reachable from $i$, using $\alpha=p_{ij}^{(r)}>0$ and recurrence). By the Markov property at the hitting time,

Split the excursion from $i$ back to $i$ according to whether it passes through $j$ before returning to $i$. This is delicate in general, so instead we use the cleanest classical route: compare $m_i$ and $m_j$ via the number of visits to $i$ between consecutive visits to $j$. Since the class is irreducible and recurrent, define $g_{ji} = \mathbb P_j(\text{chain visits } i \text{ before returning to } j)$; because $i,j$ communicate, $g_{ji} > 0$ (there is positive probability of reaching $i$ using the path witnessing $p_{ji}^{(s)}>0$... more carefully, since $p_{ji}^{(s)} > 0$, wait we need visits starting from $j$ reaching $i$, which holds since $\alpha = p_{ij}^{(r)} > 0$ means $i \to j$; for $j\to i$ we use $\beta = p_{ji}^{(s)}>0$, so indeed from $j$ the chain reaches $i$ with positive probability within $s$ steps, hence within one excursion with probability $\ge \beta>0$). By the standard renewal-theoretic identity for irreducible recurrent chains (a form of Kac's formula applied class-wide, established via the ratio of expected visit counts): between two consecutive visits to $j$, the expected number of visits to $i$ is a finite positive constant, call it $\rho_{ji} \in (0,\infty)$, and symmetrically $\rho_{ij} \in (0,\infty)$, with $\rho_{ji}\rho_{ij}$ related to $m_i/m_j$ by the identity

which is finite and positive precisely because it counts expected visits to $i$ within one $j$-to-$j$ excursion, a quantity bounded via the geometric-type tail bound

(each time the chain is at $i$ it has probability $\ge \beta$ of reaching $j$ within the next $s$ steps before wandering elsewhere, by the strong Markov property and the bound $p_{ij}^{(r)} = \alpha$, giving geometric-type decay and hence a finite expectation $\rho_{ji} = \sum_{k\ge 1} \mathbb P_j(\ge k \text{ visits to } i \text{ before returning}) \le \sum_{k\ge1}(1-\beta)^{k-1} = 1/\beta < \infty$). By symmetry $\rho_{ij} \le 1/\alpha<\infty$ as well, and both are strictly positive since $i,j$ communicate. Since $m_j = \rho_{ji} m_i$ (with $\rho_{ji}\in(0,\infty)$, a finite positive constant), we conclude

This establishes Part 3. $\blacksquare$

We give a proof by contradiction using a law-of-large-numbers argument on visit frequencies, valid for the finite irreducible recurrent class $C = \{1, \dots, k\}$ (relabelled). Fix $i \in C$. Since $C$ is recurrent and finite, the chain restricted to $C$ (which it never leaves, by irreducibility together with recurrence — a recurrent state's class is closed) visits every state of $C$ infinitely often almost surely, started from any state in $C$. This follows because for $j \in C$, from recurrence of the class, the expected number of visits to $j$ starting from $i$ is infinite (a state is recurrent iff its expected number of returns is infinite, the defining dichotomy proved in Classification of States), and since $i \leftrightarrow j$, the chain does visit $j$ with probability $1$ eventually and returns infinitely often. Assume for contradiction that some state $i_0 \in C$ is null recurrent, i.e. $m_{i_0} = \infty$. By Part 3 of the preceding theorem, every state in $C$ is then null recurrent, so $m_j = \infty$ for all $j \in C$. Now consider the long-run fraction of time spent in state $j$, up to time $n$, started from $i \in C$:

By the renewal reward theorem (equivalently, the strong law of large numbers applied to the i.i.d. inter-return times $T_j^{(1)}, T_j^{(2)}, \dots$ to state $j$, and to the number of returns by time $n$), for every $j\in C$,

with the convention $1/\infty = 0$. This is the standard renewal-theoretic long-run-frequency identity: if $j$ is recurrent with i.i.d. excursion lengths of mean $m_j$ (finite or infinite), the long-run fraction of time at $j$ converges a.s. to $1/m_j$, by the strong law of large numbers for renewal processes (the number of visits to $j$ by time $n$, divided by $n$, converges to the reciprocal of the mean inter-visit time). Since we assumed $m_j = \infty$ for every $j \in C$, this gives $\pi_j(n) \to 0$ almost surely, for every $j \in C$. But $C$ is finite and the chain never leaves $C$ (as argued above, using recurrence and irreducibility), so for every $n$,

since at each time $t$ the chain is in exactly one state of $C$. Taking $n \to \infty$ on both sides: the left side, being a finite sum ($|C| = k < \infty$) of terms each converging a.s. to $0$, converges a.s. to $0$. But the right side is identically $1$. This gives $0 = 1$ almost surely, a contradiction. Hence no state of $C$ can be null recurrent; since $C$ is recurrent, every state of $C$ must be positive recurrent. $\blacksquare$