Mrthdrb

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

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 = frac12p_i - 1 + frac12p_i + 1 tag2labeleq2$$

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

$$sum_i=1^k-1 p_i = frac12sum_i=1^k-1 p_i - 1 + frac12sum_i=1^k-1 p_i + 1 tag3labeleq3$$

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

$$p_1 + sum_i=2^k - 2 p_i + p_k-1 = frac12p_0 + frac12p_1 + frac12sum_i=2^k - 2 p_i + frac12sum_i=2^k - 2 p_i + frac12p_k-1 + frac12p_k tag4labeleq4$$

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, eqrefeq4 becomes

$$frac12p_1 - frac12p_0 = frac12p_k - frac12p_k-1 tag5labeleq5$$

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 eqrefeq2 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=textlose toss$, and $Y_2=textwin 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$.