Dynamic Programming for Discrete Renewal Probabilities

Renewal Probabilities on an Integer Grid

When interarrival times take positive integer values, the probability of a renewal at each integer time can be computed sequentially. At time $n$, a renewal can occur if the preceding renewal was at $n-k$ and the next interarrival is $k$. Summing over the possible values of $k$ gives a finite recursion: to calculate through horizon $H$, only the probabilities at times $0,1,\ldots,H$ are needed. Once these probabilities are known, their sum gives the expected number of renewals through the horizon.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $X_1,X_2,\ldots$ be independent, identically distributed, positive integer-valued interarrival times, and write $f_k=\mathbb{P}(X_1=k)$ for $k\ge1$. Thus $f_k\ge0$ and $\sum_{k=1}^{\infty}f_k=1$. Define the renewal epochs by $S_0=0$ and $S_r=X_1+\cdots+X_r$ for $r\ge1$. Positivity of the interarrivals ensures that the epochs strictly increase.

Definition: For an integer $n\ge1$, the renewal-epoch probability is $u_n=\mathbb{P}(S_r=n\text{ for some }r\ge1)$. Set $u_0=1$, representing the initial epoch. Since the epochs strictly increase, at most one $S_r$ can equal a given $n$. Equivalently, $u_n=\sum_{r\ge1}\mathbb{P}(S_r=n)$ for $n\ge1$.

For an integer horizon $H\ge0$, use the endpoint convention $N(H)=\#\{r\ge1:S_r\le H\}$: renewals at time $H$ are included, but the initial epoch $S_0$ is not counted. The renewal function at this horizon is $m(H)=\mathbb{E}[N(H)]$. Because each interarrival is at least one, $N(H)\le H$, so this expectation is finite without any further moment assumption.

The Finite-Horizon Recursion

Theorem (Renewal-probability recursion): For positive integer-valued iid interarrivals with probabilities $f_k$, the renewal-epoch probabilities satisfy $$ u_0=1,\qquad u_n=\sum_{k=1}^{n}f_k u_{n-k}\quad(n\ge1). $$ For every integer $H\ge0$, the renewal function is $$ m(H)=\sum_{n=1}^{H}u_n, $$ where the sum is zero when $H=0$.

Proof. Fix $n\ge1$. The events $\{S_r=n\}$, for $r\ge1$, are disjoint: if $r<s$, then $S_s>S_r$ because all interarrivals are positive. For each $r\ge1$, condition on $X_r=k$. The sum $S_{r-1}$ uses only $X_1,\ldots,X_{r-1}$, so it is independent of $X_r$. Therefore $$ \mathbb{P}(S_r=n)=\sum_{k=1}^{n}f_k\mathbb{P}(S_{r-1}=n-k). $$ Terms with $k>n$ cannot contribute because $S_{r-1}\ge0$. Summing over $r\ge1$, and noting that for fixed $n$ only $r\le n$ can contribute, gives $$ u_n=\sum_{k=1}^{n}f_k\sum_{r\ge1}\mathbb{P}(S_{r-1}=n-k). $$ If $n-k=0$, the inner sum is $1$, contributed by $S_0=0$, and all later epochs are positive. If $n-k>0$, the inner sum is $u_{n-k}$. With $u_0=1$, this proves the stated recursion. For the renewal function, write $N(H)=\sum_{n=1}^{H}\mathbf{1}_{\{\text{a renewal occurs at }n\}}$. Taking expectations of this finite sum gives $m(H)=\sum_{n=1}^{H}u_n$, as required. $\square$

This result gives a dynamic program: initialize $u_0=1$, then calculate $u_1,u_2,\ldots,u_H$ in that order. At step $n$, every value $u_{n-k}$ on the right has already been computed. The finite-horizon calculation needs only $f_1,\ldots,f_H$; probabilities at larger interarrival times cannot contribute to a renewal by time $H$. With all probabilities stored, the direct recursion uses at most $H(H+1)/2$ products and additions. Exact fractions can be retained throughout, avoiding rounding error.

Set the initial value.
Put $u_0=1$, and set a running total $m(0)=0$.

