Gambler’s Ruin & Random Walk: Probability, Expectation, Steal the Chips

Estimated read time (minus contemplative pauses): 40 min.

1. Steal the Chips: A Gambler’s Ruin Problem

The YouTube channel LetsSolveMathProblems recently uploaded the following challenge question:

Let n be a positive integer. Angela and Brayden are playing a game of “Steal the Chips” with the following rules:

1) Each person begins with n poker chips.

2) In every turn, either Angela or Brayden is selected with equal probability. The selected person must immediately give one of his or her chips to the other person.

3) The game ends when one person has all 2n chips.

Show that the expected number of turns until the game ends is n²

Here’s the original video: Challenge 98: Steal the Chips.

Shortly after, a solution was posted to the channel: Solution 98: Expected Value in Gambler’s Ruin (Steal the Chips).

User solutions are included in the comments sections of the videos (especially the original one).

I’m a fan of the channel and am usually impressed with its content, but in this case I felt the explanation could have been more helpful. A quick survey of the comments shows that I’m not alone. There is, for example, confusion expressed about a certain intuitive jump the narrator makes near the end of the solution, and some commenters imply that standard methods of counting the paths of a random walk can be used (such methods cannot be used, though this problem does involve a random walk). More about these points shortly.

I thought it’d be fun to share my own solution to the problem, which involves a common method of solving Gambler’s Ruin–type problems. Before getting to that, it’d be illuminating to think more about an attractive approach that doesn’t work. Namely, one I referred to a moment ago that uses basic counting methods associated with basic random walks. Along the way, I’ll give a quick review of any relevant concepts that go beyond the basics of probability.

I’ll probably over-explain some things her while under-explaining others. Feel free to comment with questions, corrections, alternative solutions, etc.

2. Expectation: A Quick Review

The question is asking us to think about the expected number of turns for the game to end (i.e., for one of the players to acquire all 2n of the chips). “Expectation” or “expected value” just means “average”: how many turns will this game last, on average, when each player has n chips?

In simple cases, we calculate expectation by first multiplying each possible outcome of an “experiment” by that outcome’s probability of occurring (this probability is called a “weight,” which makes this a “weighted average”); next, add up those results to get the “expected” value of the event. This is not a sophisticated definition, but it will do.

There’s nothing special about this if you know how to take an average. All averages are weighted, it’s just that middle school averages deal in outcomes that all weigh the same.

Suppose you want to know the expected value of a fair die, where the value of a given experiment (i.e., roll) is determined by the numbers on each of the die’s faces: 1, 2, 3, 4, 5, 6. Each of those outcomes has a probability of 1/6. So, the expected value of the die is just: 1(1/6) + 2(1/6) + 3(1/6) + 4(1/6) + 5(1/6) + 6(1/6) = 3.5. (There are varying ways to talk about this stuff. We might say we’re referring to the average outcome of each role, or to the long-run average of the die’s outcomes were you to roll it many times.)

Notice that this is no different than a run-of-the-mill average, where you add up 1 + 2 + 3 + 4 + 5 + 6 = 21, and then divide by the number of elements: 21/6 = 3.5. This simple approach works because each outcome weighs the same.

But suppose the die is not fair, so that there are different probabilities for each side coming up in a toss. You’d use the same method, substituting in the relevant probabilities. You could then give them all the same denominator in order to get it to look like the middle school average. A while back I promised to write up a post (coming soon-ish) that goes deeper into what I mean here and to make all this more intuitive, but for now perhaps the following observations will suffice.

The basic takeaway so far is that the simplest expectation problems are solved by representing the possible outcomes numerically (e.g., 1, 2, 3, 4, 5, 6), then weighting each of those by their probability of occurring (1/6 for each in this case), and summing the result.

Determining the relevant probabilities is harder when there is more than one way for an outcome to come about. For example, with two dice, there is one way for a roll to sum to one—i.e., each die lands on a 1. And there are six ways for the dice to sum to seven: {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)}. Note that each of those specific outcomes, e.g., {(1,6)} has a probability of 1/36 of occurring.

So, the probability of the outcome summing to two is 1/36 (there is only one way for it to happen). And the probability of a throw summing to seven is [(1/36) × (the number of ways to get a seven = 6)]: (1/36)(6) = 6/36 = 1/6.

If you want the expected value of two dice, you have to figure out the number of ways to to sum to two, to three, to four, …, to 12 (that’s when you roll two sixes). If you haven’t tried this before, it’s a useful exercise. You should get 7. (Notice that this is just the sum of the expected expected value of each die! This isn’t a coincidence, but is due to something called linearity of expectation.)

To drive this home, I’ll demonstrate the solution, where for each term I’m multiplying the (sum of the two faces) × (number of ways to get that sum) × (probability of any particular result when rolling two dice = 1/36):

(2)(1)(1/36) + (3)(2)(1/36) + (4)(3)(1/36) + (5)(4)(1/36) + (6)(5)(1/36) + (7)(6)(1/36) +(8)(5)(1/36) + (9)(4)(1/36) + (10)(3)(1/36) + (11)(2)(1/36) + (12)(1)(1/36) = 7

The probability of each outcome there is the (number of ways an outcome can occur) × 1/36. So, the probability of two dice rolls summing to to 8 is (5)(1/36) = 5/36. I’ll rewrite the entire thing, then, as the (sum of the two faces) × (the probability of that sum occurring):

(2)(1/36) + (3)(2/36) + (4)(3/36) + (5)(4/36) + (6)(5/36) + (7)(6/36) +(8)(5/36) + (9)(4/36) + (10)(3/36) + (11)(2/36) + (12)(1/36) = 7

