Why the First Cycle Needs Separate Treatment
A regenerative process restarts its probabilistic behavior at certain times. The cycles after a restart often have the same distribution and are independent, so their long-run contribution can be summarized by mean reward divided by mean duration. The process may, however, start in a special condition: the time until its first regeneration, and the reward accumulated before then, need not follow the law of later cycles. The key question is whether that initial segment changes the long-run reward rate.
Let \(X_t\), \(t\ge0\), be a process on a state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(A(t)\) denote cumulative reward by time \(t\), with \(A(0)=0\). The first regeneration occurs after a delay \(D\), which is finite almost surely but need not have finite mean. After that time, let \(C_k\) be the duration of cycle \(k\), and \(Y_k\) its total reward, for \(k\ge1\). We consider pairs \((C_k,Y_k)\) that are iid, with \(0<C_k<\infty\) almost surely, \(c=\mathbb{E}C_1\in(0,\infty)\), and \(\mathbb{E}|Y_1|<\infty\).
To control rewards earned partway through a cycle, let \(Z_0\) bound the total absolute reward variation during the initial segment, and \(Z_k\) bound the total absolute reward variation in later cycle \(k\). Assume \(Z_0<\infty\) almost surely and that the \(Z_k\) are identically distributed with \(\mathbb{E}Z_1<\infty\). The cycle reward satisfies \(|Y_k|\le Z_k\). These assumptions allow rewards to be signed and ensure that the unfinished cycle cannot contribute a lasting rate.
The theorem uses the strong law of large numbers: for iid integrable random variables, their sample averages converge almost surely to their expectation. This standard probability result is taken as given here. The proof below supplies the remaining renewal-count and unfinished-cycle arguments.
Proof. Put \(S_n=\sum_{k=1}^n C_k\), with \(S_0=0\), and define \(N(u)=\max\{n\ge0:S_n\le u\}\), the number of complete ordinary cycles by elapsed time \(u\) after the first regeneration. By the strong law, \(S_n/n\to c>0\), so \(S_n\to\infty\) and \(N(u)\to\infty\) as \(u\to\infty\). For \(N(u)\ge1\), the definition gives \(S_{N(u)}\le u<S_{N(u)+1}\). Dividing by \(N(u)\) and using \(S_n/n\to c\) on both bounding sequence indices yields \(u/N(u)\to c\); hence \(N(u)/u\to1/c\).
Applying the strong law also to \(Y_k\) gives \(\sum_{k=1}^nY_k/n\to\mathbb{E}Y_1\) almost surely. Since \(D\) is finite, \(u=t-D\to\infty\) as \(t\to\infty\). Therefore the rewards from complete ordinary cycles satisfy $$ \frac{\sum_{k=1}^{N(t-D)}Y_k}{t} = \frac{\sum_{k=1}^{N(t-D)}Y_k}{N(t-D)} \cdot\frac{N(t-D)}{t-D} \cdot\frac{t-D}{t} \longrightarrow \frac{\mathbb{E}Y_1}{c}. $$ For sufficiently large \(t\), the denominator \(N(t-D)\) is positive; also \((t-D)/t\to1\).
It remains to bound the initial segment and the unfinished ordinary cycle. After time \(D\), the initial segment contributes a fixed total whose absolute value is at most \(Z_0\); since \(Z_0<\infty\) almost surely, its contribution divided by \(t\) tends to zero. For the ordinary cycles, integrability of \(Z_1\) implies \(Z_n/n\to0\) almost surely: for every \(\varepsilon>0\), \(\sum_{n\ge1}\mathbb{P}(Z_n>\varepsilon n)<\infty\), because the number of positive integers \(n\) with \(\varepsilon n<Z_1\) is at most \(Z_1/\varepsilon\). The Borel–Cantelli lemma then gives the claimed convergence. Since \(N(t-D)/t\to1/c\), the index of the unfinished cycle grows proportionally to \(t\), and thus \(Z_{N(t-D)+1}/t\to0\). Its partial reward is bounded in absolute value by this quantity. The initial segment, complete cycles, and unfinished cycle together make up \(A(t)\); the two boundary contributions vanish after division by \(t\), leaving the stated limit. \(\square\)
Computing the Rate with a Different First Cycle
Worked Example: A Fixed Initial Delay and Two Ordinary Cycle Types
Suppose the initial segment lasts \(D=6\) time units and earns total reward \(17\). Every later cycle independently has one of two outcomes, each with probability \(\tfrac12\): duration \(1\) and reward \(0\), or duration \(3\) and reward \(8\). Rewards are earned at cycle completion. Find the long-run rate.
First, each ordinary cycle has mean duration $$ \mathbb{E}C_1=\tfrac12(1)+\tfrac12(3)=\tfrac12+\tfrac32=2. $$ Its mean reward is $$ \mathbb{E}Y_1=\tfrac12(0)+\tfrac12(8)=4. $$ The theorem gives the rate \(4/2=2\) reward units per time unit. The initial duration and reward are finite, so they do not change this limit.
Check: If the first \(n\) ordinary cycles are observed, their total duration divided by \(n\) converges to \(2\), while their total reward divided by \(n\) converges to \(4\). Their reward-to-time ratio therefore converges to \(4/2=2\), consistent with the theorem.
Worked Example: An Initial Delay with Infinite Mean
Let the initial delay take positive integer values with \(\mathbb{P}(D=n)=1/[n(n+1)]\) for \(n\ge1\). After the delay, every ordinary cycle has duration \(2\) and reward \(3\). The initial segment earns no reward. Show that the long-run rate is still \(3/2\), even though \(\mathbb{E}D=\infty\).
The probabilities sum to one because \(1/[n(n+1)]=1/n-1/(n+1)\), so their sum over \(n\ge1\) is \(1\). Thus \(D\) is finite almost surely. But $$ \mathbb{E}D=\sum_{n=1}^{\infty}n\frac{1}{n(n+1)} =\sum_{n=1}^{\infty}\frac{1}{n+1}=\infty. $$ For each realized finite \(D\), the number of completed ordinary cycles by time \(t>D\) is \(\left\lfloor (t-D)/2\right\rfloor\). Since rewards arrive only at completion, $$ \frac{A(t)}{t} =\frac{3\left\lfloor (t-D)/2\right\rfloor}{t} \longrightarrow \frac32. $$ Indeed, the floor differs from \((t-D)/2\) by less than \(1\); the resulting error after multiplication by \(3/t\) tends to zero, and \((t-D)/t\to1\).
Check: The ordinary-cycle means are \(\mathbb{E}C_1=2\) and \(\mathbb{E}Y_1=3\), so the theorem also gives \(3/2\). The calculation of \(\mathbb{E}D\) shows why requiring a finite mean for the initial delay would be stronger than needed.
Why the Boundary Conditions Matter
Worked Example: An Infinite Delay Can Prevent a Common Rate
Suppose \(D=\infty\) with probability \(\tfrac12\), and \(D=0\) with probability \(\tfrac12\). If \(D=0\), ordinary cycles begin immediately and each has duration \(1\) and reward \(1\). If \(D=\infty\), the process earns no reward at any time. What happens to the long-run rate?
On the event \(D=0\), the number of completed cycles by time \(t\) is \(\lfloor t\rfloor\), so \(A(t)/t=\lfloor t\rfloor/t\to1\). On the event \(D=\infty\), \(A(t)/t=0\) for every \(t\). Thus the limit exists almost surely but is random: it equals \(1\) with probability \(\tfrac12\) and \(0\) with probability \(\tfrac12\). There is no single common rate for both initial conditions. This example fails the theorem’s finite-almost-sure delay assumption.
Check: The ordinary cycles alone have \(\mathbb{E}Y_1/\mathbb{E}C_1=1/1=1\). That value describes paths on which ordinary cycles begin, but it does not describe paths that never reach the first regeneration.
Common mistake. It is incorrect to add the initial delay and reward once to the ordinary-cycle means and then take a ratio. In the first example, this would give \((17+4)/(6+2)=21/8\), not the long-run rate \(2\). The calculation treats the one-time initial segment as if it recurred in every cycle. In fact, after \(n\) ordinary cycles, the initial reward and delay are still just \(17\) and \(6\), whereas ordinary-cycle totals grow on the scale of \(n\). Dividing by elapsed time makes those fixed initial contributions vanish.
The result is useful whenever a process begins out of equilibrium or in a startup configuration but later returns to a repeatable cycle structure. For example, an initial warm-up period can have a different duration and reward law without changing the asymptotic rate, provided it ends almost surely and contributes only a finite total amount of reward. What matters for the limit is the average reward and duration of the repeating cycles, together with control of rewards in a partially completed cycle.
Check Your Understanding
For each question, distinguish the initial segment from the later iid cycles and state which assumptions are relevant.
- Later cycles have mean duration \(5\) and mean reward \(7\). The initial segment has finite duration almost surely and finite total absolute reward almost surely. What is the long-run reward rate?
- Why does a finite-almost-sure initial delay not need to have finite expectation for the delayed renewal-reward limit?
- In the first worked example, recompute the mean cycle duration and mean cycle reward, then verify their ratio.
- What goes wrong in the infinite-delay example if one asserts that every path has long-run rate \(1\)?
- Why must the reward earned during an unfinished ordinary cycle be controlled when proving a limit for cumulative reward?