Gamma Interarrivals and Erlang Renewal Counts

Gamma Interarrivals as Groups of Exponential Phases

When interarrival times are exponential, the renewal count is a Poisson process. A useful extension is to require several exponential phases before each renewal. Grouping $r$ independent exponential waiting times produces a gamma interarrival time with integer shape $r$, also called an Erlang interarrival time. The renewal epochs can then be read from every $r$th arrival of a Poisson process. This representation gives both the distribution of each epoch and a finite formula for the expected renewal count.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Fix a rate $\lambda>0$ and an integer shape $r\ge1$. Let $X_1,X_2,\ldots$ be independent and identically distributed interarrival times, each with the gamma distribution of shape $r$ and rate $\lambda$. Equivalently, each $X_k$ is the sum of $r$ independent exponential random variables of rate $\lambda$. Define the renewal epochs $S_n=X_1+\cdots+X_n$, and the renewal count $N(t)=\max\{n\ge0:S_n\le t\}$ for $t\ge0$, with $S_0=0$. The renewal function is $m(t)=\mathbb{E}N(t)$.

Definition: The Erlang distribution with shape $q$, a positive integer, and rate $\lambda>0$ is the distribution of a sum of $q$ independent exponential random variables of rate $\lambda$. Its cumulative distribution function is $1-e^{-\lambda t}\sum_{j=0}^{q-1}(\lambda t)^j/j!$ for $t\ge0$.

We use the standard Poisson-process fact that the number $M_t$ of arrivals by time $t$ in a rate-$\lambda$ Poisson process has probabilities $\mathbb{P}(M_t=j)=e^{-\lambda t}(\lambda t)^j/j!$, for integers $j\ge0$. Represent each interarrival as $r$ successive exponential phases. Then the $n$th renewal occurs at the $nr$th Poisson arrival. This links renewal epochs to Poisson probabilities without requiring a general convolution calculation.

Theorem: For every integer $n\ge1$ and $t\ge0$, the renewal epoch $S_n$ has the Erlang distribution with shape $nr$ and rate $\lambda$: $$ \mathbb{P}(S_n\le t)=1-e^{-\lambda t}\sum_{j=0}^{nr-1}\frac{(\lambda t)^j}{j!}. $$

Proof. Take a rate-$\lambda$ Poisson process whose successive arrival gaps are the exponential phases used to construct the interarrivals. By construction, $S_n$ is its $nr$th arrival time. That arrival has occurred by time $t$ exactly when $M_t\ge nr$. Therefore $\mathbb{P}(S_n\le t)=\mathbb{P}(M_t\ge nr)=1-\sum_{j=0}^{nr-1}\mathbb{P}(M_t=j)$. Substituting the Poisson probabilities gives the displayed formula. This also covers $t=0$: the sum is $1$, so the probability is $0$, as $S_n>0$ almost surely. $\square$

In particular, the count distribution has a finite expression for each count value. For an integer $k\ge0$, $N(t)=k$ precisely when the $rk$th phase arrival has occurred but the $r(k+1)$th has not. Thus the count is determined by a block of $r$ possible Poisson counts.

\mathbb{P}(N(t)=k) =\mathbb{P}(rk\le M_t\le r(k+1)-1) =e^{-\lambda t}\sum_{j=rk}^{r(k+1)-1}\frac{(\lambda t)^j}{j!}.

A Finite Formula for the Renewal Function

The epoch formula immediately gives $m(t)=\sum_{n\ge1}\mathbb{P}(S_n\le t)$, since $N(t)=\sum_{n\ge1}\mathbf{1}_{\{S_n\le t\}}$. That expression involves an infinite series. The Poisson representation yields a different expression that is a finite sum: $N(t)=\lfloor M_t/r\rfloor$. Divide the Poisson count by $r$, and only its remainder modulo $r$ needs to be evaluated.

