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?


2 Answers 2


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


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .