Understanding "Markov Chains" by Norris Theorems 1.7.5 and 6

Question

On this page: https://www.statslab.cam.ac.uk/~james/Markov/s17.pdf I am trying to understand what $\gamma^k$ represents and how it is used concretely with Theorems 1.7.5 and 1.7.6. Does Theorem 1.7.6 mean that if the chain is recurrent, $\gamma^k$ is just a vector of $1$'s? I am trying to use this to work out question 1.7.3 on the same page.

For a fixed state k, $\gamma_i^k=E_k \sum_{n=0}^{T_k-1}1_{\{X_n=i\}}$

Theorem 1.7.5: Let P be irreducible and recurrent. Then,

1. $\gamma^k_k=1$
2. $\gamma^k=\{\gamma_i^k : i \in I\}$ satisfies $\gamma^k P = \gamma^k$.
3. $0 < \gamma_i^k < \infty$ for all $i$

Theorem 1.7.6: Let $P$ be irreducible and let $\lambda$ be an invariant measure for $P$ with $\lambda_k=1$. Then $\lambda \geq \gamma^k$. If $P$ is also recurrent, then $\lambda=\gamma^k$.

Exercise 1.7.3 discusses a particle moving along the edges of a cube. I need to find the number of visits through vertex $o$ until the first return to vertex $i$ ($o$ is the opposite vertex of $i$) and the expected number of steps until the first visit to $o$.

Answer 1

For a state $k$ in the state space $I$, let the random variable $T_k \mathrel{\vcenter{:}}= \inf\{\,n \geq 1 : X_n = k\,\}$ denote the first passage time of state $k$. Intuitively, if the Markov chain $(X_n)$ starts at state $k$, then $T_k$ represents the first time the Markov chain returns to state $k$, excluding the starting state. Then for states $k$ and $i$, the object $\gamma_i^k \mathrel{\vcenter{:}}= \mathbb{E}_k \left(\sum_{n=0}^{T_k - 1}\mathbf{1}_{\{X_n = i\}}\right)$ is the numerical answer to the following question: $$ \text{"If we start at state } k \text{, how many visits do we expect to make to state } i \text{ before we return to state }k \text{?"} $$ where we include the starting state at $k$ (since $n=0$ is included in the sum) and exclude the return to $k$ (since we do not include $n = T_k$ in the sum). We define the vector $\gamma^k \mathrel{\vcenter{:}}= \left(\,\gamma_i^k : i\in I\,\right)$ of the number of expected visits to each state $i$ between consecutive visits to state $k$.

Now let us discuss the two theorems you asked about. I will only give handwavy explanations for the theorems, since you can read the proper proofs in Norris's book.

Theorem 1.7.5. Let $P$ be irreducible and recurrent, and let $k$ be a state. Then

1. $\gamma_k^k = 1$,
2. $\gamma^k P = \gamma^k$, and
3. for all states i, we have $0 < \gamma_i^k < \infty$.

Explanation. The first part of the theorem says we expect to visit the state $k$ once between consecutive visits to state $k$. This should be obvious: we started at state $k$, so of course we will visit state $k$ at least once. Then we exclude the return to state $k$ in the calculation of $\gamma_k^k$, so we only visit state $k$ at most once. The third part of the theorem says we expect to visit state $i$ more than zero times, but we expect the number of visits to only be finite. This follows from the assumption of $P$ being irreducible. If $\gamma_i^k = 0$ then we expect to never visit state $i$ before returning to state k. If $\gamma_i^k = \infty$ then we expect to never return to state $k$ after visiting state $i$. Both cases go against the irreducibility and recurrence of $P$. The second part of the theorem is the most interesting part: it says the vector $\gamma^k$ is an invariant measure for $P$. Writing $P = (p_{i,j})_{i,j\in I}$, for each state $j$ we have $$ \left(\gamma^k P\right)_j = \sum_{i \in I} \gamma^k_ip_{i,j} $$ which, roughly speaking, averages over the number of times we visit state $i$ followed immediately by visiting state $j$, all between consecutive visits to state $k$. Brushing the details of the brute calculation under the carpet, this gives the average number of times state $j$ is visited between consecutive visits to state $k$, which is precisely $\gamma_j^k$. You can see parallels between this line of thinking and the proof presented in Norris's book.

Theorem 1.7.6. Let $P$ be irreducible and let $\lambda$ be an invariant measure for $P$, with $\lambda_k = 1$ for some state $k$. Then $\lambda \geq \gamma^k$. Furthermore, if $P$ is recurrent then $\lambda = \gamma^k$.

Explanation. The first part says if $\lambda$ is an invariant measure with a non-zero entry in the $k$-th position, then rescaling $\lambda$ so that $\lambda_k = 1$ will ensure that all the entries of $\lambda$ will be at least as large as $\gamma^k$, i.e. $\lambda_j \geq \gamma^k_j$ for all states $j$. The main part of the theorem is the second part, which says that if $P$ is recurrent then we actually have $\lambda = \gamma^k$. So if $\lambda$ is an invariant measure with non-zero entry in the $k$-th position, then $\lambda$ actually equals $\gamma^k$ up to scaling. This, in effect, gives some uniqueness to invariant measures of $P$. To answer your question, this does not say that $\gamma^k$ is a vector of 1's; it just implies that the $k$-th position of $\gamma^k$ equals 1, as we expect due to the first part of Theorem 1.7.5.

Now, for the Exercise 1.7.3 you mentioned, you would like to find the value of $\gamma_o^i$. You can check that the transition matrix associated with this Markov chain is irreducible and recurrent, so $\gamma^i$ would equal any invariant measure whose $i$-th entry is equal to $1$ by Theorem 1.7.6. You would therefore solve the left-eigenvector equation $\lambda P = \lambda$, where $P$ is the transition matrix for the particle, and among those which have $\lambda_i \neq 0$ you would rescale it so it's $i$-th position is equal to 1. This rescaled eigenvector would equal $\gamma^i$, so you may then read off the value of $\gamma_o^i$.