Two-Point Interarrival Distributions

Two Possible Waiting Times

When every interarrival time has one of two possible lengths, a renewal count at a fixed time can be calculated by a finite enumeration. The key observation is that after $n$ intervals, the epoch time depends only on how many of those intervals had the shorter length. That number has a binomial distribution, so both the probabilities of renewal epochs and the distribution of the renewal count can be found without approximating or simulating the process.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $X_1,X_2,\ldots$ be independent, identically distributed positive interarrival times, with $a<b$, $0<p<1$, and $\mathbb{P}(X_k=a)=p$, $\mathbb{P}(X_k=b)=1-p$. Write $q=1-p$. Define the $n$th renewal epoch by $S_0=0$ and $S_n=X_1+\cdots+X_n$ for $n\ge1$. At time $t\ge0$, use the count $N(t)=\max\{n\ge0:S_n\le t\}$. Thus, an epoch exactly at $t$ is included in the count. Since each interval is at least $a>0$, $S_n\ge na$; consequently $N(t)\le\lfloor t/a\rfloor$, so this count is finite.

Definition: For $n\ge0$, let $K_n$ be the number of the first $n$ interarrival times that equal $a$. For $n\ge1$, $S_n=K_na+(n-K_n)b$. For $0\le k\le n$, the event $K_n=k$ has probability $\binom{n}{k}p^kq^{n-k}$.

The two endpoint cases $p=0$ and $p=1$ give deterministic interarrivals and are not part of the nondegenerate two-point setting considered here. For $0<p<1$, each possible number of short intervals has positive probability. The formula for $S_n$ converts that count into an epoch time; different values of $k$ can produce different times, and the resulting probabilities can be added when calculating the probability of an epoch at a specified time.

Probabilities of Renewal Epochs

Proposition: For $n\ge1$ and any real number $s$, $$ \mathbb{P}(S_n=s)= \sum_{\substack{0\le k\le n\\ka+(n-k)b=s}} \binom{n}{k}p^kq^{n-k}. $$ An empty sum is $0$. In particular, $S_1=X_1$, so its only possible values are $a$ and $b$, with probabilities $p$ and $q$, respectively.

Proof. For each $k\in\{0,\ldots,n\}$, the event $K_n=k$ means that exactly $k$ of the $n$ intervals equal $a$. There are $\binom{n}{k}$ choices for their positions. Independence gives probability $p^kq^{n-k}$ for each such choice, so $\mathbb{P}(K_n=k)=\binom{n}{k}p^kq^{n-k}$. On that event, $S_n=ka+(n-k)b$. The events $K_n=k$ are disjoint, and $S_n=s$ occurs precisely for the values of $k$ in the displayed sum. Adding their probabilities proves the formula. For $n=1$, $S_1=X_1$ by definition, which gives the stated two probabilities. $\square$

This formula gives the probability of an epoch at an exact time. For a count at a fixed observation time, it is also useful to calculate $H_n(t)=\mathbb{P}(S_n\le t)$. The same enumeration gives $$ H_n(t)=\sum_{k=0}^{n}\binom{n}{k}p^kq^{n-k} \mathbf{1}_{\{ka+(n-k)b\le t\}},\qquad n\ge1, $$ where $\mathbf{1}_{\{ka+(n-k)b\le t\}}$ is $1$ when the inequality holds and $0$ otherwise. Here the inequality is non-strict: an epoch at time $t$ is counted. Set $H_0(t)=1$ for $t\ge0$, since $S_0=0$.

Worked Example: The First Epoch and the Third Epoch

Suppose each interarrival is $2$ with probability $p=\tfrac13$, and $5$ with probability $q=\tfrac23$. First, $S_1=X_1$, so $\mathbb{P}(S_1=2)=\tfrac13$ and $\mathbb{P}(S_1=5)=\tfrac23$; these probabilities sum to $\tfrac13+\tfrac23=1$.

For $S_3$, the number $k$ of intervals of length $2$ ranges from $0$ to $3$. Substitution into $2k+5(3-k)$ gives all four possible epoch times:

