I am trying to understand the example 2.2. from this course

It is below. However, I am struggling to understand a key step in the reasoning. Specifically, I don't understand why this statement is true.

If we let f(−B + 1) = α, then it follows that f(−B + r) = αr for all r ≤ A + B.

given this the solution is obvious algebra, but I just don't understand this at all. Any help would be appreciated.

Suppose that a gambler plays the following game. At each turn the dealer throws an un-biased coin, and if the outcome is head the gambler wins $1, while if it is head she loses \$1. If each coin toss is independent, then the balance of the gambler has the distribution of the simple random walk.

For two positive integers A and B, what is the probability that the random walk reaches A before it reaches −B? Let τ be the first time at which the random walk reaches either A or −B. Then Xτ = A or −B. Define f(k) = P(Xτ = A | X0 = k), and note that our goal is to compute f(0). The recursive formula f(k) = 0.5 f(k + 1) + 0.5 f (k −1) follows from considering the outcome of the first cointoss. We also have the boundary conditions f(A) = 1, f(−B) = 0. If we let f(−B + 1) = α, then it follows that f( 1 −B + r) = αr for all r ≤ A + B. Therefore, α = A+B , and it follows that


1 Answer 1


You can prove this by induction, and rearranging the formula to the form:

$$f(k) = 2f(k-1) - f(k-2)$$.

Supposing $f(-B + s) = \alpha s$ for $1 \leq s \leq r-1$ then

$$ \begin{align} f(-B + r) & = 2f(-B + r-1) - f(-B +r - 2) \\ & = 2\alpha(r-1) - \alpha(r-2) \\ & = \alpha r. \end{align} $$


You must log in to answer this question.

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