# Fair gambler's ruin problem intuition

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