Recognizing Regenerative Structure in Stochastic Models

What Makes a Cycle Regenerative?

Many stochastic models can be divided into successive intervals: times between renewals, excursions away from an empty population, operating-and-repair intervals in a reliability model, or returns of a queue to the empty state. The intervals may have similar descriptions without being independent or identically distributed. To recognize a regenerative structure, check not only whether the system appears to restart, but also whether it actually returns to the same probabilistic starting condition and whether future randomness is fresh.

Let \((X_t)_{t\ge0}\) be a process on a state space \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\). Time may be discrete or continuous. Let \((\mathcal F_t)\) be a filtration describing the information available by time \(t\); in discrete time write \((\mathcal F_n)\). Candidate regeneration times \(T_0<T_1<T_2<\cdots\) are stopping times: for each \(t\), the event \(\{T_r\le t\}\) is known by time \(t\). A cycle is the path segment from \(T_r\) up to, but not including, \(T_{r+1}\), together with its duration \(L_r=T_{r+1}-T_r\). The endpoint is the start of the next cycle; when recording the path, its reset state can be recorded as the next cycle's initial state.

Definition: The cycles after \(T_0\) are regenerative and iid if each \(T_r\) is finite almost surely, and the random cycle objects (duration and path segment) are independent and have the same distribution for every \(r\ge0\). A regeneration means that, at \(T_r\), the system restarts in the same probabilistic condition and the future after \(T_r\) is independent of the history through \(T_r\), with a law not depending on \(r\).

The cycle object is the whole segment, not just its length. Equal distributions of the \(L_r\) alone do not establish iid cycles: path features or rewards within different cycles can still be dependent. Conversely, a first interval that starts from a special initial condition need not have the same law as later cycles. The iid claim concerns cycles beginning at the stated regeneration times.

A Practical Test and Its Justification

A useful test is to identify the state of the system at each proposed regeneration time, then ask two questions. First, is the system in the same complete probabilistic condition each time? Second, is the randomness that determines what happens next independent of the past and governed by the same rule? A state that omits a persistent environment, an age, or a residual lifetime may not be a complete condition.

Proposition: Suppose \((C_r)_{r\ge0}\) are cycle objects and \(\mathcal H_r\) is the information from all cycles before cycle \(r\). If, for every \(r\), the conditional distribution of \(C_r\) given \(\mathcal H_r\) is a fixed distribution \(\nu\), almost surely, then the \(C_r\) are iid with distribution \(\nu\). Conversely, if the \(C_r\) are iid with distribution \(\nu\), then their conditional distribution given \(\mathcal H_r\) is \(\nu\), almost surely.

Proof. For measurable sets \(A_0,\ldots,A_m\) of cycle objects, the fixed conditional distribution gives \(\mathbb P(C_m\in A_m\mid\mathcal H_m)=\nu(A_m)\) almost surely. Since the earlier events \(\{C_0\in A_0,\ldots,C_{m-1}\in A_{m-1}\}\) belong to \(\mathcal H_m\), taking expectations yields \(\mathbb P(C_0\in A_0,\ldots,C_m\in A_m)=\nu(A_m)\mathbb P(C_0\in A_0,\ldots,C_{m-1}\in A_{m-1})\). Iterating this identity gives \(\prod_{r=0}^m\nu(A_r)\), which is the definition of independence with common distribution \(\nu\). In the converse direction, independence implies that for every measurable \(A\) and every event \(H\in\mathcal H_r\), \(\mathbb P(C_r\in A,H)=\nu(A)\mathbb P(H)\). This is exactly the defining integral identity for the conditional probability \(\mathbb P(C_r\in A\mid\mathcal H_r)=\nu(A)\) almost surely. \(\square\)

In models built from independent innovations, the reset-and-fresh-randomness test has a particularly direct justification.

Theorem: Let \((U_n)_{n\ge1}\) be iid innovations, and suppose the state evolves by the same rule after each proposed regeneration time, starting from a fixed reset state. Suppose each cycle ends according to a rule that uses only the innovations since its start, and every cycle ends in a finite number of steps almost surely. Then the successive cycle objects are iid.

