Counting Paths and Endpoint Conventions

Counts from Renewal Epochs

A renewal count records how many renewal events have occurred by an observation time. The phrase “by time $t$” includes an event occurring exactly at $t$; “strictly before $t$” does not. These conventions agree for most fixed observation times in some models, but they need not agree when renewal epochs have atoms or when the observation time is itself a renewal epoch. Keeping the endpoint convention explicit is essential when translating between counts and probabilities.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $X_1,X_2,\ldots$ be independent, identically distributed, strictly positive interarrival times, and define $S_0=0$ and $S_n=X_1+\cdots+X_n$ for $n\ge1$. Assume the renewal epochs diverge, $S_n\to\infty$ almost surely, so only finitely many renewals occur in every bounded time interval. For independent, strictly positive interarrivals this divergence holds almost surely. The count $N(t)$, for $t\ge0$, includes renewals at $t$: it is the largest index $n\ge0$ such that $S_n\le t$. The epoch $S_0=0$ marks the starting point; it is not counted as a renewal event.

Definition: For $t\ge0$, $N(t)=\max\{n\ge0:S_n\le t\}$. For $t>0$, define $N(t-)=\#\{n\ge1:S_n<t\}$, the number of renewal events strictly before $t$. Set $N(0-)=0$. The symbol $N(t-)$ is the left-limit count at positive $t$; its value at zero is set separately.

Strict positivity of the interarrivals means $S_0<S_1<S_2<\cdots$ almost surely. Thus at most one renewal event can occur at any given time. In particular, for every $t\ge0$, the difference between the inclusive and strict-before counts is either zero or one: it is one exactly when some renewal epoch $S_n$, $n\ge1$, equals $t$.

Count Events and Renewal-Epoch Events

Theorem (Pathwise endpoint identities): For every $t\ge0$ and integer $n\ge0$, $N(t)\ge n$ if and only if $S_n\le t$. For $t>0$ and integer $n\ge1$, $N(t-)\ge n$ if and only if $S_n<t$. For $t>0$, $N(t-)\ge0$ always. At a renewal epoch $S_k$, $k\ge1$, one has $N(S_k)=k$ and $N(S_k-)=k-1$, almost surely.

Proof. Fix a sample point at which the epochs are strictly increasing and diverge. The count $N(t)$ is the largest index whose epoch is at most $t$. Therefore it is at least $n$ exactly when the $n$th epoch is at most $t$, giving $N(t)\ge n$ if and only if $S_n\le t$. This includes $n=0$, since $S_0=0\le t$ for all $t\ge0$. For $t>0$, the strict-before count is the number of positive-index epochs less than $t$. It is at least $n\ge1$ exactly when the $n$th such epoch satisfies $S_n<t$; it is always at least zero. Finally, strict increase gives $S_j<S_k$ for $j<k$ and $S_j>S_k$ for $j>k$. Exactly $k$ positive-index epochs are at most $S_k$, and exactly $k-1$ are strictly less than $S_k$, proving the last assertions. $\square$

Define $F_n(t)=\mathbb{P}(S_n\le t)$ for $n\ge0$, with $F_0(t)=1$ for $t\ge0$. The pathwise equivalence turns the count probabilities into differences of renewal-epoch probabilities.

Theorem (Count distribution): For $t\ge0$ and $n\ge0$, $$ \mathbb{P}(N(t)=n)=F_n(t)-F_{n+1}(t). $$ For strict-before counts, let $F_n^{<}(t)=\mathbb{P}(S_n<t)$ for $n\ge1$. For $t>0$, $$ \mathbb{P}(N(t-)=0)=1-F_1^{<}(t), \qquad \mathbb{P}(N(t-)=n)=F_n^{<}(t)-F_{n+1}^{<}(t)\quad(n\ge1). $$ At $t=0$, $\mathbb{P}(N(0-)=0)=1$.

