# Gambler's ruin: verifying Markov property

Gambler's ruin: the gambler starts with $\$i$, where$ 1<i<N$. He wins$\$1$ with probability $p$ and loses $\$1$with probability$1-p$. When he reaches$0$(ruin) or$N$(win), he stops playing. Durrett's book on Stochastic Processes states: Let$X_n$be the amount of money after$n$plays. For any possible history of your wealth,$i_0, \ldots , i_{n-1},i,$$$P(X_{n+1}=i+1 | X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)=p$$ since to increase your wealth by$1$unit you have to win the next bet. Although I see the point, I don't know how to prove the Markov property: $$P(X_{n+1}=j | X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)=P(X_{n+1}=j | X_n=i)$$ given the following hypothesis for the probability distribution of the sequence$\{X_n\}$: • If$1<i<N$, then$P(X_{n+1}= i+1 | X_n=i)=p$and$\ P(X_{n+1}=i-1 | X_n=i)=1-p$• If$i=1$or$i=N$, then$P(X_{n+1}= i | X_n=i)= 1$How do I prove that the Markov property holds? Edit: the states space is$\{0, \ldots, N \}$and the probability distribution for$X_0$is considered given • The Markov property cannot be proven from those hypotheses. – George Lowther Oct 18 '16 at 22:02 • Either the property holds or doesn't hold. What do you mean it can't be proven? Doesn't the hypothesis define a sequence$\{X_n\}$of random variables? Lets add to the question that the probability distribution for$X_0$is given – Emilio Oct 18 '16 at 22:07 • You haven't defined the full distribution, and whether the property holds depends on the full distribution. The distribution of$X_{n+1}$conditional on$X_n$is not enough to determine the full distribution.You need to add something along the lines of the Markov property to the hypotheses. – George Lowther Oct 18 '16 at 22:21 • The way I see it, the distribution for$X_1$is given by$P(X_1=j)=\sum_{k=0}^N P(X_1=j | X_0=k)$and in this way we can recursively define the distribution for$X_2, X_3,$etc. starting from the$X_0$distribution. If I am wrong please tell me how – Emilio Oct 18 '16 at 22:29 ## 1 Answer You can see that Markov property holds, using Durret's condition: Let$X_n$be the amount of money after$n$plays. For any possible history of your wealth,$i_0, \ldots , i_{n-1},i,$$$P(X_{n+1}=i+1 | X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)=p$$ since to increase your wealth by$1$unit you have to win the next bet. Indeed, writing: $$P(X_{n+1}= i+i | X_n=i) = \frac{P(X_{n+1}= i+i , X_n=i)}{P(X_n=i)} = \frac{\sum_{i_k, k \in \{1,\ldots,n-1\}}P(X_{n+1}=i+1 , X_n=i, X_{n-1}=i_{n-1}, \ldots, X_0=i_0)}{\sum_{i_k, k \in \{1,\ldots,n-1\}}P( X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)} = \frac{\sum_{i_k, k \in \{0,1,\ldots,n-1\}}p\cdot P( X_n=i, X_{n-1}=i_{n-1}, \ldots, X_0=i_0)}{\sum_{i_k, k \in \{1,\ldots,n-1\}}P( X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)} \\ =p\frac{\sum_{i_k, k \in \{1,\ldots,n-1\}} P( X_n=i, X_{n-1}=i_{n-1}, \ldots, X_0=i_0)}{\sum_{i_k, k \in \{1,\ldots,n-1\}}P( X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)} = p$$ where we considered the set of every possible outcomes in the$(n-1)\$ bets in the sum and used that

$$p = P(X_{n+1}=i+1 | X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0) = \frac{P(X_{n+1}=i+1 , X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)}{P( X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)}$$ implies $$p\cdot P( X_n=i, X_{n-1}=i_{n-1}, \ldots, X_0=i_0) \\= P(X_{n+1}=i+1 , X_n=i , X_{n-1}=i_{n-1}, \ldots, X_0=i_0)$$