# Markov property for the gambler's ruin problem

Let $(X_n)_{n\ge 0}$ be a simple asymmetric random walk on states $0,1,\dots,M$, where $0$ and $M$ are absorbing. Initial state is $i\neq 0,M$. Let $(X_n^*)_{n\ge 0}$ be the process $(X_n)$ conditional on event $A:=\{X_m=M\text{ finally }\}$. That is $$P((X_0^*,X_1^*,\dots,X_k^*)\in B)=P((X_0,X_1,\dots,X_k)\in B|A)=\frac{P(\{(X_0,X_1,\dots,X_k)\in B\}\cap A)}{P(A)}$$ for any $k\ge 0$ and $B\subset \{0,1,\dots,M\}^{k+1}$.

I need to show that $(X^*_n)$ is a Markov chain.

It's clear to me intuitively why it is so: on the event $A$ none of $X_k$'s should be equal 0, and then the Markov property is inherited from $(X_n)$, but I'm struggling with showing it rigorously.

We can prove this by using the Strong Markov Property. So, the Strong Markov Property says that (Theorem 1.4.2 from the book Markov Chain, by Norris'):

Let $$(X_n)_{n\geq0}$$ be $$Markov(\lambda,p)$$ and let $$T$$ be a stopping time of $$(X_n)_{n\geq0}$$. Then, conditional on $$T<\infty$$ and $$X_T = i, (X_{T+n})_{n\geq0}$$ is $$Markov(\delta_i,P)$$ and independent of $$X_0,X_1,...,X_T$$, where $$\delta_i$$ is the unit mass at $$i$$.

Now, we only have to prove that the time time to hit $$M$$ for the first time is a stopping time. The definition of stopping time is:

A random variable $$T:\Omega\to \{{0,1,2,...\}}\cup\{{\infty\}}$$ is called stopping time if the event $$\{{T=n\}}$$ depends only on $$X_0,X_1,...,X_n$$ for $$n=0,1,2,...$$.

Well, the time to hit $$M$$ for the first time is clearly a stopping time, since:

$$\{{T_M=m\}} = \{X_0\neq M,X_1\neq M,...,X_{m-1}\neq M,X_m=M\}$$

Therefore, $$(X^*_n)=(X_{T_M+n})$$ is a Markov chain.