Markov chain returning to its starting position Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space and let $(X_n)_{n \in \mathbb{N_0}}$ be an $I$-valued (homogeneous) Markov chain, where $I \subset \mathbb{R}$ is countable. For $i \in I$, set
$$
T_i := \inf\{ n \geq 1 : X_n = i \} \quad (\inf \emptyset = + \infty),
$$
which represents the first time $X$ takes the value $i$ starting from time $1$. Furthermore, set $T_i^{(1)} := T_i$ and
$$
T_i^{(k)} := \inf\{ n \geq T^{(k-1)}_i : X_n = i \}, \quad k \geq 2.
$$
Now let $i, j \in \mathbb{N}$ be such that $i \neq j$ and
$$
\mathbb{P}( T_j < T_i \mid X_0 = i ) = \mathbb{P}( T_i < T_j \mid X_0 = j ). \tag{1}
$$
Denote by $\mathbb{P}_i (B) := \mathbb{P} ( B \mid X_0 = i )$, $\mathbb{P}_j (B) := \mathbb{P} ( B \mid X_0 = j )$, $B \in \mathscr{B}(\mathbb{R})$.

Task: Given $X_0=i$, determine the expected number of visits to $j$ before the chain returns to $i$.


Hint: Let $N$ denote the number of visits to $j$ before it returns $i$. Show that
$$
\mathbb{P}_{i} (N \geq k) = \mathbb{P}_i (T_i > T_j) \left( \mathbb{P}_j (T_i > T_j) \right)^{k-1}. \tag{2}
$$


My approach:
One can first observe that
$$
N = \sum_{ k = 1 }^{ \infty } \mathbb{1}_{\{ X_k = j \}} \mathbb{1}_{\{ T_i > k \}},
$$
which is well-defined as a countable sum of non-negative random variables.
If one is able to show $(2)$, then due to $(1)$, it follows that
$$
\mathbb{P}_{i} (N \geq k) = \mathbb{P}_i (T_i > T_j) \left( \mathbb{P}_j (T_i > T_j) \right)^{k-1} = \mathbb{P}_j (T_j > T_i) \left( \mathbb{P}_j (T_i > T_j) \right)^{k-1} = \alpha ( 1 - \alpha)^{k-1},
$$
where $\alpha : =  \mathbb{P}_j (T_j > T_i)$.
Since $N$ is non-negative, we can further use the formula
$$
\mathbb{E}_i(N) = \sum_{ k = 1 }^{\infty} \mathbb{P}_i ( N \geq k ) = \sum_{ k = 1 }^{\infty} \alpha ( 1 - \alpha)^{k-1} = \sum_{ k = 0 }^{\infty} \alpha ( 1 - \alpha)^k = \frac{\alpha}{1 - (1 -\alpha )} = 1,
$$
if $0< \alpha < 1$; otherwise $\mathbb{E}_i(N) = 0$.

But how can one show $(2)$? It is possible to observe that for $k \geq 1$, we have $N \geq k$ if and only if the first time $X$ visits $i$ is strictly greater than the $k$'th time $X$ vsits $j$, i.e.,
$$
\mathbb{P}_{ i }  ( N \geq k ) = \mathbb{P}_i ( T_i >  T^{(k)}_j ) = \ldots
$$
Can this be transformed to $(2)$? If the answer includes the application of a certain property of Markov chains, I would kindly ask to state this property explicitly as well.
 A: Consider the event $\{N \geq k\}$ for $k \geq 1$. From this catalogue I would suggest that you read this chapter on the Strong Markov Property and stopping times. It contains everything that I need to solve this problem.