Advance through the horizon.
For each $n=1,\ldots,H$, calculate $u_n=\sum_{k=1}^{n}f_k u_{n-k}$.

Accumulate the renewal function.
After calculating $u_n$, add it to the running total: $m(n)=m(n-1)+u_n$.

The algorithm is justified at every step by the theorem: its recurrence gives the actual probability at time $n$, and its running total is the expected count through time $n$. The order matters computationally, not because of an approximation, but because the formula for $u_n$ depends only on earlier values.

Worked Example: Interarrivals of One or Three Units

Suppose $f_1=\tfrac12$, $f_3=\tfrac12$, and all other interarrival probabilities are zero. These probabilities sum to $\tfrac12+\tfrac12=1$. Compute the renewal function through $H=6$.

Apply the recursion successively, using the zero probabilities at $k=2$ and $k\ge4$:

\begin{aligned} u_0&=1,\\ u_1&=\tfrac12u_0=\tfrac12,\\ u_2&=\tfrac12u_1=\tfrac14,\\ u_3&=\tfrac12u_2+\tfrac12u_0=\tfrac18+\tfrac12=\tfrac58,\\ u_4&=\tfrac12u_3+\tfrac12u_1=\tfrac5{16}+\tfrac14=\tfrac9{16},\\ u_5&=\tfrac12u_4+\tfrac12u_2=\tfrac9{32}+\tfrac18=\tfrac{13}{32},\\ u_6&=\tfrac12u_5+\tfrac12u_3=\tfrac{13}{64}+\tfrac5{16}=\tfrac{33}{64}. \end{aligned}

Thus $$ m(6)=\tfrac12+\tfrac14+\tfrac58+\tfrac9{16}+\tfrac{13}{32}+\tfrac{33}{64} =\tfrac{32+16+40+36+26+33}{64} =\tfrac{183}{64}. $$

Check by summing probabilities of each renewal count position. For $r=1$, $\mathbb{P}(S_1\le6)=1$. For $r=2$, the largest possible sum is $3+3=6$, so $\mathbb{P}(S_2\le6)=1$. For $r=3$, the sum is at most six exactly when there are zero or one interarrivals of length three; the probability is $\tfrac18+3(\tfrac18)=\tfrac12$. For $r=4$, the sum is at most six exactly when there are zero or one such interarrivals; the probability is $\tfrac1{16}+4(\tfrac1{16})=\tfrac5{16}$. For $r=5$, all five interarrivals must equal one, giving probability $(\tfrac12)^5=\tfrac1{32}$. For $r=6$, all six must equal one, giving probability $(\tfrac12)^6=\tfrac1{64}$. No $r\ge7$ can contribute since $S_r\ge r>6$. Adding these probabilities gives $1+1+\tfrac12+\tfrac5{16}+\tfrac1{32}+\tfrac1{64}=\tfrac{183}{64}$, matching the dynamic program.

Worked Example: Interarrivals of Two or Three Units

Let $f_2=\tfrac13$, $f_3=\tfrac23$, with all other $f_k=0$. The probabilities sum to $\tfrac13+\tfrac23=1$. Find $m(7)$. Since neither possible interarrival is one, $u_1=0$; applying the recursion gives

\begin{aligned} u_2&=\tfrac13u_0=\tfrac13,\\ u_3&=\tfrac23u_0=\tfrac23,\\ u_4&=\tfrac13u_2=\tfrac19,\\ u_5&=\tfrac13u_3+\tfrac23u_2=\tfrac29+\tfrac29=\tfrac49,\\ u_6&=\tfrac13u_4+\tfrac23u_3=\tfrac1{27}+\tfrac49=\tfrac{13}{27},\\ u_7&=\tfrac13u_5+\tfrac23u_4=\tfrac4{27}+\tfrac2{27}=\tfrac6{27}. \end{aligned}

Therefore $m(7)=\tfrac13+\tfrac23+\tfrac19+\tfrac49+\tfrac{13}{27}+\tfrac6{27}=\tfrac{9+18+3+12+13+6}{27}=\tfrac{61}{27}$. The omitted $u_1$ contributes zero.