Theorem: Let $r\ge1$ be an integer, $\lambda>0$, and $x=\lambda t$. Define $\zeta=e^{2\pi i/r}$. Then $$ m(t)=\frac{x}{r} -\frac{1}{r^2}\sum_{a=0}^{r-1}a \sum_{\ell=0}^{r-1}\zeta^{-a\ell} \exp\!\bigl(x(\zeta^\ell-1)\bigr). $$ The expression is real; terms with conjugate complex values combine to real numbers. For $r=1$, the double sum is zero, so $m(t)=\lambda t$.

Proof. Set $R=M_t-r\lfloor M_t/r\rfloor$, the remainder on dividing $M_t$ by $r$. It takes values in $\{0,\ldots,r-1\}$, and $N(t)=\lfloor M_t/r\rfloor=(M_t-R)/r$. Since $\mathbb{E}M_t=x$, $m(t)=x/r-\mathbb{E}R/r$.

It remains to compute the probabilities of the possible remainders. For integers $q$, the finite geometric sum gives $\frac1r\sum_{\ell=0}^{r-1}\zeta^{\ell q}=1$ if $q$ is divisible by $r$, and $0$ otherwise. Indeed, if $\zeta^q\ne1$, the sum is $(1-(\zeta^q)^r)/(1-\zeta^q)=0$; if $\zeta^q=1$, all $r$ terms equal $1$. Applying this identity to $q=M_t-a$ gives \[ \mathbb{P}(R=a)=\frac1r\sum_{\ell=0}^{r-1}\zeta^{-a\ell}\mathbb{E}[\zeta^{\ell M_t}]. \] The Poisson probabilities give, by summing their exponential series, \[ \mathbb{E}[\zeta^{\ell M_t}] =e^{-x}\sum_{j=0}^{\infty}\frac{(x\zeta^\ell)^j}{j!} =\exp\!\bigl(x(\zeta^\ell-1)\bigr). \] Consequently, $\mathbb{E}R=\sum_{a=0}^{r-1}a\mathbb{P}(R=a)$ equals the double sum in the theorem divided by $r$. Substituting into $m(t)=x/r-\mathbb{E}R/r$ proves the formula. The left side is an expectation of a real random variable, so the expression is real as asserted. When $r=1$, the only remainder is $0$, giving $m(t)=x$. $\square$

The formula is finite for every fixed integer shape. Although the root-of-unity notation may be complex, conjugate terms can be paired, or the remainder probabilities can be computed directly from the Poisson probabilities. The following examples show both approaches.

Worked Example: The Second Epoch for Shape Two

Suppose each interarrival is gamma with shape $r=2$ and rate $\lambda$. Find the probability that the second renewal has occurred by a time $t$ such that $\lambda t=1$.

The second renewal is the fourth exponential phase, so its Erlang shape is $nr=2\cdot2=4$. Substituting $x=\lambda t=1$ into the epoch formula gives

\mathbb{P}(S_2\le t) =1-e^{-1}\left(\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}\right) =1-\frac{8}{3e}.

Here the four terms sum to $1+1+\tfrac12+\tfrac16=\tfrac83$. As a check, the Poisson representation says $S_2\le t$ exactly when $M_t\ge4$. Thus its complement has counts $0,1,2,3$, whose probabilities sum to $e^{-1}(1+1+\tfrac12+\tfrac16)=\tfrac{8}{3e}$, giving the same result.

Worked Example: The Renewal Function for Shape Two

Again take $r=2$, and let $x=\lambda t$. A Poisson count $M_t$ is even with probability $(1+e^{-2x})/2$ and odd with probability $(1-e^{-2x})/2$. To verify the odd probability, use the root-of-unity formula with $\zeta=-1$: the two terms are $1$ and $-e^{-2x}$, divided by $2$. The remainder $R$ is $0$ for an even count and $1$ for an odd count, so $\mathbb{E}R=(1-e^{-2x})/2$. Therefore

m(t)=\frac{x}{2}-\frac{1-e^{-2x}}{4}.

