From Cycle Averages to Reward per Unit Time
A regenerative model repeatedly returns to a comparable starting condition. Each cycle has a duration and a total reward. The long-run reward rate is not generally the expected reward from one cycle: cycles of different lengths contribute for different amounts of calendar time. The renewal-reward theorem identifies the rate by comparing the average reward per cycle with the average time per cycle.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_k,R_k)_{k\ge1}\) be iid random pairs taking values in the cycle-pair state space \((0,\infty)\times\mathbb{R}\). Here \(X_k\) is the length of cycle \(k\), and \(R_k\) is its total reward. Assume \(X_k\) is finite and strictly positive almost surely, and write \(\mu=\mathbb{E}[X_1]\). Define cycle-end times \(S_0=0\), \(S_n=\sum_{k=1}^n X_k\), and the number of completed cycles by time \(t\) as \(N(t)=\max\{n\ge0:S_n\le t\}\). The cumulative reward credited at cycle ends is \(C(t)=\sum_{k=1}^{N(t)}R_k\), with an empty sum equal to zero.
The ratio has a direct interpretation: over many cycles, total reward divided by the number of cycles approaches \(\mathbb{E}[R_1]\), while elapsed time divided by the number of cycles approaches \(\mathbb{E}[X_1]\). Their quotient is therefore the reward accumulated per unit of calendar time. The proof needs a precise link between elapsed time \(t\) and the random number \(N(t)\) of cycles completed by then.
The Renewal Count per Unit Time
Proof. The strong law of large numbers, a standard probability result, gives \(S_n/n\to\mu\) almost surely. Fix an outcome on which this convergence holds. Since each \(X_k>0\), the sequence \(S_n\) increases, and \(S_n\to\infty\). Thus \(N(t)\to\infty\) as \(t\to\infty\). For all sufficiently large \(t\), \(N(t)\ge1\), and the definition of \(N(t)\) gives \(S_{N(t)}\le t<S_{N(t)+1}\). Dividing by \(N(t)\) yields $$ \frac{S_{N(t)}}{N(t)} \le \frac{t}{N(t)} < \frac{S_{N(t)+1}}{N(t)} = \frac{S_{N(t)+1}}{N(t)+1}\frac{N(t)+1}{N(t)}. $$ As \(t\to\infty\), \(N(t)\to\infty\). The left side therefore tends to \(\mu\); the right side also tends to \(\mu\), because its first factor tends to \(\mu\) by the strong law and its second factor tends to \(1\). Hence \(t/N(t)\to\mu\). Since \(\mu>0\), taking reciprocals gives \(N(t)/t\to1/\mu\). \(\square\)
This proposition establishes the time scale for the reward calculation. The reward sum itself is governed by the strong law applied to \(R_k\), which is available because \(\mathbb{E}[|R_1|]<\infty\). The next proof puts these two averages together.
Proof of the Renewal-Reward Theorem
Proof. The strong law of large numbers applied to the integrable iid rewards gives $$ \frac{1}{n}\sum_{k=1}^{n}R_k\longrightarrow \mathbb{E}[R_1] \quad\text{almost surely}. $$ By the proposition, \(N(t)/t\to1/\mu\) almost surely. On the event of probability one where both limits hold, \(N(t)\to\infty\), so for all sufficiently large \(t\) we can write $$ \frac{C(t)}{t} = \left(\frac{1}{N(t)}\sum_{k=1}^{N(t)}R_k\right) \frac{N(t)}{t}. $$ The first factor tends to \(\mathbb{E}[R_1]\), since it is the reward strong-law average evaluated at the integer index \(N(t)\), which tends to infinity. The second factor tends to \(1/\mu\). The product therefore tends to \(\mathbb{E}[R_1]/\mu\), proving the theorem. \(\square\)
The displayed definition of \(C(t)\) counts only completed-cycle rewards. In applications, reward can accrue during a cycle rather than at its end. To include that partial reward, suppose the additional reward accumulated in cycle \(k\), up to any time within that cycle, has absolute value at most \(Z_k\), where the \(Z_k\) are iid, nonnegative, and \(\mathbb{E}[Z_1]<\infty\). The same limit holds: the difference from \(C(t)\) is bounded by \(Z_{N(t)+1}\), and that single-cycle contribution divided by \(t\) tends to zero.
Here is the needed bound. For any \(\varepsilon>0\), nonnegativity and integrability give $$ \sum_{n=1}^{\infty}\mathbb{P}(Z_n>\varepsilon n) = \sum_{n=1}^{\infty}\mathbb{P}(Z_1>\varepsilon n) \le \frac{\mathbb{E}[Z_1]}{\varepsilon}<\infty. $$ Indeed, for a fixed value \(z\ge0\), the number of positive integers \(n\) satisfying \(\varepsilon n<z\) is at most \(z/\varepsilon\); taking expectations gives the inequality. The first Borel–Cantelli lemma then implies \(Z_n/n\to0\) almost surely. Also, \(N(t)/t\to1/\mu\), so \((N(t)+1)/t\to1/\mu\). Consequently, $$ \frac{Z_{N(t)+1}}{t} = \frac{Z_{N(t)+1}}{N(t)+1}\frac{N(t)+1}{t} \longrightarrow 0 \quad\text{almost surely}. $$ This condition is useful when rewards are accumulated continuously during cycles. Integrability of the final net reward alone does not control large positive and negative rewards that cancel within a cycle; an integrable bound on the partial reward is what justifies this extension.
Worked Example: Two Possible Cycle Types
Suppose each cycle independently has length \(1\) and reward \(2\) with probability \(\tfrac12\), or length \(3\) and reward \(0\) with probability \(\tfrac12\). Find the long-run reward rate.
The two probabilities sum to \(\tfrac12+\tfrac12=1\). The mean length is $$ \mathbb{E}[X_1] =\tfrac12(1)+\tfrac12(3) =\tfrac12+\tfrac32 =2. $$ The mean reward is $$ \mathbb{E}[R_1] =\tfrac12(2)+\tfrac12(0) =1+0 =1. $$ Both means are finite, and the mean length is positive. The renewal-reward theorem therefore gives rate \(1/2\) reward units per time unit.
Check: For \(n\) cycles, the strong law says total length divided by \(n\) tends to \(2\), and total reward divided by \(n\) tends to \(1\). Dividing these limiting averages gives \(1/2\), as in the theorem. The longer cycle type contributes no reward, so using the expected reward alone, \(1\), as the per-time rate would ignore the time spent in those cycles.
Worked Example: Reward Accruing Within a Deterministic Cycle
Consider iid degenerate cycles of length \(2\). In every cycle the reward rate is \(1\) during its first time unit and \(0\) during its second. Compute the long-run reward per unit time, including the current partial cycle.
Each cycle earns total reward \(1\), so \(X_k=2\), \(R_k=1\), \(\mathbb{E}[X_1]=2\), and \(\mathbb{E}[R_1]=1\). The theorem gives the rate \(1/2\). We can verify it directly. Write \(t=2m+u\), where \(m=\lfloor t/2\rfloor\) and \(0\le u<2\). The first \(m\) complete cycles earn \(m\); the current cycle earns \(\min(u,1)\). Thus the cumulative reward is \(C_{\mathrm{all}}(t)=m+\min(u,1)\), while \(t/2=m+u/2\).
For \(0\le u\le1\), the difference \(C_{\mathrm{all}}(t)-t/2=u/2\), which lies between \(0\) and \(1/2\). For \(1\le u<2\), the difference is \(1-u/2\), also between \(0\) and \(1/2\). Therefore \(0\le C_{\mathrm{all}}(t)-t/2\le1/2\). Dividing by \(t>0\), the difference between \(C_{\mathrm{all}}(t)/t\) and \(1/2\) is at most \(1/(2t)\), which tends to zero.
Check: The expected-reward ratio is \(1/2\), and the explicit calculation differs from \(1/2\) by at most \(1/(2t)\). Hence the partial cycle does not change the limiting rate.
Worked Example: Signed Rewards and Cancellation
Suppose every cycle has length \(2\). Independently, its reward is \(3\) with probability \(\tfrac14\) and \(-1\) with probability \(\tfrac34\). Find the almost-sure long-run reward rate.
The probabilities sum to \(\tfrac14+\tfrac34=1\), and the cycle length has mean \(\mathbb{E}[X_1]=2\). The reward has finite absolute mean: $$ \mathbb{E}[|R_1|] =\tfrac14|3|+\tfrac34|-1| =\tfrac34+\tfrac34 =\tfrac32. $$ Its mean, including the signs, is $$ \mathbb{E}[R_1] =\tfrac14(3)+\tfrac34(-1) =\tfrac34-\tfrac34 =0. $$ The theorem gives long-run rate \(0/2=0\) almost surely.
Check: Over \(n\) cycles the average signed reward tends to \(0\), while the average cycle length is exactly \(2\). Their ratio tends to \(0\). The rate is not the expected absolute reward divided by the mean length: absolute reward does not account for cancellation between positive and negative rewards.
Why the Integrability Condition Matters
The assumptions do real work. In particular, if rewards are not integrable, a finite expected reward per cycle—and hence the finite ratio in the theorem—may not exist. Consider cycles of deterministic length \(1\), and let the nonnegative iid reward \(R_k\) have distribution \(\mathbb{P}(R_k=2^j)=2^{-j}\) for integers \(j\ge1\). These probabilities sum to \(1\), because \(\sum_{j=1}^{\infty}2^{-j}=1\), but \(\mathbb{E}[R_k]=\sum_{j=1}^{\infty}2^j2^{-j}=\infty\).
To see what happens to the time average, fix an integer \(m\ge1\) and truncate each reward at \(2^m\), writing \(R_k^{(m)}=\min(R_k,2^m)\). This variable is bounded, so the strong law applies. Its mean is $$ \mathbb{E}[R_k^{(m)}] =\sum_{j=1}^{m}2^j2^{-j} +2^m\sum_{j=m+1}^{\infty}2^{-j} =m+2^m 2^{-m} =m+1. $$ Since \(R_k\ge R_k^{(m)}\), the liminf of the average untruncated reward is at least \(m+1\) almost surely. This holds simultaneously for every integer \(m\ge1\), by taking the intersection of countably many probability-one events. As \(m+1\) is unbounded, the average reward per unit time tends to \(+\infty\) almost surely, rather than to a finite rate.
Common mistake. A tempting but incorrect calculation is to divide expected reward by expected time in the first example and report rate \(1\), because its expected reward per cycle is \(1\). That omits the mean cycle length. The corrected calculation substitutes both expectations: \(\mathbb{E}[R_1]/\mathbb{E}[X_1]=1/2\). The denominator is essential whenever cycle lengths are not all one time unit.
The theorem is useful because it turns a long-run sample-path question into two one-cycle expectations. The iid assumption supplies the strong laws for cycle lengths and rewards; finite positive mean length makes the renewal count grow at a finite positive rate; and integrable reward makes the cycle-reward average converge to a finite value. Once those conditions are checked, the ratio gives the almost-sure long-run rate without requiring the full distribution of the cumulative reward.
Check Your Understanding
Use the theorem’s hypotheses carefully, and distinguish a cycle average from a time average.
- For iid cycles with mean length \(5\) and mean reward \(3\), what is the long-run reward rate, provided the theorem’s assumptions hold?
- Why does the proposition require \(0<\mathbb{E}[X_1]<\infty\), rather than only finite cycle rewards?
- If rewards are credited only at cycle ends, which strong-law averages combine to prove the renewal-reward theorem?
- In the deterministic length-\(2\) example, what bound controls the difference between cumulative reward including the partial cycle and \(t/2\)?
- For the nonintegrable reward example, compute the mean of the reward truncated at \(2^m\), and explain why these means rule out a finite limiting average.