\begin{array}{c|c|c} k & 2k+5(3-k) & \mathbb{P}(K_3=k)\\ 0 & 15 & \binom{3}{0}(\tfrac13)^0(\tfrac23)^3=\tfrac{8}{27}\\ 1 & 12 & \binom{3}{1}(\tfrac13)^1(\tfrac23)^2=\tfrac{12}{27}\\ 2 & 9 & \binom{3}{2}(\tfrac13)^2(\tfrac23)^1=\tfrac{6}{27}\\ 3 & 6 & \binom{3}{3}(\tfrac13)^3(\tfrac23)^0=\tfrac{1}{27} \end{array}

Therefore $\mathbb{P}(S_3=9)=\tfrac{6}{27}=\tfrac29$. The four probabilities sum to $\tfrac{8+12+6+1}{27}=1$, checking that every possible value of $K_3$ has been included. In particular, the event $S_3=9$ corresponds to exactly two short intervals, not one: $2(2)+1(5)=9$.

From Epoch Probabilities to a Count Distribution

Proposition: For $t\ge0$ and $n\ge0$, $$ \mathbb{P}(N(t)\ge n)=H_n(t), \qquad \mathbb{P}(N(t)=n)=H_n(t)-H_{n+1}(t). $$ In particular, the event $N(t)=n$ is $S_n\le t<S_{n+1}$.

Proof. Since all interarrival times are positive, the epochs increase strictly: $S_{j+1}=S_j+X_{j+1}>S_j$. By the definition of $N(t)$, there are at least $n$ renewals by time $t$ exactly when $S_n\le t$. Thus $\{N(t)\ge n\}=\{S_n\le t\}$, and its probability is $H_n(t)$. For each $n\ge0$, the event $N(t)=n$ is the event of at least $n$ renewals but not at least $n+1$; subtracting the nested-event probabilities gives $H_n(t)-H_{n+1}(t)$. Equivalently, exactly $n$ epochs have occurred by $t$ when $S_n\le t$ and the next epoch is strictly later than $t$. The strict upper inequality is required because an epoch at $t$ is included in $N(t)$. $\square$

The proposition turns the count calculation into a sequence of finite sums. First calculate $H_n(t)$ for $n=1,2,\ldots,\lfloor t/a\rfloor+1$; the last term is zero because even that many shortest intervals exceed $t$. Then take successive differences, beginning with $H_0(t)=1$. These probabilities must be nonnegative and sum to one: the differences telescope from $H_0(t)=1$ down to the first zero term.

Worked Example: Count Renewals at Time Six

Let $a=2$, $b=5$, and $p=q=\tfrac12$. We calculate the distribution of $N(6)$, including epochs that occur exactly at time $6$. Since $S_1\le6$ for either possible first interval, $H_1(6)=1$. For two intervals, their possible sums are $4,7,10$; only $4$ is at most $6$, and it requires two short intervals. Hence $H_2(6)=(\tfrac12)^2=\tfrac14$.

For three intervals, the minimum possible sum is $3(2)=6$. The event $S_3\le6$ therefore consists only of three short intervals, with probability $H_3(6)=(\tfrac12)^3=\tfrac18$. For four intervals the minimum sum is $4(2)=8>6$, so $H_4(6)=0$. Taking differences gives

\begin{aligned} \mathbb{P}(N(6)=0)&=H_0(6)-H_1(6)=1-1=0,\\ \mathbb{P}(N(6)=1)&=H_1(6)-H_2(6)=1-\tfrac14=\tfrac34,\\ \mathbb{P}(N(6)=2)&=H_2(6)-H_3(6)=\tfrac14-\tfrac18=\tfrac18,\\ \mathbb{P}(N(6)=3)&=H_3(6)-H_4(6)=\tfrac18-0=\tfrac18. \end{aligned}

Check: The probabilities sum to $0+\tfrac34+\tfrac18+\tfrac18=1$. Three renewals by time $6$ occur precisely when all three intervals have length $2$; then $S_3=6$, which confirms why the endpoint is included.

Worked Example: A Count with Several Epochs at the Endpoint

