Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
Sorry, I'm new to Markov chains, can you clarify what you mean by this? – Moderat 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 – Moderat 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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