Why General Renewal Counts Have Dependent Increments

Counts in Separate Intervals

A renewal process is built from independent waiting times, but its counts over separate time intervals are not generally independent. The reason is that an interval's count depends on where the process stands when the interval begins: the time since the last renewal affects how soon the next one can occur. Exponential waiting times are a special case, because their memoryless property removes this dependence on elapsed waiting time.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, and let $X_1,X_2,\ldots$ be independent, identically distributed, strictly positive interarrival times. Define the renewal epochs $S_0=0$ and $S_n=X_1+\cdots+X_n$ for $n\ge1$. The renewal count $N(t)$, for continuous time $t\ge0$, takes values in the state space $\mathbb{N}_0=\{0,1,2,\ldots\}$ and counts renewals by time $t$: $N(t)=\#\{n\ge1:S_n\le t\}$. Its history through time $t$ is represented by the filtration $\mathcal{F}_t=\sigma(N(s):0\le s\le t)$.

Definition: For $0\le a<b$, the count in $(a,b]$ is the increment $\Delta(a,b)=N(b)-N(a)$. It counts epochs in $(a,b]$, so an epoch at $b$ is included and an epoch at $a$ is excluded. Two increments are independent if their joint probabilities factor into the product of their marginal probabilities for every pair of count values.

The convention matters when interarrival times can have atoms. Throughout the examples, intervals are of the form $(a,b]$; thus adjacent intervals do not count a shared boundary epoch twice. The process starts with a renewal at time $0$, which is not counted by $N(0)$.

A Two-Point Example: Direct Dependence

Consider interarrival times that equal $1$ with probability $p$ and $3$ with probability $1-p$, where $0<p<1$. The count in the first unit interval tells us whether $X_1=1$. If it does, the next renewal time depends on $X_2$, so the first count changes the chance of a renewal in the following interval.

Worked Example: Adjacent Counts Are Dependent

For the two-point interarrival law just specified, compute the dependence between $A=\Delta(0,1)$ and $B=\Delta(1,2)$. The intervals are $(0,1]$ and $(1,2]$, so they are disjoint under the stated endpoint convention.

Since every interarrival is at least $1$, there can be at most one renewal in either interval. A renewal in $(0,1]$ occurs exactly when $X_1=1$, so $A=\mathbf{1}_{\{X_1=1\}}$. A renewal in $(1,2]$ requires the first renewal at time $1$ and the second interarrival equal to $1$. Therefore $B=\mathbf{1}_{\{X_1=1,\,X_2=1\}}$.

Independence of $X_1$ and $X_2$ gives $\mathbb{E}[A]=p$ and $\mathbb{E}[B]=p^2$. Because $AB=B$, $\mathbb{E}[AB]=p^2$. Thus

\operatorname{Cov}(A,B) =\mathbb{E}[AB]-\mathbb{E}[A]\mathbb{E}[B] =p^2-p\cdot p^2 =p^2(1-p)>0.

Check: For $p=\tfrac12$, the first count has mean $\tfrac12$, the second has mean $\tfrac14$, and their product expectation is $\tfrac14$. The covariance is $\tfrac14-\tfrac12\cdot\tfrac14=\tfrac18$, agreeing with $p^2(1-p)=\tfrac14\cdot\tfrac12=\tfrac18$. Since independent variables with finite means have covariance zero, this positive covariance proves that these increments are dependent.

Proposition: For the two-point interarrival law above, the counts in $(0,1]$ and $(1,2]$ are dependent whenever $0<p<1$.

Proof. The indicators derived in the example give $\mathbb{E}[A]=p$, $\mathbb{E}[B]=p^2$, and $\mathbb{E}[AB]=p^2$, because $AB=B$. Hence $\operatorname{Cov}(A,B)=p^2(1-p)$. The assumptions $0<p<1$ imply $p^2(1-p)>0$, whereas independence and finite expectations would imply zero covariance. Therefore $A$ and $B$ are not independent. $\square$

The restriction $0<p<1$ is substantive. At $p=0$, both counts are constant zero; at $p=1$, both are constant one. Constant random variables are independent, so those boundary cases do not give dependence.