Proof. For the inclusive count and any $n\ge0$, the event $\{N(t)=n\}$ is the event $\{N(t)\ge n\}$ with $\{N(t)\ge n+1\}$ removed. These are nested events. By the pathwise identity, their probabilities are $F_n(t)$ and $F_{n+1}(t)$, so subtraction gives the stated formula. For $t>0$, $\{N(t-)\ge n\}=\{S_n<t\}$ for $n\ge1$. For $n\ge1$, subtract the probability of $\{N(t-)\ge n+1\}$ from that of $\{N(t-)\ge n\}$ to obtain the difference formula. The event $N(t-)=0$ is the complement of $\{N(t-)\ge1\}=\{S_1<t\}$, giving $1-F_1^{<}(t)$. At zero there are no positive-index epochs before zero, since all interarrivals are positive; by definition $N(0-)=0$, so its probability is one. $\square$

The special handling of zero is not cosmetic. For positive $t$, one could set $F_0^{<}(t)=1$, since $S_0=0<t$, and then write the difference formula starting at $n=0$. At $t=0$, however, $S_0<0$ is false. The formula using $\mathbb{P}(S_0<t)$ would then incorrectly return zero for $\mathbb{P}(N(0-)=0)$. The strict-before formula must therefore be restricted to positive $t$, with the zero-time case stated separately.

Worked Example: Deterministic Renewals at an Endpoint

Suppose $X_k=2$ for every $k$, with probability one. The epochs are $S_0=0,S_1=2,S_2=4,S_3=6$, and so on. Find the inclusive and strict-before counts at $t=4$, and verify the count formulas.

Since $S_2=4\le4$ but $S_3=6>4$, the largest index with $S_n\le4$ is $2$, so $N(4)=2$. The positive-index epochs strictly before $4$ consist only of $S_1=2$, so $N(4-)=1$.

For the inclusive count, $F_0(4)=1$, $F_1(4)=1$, $F_2(4)=1$, and $F_3(4)=0$. Thus the formula gives probabilities $0$ for counts $0$ and $1$, and $F_2(4)-F_3(4)=1-0=1$ for count $2$. For the strict-before count, $F_1^{<}(4)=1$, $F_2^{<}(4)=0$, and $F_3^{<}(4)=0$. Hence $\mathbb{P}(N(4-)=0)=1-1=0$, $\mathbb{P}(N(4-)=1)=1-0=1$, and the probabilities for counts $n\ge2$ are zero.

Check: The formulas give $N(4)=2$ and $N(4-)=1$ with probability one, matching the direct count. The one-event difference is the renewal at epoch $S_2=4$, which is included by $N(4)$ and excluded by $N(4-)$.

Worked Example: Random Interarrivals with an Atom at the Observation Time

Let the $X_k$ be independent, with $\mathbb{P}(X_k=1)=\tfrac12$ and $\mathbb{P}(X_k=2)=\tfrac12$. Find the distributions of $N(2)$ and $N(2-)$.

The first epoch satisfies $S_1\le2$ in both cases, so $F_1(2)=1$. The second epoch is at most $2$ only if $X_1=X_2=1$, an event of probability $\tfrac12\cdot\tfrac12=\tfrac14$; therefore $F_2(2)=\tfrac14$. Since each interarrival is at least $1$, $S_3\ge3$, and $F_3(2)=0$. Also $F_0(2)=1$. The inclusive-count formula gives $$ \mathbb{P}(N(2)=0)=1-1=0,\quad \mathbb{P}(N(2)=1)=1-\tfrac14=\tfrac34,\quad \mathbb{P}(N(2)=2)=\tfrac14-0=\tfrac14. $$

For the strict-before count, $S_1<2$ exactly when $X_1=1$, so $F_1^{<}(2)=\tfrac12$. Since $S_2\ge2$, $F_2^{<}(2)=0$, and $S_3\ge3$ gives $F_3^{<}(2)=0$. Thus $$ \mathbb{P}(N(2-)=0)=1-\tfrac12=\tfrac12,\quad \mathbb{P}(N(2-)=1)=\tfrac12-0=\tfrac12, $$ with probability zero for counts of $2$ or more.