Now put it all into one fraction:

Again, this is looking more and more like a middle school average. There are 36 outcomes, and we divide by 36. One of those 36 outcomes sums to two, while two of them sum to three, three of them sum to four, and so on. We could list out the numerator as 2 + 3 + 3 + 4 + 4 + 4 +… and so on (it would be 36 numbers in all!), but instead we just multiply each of those results by the expected frequency among the overall outcomes, then divide by the total number of outcomes, which is 36.

Notice, too, that we could double the number of times each outcome is represented—i.e., 2 + 2 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 +… and so on, resulting in 72 values—so long as we also double the denominator so that we are dividing by 72. Same goes for tripling, quadrupling, cutting in half, and so on. What matters is that the proportions are maintained. You’ll always get to a final answer of 7.

So there you have a quick overview of expectation, with emphasis on the fact that it’s just an average. There’s more to say about even the basic concept of expectation—e.g., it’s worth thinking about why the weight of an outcome is its probability of occurring (if you roll two dice many times, you’d expect to see a sum of 4 about 3/36 of the time, which is to say you’d expect it to account for about 3/36 of the results in the numerator when you take the average)—and there are of course much more advanced dimensions of the topic we won’t talk about here today.

3. Random Walk And Gambler’s Ruin

3.1 Random Walks on a Regular Grid

I’ve noted that, the above method of counting up ways to get the results in question will not solve the problem at hand.  As noted above, however, several LetsSolveMathProblems subscribers assumed it would. They just needed to figure out the pattern behind the number of ways each outcome could come about—that is, a pattern that tells you the number of ways to win (or lose) in a given number of moves, and thus the probability (or weight) corresponding to that number of moves.

The problem is that there is no such pattern for some arbitrary n (if you know of one, let me know!), though it will work for a specific, reasonably sized n. It’s instructive to look at what’s going on here.

I will consider n = 2, 3, 4, and 5. We can use good old fashioned expectation and counting methods, just as above, for these, but different n‘s require different formulas. Actually n=2 and n=3 use the same formula (they follow the same pattern), but 4 and 5 each produces a new pattern.

To get started in figuring these out, let’s review random walks. A random walk is a situation in which you start at some point on the number line and end up at another point in a certain number of steps. There’s a lot to cover in this simple idea. I’ll only review the basics.

Let’s first look at the simple case of going from 2 to 4 in two steps. We don’t need a sophisticated diagram to see the number of ways to do this:

Next we’ll work out the number of ways (or paths) for getting from 2 to 4 in four steps (notice that it is impossible to get there in three steps!): from 2 to 3 to 4 to 5 to 4: OR from 2 to 3 to 4 to 3 to 4; OR from 2 to 1 to 2 to 3 to 4; OR from 2 to 3 to 2 to 3 to 4. Here’s an illustration:

There are four ways to do that. Notice that in each one of these four ways, we go one to the left (or back) and three to the right (or forward). In other words, we can count how many ways to get from 2 to 4 in four steps by just choosing one of them as our leftward move: ⁴C₁ = 4*.

[*This denotes a combination, and is usually stated as “four-choose-one.”  Of course, we could just as well do ⁴C₃. You’ll more often see these represented in math problems as .

The formula for these calculations is:

If you’re not familiar with, or need to review, basic combinatorics, I recommend starting with this Khan Academy video, which deals with Permutations, and working through to the next section on Combinations: “Factorial and Counting Seat Arrangements.”]

Now, if we want to get from 2 to 4 in six steps (notice again, we can’t do it in five steps), we can just figure out how many forward and back steps are needed. For example, we can go from 2 to 3 to 4 to 5 to 6 to 5 to 4. That’s four forward and two back. We see the same result if we go 2 to 1 to 0 to 1 to 2 to 3 to 4.

This gives us ⁶C₂ = 15. Instead of writing those 15 paths with the same method as above, I’ll use a grid (made at GeoGebra) in which the x-axis represents the first, second, third, fourth, etc. step taken; and the y-axis represents location. For example, here’s a diagram for starting at 2 and ending at 4 four steps:

The above graph contains all possible paths for getting from 2 to 4 in four steps. Here is the same diagram with two paths highlighted:

The pink path goes from 2 to 1 to 2 to 3 to 4; the green path goes from 2 to 3 to 4 to 3 to 4. Because the location axis is vertical, we can think of this as up three, down one (note that each new move must go to the right with respect to the x-axis; otherwise, it would be like going back in time).

Luckily, there is a simple way to count the number of paths on a grid. We can call this the Pascal’s Triangle method of counting; as such, it’s also intimately related to the binomial theorem and to combinations (which makes sense, given that we’ve been using combinations as a shortcut thus far).*

[*I’ll try to explain the method clearly here, but it might be extra helpful to see this method explained and performed in real-time, which you can do in the following YouTube videos, which also cover the irregular cases—e.g., cases in which grids overlap or appear to have chunks removed (it will soon be clear that our Gambler’s Ruin problem involves an irregular random walk):

“Math Principles: Paths on a Grid: Two Approaches” by readingrocks88: Nicely gets across the basic idea in just over five minutes.

“Math 12 Apr 7 U4L5 Pascal and Pathways” by Kelvin Dueck: A longer video (about 37 minutes) that goes more into Pascal’s Triangle.

“The mathematical secrets of Pascal’s triangle – Wajdi Mohamed Ratemi” by TED-ed: This short video (just under five minutes) isn’t about paths on a grid, but gives a nice overview of Pascal’s Triangle (includes a bit about binomial expansion and points out that Pascal was by no means the first to discover this mathematical tool).

A search will yield many other tutorials.]

