In a fair gambler's ruin problem, where the gambler starts with k dollars, wins \$1 with probability 1/2 and loses \$1 with probability 1/2, and stops when he/she reaches \$n or \$0.
In the solution (from Dobrow's Introduction to Stochastic Processes with R), they let $p_k$ be defined as the probability of reaching \$n with \$k in one's inventory. Then they use the fact that $p_k – p_{k-1} = p_{k-1} – p_{k-2} = … = p_1 – p_0 = p_1$.
Intuitively this means the probability of reaching \$n with \$k minus the probability of reaching \$n with \$k-1 is equivalent to the probability of reaching \$n with only \$1.
Is there an intuitive reason why this is the case?
Best Answer
The probability of reaching \$$n$ starting with \$$k$ can be split up by what possible first steps you can take - you either lose the first toss or win, each with probability $1/2$. If you win, you have \$$(k+1)$, so the probability of reaching \$$n$ from here is $p_{k+1}$. If instead, you lose the first toss, then its \$$p_{k-1}$. Then use the Law of Total Probability $P(X)=\sum_n P(X|Y_n)P(Y_n)$ where $Y_n$ is a partition of the sample space. In this case, $Y_1=\{\text{lose toss}\}$, and $Y_2=\{\text{win toss}\}$. Then you get
$$p_k=\frac12(p_{k-1}+p_{k+1})$$ Rearranging this gives $$2p_k=p_{k-1}+p_{k+1}\\p_k-p_{k-1}=p_{k+1}-p_k$$ as required, and iterating it multiple times gets to $p_1-p_0$, and of course, $p_0=0$.