# Stopping times of Markov chains

I have the following problem:

Consider a state space $E$ and a Markov chain $X$ on $E$ with transition matrix $Q$ such that for every $x \in E$, $Q(x,x)<1$. Define: $\tau:=\inf\{n\geq 1:X_n\neq X_0\}$.

1. Show that $\tau$ is a stopping time
2. Show that, for every $x\in E$, $\tau<\infty$ $P_x -a.s.$
3. Compute the distribution of $\tau$ and that of $X_\tau$ under $P_x$

So for the first point I tried this: $\tau$ is a stopping time if $\{\tau =n\}$ is $\mathbb{F}_n$-measurable $\forall n$. Since the Markov chain is based on its natural filtration we know that $\forall n : X_n$ is $\mathbb{F}_n$-measurable.

Define $A:=\{X_n:X_n\neq X_0\}$ and so $\tau = \inf\{n\geq 1: X_n \in A\}$ so I can write $\{\tau =n\}= \{X_n \in A\}\bigcap \{X_{n-1} \not\in A\}\bigcap...\bigcap \{X_0 \not\in A\}$ And by this equation we see that $\{\tau =n\}$ is $\mathbb{F}_n$-measurable $\forall n$.

For points 2 and 3 I can't get the meaning of $P_x$-a.s. I think it should be easy since by assumption I have $Q(x,x)<1$ (which it should implies that there exist an y s.t. $Q(x,y)>0$. But this is only a thought..

• The definition of A seems unsound. You might want to expand it. At the moment, A is a random subset of the state space, is this what you mean and, if so, what is A exactly? – Did Nov 24 '13 at 10:14
• Yes, I want A to be a subset of my statespace and the complement of $X_0$ does it make sense? – sky90 Nov 24 '13 at 11:10
• Then define $A=E\setminus\{X_0\}$, this is clearer. Indeed, with this definition, $[X_n\in A]$ is in $F_n$ and you are done. To show that $\tau\lt\infty$ almost surely conditionally on $X_0=x$, one may compute $P[\tau=n\mid X_0=x]$ for every $n$, then check that these probabilities sum to $1$. – Did Nov 24 '13 at 11:29
• I don't understand really what do you mean with this sum. Could you say me if this other way make sense? I assume that $\tau = \infty$ Then I can say that $\forall y\in E: P_x(H_y<\infty)=0$ where $H_y=\{n\geq 1: X_n =y\}$ so I can say that X is not irreducible (all states do not communicate) but that's a contradiction since $Q(x,x)<1$ – sky90 Nov 24 '13 at 12:32
• And for point 3.. What is mean to be the distribution of a stopping time? – sky90 Nov 25 '13 at 12:22

From the looong string of comments above, it seems a problem of understanding might be related to the words distribution of a stopping time. Let us explain these. To this end, one should consider a probability space $(\Omega,\mathcal F,P)$, a filtration $(\mathcal F_n)_{n\in\mathbb N}$ on $(\Omega,\mathcal F)$, and a random variable $S:(\Omega,\mathcal F)\to \mathbb N\cup\{+\infty\}$.
Recall that $S$ has a distribution. This is the image of $P$ by $S$, that is, the measure $\mu$ defined by $\mu(M)=P[S\in M]$ for every $M\subseteq\mathbb N\cup\{+\infty\}$. The measure $\mu$ is entirely characterized by the collection of probabilities $\{\mu(\{n\})\mid n\in\mathbb N\}$, or, equivalently, by the collection of probabilities $\{\mu(\{1,2,\ldots,n\})\mid n\in\mathbb N\}$, or, equivalently, by the collection of probabilities $\{\mu(\{n,n+1,\ldots\})\mid n\in\mathbb N\}$.
Furthermore, $S$ is a stopping time with respect to $(\mathcal F_n)_{n\in\mathbb N}$ if and only if the event $\{S\leqslant n\}$ is in $\mathcal F_n$, for every $n$ in $\mathbb N$. Equivalently, one can ask that the event $\{S=n\}$ is in $\mathcal F_n$, for every $n$ in $\mathbb N$.
Consequently, in the present case, question 1. asks to show that $\{\tau=n\}$ is in $\mathcal F_n$, for every $n$ in $\mathbb N$, for some unspecified (but canonical) filtration $(\mathcal F_n)_{n\in\mathbb N}$ I will let you explain, and the first part of question 3. asks to compute $P[\tau=n]$ for every $n$ in $\mathbb N$, or equivalently, $P[\tau\leqslant n]$ for every $n$ in $\mathbb N$, or equivalently, $P[\tau\geqslant n]$ for every $n$ in $\mathbb N$.