All we need to do is count the number of ways to get to each point, until we’ve arrived at the final point. Here again is the same diagram from 2 to 4 in four steps, with the counting method included (if this doesn’t clear things up right away, it will hopefully get clearer as we look at more examples):

Now let’s apply this to getting from 2 to 4 in six steps. I already calculated that this is ⁶C₂ = 15. When drawing such a diagram, I like to start with the path that includes the lowest location I can get to—here that’s 0, as we can go from 2 to 1 to 0 to 1 to 2 t0 3 to 4—along with the highest location we can get to, which is 6 (i.e., from 2 to 3 to 4 to 5 to 6 to 5 to 4):

Then I fill in the rest of the grid. Here’s the whole grid, with numbers filled in to indicate the path to each point:

3.2 Random Walks to a Gambler’s Ruin: Counting Paths on an Irregular Grid

We are finally ready to return to our Gambler’s Ruin problem. As I noted above, the problem we’re interested in does not produce a regular grid, due to our boundary conditions.

Recall that we are starting with n chips (i.e., at location n on our grid), and the game ends when we hit 2n or 0. In other words, if we start at 2 chips, the game ends when we have 4 chips or 0 chips. Let’s focus for now just on what this means for winning. In fact, I’m only going to represent winning in these diagrams (an easy thing to account for later, when calculating the overall expectation).

If the game ends when we hit 4, that means we have a boundary condition that we do not have with basic random walks. For example, look again at getting from 2 to 4 in four steps. We can take a path from 2 to 3 to 4 to 5 to 4: OR from 2 to 3 to 4 to 3 to 4; OR from 2 to 1 to 2 to 3 to 4; OR from 2 to 3 to 2 to 3 to 4. But only two of these are valid, because once you hit 4, the game ends! I’ve crossed out the invalid paths. If we don’t remove those, we over-count. And if we were looking at getting from 2 to 4 in six steps (or turns, really), we’d have to remove anything that hits 0 or 4 before turn number six.

What to do? First, let’s take a step back to remind ourselves of what we’re looking for. We’re trying to formulate a simple bit of expectation, as described in the dice scenarios above. This means that, for starting with two chips, we need to fill in the following (again, I’m focused for now only on winning; recall that “winning” here means “getting from n to 2n; in this particular case, that means going from 2 to chips 4 chips):

[2 × (probability of winning in two turns)] + [4 × (probability of winning in four turns)] + [6 × (probability of winning in six turns)] + …. on forever (we can’t restrict how long the game will last; it can be shown that the game won’t last forever, but we need not worry about this here.)

All we’re missing is the probability of winning in each number of turns. This breaks down to the (the number of paths to win in that many turns) × (1/2 to the power of the number of turns). Where did the 1/2 come from? Easy: the probability of winning a turn is 1/2. So the probability of winning in two turns is the (number of paths to win in two turns) × (1/2)². This is all analogous to what we saw above with the probability of two rolled dice summing to a given number.

I should also note that for more than two turns, the 1/2 will still be raised to the number of turns, because there is also a 1/2 probability of losing a given turn. For example, the probability of winning two turns and then losing four turns is (1/2)⁶; this would of course work out differently were the probability of winning and losing not the same! (See below for a little more on that point.)

This in mind, we end up with:

[(2) × (number of paths that win in two turns) × (1/2)² ] + [(4) × (number of paths that win in four turns) × (1/2)⁴] + [(6) × (number of paths that win in six turns) × (1/2)⁶ ] + …. and onward with this pattern.

There is an obvious pattern here for everything except the number of paths to win in a certain number of turns. Let’s find that pattern. I’ll make a diagram for winning in two moves, four moves, six moves, and eight moves, and will count the paths for each exactly as I did with the regular grids above.

There is one way (or path) to win (i.e., to get from 2 to 4) in two moves (notice that the path to losing is symmetrical to the path for winning; I’m not including losing paths here, but this fact will help us count the paths to game’s end later):

There are two paths for winning in four turns:

There are four paths for winning in six turns:

A pattern is emerging. A new square is added each time we increase the number of turns. And, for anything greater than four moves, that new square bumps what we did in the preceding graph two units to the right. It’s safe to assume that this will keep happening over and over again, but let’s do a couple more.

Notice, too, that we are essentially bouncing around between 1 and 3 before crossing over to 4 for the win. In other words, if we pass 3, we win (and if we pass 1, we lose). I’ll demarcate those boundaries here as well:

I’d say the patter is now well established. In fact, we could have just mapped out several steps at once in order to see the pattern. Here is a diagram for winning in up to ten turns (or “moves,” as I put it in the diagram):

We now have 1 way to win in two turns; 2 ways to win in four turns; 4 ways to win in six turns; 8 ways to win in eight turns; 16 ways to win in ten turns. The ways to win are doubling, which is to say we have this sequence: 2⁰ ways to win in two moves, then 2¹, 2², 2³, 2⁴, 2⁵, … and so on.

This makes it easy to find expectation with a calculator. Recall what we are missing:

[(2) × (number of paths that win in two turns) × (1/2)² ] + [(4) × (number of paths that win in four turns) × (1/2)⁴] + [(6) × (number of paths that win in six turns) × (1/2)⁶ ] + …. and onward with this pattern.

We can fill that in as:

[(2) × (2⁰) × (1/2)² ] + [(4) × (2¹) × (1/2)⁴] + [(6) × (2²) × (1/2)⁶ ] + ….

I’m going to rewrite this which different bracketing (and a few more terms) in order to make the probabilities more salient:

(2 × [2⁰ × (1/2)²]) + (4 × [2¹ × (1/2)⁴]) + (6 × [2² × (1/2)⁶]) + (8 × [2³ × (1/2)⁸]) + (10 × [2⁴ × (1/2)¹⁰]) + (12 × [2⁵ × (1/2)¹²]) + …

The probabilities (i.e., the weights for our average) are in square brackets. The probabilities alone continue indefinitely in the form 2ⁱ × (1/2)²⁺²ⁱ, where i starts at 0, which is one less than the turn number. Just as with the dice examples above, these probability are multiplied by the number of turns involved: 2, 4, 6, 8, 10, 12, …

Since the power to which we raise 1/2 is equal to the number of turns involved, we can represent the number of turns with (2+2i).

I’m probably making this more complicated than it needs to be. The upshot is that we end up with a final expression of: (2+2i) × 2ⁱ × (1/2)²⁺²ⁱ. To add this up for large i‘s, simply pop this into a sigma calculator (if you need a refresher on sigma notation, see this page at Math Is Fun; calculator-wise, I like Desmos):

I constructed it so that the number of turns is on the left and the probability (slightly simplified) is on the right. Recall that we know the final answer should be 2², or 4. The answer here is 2 because we’ve only included the number of ways to win. Losing here is symmetrical to winning, so all we need to do now is double the number of ways to win; this updates our probabilities to reflect the number of ways to win or lose, which effectively doubles the final result of the above expectation, which yields 4. And that’s that.

When each player has two chips, we expect the game to last about four turns on average.

(Note that if we remove the (2+2i) from the expression, the series converges to 1, which is something we require of a valid probability distribution. That is, the probability that you win or lose in 2 or 4 or 6 or 8 or so on turns is 1:

This time I put the 2 out front to account for both winning and losing. This approach also works for the series considered below.)

Interestingly, we get the same pattern when starting with three chips, just replace the 2 with 3. I’ll go right to the extended diagram this time:

Pop this into a sigma calculator with appropriate adjustments (and multiplying by 2):

As expected, we get n², which in this case is 3² = 9.

But look at what happens when n = 4:

This is a new pattern: 1, 4, 14, 48, 164, 560, 1912 (I calculated the 1912 in order to refine the search I’m about to do).

To figure out what sequence this is, I’ll pop it into The On-Line Encyclopedia of Integer Sequences, which yields a sequence that starts: 1, 4, 14, 48, 164, 560, 1912, 6528, …

This is sequence number A007070, which can be found here with discussion and formulas and whatnot (also included is a nearly identical sequence, but with an extra 1 at the beginning). I’ll go ahead and pop a formula for this sequence into our sigma notation as well, just for comparison’s sake.

Let’s express the sequence as a function f:

This gives: f(0) = 1; f(1) = 4; f(2) = 14; f(3) = 48; … and so on. So, f(i) will be used in the sigma notation instead of 2ⁱ or 3ⁱ:

As assumed, we get 4² = 16. The main point, however, is that we can’t use the same setup for n = 4 that we used for n = 2 or 3. This is also true for n = 5, which I’ll graph for up to 15 turns:

Here we get: 1, 5, 20, 75, 275, 1000. A search for this at eois brings up sequence number A030191, which is actually the same as sequence A093131, but without the starting number of 0; both sequences can be found here. I won’t bother with popping this one into our sigma notation.

It’s clear by now that there’s no obvious pattern (to me) that we can use by this method to answer the question at hand, though it’s been instructive (to me) to work through the diagrams to more intuitively understand the problem and to get practice with counting and alternative ways of modeling such problems, etc. It has also answered the question of why we can’t solve it in the same way as we would a basic random walk: we cannot pass 1 or 2n-1 until the next-to-last move before game’s end, which leads to over-counting when using standard methods. Still, it’s a pretty deterministic and well-controlled setup—and thus, good practice but also a nice reminder of how much messier and complex real-world situations must get.

At any rate, while I’m tempted to see how much more I can pull out of the above patterns, I’ll move on to finally solving the problem.

4. Gambler’s Ruin: Steal the Chips

To solve the problem, I’ll use a first-step analysis (or conditioning) to produce a difference equation (the discrete analog a differential equation). This approach isn’t unique. As I go along here, I’ll share sources for learning more about the techniques involved, including in application to Gambler’s Ruin–type problems. (To be clear, these are not the only techniques one may use to solve the problem, as demonstrated by various comments at the original “Steal the Chips” challenge video, or by doing a YouTube search for “Gambler’s Ruin.”)

First-step analysis is a common way to find expectation. The basic idea is something like this.

Suppose we want to find the expected number of flips of a fair coin to see two Heads in a row (which actually makes this two-step conditioning, but it’s the same idea as with “first-step” analysis). We know that it takes E flips to see two Heads in a row (that is, we assume that there is some number E that we can discover mathematically; in other terms, we assume that there is some mathematically calculable number E that, were we to flip a coin many times, we would observe as the average number flips it takes to see two Heads in a row).

There are three things that can happen within our first two flips. If we flip Heads in each of our first two flips, we’re done, and we did it in two flips. If we flip a Heads and then a Tails, we’re right back where we started, and the expectation is now (E + 2), because we wasted two flips. If our first flip is Tails, we’re also we’re right back where we started, and we still expect it take E flips to see two Heads in a row, so our overall expectation is (E + 1) flips.

These observations can be used to make an equation. Let E stand for the expected number of tosses to see two Heads in a row, and let P_x stand for the probability of event x occurring. We’re looking for:

E = P_HH(2) + P_HT(E + 2) + P_T(E + 1)