For example, at $x=1$, the result is $m(t)=\tfrac12-\tfrac{1-e^{-2}}4=\tfrac14+\tfrac{e^{-2}}4$. This value is positive, as it must be because the count is nonnegative. At $t=0$, $x=0$, and the formula gives $m(0)=0$, in agreement with the count definition.

Check from the count representation: at $x=1$, $\mathbb{E}M_t=1$. The odd-count probability is $(1-e^{-2})/2$, so $\mathbb{E}\lfloor M_t/2\rfloor=(\mathbb{E}M_t-\mathbb{E}R)/2 =(1-(1-e^{-2})/2)/2=\tfrac14+\tfrac{e^{-2}}4$. This independently recovers the formula.

Worked Example: Exact Count Probabilities for Shape Three

Let $r=3$ and choose $t$ such that $\lambda t=1$. The count $N(t)=1$ means that exactly three, four, or five Poisson phases have occurred. Hence

\mathbb{P}(N(t)=1) =e^{-1}\left(\frac{1}{3!}+\frac{1}{4!}+\frac{1}{5!}\right) =e^{-1}\left(\frac{20+5+1}{120}\right) =\frac{13}{60e}.

Check this using epoch probabilities. The first renewal has Erlang shape $3$, so $\mathbb{P}(S_1\le t)=1-e^{-1}(1+1+\tfrac12)=1-\tfrac{5}{2e}$. The second has shape $6$, so \[ \mathbb{P}(S_2\le t) =1-e^{-1}\left(1+1+\tfrac12+\tfrac16+\tfrac1{24}+\tfrac1{120}\right) =1-\frac{163}{60e}. \] The event $N(t)=1$ is $S_1\le t<S_2$; subtracting the second probability from the first gives $(163-150)/(60e)=13/(60e)$, as before. For a fixed $t$, equality at an epoch has probability zero because the Erlang distribution is continuous, so the endpoint convention does not change this calculation.

Interpretation and a Common Pitfall

The finite formula for $m(t)$ does not say the renewal count is Poisson. When $r>1$, renewals occur only at every $r$th arrival of the underlying phase process. The phase count $M_t$ is Poisson, but the renewal count is its integer quotient $\lfloor M_t/r\rfloor$. Its mean is close to $x/r$ for large $x$, with a correction determined by the remainder. The formula gives that correction exactly at each time; no limiting approximation is needed.

Common mistake. Replacing the renewal count by a Poisson count of rate $\lambda/r$ would give $m(t)=\lambda t/r$ exactly. For shape two, that omits $(1-e^{-2\lambda t})/4$. For example, at $\lambda t=1$, the incorrect answer is $1/2$, whereas the correct value is $1/4+e^{-2}/4$. The discrepancy is the contribution of the odd phase counts, for which one phase has occurred but the next renewal has not. The Poisson process describes phase arrivals; grouping those arrivals into blocks is essential.

Use the epoch formula when a question asks whether a particular renewal has occurred by time $t$, and use the block formula when it asks for a specific count. For the expected count, the finite remainder formula avoids summing infinitely many epoch probabilities. These formulas rely on the integer shape: grouping a fixed number of exponential phases is what makes the Poisson-count representation available.

Check Your Understanding

Assume throughout that the rate is positive and the shape is a positive integer. Check each answer against either the Poisson phase count or the stated finite formula.

For shape $r=3$, what is the Erlang shape of $S_4$, and what finite Poisson sum gives $\mathbb{P}(S_4\le t)$?
For shape $r=2$, express $\mathbb{P}(N(t)=0)$ as a sum of Poisson probabilities.
For shape $r=2$ and $\lambda t=1$, calculate $\mathbb{P}(N(t)=2)$ from the possible values of $M_t$.
Why is $\lambda t/r$ not, in general, the exact renewal function for shape $r>1$?
In the root-of-unity formula, what does the remainder $R$ represent, and why does it take only finitely many values?

Gamma Interarrivals and Erlang Renewal Counts

What You'll Learn