Forward Recurrence Times at a Random Observation Time

Time from an Observation to the Next Renewal

Suppose events occur at renewal times $S_0,S_1,S_2,\ldots$, with $S_0=0$ and successive gaps given by independent, identically distributed positive random variables. At an observation time $t$, the next renewal may be close or far away, depending on where $t$ falls within its current interarrival interval. The resulting forward recurrence time is random even when the observation time $t$ is fixed.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $X_1,X_2,\ldots$ be independent, identically distributed random variables with $X_n>0$ almost surely and finite mean $\mu=\mathbb{E}X_1$, where $0<\mu<\infty$. Define $S_n=X_1+\cdots+X_n$ for $n\ge1$, and $S_0=0$. For $t\ge0$, let $N(t)=\max\{n\ge0:S_n\le t\}$. The forward recurrence time at $t$ is $R(t)=S_{N(t)+1}-t$. We use the strict tail $\mathbb{P}(R(t)>x)$, for $x\ge0$, and write $\overline F(u)=\mathbb{P}(X_1>u)$ for $u\ge0$.

Definition: The interarrival distribution is nonarithmetic if there is no $h>0$ such that $\mathbb{P}(X_1\in h\mathbb{Z})=1$. Otherwise it is arithmetic. Nonarithmeticity rules out a common lattice for all renewal times; it will be essential for the fixed-time limit below.

The observation time in this result is a deterministic $t$ that tends to infinity. “Random” refers to the position of $t$ within the renewal interval, not to an additional random choice of observation time. The exact finite-time formula shows how the renewal process produces that randomness.

An Exact Tail Formula

Define the renewal measure $U$ on $[0,\infty)$ by $U(C)=\sum_{n=0}^{\infty}\mathbb{P}(S_n\in C)$ for measurable sets $C$. It includes the unit mass at $S_0=0$. Because the interarrivals are positive with finite positive mean, the renewal times tend to infinity almost surely, so $N(t)$ is finite almost surely.

Proposition: For every $t\ge0$ and $x\ge0$, $$ \mathbb{P}(R(t)>x)=\int_{[0,t]}\overline F(t+x-s)\,U(ds). $$ The inequality in the event is strict, including when $t$ itself is a renewal time.

Proof. For each $n\ge0$, the event $N(t)=n$ is $S_n\le t<S_{n+1}$. On this event, $R(t)>x$ exactly when $S_{n+1}>t+x$. Since $x\ge0$, the latter inequality also implies $S_{n+1}>t$, so the joint event is exactly $\{S_n\le t,\ X_{n+1}>t+x-S_n\}$. The variable $X_{n+1}$ is independent of $S_n$; conditional on $S_n=s\le t$, the probability of this event is $\overline F(t+x-s)$. The events $N(t)=n$ are disjoint and exhaust the sample space. Summing their probabilities gives $$ \mathbb{P}(R(t)>x)=\sum_{n=0}^{\infty}\mathbb{E}\!\left[\mathbf{1}_{\{S_n\le t\}}\overline F(t+x-S_n)\right] =\int_{[0,t]}\overline F(t+x-s)\,U(ds). $$ The sum is well-defined: its terms are nonnegative and the events being summed are disjoint. This proves the identity. $\square$

This formula is useful because its integrand depends on $t-s$, the time since a possible renewal, and the renewal measure records where renewals can occur. To take $t$ to infinity, we use the key renewal theorem. We state the version needed here as a standard result from the earlier material on renewal equations; its proof is not repeated here.

Standard result (Key Renewal Theorem): Suppose the interarrival distribution is nonarithmetic, has mean $0<\mu<\infty$, and $g:[0,\infty)\to\mathbb{R}$ is directly Riemann integrable. Then $$ \lim_{t\to\infty}\int_{[0,t]}g(t-s)\,U(ds)=\frac{1}{\mu}\int_0^\infty g(y)\,dy. $$ A nonnegative, nonincreasing, integrable function such as the tail functions used below is directly Riemann integrable.

The Limiting Forward-Recurrence Distribution

Theorem: Let $X_1,X_2,\ldots$ be independent, identically distributed, strictly positive interarrivals with finite mean $0<\mu<\infty$ and a nonarithmetic distribution. Then, for every $x\ge0$, $$ \lim_{t\to\infty}\mathbb{P}(R(t)>x) =\frac{1}{\mu}\int_x^\infty \overline F(u)\,du. $$ The right-hand side is the tail of a probability distribution on $[0,\infty)$; consequently $R(t)$ converges in distribution to that law.

