Renewal Equations by Conditioning on the First Renewal

Conditioning on the First Renewal

A renewal process starts afresh after each renewal: the interarrivals after the first have the same distribution as the original sequence and are independent of the first interarrival. Conditioning on that first waiting time therefore separates a quantity observed by time $t$ into a contribution from the first cycle and a contribution from the process that follows it. This decomposition is the basic source of renewal equations.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $X_1,X_2,\ldots$ be independent, identically distributed, strictly positive random variables with distribution $F$, and define $S_0=0$, $S_n=X_1+\cdots+X_n$ for $n\ge1$. The renewal count is $N(t)=\max\{n\ge0:S_n\le t\}$, for continuous time $t\ge0$; it is a process with state space $S=\{0,1,2,\ldots\}$. Write $\mathcal{F}_t=\sigma(N(s):0\le s\le t)$ for its natural filtration. We use $F(t)=\mathbb{P}(X_1\le t)$, so an atom at $t$ is included in $F(t)$ and in integrals over $[0,t]$.

Definition: A renewal equation with interarrival distribution $F$ has the form $u(t)=g(t)+\int_{[0,t]}u(t-x)F(dx)$. The function $g$ is the first-cycle contribution, and the integral is the expected continuation after the first renewal by time $t$. The integral includes $x=t$, where the continuation is evaluated at $u(0)$.

The same form applies beyond expected counts. Suppose a quantity $Z(t)$ has a decomposition into a first-cycle term $C(t)$ and a fresh copy of the quantity after the first renewal: $Z(t)=C(t)+\mathbf{1}_{\{X_1\le t\}}Z'(t-X_1)$. Here $Z'$ has the same law as the original response mechanism and is independent of $X_1$; $C(t)$ may depend on $X_1$. Assume the quantities are integrable. If $u(t)=\mathbb{E}[Z(t)]$ and $g(t)=\mathbb{E}[C(t)]$, taking expectations gives the renewal equation.

Theorem (First-renewal decomposition): Under the decomposition and integrability assumptions above, $$ u(t)=g(t)+\int_{[0,t]}u(t-x)F(dx). $$

Proof. Taking expectations in the assumed pathwise decomposition gives $u(t)=\mathbb{E}[C(t)]+\mathbb{E}[\mathbf{1}_{\{X_1\le t\}}Z'(t-X_1)]$. The first term is $g(t)$. Conditional on $X_1=x\le t$, the future response $Z'$ is independent of $X_1$ and has expected value $u(t-x)$. Integrating this conditional expectation against the distribution $F$, restricted to $x\in[0,t]$, gives $\mathbb{E}[\mathbf{1}_{\{X_1\le t\}}Z'(t-X_1)]=\int_{[0,t]}u(t-x)F(dx)$. Adding the two terms proves the identity. $\square$

The Renewal Count Equation

For the renewal count, write $m(t)=\mathbb{E}[N(t)]$. Its first-cycle term is one renewal if $X_1\le t$, and zero otherwise. Once that first renewal has occurred, the remaining count is a fresh renewal count over the remaining time $t-X_1$. Thus the forcing term is $g(t)=F(t)$, not a constant one.

Theorem (Renewal-function equation): If $X_k>0$ almost surely and the $X_k$ are iid with distribution $F$, then $m(t)$ is finite for each finite $t\ge0$ and satisfies $$ m(t)=F(t)+\int_{[0,t]}m(t-x)F(dx). $$

Proof. First verify finiteness. Fix $a>0$, and set $\phi(a)=\mathbb{E}[e^{-aX_1}]$. Since $X_1>0$ almost surely, $0\le e^{-aX_1}<1$ almost surely, so $\phi(a)<1$. For $n\ge1$, the event $S_n\le t$ implies $e^{-aS_n}\ge e^{-at}$, and hence $\mathbb{P}(S_n\le t)\le e^{at}\mathbb{E}[e^{-aS_n}]=e^{at}\phi(a)^n$, where independence gives the last equality. Since $N(t)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le t\}}$, summing these bounds yields $m(t)\le e^{at}\sum_{n\ge1}\phi(a)^n=e^{at}\phi(a)/(1-\phi(a))<\infty$.

