Imagine you're playing a random game with a very rich person (he has an infinite amount of money).
You have $m$ dollars at first and in each turn of this game, you win one dollar(you earn one dollar) or you lose one dollar(you pay one dollar). The probability of winning one dollar in each turn is $p$ and the probability of losing one dollar in each turn is $1-p$.
You will win the game when your money reaches to $N$ dollars and you will lose when you have no money.
What is the probability of your $(1)$ winning and $(2)$ losing?
I first found out that for example if someone wins with x failiures, then the answer for probability of winning will be equal to :
$\sum_{x=0}^{\infty} p^{N-m+x}(1-p)^{x}$ ${N-m+x}\choose {x}$
but it is not correct because of the occurrences for the steps than someone loses is not completely arbitrary and we can not multiply ${N-m+x}\choose {x}$ in each term of the above sum.
so I need help in solving this problem.
Best Answer
I just report the answer here Gambler's Ruin and Markov Chains by joriki generalized to this problem
The trick here is to consider $w_k$ as the probablity of winning starting with $k$ dollars. Than we have the recurrence relation:
$w_{k}=p w_{k+1}+(1-p) w_{k-1}$, $1 <k<N$
$w_{0}=0$
$w_{N}=1$
The characteristic polynomial of the recurrence is:
$x^2-x/p+(1-p)/p=0$
with roots $x_1=1$ and $x_2=1/p-1$, so that the generic solution is:
$w_k=A+B(1/p-1)^k$
Imposing the boundary conditions we get $B=-A$ and $A=\frac{1}{1-(1/p-1)^N}$
The solution is then: