The Renewal Reward Theorem

An execution algorithm posts a passive order, waits until either it fills or a timer expires and it reposts, and repeats this cycle continuously through the trading day. Each cycle takes a random amount of time (some orders fill fast, some sit the full timeout) and earns a random reward (filled orders capture the spread; timed-out reposts cost a little in missed opportunity). You want to know the algorithm's average profit per minute over the whole day. Tracking every individual cycle and its exact timing is possible but painful — you'd need to know the full joint distribution of cycle lengths and rewards together. The renewal reward theorem says you don't need any of that: you only need two much simpler averages, computed independently, and you can just divide one by the other.

An analogy: a fisherman's average catch

A fisherman goes out on trips of random length — some trips are quick, some run long — and comes back with a random-sized catch each time. Over many trips, you want to know his average catch per hour fished, not per trip. You don't need to track which specific long trips had big catches and which short trips had small ones, or worry about how catch size and trip length are correlated trip-by-trip. You just need two separate numbers: his average catch per trip, and his average trip length. Divide the first by the second, and — as long as he keeps going out on similar, independent trips indefinitely — that ratio settles down to his true long-run rate of catch per hour, regardless of how wildly any single trip's catch or duration varied.

The theorem, one symbol at a time

Consider a process that runs in a sequence of cycles (renewal periods), where each cycle restarts the process from the same conditions — cycle $n$ has length $T_n$ (a random variable) and earns reward $R_n$ (also random), and different cycles are independent and identically distributed. Let $R(t)$ be the total reward accumulated up to time $t$. The renewal reward theorem states:

$$\lim_{t \to \infty} \frac{R(t)}{t} = \frac{\mathbb{E}[R]}{\mathbb{E}[T]} \quad \text{(with probability 1)},$$

where $\mathbb{E}[R]$ is the expected reward per cycle and $\mathbb{E}[T]$ is the expected cycle length. In plain English: the long-run average reward per unit time equals the average reward earned in one cycle, divided by the average time one cycle takes — a single clean ratio, even though individual cycles can vary enormously in both their length and their reward, and even though a longer cycle might tend to earn more or less reward than a shorter one. The theorem holds as long as cycles are independent repeats of the same underlying random mechanism; it doesn't require reward and cycle length to be independent within a cycle, only that each full (length, reward) pair is drawn fresh and identically for every cycle.

The intuition for why the correlation within a cycle doesn't matter: over many cycles, the total reward accumulated is (by the law of large numbers) close to $n \cdot \mathbb{E}[R]$ after $n$ cycles, and the total time elapsed is close to $n \cdot \mathbb{E}[T]$. Dividing these two large-number approximations, the $n$ cancels, leaving $\mathbb{E}[R]/\mathbb{E}[T]$ regardless of cycle-by-cycle noise.

Worked example 1: the execution algorithm by hand

Suppose historical data on the algorithm's cycles shows: 60% of cycles fill quickly, averaging 8 seconds and earning $4 (spread capture); 40% of cycles time out, averaging 20 seconds and earning −$1 (opportunity cost). The expected reward per cycle:

$$\mathbb{E}[R] = 0.6 \times 4 + 0.4 \times (-1) = 2.4 - 0.4 = 2.0 \; (\text{dollars}) .$$

The expected cycle length:

$$\mathbb{E}[T] = 0.6 \times 8 + 0.4 \times 20 = 4.8 + 8 = 12.8 \; (\text{seconds}) .$$

By the renewal reward theorem, the long-run average profit rate is

$$\frac{\mathbb{E}[R]}{\mathbb{E}[T]} = \frac{2.0}{12.8} \approx 0.156 \; \text{dollars per second} \approx 9.38 \text{ per minute} .$$

That is, roughly $9.38 per minute.

Notice this required no simulation of the actual sequence of fills and timeouts — just the two average building blocks, combined by a single division, to get a rate you can compare directly against a different execution strategy's rate.

Worked example 2: a maintenance/replacement cycle

A trading server component fails and gets replaced at random intervals averaging 100 days, and each replacement (including the value of downtime avoided by proactive servicing) costs on average $500 in parts and technician time. What's the long-run average maintenance cost per day?

$$\frac{\mathbb{E}[R]}{\mathbb{E}[T]} = \frac{500}{100 \text{ days}} = 5 \text{ per day} .$$

That is, $500 over 100 days works out to $5 per day.

Now suppose an alternative maintenance policy replaces the component proactively every 60 days regardless of failure, at a lower cost of $350 per cycle (planned replacements are cheaper than emergency ones) but shorter cycles:

$$\frac{350}{60} \approx 5.83 \text{ per day} .$$

That is, roughly $5.83 per day.

Even though the proactive policy has a smaller cost per event ($350 vs $500), its shorter average cycle length makes its long-run rate higher ($5.83/day vs $5.00/day) — the reactive policy is actually cheaper on a per-day basis. This is exactly the kind of comparison renewal reward makes trivial: convert any repeating cost-or-reward process into a single rate, and compare rates directly, rather than trying to compare "cost per event" figures that are measured over different cycle lengths and therefore not comparable on their own.

What this means in practice

Renewal reward is the standard tool for converting any repeating, cycle-based process into a single comparable long-run rate: execution algorithms that repost, market-making quote-and-requote cycles, server maintenance schedules, or a strategy that enters and exits positions in a repeated pattern. It's the theoretical justification behind Little's Law (see Little's Law) and behind computing an execution algorithm's steady-state cost or fill rate from historical cycle statistics rather than full trajectory simulation. The two numbers you need — average reward per cycle and average cycle length — are usually far easier to estimate reliably from historical data than the full joint process, which is exactly why the theorem is useful in practice rather than just in theory.