From lecture notes I understand that the recurrence relation of Gambler's ruin problem is $$ x_z = p x_{z+1} + (1-p) x_{z-1} $$ where $x_z$ is the probability that a gambler's money can reach $a$ before reaching $0$ if he has $z$ dollars now and $p$ is the probability of winning one game.
If I get it right, the reasoning behind the formula is that at $x_z$, there could only be two outcomes if he plays one more game:
- He wins the game: the probability is $p$ and now he is better off, standing at $x_{z+1}$ instead of $x_z$
- He loses the game: the probability is $(1-p)$ and now he is wrose off, standing at $x_{z-1}$ instead of $x_z$
So $x_z$ and $p x_{z+1} + (1-p) x_{z-1}$ should be equal and thus we get the recurrence relation.
However, I am thinking the problem the other way around: let's say the gambler has $z$ dollars now. So in the last game, he has either $z+1$ dollars and lost the game or he has $z-1$ dollars and won the game. Following this logic, I can write the following formula: $$ x_{z+1} (1 - p) + x_{z-1} p = x_z $$ which is different from the standard one (i.e., $x_z = p x_{z+1} + (1-p) x_{z-1}$). Also, I notice that the standard formula is related to the concept of conditional probability but the formula I come up with is somehow a kind of dynamic programming.
If the one I created is wrong, what's wrong?
Thanks!
For the usual equation, $x_z$ is the probability that the gambler will win, given that his current bankroll is $z$. Either he wins the game, and his probability of winning becomes $x_{z+1}$, or he loses, and his probability of winning becomes $x_{z-1}$. The probabilities are for the upcoming game, not the previous one. $$x_z=px_{z+1}+(1-p)x_{z-1}$$
Your retrospective approach is incorrect. When we look at the term $px_{z-1}$ in your formula, $p$ is the probability that he won the last game, and $x_{z-1}$ is the probability of winning, given that his current bankroll is $z-1$. It's difficult to see what probability the product represents.
Suppose that the gambler's bankroll is $1$, that he wins if he gets to $2$, and that $p=3/4.$ We have $x_0=0,x_1=3/4,x_2=1$. Your formula gives $$x_1=\frac14x_2+\frac34x_0=\frac14$$ which is wrong.
Let $A$ be the event that the gambler gets to $a$, and let $W$ be the event that the gambler wins the current game, so that $\Pr(W)=p$. The law of total probability states that $$\Pr(A)=\Pr(W)\Pr(A|W)+(1-\Pr(W))\Pr(A|W^c)$$ and the formula I gave is a direct translation of this, if $A$ is the event that the gambler wins, given that his current bankroll is $z$.
There is no way to state the formula you propose into this form. You are trying to say that the probability that he wins is equal to the probability that he wins, given that he won the last game, plus the probability that he wins, given that he lost the last game. This is true enough, but it's not the formula you wrote down. The the same formula as before, where now $W$ is the event that the gambler won the last game: $$\Pr(A)=\Pr(W)\Pr(A|W)+(1-\Pr(W))\Pr(A|W^c)$$ However, in computing the probability of success, we don't care whether he won or lost the last game. All that matters is how much money he has now. So the formula translates as $$x_z=px_z+(1-p)x_z$$ which is true, but unhelpful.