Auditing a Regenerative Reward Calculation
Regenerative calculations reduce a long-run average to a ratio of quantities measured over one cycle. That ratio is powerful, but it is easy to apply incorrectly: a boundary can be counted twice, a rate can be divided by a duration as though it were a total reward, or the unfinished cycle at the observation time can be discarded. Even the right cycle-level ratio may fail to describe the reward accumulated at every time if large positive and negative rewards cancel within cycles.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(T_0=0<T_1<T_2<\cdots\) be regeneration times and \(C_k=T_k-T_{k-1}\) the duration of cycle \(k\). Assume the cycles are independent and identically distributed, with \(0<\mathbb{E}C_1<\infty\). A cycle includes its start and excludes its end: in continuous time its interval is \([T_{k-1},T_k)\). If \(r_s\) is the reward rate at time \(s\), define the signed cycle reward and the total absolute reward by \(R_k=\int_{T_{k-1}}^{T_k}r_s\,ds\) and \(A_k=\int_{T_{k-1}}^{T_k}|r_s|\,ds\). The reward accumulated by time \(t\) is \(S(t)=\int_0^t r_s\,ds\). In discrete time, the corresponding convention is that a reward \(g(X_n)\) is accrued during step \(n\), over \([n,n+1)\); a cycle from integer time \(T_{k-1}\) to \(T_k\) includes steps \(T_{k-1},\ldots,T_k-1\).
Two Ratios That Must Not Be Confused
A total reward \(R_k\) has units of reward, while \(C_k\) has units of time. Their mean ratio \(\mathbb{E}R_1/\mathbb{E}C_1\) therefore has units of reward per time. A reward rate \(r_s\), by contrast, already has units of reward per time; its integral over a cycle is the total reward. Averaging a rate and then dividing by a duration generally produces the wrong units and the wrong answer.
Worked Example: A Rate Is Not a Cycle Reward
Suppose cycles have duration \(1\) hour or \(3\) hours, each with probability \(1/2\), and the reward rate is constantly \(2\) units per hour. The cycles are iid, and each cycle reward is \(R_k=2C_k\). Find the long-run reward rate and diagnose a tempting incorrect calculation.
The mean duration is \(\mathbb{E}C_1=(1+3)/2=2\) hours. The two possible cycle rewards are \(2\) and \(6\) units, so \(\mathbb{E}R_1=(2+6)/2=4\) units. The cycle ratio is \(4/2=2\) units per hour. Indeed, the reward accumulated by any time \(t\) is exactly \(2t\), so \(S(t)/t=2\).
Wrong calculation: dividing the mean rate \(2\) units per hour by the mean duration \(2\) hours gives \(1\) unit per hour squared. This is not a reward rate; it divides by time twice. The correction is to integrate the rate over each cycle first, obtaining \(R_k=2C_k\), and then use \(\mathbb{E}R_1/\mathbb{E}C_1=2\).
Cycle Boundaries: Count Each Reward Once
Cycle definitions are bookkeeping rules as well as probabilistic assumptions. In continuous time, including or excluding a single endpoint does not change an ordinary time integral, because a single instant has zero length. In discrete time, however, the reward at an integer time is a whole step’s reward. A cycle from \(T_{k-1}\) to \(T_k\) must include the steps beginning at \(T_{k-1}\) and ending just before \(T_k\), not both endpoints.
Worked Example: Double-Counting a Regeneration State
Consider the deterministic discrete-time chain on \(S=\{0,1\}\) that moves \(0\to1\to0\to1\to\cdots\), started at \(X_0=0\). Its transition matrix is \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\); both rows sum to \(1\). Regeneration times are \(T_k=2k\). Let the reward per step be \(g(0)=2\) and \(g(1)=0\). Compute the correct rate and the result of including both cycle endpoints.
Cycle \(k\) consists of steps \(2k-2\) and \(2k-1\), with rewards \(2\) and \(0\). Thus \(C_k=2\), \(R_k=2+0=2\), and the cycle ratio is \(2/2=1\) unit per step. Directly, the first \(2n\) steps have total reward \(2n\), so their average is \(2n/(2n)=1\).
Wrong calculation: summing the rewards at times \(0,1,2\) for the first cycle includes the next cycle’s starting time \(2\). That sum is \(g(0)+g(1)+g(0)=2+0+2=4\); dividing by the duration \(2\) gives \(2\), an incorrect rate. The correction is to sum only at times \(0\) and \(1\), excluding the endpoint \(2\), which belongs to the next cycle. The transition rows and the direct long-run average confirm the corrected value.
The Unfinished Cycle at a Fixed Time
At a time \(t\) between regeneration times, the accumulated reward usually consists of all completed-cycle rewards plus a partial reward from the current cycle. Write \(N(t)=\max\{n:T_n\le t\}\). Then \(S(t)=\sum_{k=1}^{N(t)}R_k+\text{reward accumulated from }T_{N(t)}\text{ to }t\). Dropping the last term is not an exact finite-time calculation. It can be negligible after division by \(t\) under suitable assumptions, but that fact requires a condition controlling within-cycle reward.
Worked Example: Omitting the Partial Cycle Changes the Finite-Time Answer
Suppose every cycle lasts \(2\) hours. In each cycle, the reward rate is \(4\) units per hour during its first hour and \(0\) during its second hour. Find the accumulated reward and average rate at \(t=3\) hours, both with and without the unfinished cycle.
The cycle reward is \(4\cdot1+0\cdot1=4\) units, and the cycle duration is \(2\) hours, so the long-run ratio is \(4/2=2\) units per hour. By time \(3\), the first cycle is complete and contributes \(4\) units. The second cycle has run for one hour, during which it contributes \(4\cdot1=4\) more units. Therefore \(S(3)=4+4=8\), and the actual average is \(8/3\) units per hour.
If the unfinished cycle is omitted, the calculation uses only \(4\) units and reports \(4/3\) units per hour. That is not \(S(3)/3\). The correction is to include the partial reward; the example also shows why a finite-time average need not equal the eventual cycle ratio.
What the Long-Run Limit Requires
Proof. Let \(T_n=\sum_{k=1}^n C_k\). By the strong law of large numbers, \(T_n/n\to c=\mathbb{E}C_1>0\) almost surely and \(\sum_{k=1}^nR_k/n\to\mathbb{E}R_1\) almost surely; the latter applies because \(|R_k|\le A_k\) and \(\mathbb{E}A_1<\infty\). At \(t=T_n\), division of these limits gives \(\sum_{k=1}^nR_k/T_n\to\mathbb{E}R_1/c\).
For arbitrary \(t\), the inequalities \(T_{N(t)}\le t<T_{N(t)+1}\), together with \(T_n/n\to c\), imply \(N(t)/t\to1/c\). To see this, as \(t\to\infty\), \(N(t)\to\infty\); dividing the inequalities by \(N(t)\) and using \(T_{N(t)}/N(t)\to c\) and \(T_{N(t)+1}/N(t)\to c\) squeezes \(t/N(t)\) to \(c\).
It remains to control the partial cycle. Since \(A_k\) are iid, nonnegative, and integrable, \(A_k/k\to0\) almost surely: for every \(\varepsilon>0\), \(\sum_{k\ge1}\mathbb{P}(A_k>\varepsilon k)<\infty\), by the finite-mean tail bound, and the first Borel–Cantelli lemma then gives \(A_k\le\varepsilon k\) eventually. Since \(\varepsilon\) is arbitrary, the claimed limit follows. The absolute value of the reward accumulated in the unfinished cycle is at most \(A_{N(t)+1}\). Hence \(\displaystyle \frac{A_{N(t)+1}}{t}=\frac{A_{N(t)+1}}{N(t)+1}\frac{N(t)+1}{t}\longrightarrow0\) almost surely: the first factor tends to \(0\), and the second tends to \(1/c\). Combining this with the completed-cycle limit proves the all-time assertion. If only \(\mathbb{E}|R_1|<\infty\) is assumed, the strong law still proves the limit along \(T_n\); it does not control the partial-cycle term. \(\square\)
Cancellation Can Hide Large Within-Cycle Rewards
For signed rewards, a small or even zero total cycle reward does not imply that the reward accumulated partway through the cycle is small. The distinction between \(|R_k|\) and \(A_k\) is essential: \(|R_k|\le A_k\), but finite \(\mathbb{E}|R_k|\) does not imply finite \(\mathbb{E}A_k\). The next example shows that even a completed-cycle rate of zero need not be the limit over all times.
Worked Example: Zero Net Cycle Rewards but No All-Time Limit
Let every cycle have length \(1\). Let \(Y_k\) be iid with \(\mathbb{P}(Y_k>x)=1/x\) for \(x\ge1\). In cycle \(k\), use reward rate \(+Y_k\) during its first half and \(-Y_k\) during its second half. Determine the completed-cycle rewards and show that the all-time rate does not converge to zero.
The total signed reward in each cycle is \(R_k=Y_k/2-Y_k/2=0\), so \(\mathbb{E}|R_k|=0\), and the completed-cycle ratio is zero. But at time \(t=n+1/2\), the first \(n\) cycles have net reward zero and the first half of cycle \(n+1\) has reward \(Y_{n+1}/2\). Thus \(S(n+1/2)=Y_{n+1}/2\).
For each \(n\ge1\), the event \(Y_{n+1}>n+1\) has probability \(1/(n+1)\). These events are independent, and their probabilities have divergent sum, so the second Borel–Cantelli lemma implies they occur infinitely often almost surely. At each such \(n\), \(\displaystyle \frac{S(n+1/2)}{n+1/2}>\frac{(n+1)/2}{n+1/2}=\frac{n+1}{2n+1}>\frac12.\) Consequently the all-time ratio cannot converge to zero, although it is zero at every completed-cycle time. Here \(A_k=Y_k\), whose mean is infinite; the condition \(\mathbb{E}A_1<\infty\) in the theorem fails.
A different failure occurs if the mean cycle reward itself is not finite. For example, take cycles of length \(1\) and nonnegative cycle rewards \(R_k\) with \(\mathbb{P}(R_k>x)=1/x\) for \(x\ge1\). Then \(\mathbb{E}R_k=\infty\), so the finite ratio \(\mathbb{E}R_1/\mathbb{E}C_1\) is not defined. A finite-mean renewal–reward formula cannot be invoked to produce a finite rate. The lesson is to check the relevant integrability assumptions, not to infer them from a plausible-looking cycle calculation.
A Practical Audit
Before accepting a regenerative reward answer, check the following points.
- Cycle boundaries: specify whether the interval is \([T_{k-1},T_k)\), and verify that each discrete-time reward is assigned to exactly one cycle.
- Units: identify whether the numerator is a total reward per cycle or a reward rate. Divide expected total cycle reward by expected cycle duration.
- Observation time: for a finite \(t\), include the reward accumulated in the unfinished cycle. Do not replace \(S(t)\) by a completed-cycle sum without justification.
- Integrability: for an all-time signed reward limit, check finite expected cycle duration and finite expected total absolute reward within a cycle. Finite expected absolute net cycle reward alone is weaker.
- Claimed limit: distinguish a result along regeneration times from one holding as \(t\) ranges over all times.
Common mistake. The calculation \(\mathbb{E}R_1/\mathbb{E}C_1\) is not, by itself, proof that \(S(t)/t\) converges for all \(t\). It gives the completed-cycle limit under the usual integrability of \(R_1\); to pass to arbitrary times with signed rewards, control the unfinished cycle, for example by assuming \(\mathbb{E}A_1<\infty\). The cancellation example shows why that additional check matters.
Check Your Understanding
For each question, state which assumptions or bookkeeping conventions you would check before accepting the calculation.
- A discrete-time regenerative cycle runs from step \(T_{k-1}\) to step \(T_k\). Which step rewards belong to that cycle, and why should the reward at \(T_k\) not also be included?
- Cycle duration has mean \(3\) hours and total cycle reward has mean \(12\) dollars. What are the units and value of the regenerative reward rate?
- At a finite observation time inside a cycle, what term is missing if a calculation sums only completed-cycle rewards?
- Why does \(\mathbb{E}|R_1|<\infty\) not by itself control the unfinished-cycle reward when rewards can have both signs?
- In the cancellation example, what are the completed-cycle reward and the absolute within-cycle reward? Which integrability condition fails?