2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The Markov property cannot be proven from those hypotheses. $\endgroup$ – George Lowther Oct 18 '16 at 22:02
  • $\begingroup$ 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 $\endgroup$ – Emilio Oct 18 '16 at 22:07
  • 1
    $\begingroup$ 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. $\endgroup$ – George Lowther Oct 18 '16 at 22:21
  • $\begingroup$ 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 $\endgroup$ – Emilio Oct 18 '16 at 22:29
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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