Argthtjtr

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?

Regarding an "intuitive" reason for this relation, note that winning or losing a dollar has an equal chance and is independent of how much your currently have. Thus, the change in probability of winning or losing when starting off with $$1$ more is independent of what your starting value is. Note that if $q_k = 1 - p_k$ is the probability of losing when starting with $$k$, then plugging $p_k = 1 - q_k$ in gives that

$$q_{k-1} - q_k = q_{k-2} - q_{k - 1} = ldots = q_1 - q_2 = q_0 - q_1 tag{1}label{eq1}$$

Note you can reverse all the elements by multiplying by $-1$ to give the exact same relationship as with $p_k$.

Regarding how to get the relationship, this answer originally started with that, as the answer by John Doe states, the difference relation for reaching $n starting with $i is given by

$$p_i = frac{1}{2}p_{i - 1} + frac{1}{2}p_{i + 1} tag{2}label{eq2}$$

based on the probabilities of either winning or losing the first time. Summing eqref{eq2} for $i$ from $1$ to $k - 1$ gives

$$sum_{i=1}^{k-1} p_i = frac{1}{2}sum_{i=1}^{k-1} p_{i - 1} + frac{1}{2}sum_{i=1}^{k-1} p_{i + 1} tag{3}label{eq3}$$

Having the summations only include the common terms on both sides gives

$$p_1 + sum_{i=2}^{k - 2} p_i + p_{k-1} = frac{1}{2}p_0 + frac{1}{2}p_1 + frac{1}{2}sum_{i=2}^{k - 2} p_i + frac{1}{2}sum_{i=2}^{k - 2} p_i + frac{1}{2}p_{k-1} + frac{1}{2}p_k tag{4}label{eq4}$$

Since the summation parts on both sides up to the same thing, they can be removed. Thus, after moving the $p_0$ and $p_1$ terms to the LHS and the $p_{k-1}$ term on the left to the RHS, eqref{eq4} becomes

$$frac{1}{2}p_1 - frac{1}{2}p_0 = frac{1}{2}p_k - frac{1}{2}p_{k-1} tag{5}label{eq5}$$

Multiplying both sides by $2$, then varying $k$ down, gives the relations you stated are used in the solution. However, it's generally simpler & easier to just manipulate eqref{eq2} to get that $p_{i+1} - p_{i} = p_{i} - p_{i-1}$, like John Doe's answer states.

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