The stuff in parentheses just represents the number of flips involved in a given scenario. Again, if we get two Heads in a row, it took two flips; if we get Heads then Tails, we expect it to take (E + 2) flips overall; if we get a Tails on our first flip, we expect it to take (E + 1) flips overall. Then just solve for E. I’ll assume that the coin is fair. If the coin weren’t fair, I’d assign probability p to Heads and probability (1 – p) to Tails.

(See that done in this paper, along with a general result for finding expectation to arbitrary numbers of Heads or Tails in a row: “How many coin flips on average does it take to get n consecutive heads?,” which appear to be lecture notes by Paul Ginsparg.)

E = P_HH(2) + P_HT(E + 2) + P_T(E + 1)

E = (.25)(2) + (.25)(E + 2) + (.5)(E + 1)

E = .5 + .25E + .5 + .5E + .5

E = 1.5 + .75E

.25E = 1.5

E = 6

I’ve also used this technique with examples of so called counterintuitive dice problems at the end of this post and at the end of this post (the first deals with expectation, the second with probability).

Let’s apply first-step analysis to our Gambler’s Ruin problem, where we expect the game to end in E turns when one of the players has n chips (notice that I’m focused now on the game ending, not just on a specific player winning, as above). Here goes.

(1) Let E_k represent the expected number of turns it’ll take for the game to end, given that one of the players has k chips. Where 0≤k≤2n, because the game ends when either player has 2n chips (in which case the other player must have 0 chips). That is, the total number of chips available is 2n.

Notice that this involves conditioning: we’re formulating the expected number of turns to game’s end conditional on a player having k chips. In fact, another way to refer to this sort of first-step analysis is as “expectation by conditioning.”

(2) We aim to prove is that E_n = n². But before considering n chips, let’s think more generally, in terms of k chips.

(3) We can use our boundary conditions to define some values for E_k:

E₀ = 0 (because the game is obviously expected to last zero turns once a player has no more chips).

E_2n = 0 (because when one player has 2n chips, the other player has zero chips).

(4) We are also given some probabilities:

Let p be the probability of a given player winning a given turn. Let q be the probability of a given player losing a given turn. Note that p = q = 1/2, a fact whose implications I’ll rely on whenever convenient; for example, this means that p + q = 1 and that q = 1 – p (notice that these implications will also be true when p ≠ q). For now, I’ll stick to using “p” and “q” rather than inserting 1/2, so that we can better see what’s going on more generally (i.e., when p ≠ q).

(5) Now for the first-step analysis. When a player has k chips, the expected number of turns to game’s end is E_k. Assuming the game is not already over, when that player wins a turn (with probability p), the expected number of turns to game’s end goes from E_k to E_k+1 + 1.

For example, suppose the goal is to win 6 chips. When a player has 3 chips, the expected number of turns to game’s end is E₃. If that player wins the next turn, then the number of expected turns to game’s end is E₄ + 1. Just as with the coin example above, the 1 is added to account for the fact that 1 turn has already occurred—i.e., the turn that took that player from 3 to 4 chips.

(6) The same reasoning applies to losing a turn at k chips, giving: E_k-1 +1.

(7) Notice that either the player with k chips will win or lose on the next turn. We can use this fact to make a difference equation. That is, the law of total expectation tells us that E_k amounts to the player with k chips either winning the next turn and then having E_k+1 + 1 overall expectation to game’s end, or losing the turn and then having E_k-1 + 1 overall expectation to game’s end. Here is the resulting equation (recall that expectation is a weighted average of the possible outcomes, and that the probability of winning a turn here is p, the probability of losing a turn is q):

E_k = p(E_k+1 + 1) + q(E_k-1 + 1)

Now distribute the p and q:

E_k = pE_k+1 + p + qE_k-1 + q

Simplify further by replacing the q with (1 – p) and combining like terms:

E_k = pE_k+1 + p + qE_k-1 + 1 – p

E_k = pE_k+1 + qE_k-1 + 1

This is called a difference equation, and it defines E_k for 0<k<2n; that is, between our boundary conditions of E₀ = 0 and E_2n = 0.

(8) Here is where things get a little tricky, unless you’re used to dealing with these sorts of problems. Namely, what we specifically have here is a non-homogeneous (sometimes called inhomogeneous) linear recurrence relation.*

[*I will cover enough here to solve this and similar problems, but if you want to go deeper into these (and other) techniques for solving linear recurrence relations, I recommend two playlists at YouTube:

Discrete Math 2 by TheTrevTutor: Start at the 17th video—called “[Discrete Math 2] Recurrence Relations”—and watch to the 22nd video, called “[Discrete Math 2] Nonhomogeneous Recurrence Relation Examples.” Clearly explained with fun examples. To go even deeper, watch also videos number 11 and 23 to learn about recurrence relations and generating functions.

Recurrence Relations by Mayur Gohil: Sixteen videos giving an excellent overview of the topic (includes examples). The technique I’m using today involves finding characteristic roots. Gohil also explains techniques involving iteration and generating functions. Also included is a video on finding an explicit solution to the Fibonacci sequence using the generating function approach.

As an added bonus, here’s a fascinating little (seven minutes) video on generating functions by YY Ahn: “A brief introduction to generating functions.”

If you watch all that, what I do next will seem easy.]

The first thing we want to do is to rearrange our equation to get all the E_k terms on one side.

pE_k+1 – E_k + qE_k-1 = -1

That fact that it is not equal to zero is what makes it non-homogeneous. If we ignore the -1, we get a homogeneous linear recurrence relation: pE_k+1 – E_k + qE_k-1 = 0.