Dependence Need Not Show Up in Covariance

Covariance is a useful test, but it does not capture every form of dependence. The same interarrival law gives a simple example: compare the count in $(0,1]$ with the count in a later interval. Their covariance will be zero, yet their joint distribution will not factor.

Worked Example: Zero Covariance but Dependence

Take $p=\tfrac12$, so each $X_n$ equals $1$ or $3$ with probability $\tfrac12$. Let $A=\Delta(0,1)$ and $C=\Delta(2,3)$. Compute the probabilities needed to test independence.

As before, $A=1$ exactly when $X_1=1$, so $\mathbb{P}(A=1)=\tfrac12$. If $A=0$, then $X_1=3$, giving a renewal at time $3$, and no other renewal by time $3$; thus $C=1$. If $A=1$, then $X_1=1$. When $X_2=1$, renewals occur at times $2$ and $3$, so $C=2$. When $X_2=3$, the next renewal is at time $4$, so $C=0$. Consequently, conditional on $A=1$, $C=0$ or $2$, each with probability $\tfrac12$; conditional on $A=0$, $C=1$ with probability $1$.

In particular, $\mathbb{P}(C=1)=\mathbb{P}(A=0)=\tfrac12$, but $\mathbb{P}(A=1,C=1)=0$. If $A$ and $C$ were independent, that joint probability would instead be $\mathbb{P}(A=1)\mathbb{P}(C=1)=\tfrac12\cdot\tfrac12=\tfrac14$. They are therefore dependent. As a check on the limitation of covariance, the conditional means are $\mathbb{E}[C\mid A=1]=\tfrac12\cdot0+\tfrac12\cdot2=1$ and $\mathbb{E}[C\mid A=0]=1$. Hence $\mathbb{E}[C]=1$ and $\mathbb{E}[AC]=\tfrac12$, giving $\operatorname{Cov}(A,C)=\tfrac12-\tfrac12\cdot1=0$, despite the dependence.

This example shows why dependence should be tested through probabilities or distributions, not only through covariance. Earlier counts can change the distribution of a later count even when they leave its conditional mean unchanged.

Why Exponential Interarrivals Are Different

For exponential interarrivals, renewal counts do have independent increments. The result applies when $X_1,X_2,\ldots$ are independent exponential random variables with a common rate $\lambda>0$, and the process starts with $S_0=0$. We verify the independent-count formula directly. This also makes the contrast with the two-point examples precise.

Theorem: Suppose the interarrivals are independent with exponential rate $\lambda>0$. For any partition $0=t_0<t_1<\cdots<t_r=T$, let $h_j=t_j-t_{j-1}$. For nonnegative integers $k_1,\ldots,k_r$, the counts in the adjacent intervals $(t_{j-1},t_j]$ satisfy $$ \mathbb{P}\bigl(\Delta(t_{j-1},t_j)=k_j,\ 1\le j\le r\bigr) =\prod_{j=1}^r e^{-\lambda h_j}\frac{(\lambda h_j)^{k_j}}{k_j!}. $$ Thus these counts are independent. Counts in any finite collection of disjoint time intervals are also independent.

Proof. Fix $T>0$ and let $m\ge1$. For ordered arrival times $0<s_1<\cdots<s_m\le T$, the transformation from interarrivals to epochs is $x_1=s_1$ and $x_j=s_j-s_{j-1}$ for $2\le j\le m$; its Jacobian determinant is $1$. The joint density of the first $m$ exponential interarrivals is $\lambda^m e^{-\lambda s_m}$. Having exactly $m$ arrivals by $T$ also requires $X_{m+1}>T-s_m$, whose probability is $e^{-\lambda(T-s_m)}$. Multiplying gives the joint density $\lambda^m e^{-\lambda T}$ for the ordered epochs together with no further arrival by $T$. When $m=0$, the probability of no arrival by $T$ is $e^{-\lambda T}$.

