# How to show that the $k$th return to $y$ is a stopping time

Define the $k$-th return to $y$ as $T_y^k= \min\{n \ge T_y^{k-1} +1 : X_n = y\}$

I am trying to prove as a "left to the reader" that this is a stopping time. I understand how to argue intuitively that it is a stopping time, but writing it out formally is proving difficult.

My Attempt:

Proof by Induction: We have that $T_y = \min\{ n \ge 1 : X_n = y\}$ is a stopping time because it may be described fully by $$\{T_y = n_1\} = \{X_i \ne y \text{ and } X_0, X_{n_1} = y\} \quad (1 \le i \le n_1-1)$$This description depends only on the past states of the $X_i$s. With the base case established, assume that this holds for $j = k-1$ and show that this implies that $T_y^{j+1} = T_y^k$ is a stopping time.

Then $T_y^k$ may be described by $$\{T_y^k = n_k\} = \{X_i \ne y \text{ and } X_{n_{k-1}}, X_{n_k} = y\} \quad (n_{k-1}+1 \le i \le n_k-1)$$

Since $T_y^{k-1}$ was a stopping time, we know that $T_y^{k-1}$ can be determined by $X_0, \dots, X_{n_{k-1}}$, so we know that $X_i$ has assumed the value of $y$ $k-1$ times, and we need only consider those $X_i$ for $i \ge n_{k-1}$. We need no future information when determining $T_y^k$, and so $T_y^k$ is a stopping time.

Where are my inconsistencies? Can I make the assumptions I listed in the last paragraph?

-

In order to show that a random time $T$ is a stopping time, you need to be able to write $(T=n)$ as a function of $X_0,X_1,\dots, X_n$ for every $n\geq 0$. This is the same as being able to write $(T\leq n)$ or $(T>n)$ as a function of $X_0,X_1,\dots, X_n$ for every $n\geq 0$.

If $T^k_y$ is the time of the $k$th visit to state $y$ (not counting time 0) we can show this property directly: $$(T^k_y>n)=\left(\sum_{j=1}^n1_{(X_j=y)}<k\right).$$

-
Sorry, I'm new to Markov chains, can you clarify what you mean by this? –  KingOliver Sep 4 '12 at 23:02
So you mean that the event that $T_y^k$ is greater than $n$? If so, I understand thank you –  KingOliver Sep 4 '12 at 23:18
Yes, $(T^k_y>n)$ is shorthand for $(\omega: T^k_y(\omega)>n)$ the event that $T^k_y$ is greater than $n$. –  Byron Schmuland Sep 4 '12 at 23:20