number of visits between recurrent and transient states $\mathbb{P}^x(V_y < \infty) = 1$, $\mathbb{P}^x(V_y = \infty) = 1$

Question

Given is an irreducible Markov chain $X=(X_n)_{n\geq0}$ on state space $V$ and transition matrix $P$. Let $V_x$ denote the number of visits to state $x\in V$ and $\mathbb{P}^x$ the conditioned probability on $X_0=x$.

If $x \neq y\in V$ are two transient states, I want to show that $\mathbb{P}^x(V_y < \infty) = 1$.

First I will give you my intuition and I hope that the intuition is correct.

We visit $x$ and $y$ only a finite number of times, starting in $x$ or $y$, respectively (by definition). Starting in $X_0=x$, we have two cases. The first is that $x$ and $y$ are not connected, giving that the number of visits to $y$ starting in $x$ is $0<\infty$. The second case is that $x$ and $y$ are connected. Starting in $x$ and going to $y$ we will count $1$ visit in $y$. Then starting in $y$, by definition, we visit $y$ only a finite number $k<\infty$ of times. All in all, starting in $x$, the number of visits to $y$ is $k+1 <\infty$.

Moreover, I want to show that, if $x \neq y\in V$ are two recurrent states, $\mathbb{P}^x(V_y = \infty) = 1$.

The argument therefore will be similar as above, considering that if we are in $y$, we will return to $y$ an infinite number of times. So all in all, the number of visits to $y$ is $1 + \infty = \infty$, where the $1$ comes from going from $x$ to $y$.

Do you have any tips for me how to put this into formulas? Thank you very much in advance.

Answer 1

Your answers are missing a key detail I'll outline below; this isn't really an issue for the first problem, but means your solution to the second problem is importantly incomplete.

We know that $\mathbb P^y(V_y = \infty)$ is $0$ in the first problem, and $1$ in the second problem. We want to show that the same is true for $\mathbb P^x(V_y = \infty)$.

These are related via \begin{align} \mathbb P^x(V_y = \infty) &= \mathbb P^x(V_y > 0) \cdot \mathbb P^x(V_y = \infty \mid V_y > 0)\\ &= \mathbb P^x(V_y > 0) \cdot \mathbb P^y(V_y = \infty). \end{align} The first holds by the definition of conditional probability. The second holds because, given that we ever actually visit $y$, the probability that after that we visit $y$ infinitely many times is exactly $\mathbb P^y(V_y = \infty)$.

Now, the place where you go wrong is you assume that if $x$ and $y$ are connected, then we do visit $y$ from $x$ eventually: that if $\mathbb P^x(V_y > 0)$ is not $0$, then it must be $1$. This means that in the first problem:

• You correctly say that if there's no way to get to $y$ from $x$, then we're done. Actually, this case is impossible, because we're told the Markov chain is irreducible, but it's still true.
• You correctly say that even if we do get to $y$ from $x$, then that's fine. (Essentially, because the $\mathbb P^y(V_y = \infty)$ factor is still $0$.)
• You fail to consider the case where it's possible to get to $y$ from $x$, but we never do. However, that's not a super important case, since we have $V_y = 0 <\infty$ whenever this happens.

On the other hand, in the second problem, it's important to look at both factors. We have $\mathbb P^y(V_y = \infty) = 1$, but to conclude that $\mathbb P^x(V_y = \infty) = 1$, you also have to show that $\mathbb P^x(V_y > 0)=1$ as well: that, starting in $x$, we are guaranteed to eventually visit $y$.

This does not follow from irreducibility: that only guarantees that there is some path from $x$ to $y$, not that we'll ever take it. So you still have to complete this step.