Now constrain the ordered epochs to have exactly $k_j$ arrivals in each interval $(t_{j-1},t_j]$, and write $m=\sum_{j=1}^r k_j$. In an interval of length $h_j$, the volume of the region containing $k_j$ ordered points is $h_j^{k_j}/k_j!$: the cube of volume $h_j^{k_j}$ is divided into $k_j!$ equal orderings, and ties have volume zero. The intervals are ordered and nonoverlapping, so the total constrained volume is the product of these volumes. Integrating the density over that region gives $$ \lambda^m e^{-\lambda T}\prod_{j=1}^r\frac{h_j^{k_j}}{k_j!} =\prod_{j=1}^r e^{-\lambda h_j}\frac{(\lambda h_j)^{k_j}}{k_j!}, $$ because $T=\sum_j h_j$ and $m=\sum_j k_j$. This is a product of the marginal probabilities, proving independence for the partition counts. For any finite set of disjoint intervals, include their endpoints and any intervening gaps in a partition of $[0,T]$. The partition counts are independent by the formula; summing over the counts in the gap intervals preserves the product factorization for the selected intervals. Therefore counts in the original disjoint intervals are independent as well. $\square$

The exponential law's lack of memory is the probabilistic reason behind this special behavior: conditional on having waited $u$ time units without a renewal, the remaining wait is still exponential with rate $\lambda$. The proof above establishes the independent-count formula directly, without assuming that property is enough by itself.

Worked Example: Exponential Counts on Two Intervals

Let the interarrivals be independent exponential random variables with rate $\lambda=2$. Compare the event of exactly one renewal in $(0,\tfrac12]$ and no renewals in $(\tfrac12,\tfrac32]$. The interval lengths are $\tfrac12$ and $1$.

The theorem gives probability $e^{-2(1/2)}(2(1/2))^1/1!=e^{-1}$ for exactly one renewal in the first interval. It gives probability $e^{-2(1)}(2(1))^0/0!=e^{-2}$ for zero in the second. The joint probability is therefore $e^{-1}e^{-2}=e^{-3}$.

Check: Applying the joint formula directly with $k_1=1$, $k_2=0$, $h_1=\tfrac12$, and $h_2=1$ gives $e^{-2(1/2)}(2(1/2))^1/1!\times e^{-2(1)}(2(1))^0/0!=e^{-3}$, exactly the product of the two marginal probabilities.

A Common Mistake and Its Correction

Common mistake: “The interarrival times are independent, so counts in disjoint intervals must be independent.” Independence of the gaps does not imply independence of the counts: the interval boundary may fall partway through a gap, and the location of that boundary relative to the current renewal epoch depends on earlier gaps.

For a concrete incorrect calculation, return to the two-point example with $p=\tfrac12$, and let $A=\Delta(0,1)$, $B=\Delta(1,2)$. The mistaken independence assumption gives $\mathbb{P}(A=1,B=1)=\mathbb{P}(A=1)\mathbb{P}(B=1)=\tfrac12\cdot\tfrac14=\tfrac18$. But $A=1$ and $B=1$ occur exactly when $X_1=X_2=1$, so the actual probability is $\tfrac12\cdot\tfrac12=\tfrac14$. The correction is to derive each interval event from the renewal epochs, then check whether the resulting events factor; do not infer independence from the interarrivals alone.

Independent increments are an important feature of the exponential-interarrival renewal process, not a generic property of renewal counts. For other interarrival laws, the increment distribution can depend on the renewal history at the start of an interval. The two-point calculations demonstrate this dependence explicitly, while the exponential calculation identifies a setting in which it disappears.

Check Your Understanding

Use the endpoint convention $(a,b]$ and show the event calculations that support your answers.

For interarrivals $1$ with probability $p$ and $3$ with probability $1-p$, derive the indicators for $\Delta(0,1)$ and $\Delta(1,2)$. For which $p$ are these counts dependent?
In the zero-covariance example with $p=\tfrac12$, calculate $\mathbb{P}(A=1,C=1)$ and compare it with $\mathbb{P}(A=1)\mathbb{P}(C=1)$.
For exponential interarrivals of rate $\lambda$, use the theorem to find the probability of zero renewals in $(0,a]$ and exactly two in $(a,a+b]$, where $a,b>0$.
Why does independence of interarrival times alone not establish independence of renewal-count increments?
What feature of exponential interarrivals makes them a special case for independent increments?