Our task to find a solution to both the homogeneous and non-homogeneous equations, and then to add those results to get a final solution. These results, by the way, are known as our “homogeneous” and “particular” solutions, respectively. More on this when we get to that step.

(9) First let’s find the homogeneous solution. Notice that it has a form similar to a quadratic equation (i.e., a second-degree polynomial): ax² + bx¹ + cx⁰. Observe that the descending degrees of the exponents in our equation matches the descending k values a quadratic equation: (k + 1), (k), and (k-1). (In fact, we are working with a second-degree recurrence relation.)

This leads to us to a standard “guess” of E_k = r^k. This is a standard move, which is briefly discussed in this under-four-minutes video by GVSUmath: “Characteristic equation and characteristic roots of recurrence relations” (which I think worth watching in addition to the above-recommended videos).

If E_k = r^k, then E_k+1 becomes r^k+1 and E_k-1 becomes r^k-1, resulting in:

pr^k+1 – r^k + qr^k-1 = 0

To make this easier to work with, we can divide each term by r^k-1 (i.e., by the r-term of the smallest degree; this is also standard practice):

pr² – r¹ + qr⁰ = 0

pr² – r + q = 0

This is called our characteristic equation (or characteristic polynomial), and will be nicely solved by the quadratic formula. Before doing so, I’m going to use some foresight to make it even nicer by replacing q with (1 – p):

pr² – r + (1 – p) = 0

Recall that the quadratic formula starts as ax² + bx + c = 0, and then (after completing the square) ends up as:

For us, this means:

a = p

b = -r

c = (1 – p)

Which gets plugged in as:

This gives us two solutions:

And:

So, we get r = 1 and r = q/p.

(10) Now that we have our roots (or “characteristic” roots), we can fill out our homogeneous solution. This move exploits our understanding from linear algebra that any linear combination of the solutions to a linear difference equation is also a solution to that equation.*

[*If you’d like to see a discussion of this, try this thread at the Mathematics Stack Exchange: Why is a linear combination of solutions also a solution? And here’s a short proof at ProofWiki: Linear Combination of Solutions to Homogeneous Linear 2nd Order ODE. These links refer to differential equations, but the idea is similar; note that our homogeneous equation is a second-order difference equation because the history it contains goes back two steps in the recursive sequence.

There’s also a proof in these notes by Niloufar Shafiei, which deal specifically with homogeneous and nonhomogeneous linear recurrence relations, but they can be difficult to follow until you have a good handle on what’s going on here (includes a closed-form solution to the Fibonacci recurrence relation, using the characteristic roots method I’m outlining here): Solving Linear Recurrence Relations.]

The way to do this is to plug the roots into our “guess” of r^k, then assign coefficients (I’ll use A and B):

A(1)^k + B(q/p)^k

Let’s pause to reflect on the fact that, in the scenario we’re given, p = q. This means that q/p = 1. Which gives us a double root. Double roots require special attention, for reasons that will become apparent as we go along. (Below, when I consider the probability of winning the game, I’ll demonstrate the procedure for when p ≠ q.) This means we can revise our expression to:

A(1)^k + B(1)^k

The way we deal with a repeated root is by multiplying one of the expressions by k, like so:

Ak(1)^k + B(1)^k

This simplifies to Ak + B. That’s our homogeneous solution. The terminology can get confusing here (let me know if I make any errors!), so to clarify, the homogeneous equation is the one we got when taking our original equation pE_k+1 – E_k + qE_k-1 = -1, and replacing the -1 with a 0: pE_k+1 – E_k + qE_k-1 = 0. The solution we found to this, Ak + B, is our homogeneous solution.

We now need to put the -1 back in and find our particular solution for the entire equation. Recall that our final solution will be derived by adding our homogeneous solution and our particular solution.

(11) Now to find the particular solution, which is just the solution to pE_k+1 – E_k + qE_k-1 = -1.

Once again, there’s a standard guess for what E_k equals here, given the particular form of the homogeneous portion of this relation and the fact that it has double roots (see the table in this video, which is part of Gohil’s above-recommended playlist). The appropriate guess here is ak². Plug this in, just as we did with r^k in the homogeneous equation:

Start with: pE_k+1 – E_k + qE_k-1 = -1

Guess that E_k = ak². This means that E_k+1 = a(k+1)² and E_k-1 = a(k-1)²

Update the original equation accordingly and then simplify by distributing and combining like terms; I’m also going to go ahead and change the q to a p since they are equal (were they not equal, we’d at some point change all q’s to (1-p)) :

p(a(k+1)²) – ak² + p(a(k-1)²) = -1

