Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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

Your Answer

 
discard

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.