Now let $N'(s)$ be the count formed from $X_2,X_3,\ldots$, measured from the first renewal. Pathwise, $N(t)=\mathbf{1}_{\{X_1\le t\}}\bigl(1+N'(t-X_1)\bigr)$. Taking expectations, the first indicator contributes $F(t)$. The sequence $X_2,X_3,\ldots$ is independent of $X_1$ and has the same distribution as the original sequence, so the expected remaining count conditional on $X_1=x\le t$ is $m(t-x)$. Integrating over $x\in[0,t]$ proves the equation. $\square$

Strict positivity is a convenient sufficient condition: it rules out zero-length interarrivals and, as the finiteness argument shows, ensures a finite expected count on every bounded time interval. The equation itself includes endpoint atoms. In particular, when $X_1=t$, the first renewal contributes one and the remaining time is zero.

Worked Example: A Mixed Interarrival Law

Let each interarrival equal $1$ or $2$, each with probability $\tfrac12$. Find the expected number of renewals by time $2$, counting renewals at time $2$.

The distribution has $F(0)=0$, $F(1)=\tfrac12$, and $F(2)=1$, with mass $\tfrac12$ at each of $1$ and $2$. Also $m(0)=0$, since strictly positive interarrivals allow no renewal by time zero. At time $1$, the equation gives $m(1)=F(1)+\tfrac12m(0)=\tfrac12$. At time $2$, both possible first interarrivals are included:

m(2)=F(2)+\tfrac12m(2-1)+\tfrac12m(2-2) =1+\tfrac12\cdot\tfrac12+\tfrac12\cdot0 =\tfrac54.

Check by direct enumeration. If $X_1=2$, which has probability $\tfrac12$, there is one renewal by time $2$, contributing $\tfrac12\cdot1=\tfrac12$ to the expectation. If $X_1=1$, which has probability $\tfrac12$, then $X_2=1$ with probability $\tfrac12$, giving two renewals by time $2$; or $X_2=2$ with probability $\tfrac12$, giving one. The conditional expected count in this case is $\tfrac12\cdot2+\tfrac12\cdot1=\tfrac32$, contributing $\tfrac12\cdot\tfrac32=\tfrac34$. The total is $\tfrac12+\tfrac34=\tfrac54$, as above.

Event Probabilities and the Kernel

Conditioning on the first renewal also applies to event probabilities, but the continuation term depends on what happens at that renewal. For example, suppose each renewal is independently marked a success with probability $p$, independently of all interarrivals and other marks. Let $r(t)$ be the probability of at least one successful renewal by time $t$. If the first interarrival exceeds $t$, success is impossible by time $t$. If it is at most $t$, the first renewal succeeds with probability $p$; if it fails, with probability $1-p$, the process continues with the same success probability over the remaining time.

Takeaway: In this marked-event example, the forcing term is $g(t)=pF(t)$, and continuation requires both a first renewal by $t$ and a failure mark at that renewal. Therefore $r(t)=pF(t)+(1-p)\int_{[0,t]}r(t-x)F(dx)$. The continuation kernel is the defective measure $(1-p)F$, rather than $F$ itself.

Worked Example: Probability of a Successful Renewal

Use the interarrival law with mass $\tfrac12$ at $1$ and $\tfrac12$ at $2$, and let each renewal succeed independently with probability $p=\tfrac12$. Compute $r(1)$ and $r(2)$.

At time zero no renewal has occurred, so $r(0)=0$. At time $1$, the first renewal is by time $1$ with probability $\tfrac12$; conditional on this, it succeeds with probability $\tfrac12$. The continuation term uses the remaining time $0$, where $r(0)=0$. Thus $r(1)=\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac12r(0)=\tfrac14$.

At time $2$, the first renewal is by time $2$ with probability $1$. The continuation contribution is the sum over first interarrivals $1$ and $2$: $$ r(2)=\tfrac12\cdot1+ \tfrac12\left(\tfrac12r(1)+\tfrac12r(0)\right) =\tfrac12+\tfrac12\left(\tfrac12\cdot\tfrac14+\tfrac12\cdot0\right) =\tfrac9{16}. $$