Check: Each distribution sums to one: $0+\tfrac34+\tfrac14=1$ and $\tfrac12+\tfrac12=1$. The probability of a renewal exactly at $2$ is $\tfrac12+\tfrac14=\tfrac34$: either $S_1=2$, with probability $\tfrac12$, or $S_2=2$, with probability $\tfrac14$. These events are disjoint because $S_1=2$ requires $X_1=2$, whereas $S_2=2$ requires $X_1=1$. This matches the probability that the inclusive and strict-before counts differ.

Worked Example: Counting at a Random Renewal Epoch

Use the same interarrival distribution, and observe the process at the random time $S_2$. Verify the inclusive and strict-before counts for every possible pair $(X_1,X_2)$.

Each of the four pairs $(1,1),(1,2),(2,1),(2,2)$ has probability $\tfrac14$. In each case, $S_1<S_2$, while $S_3=S_2+X_3>S_2$ because $X_3$ is positive. Therefore the only positive-index epochs at or before $S_2$ are $S_1,S_2$, and the only positive-index epoch strictly before $S_2$ is $S_1$. The pair-by-pair values are:

$(X_1,X_2)$	$S_2$	$N(S_2)$	$N(S_2-)$
$(1,1)$	$2$	$2$	$1$
$(1,2)$	$3$	$2$	$1$
$(2,1)$	$3$	$2$	$1$
$(2,2)$	$4$	$2$	$1$

Check: The table lists all four possible pairs, each with probability $\tfrac14$; consequently $N(S_2)=2$ and $N(S_2-)=1$ each hold with probability $\tfrac14+\tfrac14+\tfrac14+\tfrac14=1$. This random observation time is exactly an epoch by construction, so the endpoint difference occurs on every sample path.

Why Endpoint Conventions Matter

The inequalities in the count identities determine which renewal-epoch probabilities belong in a calculation. For $N(t)$, use $\mathbb{P}(S_n\le t)$. For $N(t-)$, at positive $t$, use $\mathbb{P}(S_n<t)$. Replacing one inequality by the other can change the answer whenever $S_n$ has positive probability of equalling $t$. The distinction is especially important when evaluating counts at renewal epochs, where equality is guaranteed for one epoch.

Common mistake. A tempting but incorrect extension is to define $F_0^{<}(t)=\mathbb{P}(S_0<t)$ and use $\mathbb{P}(N(t-)=0)=F_0^{<}(t)-F_1^{<}(t)$ for all $t\ge0$. At $t=0$, this gives $0-0=0$, because $S_0=0$ is not strictly less than zero and $S_1>0$. But $N(0-)=0$ by definition, so its probability is $1$. The correction is to use the strict-before difference formula only for $t>0$, and state separately that $\mathbb{P}(N(0-)=0)=1$.

When setting up a renewal-count calculation, first decide whether the endpoint is included. Then translate the count event into the matching inequality for $S_n$, and check the zero-time case separately if the count is strict-before. This order prevents an endpoint convention from being hidden inside an otherwise correct probability calculation.

Check Your Understanding

For each question, identify whether the count includes an event exactly at the observation time.

Write the event equivalent to $N(t)\ge3$, for $t\ge0$.
For $t>0$, write the event equivalent to $N(t-)\ge2$.
Suppose $S_2=t$ and the epochs are strictly increasing. What are $N(t)$ and $N(t-)$?
Why is $\mathbb{P}(N(0-)=0)$ not obtained by subtracting $\mathbb{P}(S_1<0)$ from $\mathbb{P}(S_0<0)$?
If $F_1(t)=1$, $F_2(t)=\tfrac13$, and $F_3(t)=0$, find the probabilities that $N(t)$ is $1$ and $2$.

\((X_1,X_2)\)	\(S_2\)	\(N(S_2)\)	\(N(S_2-)\)
\((1,1)\)	\(2\)	\(2\)	\(1\)
\((1,2)\)	\(3\)	\(2\)	\(1\)
\((2,1)\)	\(3\)	\(2\)	\(1\)
\((2,2)\)	\(4\)	\(2\)	\(1\)

Counting Paths and Endpoint Conventions

What You'll Learn