Ruin Again: Part 2 - Classic Random Walk

As I indicated at the end of last month's article, this month I am going to derive the classic ruin formula for the one dimensional random walk. Though this derivation is available in many, many standard references, these references are probably not among most of my readers holdings. So here goes.

Think of a particle moving randomly on the positive x - axis. It moves one unit to the right with probability p and one unit to the left with probability q; p + q = 1. If the particle's position is currently at x, what is the probability that it will eventually be at zero before it reaches some position a to the right of its current position? Zero represents ruin and a represents a level of achievement. You can think of x as a gambler's stake who is trying to increase his stake to a rather than going broke.

Let us define the random variable R(x, a) as the probability of ruin at position x while trying to reach level a. If the particle is currently at position x then at the very next step the particle will be in position x + 1 with probability p or at position x - 1 with probability q. This leads to the difference equation

R(x, a) = pR(x + 1, a) + qR(x - 1, a) (1)

Clearly since p + q = 1, any constant is a solution to this equation. Also any constant times a solution to the equation is also a solution. I will now show you that the function (q/p)^x is a solution to (1).

Since (1) is linear in R the sum of any two solutions is also a solution. Thus a general solution to (1) is given by

R(x, a) = A + B(q/p)^x (2)

We next impose boundary conditions. Clearly if x = 0 we have reached ruin so that R(0, a) =1 since ruin is now certain. Hence

A + B = 1 (3)

On the other hand if we have reached a then our ruin probability is zero so R(a, a) = 0. Thus

A + B(q/p)^a = 0 (4)

(3) and (4) are a pair of simultaneous linear equations in A and B and can easily be solved:

A = - (q/p)^a/(1 – (q/p)^a)    B = 1/(1–(q/p)^a)

Substituting these into (2) we finally have

R(x, a) = ((q/p)^x – (q/p)^a/(1 – (q/p)^a) (5)

Because of the particular form of R(x, a) I’ll use next month, I want to factor (q/p)^a out of both the top and bottom of (5) (they cancel) to obtain

R(x, a) = ((q/p)^{x – a} – 1)/((q/p)^-a – 1)

We can get rid of the negative exponents by flipping q/p to obtain

R(x, a) = ((p/q)^{a – x} – 1)/((p/q)^a – 1) (6)

There is one final adjustment I want to make to (6). If the step size is not 1 but rather is b (for bet size) then (6) becomes

R(x, a) = ((p/q)^{(a – x)/b} – 1)/((p/q)^a/b – 1) (7)

You can think of this as follows. If you risk 150 dollars to make 30 by making 10 dollar bets, this is equivalent to risking 15 dollars to make 3; just divide both x and a by the bet size. Next month I'll put everything together for you. See you then.

Don Catlin can be reached at 711cat@comcast.net