Check by renewal counts. The first renewal is at or before seven with probability one, and the second is also at or before seven because $S_2\le3+3=6$. The third is at or before seven if all three interarrivals are two, or if exactly one is three. These disjoint cases have probabilities $(\tfrac13)^3=\tfrac1{27}$ and $3(\tfrac23)(\tfrac13)^2=\tfrac6{27}$, respectively. Thus $\mathbb{P}(S_3\le7)=\tfrac7{27}$. A fourth renewal cannot occur by seven because $S_4\ge4\cdot2=8$. The expected count is consequently $1+1+\tfrac7{27}=\tfrac{61}{27}$, agreeing with the sum of the renewal probabilities.

Using the Recursion as a Checkable Calculation

Worked Example: Geometric Interarrivals

Let $X_r$ have the geometric distribution on positive integers with parameter $\tfrac13$, so $f_k=\tfrac13(\tfrac23)^{k-1}$. Compute the renewal function through $H=4$. The probabilities are $f_1=\tfrac13$, $f_2=\tfrac29$, $f_3=\tfrac4{27}$, and $f_4=\tfrac8{81}$. The full distribution is valid because the geometric series sums to $\tfrac13/(1-\tfrac23)=1$.

Using the recursion at each time gives

\begin{aligned} u_1&=\tfrac13,\\ u_2&=\tfrac13\cdot\tfrac13+\tfrac29\cdot1=\tfrac19+\tfrac29=\tfrac13,\\ u_3&=\tfrac13\cdot\tfrac13+\tfrac29\cdot\tfrac13+\tfrac4{27}\cdot1 =\tfrac9{27}=\tfrac13,\\ u_4&=\tfrac13\cdot\tfrac13+\tfrac29\cdot\tfrac13 +\tfrac4{27}\cdot\tfrac13+\tfrac8{81}\cdot1 =\tfrac{27}{81}=\tfrac13. \end{aligned}

Hence $m(4)=\tfrac13+\tfrac13+\tfrac13+\tfrac13=\tfrac43$. One independent interpretation is that geometric interarrivals describe successes in independent Bernoulli trials with success probability $\tfrac13$: a renewal occurs at time $n$ exactly when trial $n$ is a success. Thus each of the four integer times has renewal probability $\tfrac13$, giving expected count $4\cdot\tfrac13=\tfrac43$, as calculated.

Common mistake: setting $u_n=f_n$. The interarrival probability $f_n$ asks whether the next gap is $n$; the renewal probability $u_n$ allows a renewal to occur after several shorter gaps. In the first example, $f_2=0$, but the recursion gives $u_2=f_1u_1=\tfrac12\cdot\tfrac12=\tfrac14$, not zero. The correction is to include every possible preceding renewal time through the convolution sum. Another endpoint error is to exclude a renewal at $H$ when computing $m(H)$. Under the stated convention, the condition is $S_r\le H$, so $u_H$ is included in the sum.

The recursion is useful when exact finite-horizon probabilities are needed and the interarrival distribution is specified on an integer grid. It does not assume that the renewal count has independent increments; it computes only the probabilities of renewal at each grid point and their expected total. For a fixed horizon, no asymptotic approximation or transform inversion is required. Always record the endpoint convention, initialize $u_0=1$, and distinguish the gap probabilities $f_k$ from the renewal probabilities $u_n$.

Check Your Understanding

Use the recurrence and the endpoint convention $S_r\le H$ in each question.

If $f_1=\tfrac14$ and $f_2=\tfrac34$, calculate $u_1,u_2,u_3$ exactly.
Explain why $u_0=1$ is part of the recursion even though the initial epoch is not counted in $N(H)$.
For interarrivals supported on $\{2,4\}$, which of $u_1,u_2,u_3$ must be zero? Justify using the recurrence.
State the exact sum of renewal-epoch probabilities that gives $m(H)$, and explain whether a renewal at $H$ is counted.
Give a reason that only $f_1,\ldots,f_H$ are needed to compute the renewal function through horizon $H$.

Dynamic Programming for Discrete Renewal Probabilities

What You'll Learn