That is, according to the same document, $T_i,T_j$ are stopping times. Something you can try to prove by yourself, is that if $S,T$ are stopping times then so is $\min(S,T)$. In other words, $\min(T_i,T_j)$ is also a stopping time. Thus, we prepare ourselves to use the Strong Markov Property with this stopping time.
We use the law of total probability to write :$$
\mathbb P_i(N \geq k) = \mathbb P_i(N \geq k | \min(T_i,T_j) < \infty) \mathbb P_i(\min(T_i,T_j)<\infty) \\+\mathbb P_i(N \geq k | \min(T_i,T_j) =\infty) \mathbb P_i(\min(T_i,T_j)=\infty)
$$
The second term is zero, since $\min(T_i,T_j) = \infty$ will force $T_j=\infty$ so $N = 0$. Therefore, we have $$
\mathbb P(N \geq k) = \mathbb P(N \geq k | \min(T_i,T_j) < \infty) \mathbb P(\min(T_i,T_j)<\infty)
$$
Now we have to look at the RHS. Note that $X_{\min(T_i,T_j)}$ is defined on each sample space element in the event $\min(T_i,T_j)<\infty$ (in fact,that's precisely where it is defined). Therefore, we can say that $$
\{\min(T_i,T_j)<\infty\} = \{X_{\min(T_i,T_j)} = i\} \cup \{X_{\min(T_i,T_j)} = j\}
$$
as a disjoint union. This leads to $$
\mathbb P(N \geq k | \min(T_i,T_j) < \infty)\mathbb P_i(\min(T_i,T_j)<\infty) = \mathbb P_i(N \geq k \cap [\{X_{\min(T_i,T_j)} = i\} \cup \{X_{\min(T_i,T_j)} = j\}] )
$$
which by the disjoint nature of the union results in$$
\mathbb P_i(N \geq k \cap \{X_{\min(T_i,T_j)} = i\}) + \mathbb P_i(N \geq k \cap \{X_{\min(T_i,T_j)} = j\})
$$
The first of these is zero, because $T_i<T_j$ implies $N = 0$. We restore the conditional formulation : ​$$
\mathbb P_i(N \geq k \cap \{X_{\min(T_i,T_j)} = j\}) =\mathbb P_i(N \geq k | \{X_{\min(T_i,T_j)} = j\}) \mathbb P_i(\{X_{\min(T_i,T_j)} = j\})
$$
Note that $$
\mathbb P_i(\{X_{\min(T_i,T_j)} = j\}) = \mathbb P_i(T_j<T_i)
$$
and because of remarks we made earlier, $$
\mathbb P_i(N \geq k | \{X_{\min(T_i,T_j)} = j\}) = \mathbb P_i(N \geq k | \{X_{\min(T_i,T_j)} = j , \min(T_i,T_j)<\infty\})
$$
Therefore, we are ready to apply the Strong Markov Property as in Norris' notes. By this, we get $$
\mathbb P_i(N \geq k | \{X_{\min(T_i,T_j)} = j , \min(T_i,T_j)<\infty\}) = \mathbb P_j(N' \geq k-1)
$$
where $N'$ is the event that the random walk beginning at $j$, returns to itself at least $k-1$ times before visiting $i$. Therefore, we get $$
\mathbb P_i(N \geq k) = \mathbb P_i(T_j<T_i)\mathbb P_j(N' \geq k-1)
$$

So we need to find $\mathbb P_j(N' \geq k-1)$. For $k=1$, this is $1$, so that gives us the formula for $k=1$ and we'll assume $k>1$. This can be done using the strong Markov Property again , just as above : but we'll see how that now leads to a reduction formula . Since we've done everything before, I'll be briefer. Indeed,
$$
\mathbb P_j(N' \geq k-1) = \mathbb P_j(N' \geq k-1 | \min(T_i,T_j) < \infty) \mathbb P_j(\min(T_i,T_j)<\infty)
$$
as before, and \begin{align}
& \mathbb P_j(N' \geq k-1 | \min(T_i,T_j) < \infty)\mathbb P_j(\min(T_i,T_j)<\infty) \\ &= \mathbb P_j(N' \geq k-1 \cap [\{X_{\min(T_i,T_j)} = i\} \cup \{X_{\min(T_i,T_j)} = j\}] ) \\ &= \mathbb P_j(N' \geq k-1 \cap \{X_{\min(T_i,T_j)} = j\}) \\ &= \mathbb P_j(N' \geq k-1 | \{X_{\min(T_i,T_j)} = j\}) \mathbb P_j(\{X_{\min(T_i,T_j)} = j\}) \\ &= \mathbb P_j(N' \geq k-1 | \{X_{\min(T_i,T_j)} = j, \min(T_i,T_j)<\infty\})\mathbb P_j(T_j<T_i) \\
&= \mathbb P_j(N' \geq k-2)\mathbb P_j(T_j<T_i)
\end{align}
Where all the lines except the last follow from analogous reasoning to the previous section. The last line results from an application of the strong Markov Property , and the key point is that a return to $j$ implies a reduction in the number that $N'$ needs to exceed, by $1$. Thus, we get $$
\mathbb P_j(N' \geq k-1)=\mathbb P_j(N' \geq k-2)\mathbb P_j(T_j<T_i)
$$
which, by iteration, leads to $$
\mathbb P_j(N' \geq k-1) = \mathbb P_j(T_j<T_i)^{k-1}
$$
Therefore, combining this with the previous section, we are done.