Proof. Let \(\mathcal F_n=\sigma(U_1,\ldots,U_n)\). At a finite stopping index \(T\), the innovations \(U_{T+1},U_{T+2},\ldots\) are iid and independent of \(\mathcal F_T\). To verify this fact, take an event \(A\in\mathcal F_T\) and a finite-coordinate event \(D\) concerning the next \(q\) innovations. Decompose \(A\) into the disjoint events \(A\cap\{T=n\}\). Each belongs to \(\mathcal F_n\), so independence of the original innovations gives \(\mathbb P(A\cap\{T=n\}\cap\{(U_{T+1},\ldots,U_{T+q})\in D\})=\mathbb P(A\cap\{T=n\})\mathbb P((U_1,\ldots,U_q)\in D)\). Summing over \(n\) proves the asserted independence for every finite block of future innovations. The reset state and the identical cycle rule mean that the next cycle is the same function of this fresh innovation sequence after each \(T_r\). Its conditional law given the past is therefore the same fixed law at every cycle. The proposition now gives iid cycle objects. \(\square\)

Worked Examples Across Models

Worked Example: An Ordinary Renewal Process

Let \((X_k)_{k\ge1}\) be iid positive integer-valued interarrival times on a probability space \((\Omega,\mathcal F,\mathbb P)\), and define the renewal epochs \(S_0=0\) and \(S_n=\sum_{k=1}^nX_k\). The cycle from \(S_{n-1}\) to \(S_n\) has length \(X_n\). Is this a regenerative model?

Yes. At each \(S_n\), the renewal count starts its next interval from zero elapsed time. The cycle length is determined by the next interarrival time, which is independent of \(X_1,\ldots,X_n\) and has the same distribution as every other interarrival time. In this description, the cycle object is just its duration. Thus the cycles are iid by the definition of the renewal process.

For a concrete check, suppose \(\mathbb P(X_k=1)=\mathbb P(X_k=2)=\tfrac12\). Each cycle has mean length \(\mathbb E X_k=1\cdot\tfrac12+2\cdot\tfrac12=\tfrac32\), and each cycle has probability \(\tfrac12\) of length 1 and \(\tfrac12\) of length 2. The probabilities sum to \(\tfrac12+\tfrac12=1\); the iid claim follows from the assumed independence of the interarrival times, not from this calculation of the marginal distribution.

Worked Example: A Population That Empties and Restarts

Consider a discrete-time population \(X_n\in\{0,1\}\), with filtration \(\mathcal F_n=\sigma(U_1,\ldots,U_n)\), where the \(U_n\) are iid Bernoulli variables with \(\mathbb P(U_n=1)=\mathbb P(U_n=0)=\tfrac12\). From state 0, \(U_{n+1}=1\) starts a one-member population and \(U_{n+1}=0\) leaves it empty. From state 1, \(U_{n+1}=1\) means the member survives and \(U_{n+1}=0\) means extinction. Start at \(X_0=0\), and let the cycles be successive intervals from one visit to 0 to the next.

Every cycle starts in the same state, 0, and uses fresh Bernoulli variables. The endpoint is the first subsequent return to 0, so the cycle rule is the same at each start. Its length \(L\) is 1 if immigration does not occur on the first step, an event of probability \(\tfrac12\). For \(k\ge1\), length \(k+1\) requires immigration on the first step, \(k-1\) consecutive survivals, and then extinction. These are \(k+1\) specified independent outcomes, so \(\mathbb P(L=k+1)=(\tfrac12)^{k+1}\).

Check the distribution and mean. The probabilities sum to \(\tfrac12+\sum_{k\ge1}2^{-(k+1)}=\tfrac12+\tfrac12=1\). Using \(\sum_{k\ge1}k2^{-(k+1)}=1\) and \(\sum_{k\ge1}2^{-(k+1)}=\tfrac12\), the mean is \(\mathbb E L=\tfrac12+\sum_{k\ge1}(k+1)2^{-(k+1)}=\tfrac12+1+\tfrac12=2\). The iid conclusion concerns the entire excursions, and follows because each uses a fresh block of the same iid Bernoulli sequence and applies the same rule.