Proof. Fix $x\ge0$ and set $g_x(y)=\overline F(x+y)$ for $y\ge0$. This function is nonnegative and nonincreasing. Also, $$ \int_0^\infty g_x(y)\,dy=\int_x^\infty \overline F(u)\,du\le\int_0^\infty \overline F(u)\,du=\mathbb{E}X_1=\mu<\infty. $$ The tail-integral identity for the mean follows by integrating the indicator $\mathbf{1}_{\{X_1>u\}}$ over $u\ge0$ and taking expectations. Thus $g_x$ is directly Riemann integrable. Applying the stated key renewal theorem to the exact tail formula gives $$ \lim_{t\to\infty}\mathbb{P}(R(t)>x) =\lim_{t\to\infty}\int_{[0,t]}g_x(t-s)\,U(ds) =\frac{1}{\mu}\int_0^\infty g_x(y)\,dy =\frac{1}{\mu}\int_x^\infty\overline F(u)\,du. $$ It remains to verify that these limits define a probability law and imply convergence in distribution. At $x=0$, the tail-integral identity gives $\mu^{-1}\int_0^\infty\overline F(u)\,du=1$. The integral decreases to zero as $x\to\infty$, because $\overline F$ is integrable. It is continuous in $x$: for $a,b\ge0$, the difference between the integrals from $a$ and $b$ is bounded in absolute value by $|a-b|$, since $0\le\overline F\le1$. Hence $H(x)=1-\mu^{-1}\int_x^\infty\overline F(u)\,du$ for $x\ge0$, extended by $H(x)=0$ for $x<0$, is a continuous distribution function. For $x\ge0$, $\mathbb{P}(R(t)\le x)=1-\mathbb{P}(R(t)>x)$ converges to $H(x)$; for $x<0$, both distribution functions are zero. Convergence of the distribution functions at every continuity point of $H$ is convergence in distribution. $\square$

The hypotheses do separate jobs. Finite positive mean supplies the normalization and integrability, while nonarithmeticity permits the fixed-time key renewal limit. The theorem is not a claim that every renewal process has a limit at every observation time.

Worked Example: Exponential Interarrivals

Let the interarrivals have an exponential distribution with rate $2$, so $\overline F(u)=e^{-2u}$ for $u\ge0$. This distribution is nonarithmetic, and its mean is $\mu=1/2$. The limiting tail is $$ \frac{1}{1/2}\int_x^\infty e^{-2u}\,du =2\left[-\frac12e^{-2u}\right]_{x}^{\infty} =e^{-2x},\qquad x\ge0. $$ Thus the limiting distribution function is $1-e^{-2x}$ for $x\ge0$, and zero for $x<0$.

Check: At $x=0$, the tail is $e^0=1$; as $x\to\infty$, $e^{-2x}\to0$. Both are required of a probability tail. The calculation uses the strict tail $\mathbb{P}(R(t)>x)$; the limiting distribution has no atoms because its distribution function is continuous.

Worked Example: Erlang Interarrivals with Two Stages

Suppose $X_1$ has an Erlang distribution with shape $2$ and rate $1$, with density $u e^{-u}$ for $u\ge0$. Its survival function is $\overline F(u)=e^{-u}(1+u)$. Indeed, integrating the density from $u$ to infinity gives $$ \int_u^\infty v e^{-v}\,dv =\left[-(v+1)e^{-v}\right]_{u}^{\infty} =(u+1)e^{-u}. $$ The mean is $\mu=2$, and this continuous distribution is nonarithmetic. Therefore $$ \lim_{t\to\infty}\mathbb{P}(R(t)>x) =\frac12\int_x^\infty e^{-u}(1+u)\,du =\frac12(x+2)e^{-x},\qquad x\ge0. $$ Here the integral follows from the antiderivative $-(u+2)e^{-u}$, whose derivative is $(u+1)e^{-u}$.

Check: At $x=0$, the expression is $\tfrac12(2)e^0=1$. Differentiating the integral with respect to its lower endpoint gives $-e^{-x}(1+x)$, so the derivative of the proposed tail, $-\tfrac12(x+1)e^{-x}$, is exactly $-\overline F(x)/\mu$, as the tail-integral formula requires.