Check by enumerating the first two interarrivals. If $X_1=2$, an event of probability $\tfrac12$, there is one opportunity for success by time $2$, contributing $\tfrac12\cdot\tfrac12=\tfrac14$. If $X_1=1$ and $X_2=1$, the joint probability is $\tfrac14$; two independent marks give success probability $1-(\tfrac12)^2=\tfrac34$, contributing $\tfrac14\cdot\tfrac34=\tfrac3{16}$. If $X_1=1$ and $X_2=2$, the joint probability is $\tfrac14$, but the second renewal is at time $3$, outside the observation interval; the first mark succeeds with probability $\tfrac12$, contributing $\tfrac18$. Adding gives $\tfrac14+\tfrac3{16}+\tfrac18=\tfrac9{16}$.

Renewal Rewards and the Forcing Term

The function $g$ records what is contributed by the first cycle up to the observation horizon. Its precise form depends on the quantity being measured. For counts, the first cycle contributes one if it ends by time $t$, giving $F(t)$. For a reward $R_1$ paid at the first renewal, the first-cycle contribution is $\mathbb{E}[R_1\mathbf{1}_{\{X_1\le t\}}]$. If later rewards follow the same rule independently from cycle to cycle, the expected cumulative reward $v(t)$ satisfies a renewal equation with this reward-specific forcing term and the ordinary kernel $F$.

Worked Example: Reward Equal to the Interarrival

Again let $X_k$ equal $1$ or $2$ with probability $\tfrac12$ each. At each renewal, pay a reward equal to the interarrival that just ended. Let $V(t)$ be the expected total reward paid by time $t$. The first-cycle forcing term is $g(t)=\mathbb{E}[X_1\mathbf{1}_{\{X_1\le t\}}]$, and after the first renewal the expected future reward is $V(t-X_1)$.

At time $1$, only an interarrival of $1$ can end by the horizon, so $V(1)=g(1)+\tfrac12V(0)=\tfrac12\cdot1+\tfrac12\cdot0=\tfrac12$. At time $2$, $g(2)=\tfrac12\cdot1+\tfrac12\cdot2=\tfrac32$, and therefore $$ V(2)=\tfrac32+\tfrac12V(1)+\tfrac12V(0) =\tfrac32+\tfrac12\cdot\tfrac12+\tfrac12\cdot0 =\tfrac74. $$

Check by enumerating cases. If $X_1=2$, the first reward is $2$, contributing $\tfrac12\cdot2=1$. If $X_1=1$, then with probability $\tfrac12$ the second interarrival is $1$, so the total reward by time $2$ is $1+1=2$; with probability $\tfrac12$ it is $2$, so only the first reward $1$ is paid by time $2$. Conditional on $X_1=1$, the expected reward is $\tfrac12\cdot2+\tfrac12\cdot1=\tfrac32$, contributing $\tfrac12\cdot\tfrac32=\tfrac34$. The total is $1+\tfrac34=\tfrac74$, agreeing with the equation.

Common Pitfall: Omitting the First-Renewal Term

A frequent error is to write $m(t)=\int_{[0,t]}m(t-x)F(dx)$ for the renewal count, forgetting that the first renewal itself contributes one. In the mixed example at $t=2$, that incorrect equation gives $\tfrac12m(1)+\tfrac12m(0)=\tfrac14$, not $\tfrac54$. The missing amount is $F(2)=1$, the probability that the first renewal occurs by time $2$. Equivalently, the count decomposition contains $\mathbf{1}_{\{X_1\le t\}}\bigl(1+N'(t-X_1)\bigr)$, not just the remaining count.

Atoms require equal care. The interval in the integral is $[0,t]$, not $[0,t)$, because a renewal exactly at $t$ is counted under $S_n\le t$. In the mixed example, the mass at $X_1=2$ contributes the first renewal at time $2$, while its remaining-time term is $m(0)=0$. Finally, do not assume every event-probability equation has kernel $F$: if continuation is possible only after an unsuccessful mark, the kernel is reduced by that failure probability.

Check Your Understanding

For each question, pay attention to whether the endpoint is included and what happens after the first renewal.

For the mixed law with masses $\tfrac12$ at $1$ and $2$, calculate $m(1)$ from the renewal equation and verify it by listing the possible first interarrivals.
Explain why the first-cycle term for the expected renewal count is $F(t)$, rather than $1$.
If a first-renewal reward is $R_1=X_1^2$, write the forcing term $g(t)$ in terms of $F$.
For independently marked renewals with success probability $p$, explain why the continuation kernel for the probability of at least one success is $(1-p)F$.
In the mixed example, identify the contribution to $m(2)$ from the atom $X_1=2$, including its remaining-time term.