p(a(k² + 2k + 1) – ak² + p(a(k² – 2k + 1) = -1

p(ak² + 2ak + a) – ak² + p(ak² – 2ak + a) = -1

pak² + 2pak + pa – ak² + pak² – 2pak + pa = -1

2pak² + 2pa – ak² = -1

Replace p with 1/2 and combine like terms:

2(1/2)ak² + 2(1/2)a – ak² = -1

ak² + a – ak² = -1

a = -1

(12) We can now replace the a in ak² with -1 to get our particular solution: ak² = (-1)k² = -k².

Our particular solution, then, is -k².

(13) As already noted, our next move is to add the homogeneous and particular solutions to get the “general” solution to the non-homogeneous equation, and to then use our given initial conditions—which in this case are also our boundary conditions—to fill in missing coefficients and get the final (or “closed-form” or “explicit”) solution we’re looking for:

Homogenous solution: Ak + B

Particular solution: -k²

Add those to get the general solution to the non-homogeneous recurrence relation: E_k = Ak + B – k²

We know that E₀ = 0, therefore:

E₀ = 0 = A(0) + B – (0)² = B = 0

So, B = 0. Put that into our solution and update:

E_k = Ak + 0 – k²

E_k = Ak – k²

Now solve for A:

E_2n = 0 = A(2n) – (2n)² = 2n(A – 2n) = 0

Divide both sides of 2n(A – 2n) = 0 by 2n to get:

A – 2n = 0

A = 2n

So, A = 2n. Put this into the solution so far to finish up with our closed-form solution:

E_k = Ak – k²

E_k = (2n)k – k²

Let’s factor out a k to get a better look at what’s going on:

E_k = k(2n – k)

This tells us that, for any k (between 0 and 2n, inclusive), the expected number of turns to see the game end is k(2n – k), where 2n is the total number of available chips (which can be any number you like that’s greater than or equal to k).

There’s a satisfying symmetry to this result: the expected number of turns to game’s end at any point is the number of chips Angela has times the number of chips Brayden has. This is, in fact, the aforementioned intuitive guess made by LetsSolveMathProblems; the guess was made directly after working out the difference equation. Many folks will no doubt see the guess as coming somewhat out of the blue.

The result may be less surprising if we consider that the total needs to come to 0 for both 2n and 0. Another helpful observation is that the prompt tells us that the answer will be n², which in that particular case just is the number of chips each player has squared—when Angela has n chips and Brayden has n chips. It’s also true that when Angela has n chips, Brayden has 2n–n chips (and vice versa). So it’d be a reasonable guess that when Angela has k chips and Brayden has 2n-k chips (or vice versa), the same approach will hold—i.e., to multiply together their holdings.

Still, it’s not the most obvious thing, and it would be even harder to arrive at if we weren’t given n² in the prompt.

(14) Which reminds me. We’ve got a final step to perform. We’re interested in the case in which k equals half the amount of available chips; i.e., when k = n. Plug in n to fulfill our goal of showing that the resulting expectation is n²:

E_n = n(2n – n) = n(n) = n²

And there you have it!

Now there’s the question of what to do when p ≠ q. I won’t cover that here, but will share some resources at the end of this writing that do.

5. Gambler’s Ruin: Probability of Winning (when p = q and when p ≠ q)

Let’s now calculate the probability of a player winning the entire game given k dollars and with a total of N dollars available, both for when that player’s probability of winning a given turn is 1/2 and for when it’s not 1/2.

What I cover here can be further generalized, for example by not assuming a lower bound of zero dollars (maybe a player wants to stop after getting down to a certain amount of money). Such cases will also be addressed by the resources I share at the end of this writing.

The Probability of Winning a Gambler’s Ruin–Type Game:

(1) Suppose A and B are playing a game in which, at each turn, either A or B is selected. The selected player must give $1 to the other player.

(2) The probability that A wins a turn (i.e., is not selected) is p. The probability that A loses a turn is 1 – p. For convenience, let (1 – p) = q.

(3) Let N be the total amount of money available. In other words: (A’s money in the game) + (B’s money in the game) = N.

(4) The game ends once one of the players has N dollars (which means the other player has zero dollars). Whoever has N dollars is the winner.

(5) What is the probability that A wins, given that A has k dollars? Notice that if A has k dollars, then B must have N – k dollars. (Notice also that this involves conditional probability: What is the probability that A wins conditional on having k dollars?)

(6) Let P_k = the probability of winning the game given k dollars, where 0≤k≤N.

(7) Once again, we’ll use first-step analysis. Nicely, we have less to worry about than when finding expectation (namely, we won’t end up with a non-homogeneous equation). That said, it might take bit of thought for the first-step approach to feel intuitive. One way to develop that intuition is to attempt to draw a probability tree of the things that can happen. The tree will grow large and unwieldy very fast, but it also illustrates what’s going on recursion-wise. (I won’t do that here, but did do it the first time I encountered this sort of problem.)

(8) Boundary conditions:

P₀ = 0 (because once you have zero dollars, you’ve no chance of winning)

P_N = 1 (because once you have N dollars, you’ve won the game)

(9) We now need to define P_k for when 0<k<N. That’s where the first-step analysis comes in. If A has k dollars and wins a turn, then A’s probability of winning becomes P_k+1, because A now has k + 1 dollars. By the same logic, if A loses a turn, then the probability of A winning becomes P_k-1.

The law of total probability tells us that:

P_k = pP_k+1 + qP_k-1

Recall that the p and q are there because the probability moving from k to a (k + 1) situation (where 0<k<N) is p, and the probability of moving from k to a (k – 1) situation (where 0<k<N) is q.

(10) So, we have P_k = pP_k+1 + qP_k-1, and (just as with the expectation example earlier) we are guessing that P_k = r^k. Plug that in to get:

r^k = pr^k+1 + qr^k-1

Set this equal to zero and rearrange by degree to get:

pr^k+1 -r^k + qr^k-1 = 0

Divide each term by the r-term of the lowest degree, which is r^k-1:

pr² – r + q = 0

This quadratic equation, once again, is called our characteristic equation (or characteristic polynomial), and is of course nicely solved by the quadratic formula, just as above. In fact, it’s the exact same equation we saw above! So I won’t plug it all into the quadratic formula again. We know the solutions are r = 1 and r = p/q. Again, these are our characteristic roots.

This time, however, we’ll deal with the case in which p and q aren’t equal as well as when they are. Let’s start with when they are not.

(11) Exactly as with our earlier example, assign a coefficient to each of these—I’ll use A and B—and add together to get a general solution:

P_k = A(1)^k + B(q/p)^k

P_k = A + B(q/p)^k

(12) Solve for A and B by plugging in our given initial conditions, which in this case are our boundary conditions of P₀ = 0 and P_N = 1.

P₀ = 0 = A + B(q/p)⁰

P₀ = 0 = A + B

Therefore, B = -A. This means we can plug -A in for B, which updates the solution to:

P_k = A + (-A)(q/p)^k

P_k = A – A(q/p)^k

Now do the same with the upper bound to solve for A:

P_N = 1 = A – A(q/p)^N

P_N = 1 = A(1 – (q/p)^N)

Divide both sides by (1 – (q/p)^N) to get:

Update the solution accordingly and simplify; I’ll go step by step to reflect the above changes:

(13) The solution to this problem, then, is:

(14) Recall that this solution only works for when p ≠ q. It obviously won’t work when p = q. That is, when q/p = 1, we end up with 0/0. One way to deal with this is by going back and multiplying one of the terms by k (as we did with the double root above), which I’ll do a moment. First, I’ll take an quick and intuitive approach I first encountered in the Harvard Stats 110 lecture (see link at the end of this section). It uses some simple tools from calculus.*

[*There are of course plenty of online resources for covering question types in basic calculus. If you’re looking for a resource to teach yourself the subject with the same depth you’d get from a classroom, I highly recommend Professor Leonard’s lectures on YouTube. A great companion to these are Paul’s Online Notes, which are clear and thorough and include practice problems with solutions. If you need more practice problems, I recommend Patrick Jones’s Calculus: 1,001 Practice Problems for Dummies. I’m going to stop myself here, or I won’t know where to stop.]

Let q/p = x, and take the limit as x approaches 1 (which is to say as p and q get closer to being equal):

As this yields the indeterminate form 0/0, we can use L’Hôpital’s rule, wherein we take the limit as x tends to 1 after taking the first derivative of the numerator and denominator:

So, the solution here is k/N, which can be verified by testing several values for k in the original difference equation.

It makes sense that this is k/N, as it means that, when the probability of winning or losing a given turn is equal, the probability of winning at k dollars is whatever proportion k is of the total amount of money in the game. For example, if A and B each has $5 and there’s a 1/2 probability of winning each turn, then, at this stage of the game, there’s a 1/2 probability that A will win the game.

(15) Finally, I’ll solve this problem by going back and plugging the characteristic roots into the general solution to our homogeneous equation:

P_k = A(1)^k + B(q/p)^k

Since p = q, this becomes:

P_k = A(1)^k + B(1)^k

P_k = A + B

As before, to deal with the double root of 1, we need to multiply one of the terms by k:

P_k = Ak + B

We then solve for A and B with our initial (i.e., boundary) conditions, which again are P₀ = 0 and P_N = 1:

P₀ = 0 = A(0) + B

So, B = 0 (which means we can drop the B from the solution)

P_N = 1 = A(N)

After dividing both sides by N we see that A = 1/N.

Plug that into P_k to get our final, closed-form solution of:

P_k = (1/N)k = k/N

That’s exactly what we got when taking the limit.

6. Additional Resources for Gambler’s Ruin-Type Problems

These resources use the methods I’ve used here.

“Lecture 7: Gambler’s Ruin and Random Variables | Statistics 110“: This is where I first encountered the Gambler’s Ruin problem and first learned about difference equations. The lecture is from Joe Blitzstein’s Harvard “Statistics 110: Probability” course (full playlist is available here), which I highly recommend, along with the textbook that accompanies the course. The book (cowritten with Jessica Hwang) is recently in its second edition and can be viewed for free at the Stat 110 website, where there are links to an edX version of the course, class handouts, and other goodies: Statistics 110: Probability. Hard copies of the book are available at Amazon: Introduction to Probability (Second Edition). I own the first edition for Kindle, which looks great on my laptop (and is searchable!). The second edition is definitely on my wish list.

“Random Walks“: Clear lecture notes by Tom Leighton and Ronitt Rubinfeld, focused on the Gambler’s Ruin problem. Covers both probability and expectation for when p = q and for when p ≠ q. Also has a nice proof that the game’s probability of going forever is 0, among other tidbits. Interestingly, the term “difference equation” doesn’t appear here. Also, this one shows more steps than the next two resources I’m about to share.

“Duration of the Gambler’s Ruin“: These notes by Steven R. Dunbar focus on expectation and might be a little harder to follow than the above notes. Includes followup problems and, unlike the other sources here, code for running simulations in several programming languages. We do encounter the term “difference equation.” I mention this because much of my interest in looking at different resources is to observe the shared and differing ways of conceptualizing, talking about, notating, etc. what is essentially the same approach to solving these problems.

“Probability 2 – Notes 3“: These notes (that bear no author credit) give more emphasis to conditioning. Might be the most technically demanding of the notes I’m sharing. References the “law of total probability for expectations” (what I, nearly four thousand words ago, referred to as the “law of total expectation”) and uses the term “difference equation,” but doesn’t use any of the terms in the phrase “(non-)homogeneous linear recurrence relation.”

---

Enjoy or find this post useful? Please consider pitching in a dollar or three to help me do a better job of populating this website with worthwhile words and music. Let me know what you'd like to see more of while you're at it. Transaction handled by PayPal.

---

Or click the banner to shop at Amazon (at no extra cost: it just gives me some of what would have gone to Amazon).

---

Further Reading

Further ReadingSelect CategoryDenotation Switch  (3)Epistemology  (13)Ethics  (16)Film  (8)Free Will  (14)Math  (21)Mind | Brain  (30)Music  (26)Philosophy  (78)Political  (14)Probability  (39)Science  (18)Social Group Ontology  (17)Technology  (14)Uncategorized  (7)Words  (17)