Expected value of Markov Chain

Question

Question from professor that I need help with

After answering exercise 14 calculate $E(N_i)$ and then $f_i$ for all $i$ in state spaces of the Markov chains depicted by the four transition matrices in exercise 14.

Question 14

Specify the classes of the following Markov chains, and determine whether they are transient or recurrent:

Partial Answer:

$$P_1=\begin{bmatrix}0&\frac{1}{2}&\frac{1}{2}\\\frac{1}{2}&0&\frac{1}{2}\\\frac{1}{2}&\frac{1}{2}&0\end{bmatrix}$$ $S=\{0,1,2\}$ recurrent.

$$P_3=\begin{bmatrix}\frac{1}{2}&0&\frac{1}{2}&0&0\\ \frac{1}{4}&\frac{1}{2}&\frac{1}{4}&0&0\\ \frac{1}{2}&0&\frac{1}{2}&0&0\\ 0&0&0&\frac{1}{2}&\frac{1}{2}\\ 0&0&0&\frac{1}{2}&\frac{1}{2}\\\end{bmatrix}$$ $S_1=\{0,2\}$ recurrent.$S_2=\{3,4\}$ recurrent.$S_3=\{1\}$ transient.

---

Definitions:

$t_i= inf\{n\geq 1, X_n=i\}$ ,return time to state I

$f_i=P_i(t_i < \infty)$ ,probability that the Markov chain starting at $i$ will ever return to $i$

$N_i=$ number of visits to state $i$

---

I only gave two of the four transition matrices just to make it a bit shorter.

My question lies in how to go about solving my professors question.

Answer 1

I'll be assuming that by $E(N_i)$ you mean $E_i(N_i)$ since that's the standard concept to be introduced at this point (just from where I gather you are in class).

In that case, let $f_{i}^k$ be $\mathbb{P}_i \left( t_{i}^k < \infty \right) $ i.e. that we have at least $k$ returns to $i$ when starting at $i$.

Then note $\mathbb{P}_i \left( N_i \geq k+1 \right) = f_{i}^{k+1}$. It follows then that $\mathbb{P}_i \left( N_i \leq k \right) = 1 - f_{i}^{k+1}$. Intuitively, this is saying that the probability we have at most $k$ returns to $i$ is equal to 1 minus the probability we have at least $k+1$ returns to $i$.

Now we note that $\mathbb{P}_i \left( N_i \leq k \right) = 1 - f_{i}^{k+1}$ is the CDF of $Geo(1 - f_i)$. Now that we know that $N_i \vert_{X_0 = i} \sim Geo(1 - f_i)$ we use our knowledge of the expectation of a geometric distribution to get:

$$ E_i N_i = \frac{f_i}{1- f_i}$$

From here we can verify that if $f_i$ = 1 then we expect infinitely many returns. Similarly if $f_i < 1$. Now the issue will be finding $f_i$. Depending on the structure of the chain this man involve a few additions of probabilities but shouldn't be too bad.