Worked Problems in Regenerative Maintenance and Queues

From Regeneration to a Performance Rate

In an operating system, a useful long-run quantity is often a fraction of time or a cost per unit time. Regeneration makes these quantities calculable: choose epochs at which the system starts afresh, measure the time and reward in one cycle, and compare their expectations. The choice of cycle boundary matters. It must make the cycles identically distributed and independent, and the reward must represent the quantity being measured.

For a continuous-time process \((X_t)_{t\ge0}\) on a state space \(S\), let \(0=T_0<T_1<T_2<\cdots\) be regeneration epochs, and write \(C_k=T_k-T_{k-1}\) for cycle lengths. Assume the cycles have the same distribution and are independent, with \(C_k>0\) almost surely and \(0<\mathbb{E}C_1<\infty\). Let \(R_k\) be the net reward in cycle \(k\). The cycle reward may be signed, as for profit minus cost. For a reward accrued over time, also track its total variation \(V_k\): the total amount of positive and negative reward accumulated in absolute value during cycle \(k\).

Proof. Let \(S_n=\sum_{k=1}^n C_k\), and let \(N(t)=\max\{n:S_n\le t\}\), the number of completed cycles by time \(t\). The standard iid strong law gives \(S_n/n\to\mathbb{E}C_1\) and \(\sum_{k=1}^n R_k/n\to\mathbb{E}R_1\) almost surely. Since the cycle lengths are positive and have finite positive mean, \(N(t)\to\infty\). The inequalities \(S_{N(t)}\le t<S_{N(t)+1}\), together with \(S_n/n\to\mathbb{E}C_1\), imply \(N(t)/t\to1/\mathbb{E}C_1\). Therefore the reward from completed cycles, divided by \(t\), converges to \(\mathbb{E}R_1/\mathbb{E}C_1\).

It remains to control the part of the current cycle that has not been completed. The strong law applied to \(V_k\) gives \(\sum_{k=1}^n V_k/n\to\mathbb{E}V_1\). Subtracting the corresponding limit for \(n-1\) from that for \(n\) shows \(V_n/n\to0\). Thus \(V_{N(t)+1}/t\to0\): indeed, \(V_{N(t)+1}/(N(t)+1)\to0\) while \((N(t)+1)/t\to1/\mathbb{E}C_1\). The unfinished-cycle reward is bounded in absolute value by \(V_{N(t)+1}\), so its contribution divided by \(t\) vanishes. Adding it to the completed-cycle reward proves the claim. \(\square\)

The total-variation condition is important for signed rewards: a small net reward for a cycle does not necessarily mean little reward was exchanged within it. In the examples below, rewards are nonnegative quantities such as operating time, cost, or time in a state. Their within-cycle accumulated amount is bounded by their cycle total, so the condition is automatic when that total has finite expectation.

Worked Example: Age-Based Maintenance

State Occupancy as a Cycle Reward

Occupancy is calculated by using time in a state as the cycle reward. For a finite state space, let \(A_i\) be the time spent in state \(i\) during one cycle. Each \(A_i\) is nonnegative and at most the cycle length. The same cycle-rate result applies to every state.

Proof. Apply the cycle-rate result to the reward that accrues at rate 1 while the process is in state \(i\), and at rate 0 otherwise. Its cycle reward is \(A_i\), and its total variation is also \(A_i\le C_1\), so its time average converges to \(\mathbb{E}A_i/\mathbb{E}C_1\). In every cycle, the state occupation times partition the cycle, so \(\sum_{i\in S}A_i=C_1\). Taking expectations and dividing by the positive finite \(\mathbb{E}C_1\) gives \(\sum_{i\in S}\mathbb{E}A_i/\mathbb{E}C_1=1\). \(\square\)

Why the Ratio Is Not an Average of Cycle Rates

The cycle-rate result uses the ratio of expected reward to expected duration. In general, it does not use the expected value of the reward-to-duration ratio within a single cycle. Short cycles and long cycles occupy different amounts of calendar time, so averaging their individual rates gives them the wrong weights.

Common Pitfall: Net Reward Can Hide Large Within-Cycle Fluctuations

A completed-cycle formula for signed rewards needs care if one wants the reward accumulated at every time \(t\), not just at cycle boundaries. For instance, a cycle might accrue a large positive reward early and an equal negative reward later. Its net cycle reward would be zero, but the reward partway through the cycle could be large. Thus finite expected absolute net reward alone does not ensure that the unfinished-cycle contribution divided by time vanishes.

A concrete incorrect calculation would set the expected net cycle reward to zero, conclude that the long-run accumulated reward per unit time is zero, and ignore the current unfinished cycle. That conclusion does not follow from the net reward alone. The correction is to use a condition that controls within-cycle accumulation, such as finite expected total variation, as in the cycle-rate result above. For nonnegative rewards bounded by the cycle total, the condition holds directly. If one only asks for the sum of rewards over completed cycles at the regeneration epochs, the standard iid strong law gives the corresponding cycle-based ratio without needing to describe within-cycle fluctuations.

In applications, identify the cycle boundary first, specify exactly what reward is counted, and check its integrability and the expected cycle length before taking a ratio. For availability, count operating time rather than the number of operating periods. For cost, include each cost at the cycle in which it is incurred. For occupancy, count time in the state, not merely the number of visits.