Renewal Count Bounds from Bounded Interarrivals

Bounding a Renewal Count from Interarrival Limits

A renewal count records how many events have occurred by a given time. When each gap between events is known to be neither too short nor too long, the count is constrained even before its probability distribution is calculated. These constraints are deterministic: they hold for every sample path on which the interarrival bounds hold. They are useful both for checking a computed count and for bounding its expectation.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $X_1,X_2,\ldots$ be independent, identically distributed, strictly positive interarrival times. For $n\ge1$, define the $n$th renewal epoch by $S_n=X_1+\cdots+X_n$, and set $S_0=0$. The renewal count $N(t)$, for continuous time $t\ge0$, takes values in the state space $\mathbb{Z}_{\ge0}$ and counts renewals at or before $t$: $N(t)=\max\{n\ge0:S_n\le t\}$. In particular, an arrival exactly at time $t$ is included. Suppose there are constants $0<a\le b<\infty$ such that $\mathbb{P}(a\le X_k\le b)=1$ for every $k$.

Theorem (Deterministic renewal-count bounds): Under these assumptions, for every fixed $t\ge0$, almost surely, $$ \left\lfloor\frac{t}{b}\right\rfloor\le N(t)\le\left\lfloor\frac{t}{a}\right\rfloor. $$ Both bounds are sharp if only $a$ and $b$ are known. The floor is the greatest integer less than or equal to its argument.

The smaller possible interarrival time $a$ controls the largest possible count: repeated gaps of length $a$ pack the most renewals into the interval. The larger possible interarrival time $b$ controls the smallest possible count: repeated gaps of length $b$ pack the fewest. The floors matter because $N(t)$ is integer-valued, and because the definition includes a renewal occurring exactly at $t$.

Proof. Since each event $\{a\le X_k\le b\}$ has probability one, their countable intersection also has probability one. Fix any sample point in this intersection. For every $n\ge1$, summing the interarrival inequalities gives $na\le S_n\le nb$. Let $r=\lfloor t/b\rfloor$. Then $rb\le t$, so $S_r\le rb\le t$ when $r\ge1$; when $r=0$, $S_0=0\le t$. Thus $r$ renewals have occurred by time $t$, and $r\le N(t)$. For the other direction, put $q=N(t)$. If $q=0$, then $q\le\lfloor t/a\rfloor$, since $t/a\ge0$. If $q\ge1$, the definition of $N(t)$ gives $S_q\le t$, and the lower bound on the epochs gives $qa\le S_q\le t$. Therefore $q\le t/a$, and, since $q$ is an integer, $q\le\lfloor t/a\rfloor$. This proves both inequalities. For sharpness, if every interarrival equals $b$, then $S_n=nb$ and $N(t)=\lfloor t/b\rfloor$. If every interarrival equals $a$, then $N(t)=\lfloor t/a\rfloor$. These constant interarrival models satisfy the stated bounds, so neither endpoint can be improved using only $a$ and $b$. $\square$

The almost-sure statement can be read simultaneously for all $t\ge0$: on the probability-one event where every interarrival lies in $[a,b]$, the pathwise proof applies to every nonnegative real $t$. At $t=0$, both floors are zero and $N(0)=0$, because every interarrival is strictly positive. If $a=b$, the two bounds agree and determine the count exactly.

Worked Example: Checking a Sample Path at a Renewal Epoch

Suppose the interarrival times are bounded by $2\le X_k\le4$. On one sample path, the first four gaps are $4,2,2,4$. Find $N(8)$ and check it against the deterministic bounds.

The successive epochs are $S_1=4$, $S_2=4+2=6$, $S_3=6+2=8$, and $S_4=8+4=12$. Since $S_3=8\le8$ but $S_4=12>8$, the count is $N(8)=3$. The bounds are $\lfloor8/4\rfloor=2$ and $\lfloor8/2\rfloor=4$, so $2\le3\le4$.

Check: the third renewal is included because the convention is $S_n\le t$, not $S_n<t$. If the count excluded renewals exactly at $t$, this sample path would instead have count $2$; that is a different convention and requires adjusting endpoint statements. Under the inclusive convention used here, the theorem's bounds hold at the boundary as stated.

Bounds for the Expected Renewal Count

The renewal function is $m(t)=\mathbb{E}[N(t)]$. The pathwise inequalities also give an immediate bound on $m(t)$. This does not require calculating the distribution of $N(t)$, although the interarrivals here are assumed identically distributed as part of the renewal model.

Corollary (Renewal-function bounds): If $0<a\le X_k\le b<\infty$ almost surely for every $k$, then for every $t\ge0$, $$ \left\lfloor\frac{t}{b}\right\rfloor\le m(t)\le\left\lfloor\frac{t}{a}\right\rfloor. $$

Proof. By the theorem, the random variable $N(t)$ lies between the two displayed constants almost surely. It is integrable: the upper bound is finite for every fixed $t$, so $0\le N(t)\le\lfloor t/a\rfloor$ almost surely. Taking expectations preserves inequalities between integrable random variables and constants. Thus $\lfloor t/b\rfloor\le\mathbb{E}[N(t)]\le\lfloor t/a\rfloor$, as required. $\square$