Worked Example: A Shifted Exponential Interarrival Law

Let $X_1=1+Y$, where $Y$ is exponential with rate $1$. Then $\mu=1+\mathbb{E}Y=2$, and the distribution is nonarithmetic. Its strict survival function is $$ \overline F(u)= \begin{cases} 1,&0\le u<1,\\ e^{-(u-1)},&u\ge1. \end{cases} $$ At $u=1$, the second expression equals $1$, since $Y>0$ almost surely. For $0\le x<1$, split the tail integral at $1$: $$ \frac12\int_x^\infty\overline F(u)\,du =\frac12\left(\int_x^1 1\,du+\int_1^\infty e^{-(u-1)}\,du\right) =\frac12((1-x)+1)=1-\frac{x}{2}. $$ For $x\ge1$, $$ \frac12\int_x^\infty e^{-(u-1)}\,du =\frac12e^{-(x-1)}. $$ The two expressions agree at $x=1$, where each equals $1/2$.

Check: At $x=0$, the first expression gives $1$; for $x\ge1$, the second decreases to zero. At the join, the left-hand formula gives $1-\tfrac12=\tfrac12$, and the right-hand formula gives $\tfrac12e^0=\tfrac12$.

Why Arithmetic Interarrivals Can Fail

For arithmetic interarrivals, the renewal process can retain the observation time’s phase relative to the lattice. The following example shows why nonarithmeticity cannot simply be dropped from a fixed-time limit theorem.

Worked Example: Deterministic Unit Interarrivals

Let $X_n=1$ almost surely for every $n$. Then $\mu=1$, and the renewal times are the nonnegative integers. For $t=n+\alpha$, where $n$ is a nonnegative integer and $0\le\alpha<1$, the next renewal is $n+1$, so $R(t)=1-\alpha$ with probability one. In particular, for the strict event $R(t)>\tfrac12$, take first $t=n+\tfrac14$: then $R(t)=\tfrac34$, and the probability is $1$. Take instead $t=n+\tfrac34$: then $R(t)=\tfrac14$, and the probability is $0$. Both sequences of observation times tend to infinity, so the probabilities do not converge.

The tail-integral expression from the theorem, if used as a candidate, is $$ \int_x^\infty\mathbb{P}(X_1>u)\,du =\begin{cases} \displaystyle\int_x^1 1\,du=1-x,&0\le x<1,\\[4pt] 0,&x\ge1. \end{cases} $$ For example, at $x=\tfrac12$ this candidate equals $\tfrac12$. It is continuous at $x=1$, but it does not describe the oscillating fixed-time probabilities just computed.

Common pitfall. Do not replace the tail integral by the value of its integrand at the lower endpoint. In the deterministic example, $\mathbb{P}(X_1>u)=1$ for $0\le u<1$, but at $x=\tfrac12$ the integral is $\int_{1/2}^{1}1\,du=1-\tfrac12=\tfrac12$, not $1$. Also, even a well-defined, continuous candidate tail does not prove convergence: the nonarithmetic hypothesis is needed for the key renewal theorem, and the deterministic example shows the failure when it is absent.

The formula summarizes how the interarrival tail and mean jointly determine the distant-observation law. The mean normalizes the tail integral to total mass one; the tail $\overline F(u)$ describes how likely an interval is to extend at least $u$ units beyond its start. In applications, first check that interarrivals are positive, have finite positive mean, and are nonarithmetic before using the fixed-time limit. If the observation-time probabilities retain a lattice phase, the limiting formula need not apply.

Check Your Understanding

Use the strict-tail convention $\mathbb{P}(R(t)>x)$ and state which hypotheses justify any limiting calculation.

Write the renewal-measure formula for $\mathbb{P}(R(t)>x)$, and explain why the event involving $X_{n+1}$ is strict.
For exponential interarrivals of rate $3$, compute the limiting forward-recurrence tail and check its value at $x=0$.
For the shape-$2$, rate-$1$ Erlang law, evaluate the limiting tail at $x=0$ and $x=2$.
For unit deterministic interarrivals, compute $\mathbb{P}(R(t)>\tfrac12)$ along $t=n+\tfrac14$ and $t=n+\tfrac34$. What does this imply about convergence?
Why does finite mean imply that the function $g_x(y)=\mathbb{P}(X_1>x+y)$ is integrable?