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.


$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.

  • $\begingroup$ Surely $N_i$ and $f_i$ are defined in your notes, textbook, etc. somewhere? $\endgroup$
    – Math1000
    Mar 15, 2020 at 21:19
  • $\begingroup$ This seems similar to the following recent question: math.stackexchange.com/questions/3582036/… $\endgroup$
    – Michael
    Mar 15, 2020 at 21:38
  • $\begingroup$ after looking at my notes I will update the question to show his definitions for $N_i$ and $f_i$ @Math1000 $\endgroup$ Mar 15, 2020 at 21:42
  • $\begingroup$ Usually the first way to learn of recurrence/transience is in the probability that the Markov chain ever returns to state $i$. This probability is 1 for a recurrent state (think about how this relates to an infinite number of visits to that state) and less than 1 for a transient state. $\endgroup$
    – Struggles
    Mar 20, 2020 at 17:13
  • $\begingroup$ In short, if you have a recurrent state, you expect an infinite number of visits (if your chain begins at that state). If your state is transient, you'll eventually never return so you expect a finite number of visits. Different books/classes/lectures will approach this differently so I'm not sure how you need it answered, but it's something to know. Your notation of $E(N_i)$ doesn't specify a starting state which i find strange since if you start in a class that $i$ isn't in, you expect $N_i = 0$ even if it's recurrent. $\endgroup$
    – Struggles
    Mar 20, 2020 at 17:13

1 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.

  • 1
    $\begingroup$ I was able to get the answer before looking at your solution, but it's reassuring to see. we got the same result. Thank you for your explanations and your solution. All the best. $\endgroup$ Mar 25, 2020 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.