Computing Renewal-Reward Rates from Cycle Data

From Cycle Data to a Long-Run Rate

When a stochastic system repeatedly returns to a regenerating condition, its long-run performance can often be calculated one cycle at a time. A cycle might represent the time between successive replacements, returns to an empty queue, or completions of a production run. The key calculation is to find the expected reward earned in one cycle and divide by the expected duration of that cycle. This turns exact cycle data into rates such as time spent in a state per unit time or cost per unit time.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be the probability space, and let \((X_t)_{t\ge0}\) be a continuous-time process with state space \(S\). Suppose the process regenerates at times \(0=T_0<T_1<T_2<\cdots\). The length of cycle \(n\) is \(L_n=T_n-T_{n-1}\). A cycle's reward may accrue gradually, such as time spent in a state, or arrive in lump payments at particular times within the cycle. Write \(R_n\) for the total reward in cycle \(n\). The cycle data are iid when each cycle has the same joint distribution and is independent of the other cycles; the length and reward within a cycle need not be independent of each other.

For a cycle with several possible types, the calculation is especially direct. If type \(z\) occurs with probability \(p_z\), its duration is \(l_z\), and its expected total reward conditional on that type is \(r_z\), then

This uses the expectation of a reward and the expectation of a duration—not the average of the separate cycle-by-cycle ratios. A cycle that is twice as long contributes twice as much elapsed time to the long-run denominator.

Proof. Let \(L_n\) and \(R_n\) be the duration and reward of cycle \(n\). Since there are finitely many types and all type durations and conditional mean rewards are finite, \(\mathbb{E}[L_1]=\sum_zp_zl_z\) is finite and \(\mathbb{E}[R_1]=\sum_zp_zr_z\). Positivity of every \(l_z\) gives \(\mathbb{E}[L_1]>0\). The finite-type assumptions also give integrable cycle rewards. Thus the hypotheses of the renewal-reward theorem hold, and its rate is \(\mathbb{E}[R_1]/\mathbb{E}[L_1]\). Substituting the two expectations gives the stated formula. \(\square\)

Worked Calculations

Rewards Paid at Random Times

The reward can depend on when it is earned, not only on which cycle type occurred. The calculation still starts with the total reward over the whole cycle. If \(U\) is a random payment time within a cycle of length \(L\), and the payment is \(g(U,L)\), its contribution to the expected cycle reward is found by conditioning on \(L\) and averaging over the conditional distribution of \(U\).

Proof. Fix a possible cycle length \(l\). By the definition of expectation for a variable with conditional density \(f_{U\mid L}(u\mid l)\), the conditional mean payment is \(\mathbb{E}[g(U,L)\mid L=l]=\int_0^l g(u,l)f_{U\mid L}(u\mid l)\,du\). Taking expectation over \(L\) gives the displayed formula by iterated expectation. Integrability ensures these expectations are finite. \(\square\)

Assumptions and Common Pitfalls

Cycle calculations rely on the cycle data representing a regenerative structure: successive cycle data must be iid, and the cycle must have finite positive mean duration. The reward must be integrable; for reward accumulated throughout a cycle, its total variation must also have finite expectation. These conditions ensure the renewal-reward theorem applies. In particular, the theorem gives an almost-sure long-run rate under its assumptions, not a claim that every finite run has exactly the expected ratio.

The iid condition cannot simply be discarded. For example, take cycles of deterministic length \(1\), but assign reward \(0\) throughout the first block of cycles, reward \(1\) throughout the next block, and continue alternating between \(0\) and \(1\). Choose successive block lengths \(2,4,16,256,\ldots\), so each block is longer than the total number of cycles before it. At the end of a block, the average reward per unit time is then arbitrarily close to that block's reward, because the previous cycles form a vanishing fraction of the elapsed time. The averages approach \(0\) along zero-reward block endpoints and \(1\) along unit-reward block endpoints. There is no long-run rate. These cycles do not have iid reward data, illustrating why that hypothesis matters.

Common mistake: averaging cycle ratios. In the random-time payment example, a tempting calculation is to average payment divided by cycle length conditional on each length. It gives \(\tfrac13(4/2)+\tfrac23(5/4)=\tfrac23+\tfrac56=\tfrac32\), not the correct rate \(\tfrac75\). The mistake weights each type by its probability rather than by its contribution to total elapsed time. The renewal-reward calculation is \(\mathbb{E}[R_1]/\mathbb{E}[L_1]\), not \(\mathbb{E}[R_1/L_1]\).

For each application, define the cycle boundary first, then count every reward exactly once. A fixed setup cost belongs to the cycle in which it is charged; time spent in a state is that cycle's duration in the state; and a payment at a random time contributes to the cycle containing that payment. Once the cycle reward is specified, compute its expectation and the expected cycle length separately, verify the theorem's assumptions, and take their ratio.