Worked Example: Reliability Cycles with a Hidden Environment

A repairable unit alternates between operation and repair. Let the probability space include a single fair random variable \(Z\in\{0,1\}\), chosen once and never reset. In every cycle the up-time is \(U_r=1\) if \(Z=0\), and \(U_r=2\) if \(Z=1\); every repair time is 1. Each cycle begins when repair is complete. The up-time marginally has probability \(\tfrac12\) of each of 1 and 2, so do these cycles qualify as iid?

No. The shared \(Z\) determines every cycle's up-time. For example, \(\mathbb P(U_1=1,U_2=1)=\mathbb P(Z=0)=\tfrac12\), whereas independence would require \(\mathbb P(U_1=1)\mathbb P(U_2=1)=\tfrac12\cdot\tfrac12=\tfrac14\). The cycle descriptions alternate in the same way, but their durations are dependent. If the environment \(Z\) is included in the system state, it is visible that the state at repair completion has not been reset to a common probabilistic condition. Similar-looking cycles are not enough.

Worked Example: Empty-State Cycles in an M/M/1 Queue

Consider an M/M/1 queue with state \(X_t\in\{0,1,2,\ldots\}\), arrival rate \(\lambda\), and service rate \(\mu\). Arrivals form a Poisson process; service times are exponential with rate \(\mu\); the input processes and successive service times are independent. Take cycle starts to be the times the queue becomes empty, and assume \(\lambda<\mu\), so busy periods end almost surely.

At each cycle start the queue length is 0. The time until the next arrival is a fresh exponential waiting time with rate \(\lambda\). From that arrival onward, the queue evolves using fresh arrivals and service times; when the queue empties, the next cycle begins. The independent-increments and memoryless properties of the Poisson arrival process, together with independent service times, ensure that the randomness after an empty time has the same law and is independent of the history up to that time. Thus these empty-to-empty path segments are iid. Here the reset state is the queue length and the assumptions include fresh, independent service and arrival mechanisms. If a shared service-speed environment persisted between cycles, the empty queue length alone would not certify regeneration.

Common Mistakes and a Reliable Checklist

Common mistake: counting too few required outcomes. In the population example, the incorrect calculation \(\mathbb P(L=k+1)=2^{-k}\) counts the \(k\) transitions after the cycle starts but omits the initial immigration. For \(k=1\), a length-2 cycle requires both immigration and extinction, so its probability is \(\tfrac12\cdot\tfrac12=\tfrac14\), not \(\tfrac12\). The corrected general probability is \(2^{-(k+1)}\), accounting for the initial immigration and all \(k\) subsequent transition outcomes. Its mean calculation must use those corrected probabilities: \(\mathbb E L=\tfrac12+\sum_{k\ge1}(k+1)2^{-(k+1)}=2\).

When examining a new model, use the following checklist:

Specify the proposed cycle-start times and check that they are stopping times for the information being used.
Identify the complete system condition at a cycle start, including any environment, age, residual lifetime, or other persistent variable that affects the future.
Check that every cycle follows the same rule and that the randomness used after a start is independent of the past.
Check that the proposed cycles end in finite time almost surely if the definition requires finite cycles.
Check independence and identical distribution of the whole path segments, not just their durations.

These checks matter because regenerative structure is the basis for treating repeated cycles as repeated samples from one common law. If the cycles are only similar in appearance, conclusions that require iid cycles cannot be justified by counting them as though they were independent replicates.

Check Your Understanding

For each question, state which part of the regeneration test is relevant.

In an ordinary renewal process, what property of the interarrival times makes successive cycle lengths independent?
For the population model, calculate \(\mathbb P(L=3)\) by listing the required outcomes in order.
In the reliability example, why does observing the same repair-complete condition not imply that the cycles are independent?
In a queueing model, name one condition about the future arrival and service mechanisms needed for empty-state cycles to be regenerative.
Can iid cycle lengths by themselves establish that the entire cycle paths are iid? Explain.