The floor bounds are finite-time constraints, not estimates of the exact renewal function. Their width can be substantial when $a$ and $b$ are far apart. In particular, they do not claim that the count is uniformly distributed between the endpoints or that either endpoint is likely. Their role is to rule out impossible values and to provide a quick consistency check before a more detailed calculation is trusted.

Worked Example: An Exact Distribution and Its Mean

Let the independent interarrival times each equal $2$ or $3$, with probability $\tfrac12$ for each value. Find the distribution and expectation of $N(7)$, then verify them using the bounds.

Here $a=2$ and $b=3$, so the bounds give $\lfloor7/3\rfloor=2\le N(7)\le\lfloor7/2\rfloor=3$. Thus the count can only be $2$ or $3$. To find which occurs, two gaps always sum to at most $3+3=6$, so $N(7)\ge2$ with probability $1$. Three gaps have sum at most $7$ exactly when at most one of the three gaps equals $3$: all gaps equal to $2$ sum to $6$, and one $3$ with two $2$'s sums to $7$. There are four such outcomes among the eight equally likely triples, so $\mathbb{P}(N(7)\ge3)=4/8=1/2$. Four gaps have sum at least $4\cdot2=8>7$, so $\mathbb{P}(N(7)\ge4)=0$.

It follows that $\mathbb{P}(N(7)=3)=1/2$ and $\mathbb{P}(N(7)=2)=1-1/2=1/2$. Therefore $$ m(7)=2\left(\frac12\right)+3\left(\frac12\right)=\frac52. $$ The deterministic bounds check this result: $2\le\tfrac52\le3$.

Check by tail probabilities: for a nonnegative integer-valued count, $N(7)=\sum_{n\ge1}\mathbf{1}_{\{N(7)\ge n\}}$. Taking expectations gives $m(7)=\sum_{n\ge1}\mathbb{P}(N(7)\ge n)=1+1+\tfrac12=\tfrac52$; all terms for $n\ge4$ are zero. This reproduces the distribution-based calculation.

Worked Example: Using the Bounds to Audit a Computed Count

Suppose a calculation uses interarrival times known to lie in $[\tfrac32,\tfrac52]$, and reports six renewals by time $10$ for a particular sample path. Check the report using the actual gaps $2,\tfrac32,\tfrac52,2,\tfrac32$.

The epochs computed successively are $S_1=2$, $S_2=2+\tfrac32=\tfrac72$, $S_3=\tfrac72+\tfrac52=6$, $S_4=6+2=8$, and $S_5=8+\tfrac32=\tfrac{19}2$. The next gap is at least $\tfrac32$, so $S_6\ge\tfrac{19}2+\tfrac32=11>10$. Hence $N(10)=5$.

The general bounds are $\lfloor10/(\tfrac52)\rfloor=\lfloor4\rfloor=4$ and $\lfloor10/(\tfrac32)\rfloor=\lfloor\tfrac{20}3\rfloor=6$, giving $4\le N(10)\le6$. The reported value six is not ruled out by the coarse bounds alone, but it is contradicted by this path's epochs: the fifth renewal occurs by time $10$, and the sixth cannot. The pathwise calculation therefore confirms that the correct count is five.

Common Mistake: Reversing the Bounds

A frequent error is to use the smallest gap to claim a lower bound on the count. A small gap permits many renewals; it does not guarantee them. For example, take $a=2$, $b=5$, and $t=11$. The incorrect calculation $\lfloor11/2\rfloor=5$, followed by the claim $N(11)\ge5$, reverses the role of $a$. If all gaps on the path equal $5$, the epochs are $5$ and $10$, followed by $15$, so $N(11)=2$, not at least $5$.

The correct reasoning starts from the epoch inequalities. Since $S_n\le nb$, the maximum gap $b$ gives guaranteed renewals and hence the lower bound $\lfloor t/b\rfloor$. Since $S_n\ge na$, the minimum gap $a$ limits how many renewals can fit and hence gives the upper bound $\lfloor t/a\rfloor$. Keeping these two implications separate prevents the reversal.

For a quick check, calculate both floors at the same observation time and confirm their order: because $a\le b$, $t/b\le t/a$, and therefore $\lfloor t/b\rfloor\le\lfloor t/a\rfloor$. A proposed count outside this interval is impossible under the assumed interarrival limits. A count inside the interval is only feasible, not thereby verified; its sample-path epochs or probability calculation must still support it.

Check Your Understanding

Use the inclusive convention $N(t)=\max\{n:S_n\le t\}$ in each question.

If $3\le X_k\le7$ almost surely, what are the deterministic bounds for $N(20)$?
For $a=2$, $b=4$, and $t=8$, explain why the lower bound is two rather than one, and how an arrival exactly at time $8$ is counted.
If $\lfloor t/b\rfloor=4$ and $\lfloor t/a\rfloor=6$, which values of $N(t)$ are ruled out by the bounds, and which values remain possible?
Why can the bounds for $m(t)$ be obtained by taking expectations of the pathwise inequalities?
Give a sample path with all gaps in $[2,5]$ for which $N(11)=2$, and use it to explain why $\lfloor11/2\rfloor$ is not a lower bound.

Renewal Count Bounds from Bounded Interarrivals

What You'll Learn