Let $a=1$, $b=3$, $p=\tfrac14$, $q=\tfrac34$, and observe the process at $t=4$. The first interval is at most $4$ with probability $H_1(4)=1$. For two intervals, the possible sums are $2,4,6$. The sum $2$ has probability $(\tfrac14)^2=\tfrac1{16}$, and the sum $4$ has probability $2(\tfrac14)(\tfrac34)=\tfrac6{16}$. Thus $H_2(4)=\tfrac7{16}$.

For three intervals, the minimum sum is $3$. To have a sum at most $4$, all three must be short: replacing any one short interval by a long interval adds $2$, producing a sum of at least $5$. Therefore $H_3(4)=(\tfrac14)^3=\tfrac1{64}$. For four intervals, the minimum sum is $4$, achieved only when all four are short, so $H_4(4)=(\tfrac14)^4=\tfrac1{256}$. Five intervals have minimum sum $5>4$, and hence $H_5(4)=0$. The count probabilities are

\begin{aligned} \mathbb{P}(N(4)=0)&=1-1=0,\\ \mathbb{P}(N(4)=1)&=1-\tfrac7{16}=\tfrac9{16},\\ \mathbb{P}(N(4)=2)&=\tfrac7{16}-\tfrac1{64}=\tfrac{27}{64},\\ \mathbb{P}(N(4)=3)&=\tfrac1{64}-\tfrac1{256}=\tfrac3{256},\\ \mathbb{P}(N(4)=4)&=\tfrac1{256}-0=\tfrac1{256}. \end{aligned}

Check: With denominator $256$, the five probabilities sum to $\tfrac{0+144+108+3+1}{256}=1$. The outcome $N(4)=4$ has probability $\tfrac1{256}$ because four short intervals give $S_4=4$, and that endpoint renewal is counted. No fifth renewal can occur by time $4$, since even five short intervals take $5$ units.

Endpoint Conventions and a Common Mistake

The calculation depends on keeping separate two events: $S_n\le t$, meaning at least $n$ renewals have occurred, and $S_n\le t<S_{n+1}$, meaning exactly $n$ have occurred. An epoch at the observation time belongs to the first event. This convention is built into $N(t)=\max\{n:S_n\le t\}$; changing the convention would change the count at times when an epoch can occur.

Common mistake. In the example with $a=2$, $b=5$, $p=q=\tfrac12$, and $t=6$, one might report $\mathbb{P}(N(6)=2)=H_2(6)=\tfrac14$. That is the probability of at least two renewals, not exactly two. The event of at least three renewals has probability $H_3(6)=\tfrac18$, so the correction is $\mathbb{P}(N(6)=2)=H_2(6)-H_3(6)=\tfrac14-\tfrac18=\tfrac18$. The removed probability is the all-short case, where the third renewal occurs exactly at time $6$. A related endpoint error is replacing $S_n\le t$ with $S_n<t$: that would omit a renewal at the observation time, contrary to the stated definition.

This finite enumeration is useful when the observation time is fixed and the interarrival distribution has only two atoms. It makes the possible epoch times explicit, preserves the exact endpoint convention, and gives the entire count distribution rather than just its mean. For larger $n$, the lower bound $S_n\ge na$ still limits the calculation to finitely many terms at every fixed $t$.

Check Your Understanding

Use the definitions and formulas above; include equality at the observation time when applying the count convention.

If $a=1$, $b=4$, and $p=\tfrac13$, what are the two possible values of $S_1$ and their probabilities?
For $a=2$, $b=5$, and $p=\tfrac12$, calculate $\mathbb{P}(S_2=7)$ by identifying the number of short intervals.
For $a=1$, $b=3$, $p=\tfrac14$, and $t=3$, calculate $H_2(t)$. Does the case of two short intervals contribute?
Explain why $\mathbb{P}(N(t)=n)$ is a difference of two successive values of $H_n(t)$, rather than simply $H_n(t)$.
For positive interarrivals with shortest value $a$, why must $H_n(t)=0$ whenever $na>t$?

Two-Point Interarrival Distributions

What You'll Learn