Somewhere between a coin flip and a chess game sits the kind of decision economics actually cares about: one made today, under uncertainty, that changes what you’re allowed to decide tomorrow. The tool for reasoning about this is called a Markov Decision Process (MDP), and the clearest way to illustrate it is with a simple lemon tree that you can either water or harvest.
A Tree That Doesn’t Remember
Picture a lemon tree you water every period, a day, a week, whatever unit of time you like. Each period, somewhere between zero and two new lemons appear, governed by fixed odds: 60% of the time nothing grows, 30% of the time you get one new lemon, 10% of the time you get two.
Before going further, it helps to write “how many lemons are on the tree” as a small row of numbers instead of a sentence. If you have 0 lemons right now, you can write that state as [1, 0, 0, 0], a 1 in the “0 lemons” slot and 0s everywhere else. If you had 2 lemons instead, it would be [0, 0, 1, 0], a 1 in the third slot. This is just bookkeeping, but it’s the bookkeeping that makes the rest of the math work.
Here’s the property that makes this whole approach possible: it doesn’t matter how the tree got to its current count. A tree with one lemon behaves identically whether it arrived there from zero lemons last period or dropped down from three. Only the present state matters for predicting the future.
“No matter how the process arrived at its present state, the possible future states are fixed.”
That single sentence is what lets you compress an entire history of watering and growing into one row of a matrix, the probability transition matrix. Rows are where you are now, columns are where you might be next, and each cell is the probability of making that jump. Here’s the full matrix for watering:
Reading the Transition Matrix
Read the matrix one row at a time, left to right. The first row says: starting from 0 lemons, there’s a 60% chance of staying at 0, a 30% chance of climbing to 1, a 10% chance of climbing to 2, and a 0% chance of jumping straight to 3 (you can only grow one or two at a time). Each row has to add up to 100%, because you have to end up somewhere.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | .6 | .3 | .1 | 0 |
| 1 | 0 | .6 | .3 | .1 |
| 2 | 0 | 0 | .6 | .4 |
| 3 | 0 | 0 | 0 | 1 |
Now watch what happens when you multiply the state vector by this matrix. If you’re at 0 lemons, your state vector is [1, 0, 0, 0]. Matrix multiplication says: take each entry of the state vector, multiply it by the matching row of the matrix, and add everything up. Because every entry of the state vector is 0 except the first one, every row except the first one gets multiplied by zero and disappears. You’re left with exactly the first row:
[1, 0, 0, 0] × P = [.6, .3, .1, 0]In plain language: if you multiply a state vector by the transition matrix, you get back the probabilities of where you’ll be next period. That’s the whole trick. The state vector “selects” a row, and the matrix hands you back the odds.
Here’s where it gets genuinely useful. If multiplying once gives you the odds one period out, what happens if you multiply by the matrix a second time?
Two Periods Out
Take the result from above, [.6, .3, .1, 0], and multiply it by P one more time. Let’s just check the first entry by hand, the probability you’re still at 0 lemons after two periods. To land back at 0 lemons twice in a row, you need to grow zero lemons in period one and grow zero lemons in period two. Those are two independent events, so you multiply their probabilities:
P(0 lemons, period 1) × P(0 lemons, period 2) = 0.6 × 0.6 = 0.36Running that same logic across every entry gives you the full picture two periods out:
| 0 | 1 | 2 | 3 |
|---|---|---|---|
| .36 | .36 | .21 | .07 |
Notice you didn’t have to re-derive anything from scratch. You just fed the output of one multiplication back in as the input to the next. Multiply five times and you’ve forecast five periods out, with zero extra bookkeeping.
Two Actions, One Tree
A Markov chain becomes a Markov Decision Process the moment you’re allowed to intervene. The lemon tree doesn’t just grow on its own. Each period you choose between two actions, water it or harvest it, and each action carries its own transition matrix, because each one sends you down a different probabilistic path.
Let It Grow
The tree evolves exactly as before, 60/30/10 odds of staying put, gaining one, or gaining two lemons. You earn nothing this period, but you’re setting up a bigger payout later.
Cash Out
You strip every lemon off the tree and sell it. Regardless of how many lemons you started with, the tree resets to 0 next period with certainty.
Because harvesting always sends you to 0 lemons no matter where you started, its transition matrix looks unusual: every single row is identical.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 |
Harvest, Then Water
Say you start with 2 lemons, harvest this period, then water the next. Your starting state vector is [0, 0, 1, 0]. First, multiply by P(harvest). Since every row of P(harvest) is [1, 0, 0, 0], it doesn’t matter which row gets selected, you land at 0 lemons with certainty:
[0, 0, 1, 0] × P(harvest) = [1, 0, 0, 0]Now you’re sitting at 0 lemons, and you water. That means you multiply this new state vector by P(water), which is exactly the first worked example from Part One:
[1, 0, 0, 0] × P(water) = [.6, .3, .1, 0]Chain the two actions together and you get the same answer in one line: harvest-then-water from 2 lemons leaves you with a 60% chance of 0 lemons, 30% chance of 1, and 10% chance of 2, next period.
Selling Lemons, Discounting the Future
The next version of the problem sharpens things. Now there are four possible states, 0, 1, 3, or 6 lemons, with 2, 4, and 5 simply unreachable, and six lemons is the ceiling. Each lemon sells for a dollar. Instead of fixed numbers like 0.6 and 0.3, let’s call the underlying probabilities p0, p1, and p2 (they still have to add up to 1), so the matrix looks like this in general form:
| 0 | 1 | 3 | 6 | |
|---|---|---|---|---|
| 0 | p0 | p1 | p2 | 0 |
| 1 | 0 | p0 | p1 | p2 |
| 3 | 0 | 0 | p0 | 1-p0 |
| 6 | 0 | 0 | 0 | 1 |
The game goes on forever in principle, except you only survive from one period to the next with probability 0.9. That survival probability doubles as a discount factor, written β (beta), and it changes how much a future dollar is worth to you today. Here’s the arithmetic behind that idea, made concrete:
Why a Future Dollar Is Worth Less
Suppose you’re guaranteed $6 next period, if the game survives that long. Because survival only happens with probability 0.9, the amount that $6 is actually worth to you today is:
Value today = β × (future payout) = 0.9 × $6 = $5.40You’re not losing money to inflation or interest here, you’re losing it to the 10% chance the game simply ends before you collect. The further out a payout sits, the more times you have to multiply by 0.9, and the smaller its value today becomes.
The question the model exists to answer: given how many lemons are on the tree right now, should you water or harvest? Harvesting at six lemons is obviously correct, since you can’t accumulate further and waiting would waste a turn. But harvesting at three is a genuine trade-off, three dollars now, guaranteed, against a shot at six dollars later, discounted for the chance the tree doesn’t keep growing and the chance the game doesn’t survive that long.
Three Candidate Policies
Harvest1 picks as soon as there’s any lemon at all, never letting the tree grow further. Harvest3 holds out until there are at least three lemons, then cashes in. Harvest6 waits for the tree to max out before ever harvesting.
Simulation is honest work, but it’s blunt. When two policies earn nearly the same amount, brute force averages can point you the wrong way. That’s the case for a sharper tool, one that gives you an exact answer instead of an approximate one.
Value Iteration: Guessing Your Way to the Truth
Dynamic programming, specifically an algorithm called value iteration, rests on an idea from Richard Bellman. First, a definition: the “value” of a state is the total amount of money you can expect to earn from now until the game ends, assuming you make the smartest possible choice in every future period. Bellman’s insight was that you can find this value for every state at once by comparing what harvesting is worth against what growing is worth, and simply keeping the larger of the two.
There are four pieces that build on each other. Let’s take them one at a time, using real numbers: p0 = 0.8, p1 = 0.1, p2 = 0.1, and β = 0.9.
Future Value
Future value tells you what a state is worth, on average, one period from now, before any discounting. You calculate it by multiplying the transition matrix by your current value guess, one row at a time, exactly like the multiplications in Part One. Suppose your current guess for the value of each state is [4, 5.46, 7, 10] (we’ll see in a moment why this particular guess is special). The future value of being at 0 lemons is:
FV(0) = .8(4) + .1(5.46) + .1(7) + 0(10) = 3.2 + 0.546 + 0.7 = 4.45Running the same calculation for every row gives future values of roughly 4.45, 6.07, 7.60, and 10.00 for the states 0, 1, 3, and 6.
Value of Growing
If you choose to water instead of harvest, you earn nothing today, so the value of growing is simply the future value, discounted by β for the chance the game continues:
Value_grow = β × Future Value = 0.9 × [4.45, 6.07, 7.60, 10.00] = [4.00, 5.46, 6.84, 9.00]Value of Harvesting
If you harvest instead, you collect today’s payout (the lemon count, in dollars) plus the discounted value of starting over from 0 lemons next period. Since harvesting always resets you to 0, every state uses the same future value, FV(0) = 4.45:
Value_harvest = payout + β × FV(0) = [0, 1, 3, 6] + 0.9(4.45) = [4.00, 5.00, 7.00, 10.00]Value, Updated
Now compare the two option-by-option and keep whichever is larger in each state:
Value = max(Value_grow, Value_harvest) = max([4.00,5.46,6.84,9.00], [4.00,5.00,7.00,10.00]) = [4.00, 5.46, 7.00, 10.00]That’s exactly the guess we started with. That’s not a coincidence, it means this vector is a fixed point: once value iteration reaches it, plugging it back in just returns the same answer. That’s how you know you’ve converged on the true value function.
Once value has converged, the optimal policy falls right out of the comparison you already made in Step 4. Look at where harvest won and where grow won:
Water
At 0 lemons, growing and harvesting tie at $4.00, so there’s nothing to gain by picking early. At 1 lemon, growing ($5.46) clearly beats harvesting ($5.00), so you hold off.
Harvest
At 3 lemons, harvesting ($7.00) edges out growing ($6.84). At 6 lemons, harvesting ($10.00) beats growing ($9.00) outright, since you can’t accumulate any further anyway.
The Tree Was Never Really About Lemons
Strip away the fruit and what’s left is a template: a set of states, a set of actions, a rule for how probability moves you between states, and a way of weighing a certain reward today against an uncertain one tomorrow. Swap lemons for job offers, inventory, or patients in a clinical trial and the machinery doesn’t change at all, only the numbers do.
As Always, shoutout to Professor Colleen O’Briant for teaching me all this!
“The tree doesn’t remember how it got here. It only asks what you’ll do next.”
Leave a Reply