From Renewal Epochs to Count Variability
The renewal function gives the expected number of renewals by a fixed time. To measure variability as well as average activity, we need the second moment of that count. It can be computed from probabilities of the form \(\mathbb{P}(S_n\le t)\): the probability that the \(n\)th renewal epoch has occurred by time \(t\). The key is to express an integer’s square as a sum of successive odd numbers, then apply that identity to the random count.
Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_k)_{k\ge1}\) be independent, identically distributed, strictly positive interarrival times with distribution \(F\). Define the \(n\)th renewal epoch by \(S_n=\sum_{k=1}^n X_k\), and set \(S_0=0\). At a fixed time \(t\ge0\), define the renewal count by \(N(t)=\max\{n\ge0:S_n\le t\}\). The inequality is inclusive: a renewal occurring exactly at time \(t\) is counted.
Under these assumptions, \(N(t)\) is finite almost surely. Indeed, some \(\varepsilon>0\) has \(\mathbb{P}(X_1\ge\varepsilon)>0\). Independence implies that interarrivals at least \(\varepsilon\) occur infinitely often almost surely: the probability of no such interarrival in any given next \(r\) trials is \((1-\mathbb{P}(X_1\ge\varepsilon))^r\), which tends to zero. Thus \(S_n\) tends to infinity almost surely. The formulas below remain valid as identities of extended nonnegative expectations; the usual finite variance formula applies when the second moment is finite.
For any nonnegative integer \(m\), its square is the sum of the first \(m\) odd integers: \(m^2=1+3+\cdots+(2m-1)\). Applying this identity to \(N(t)\) gives a formula in which later renewal epochs receive larger weights. The corresponding first-moment identity has no such weights, so the two sums should not be confused.
The Tail-Probability Identities
Proof. For each outcome, \(N(t)\) is a finite nonnegative integer. Writing \(\mathbf{1}_{\{N(t)\ge n\}}\) for the indicator that at least \(n\) renewals have occurred, we have \(N(t)=\sum_{n\ge1}\mathbf{1}_{\{N(t)\ge n\}}\). Also, \(N(t)^2=\sum_{n\ge1}(2n-1)\mathbf{1}_{\{N(t)\ge n\}}\), because the sum on the right contains exactly the first \(N(t)\) odd numbers. Taking expectations and exchanging each nonnegative sum and expectation by Tonelli’s theorem gives the two series of tail probabilities. The events \(\{N(t)\ge n\}\) and \(\{S_n\le t\}\) are identical: the count is at least \(n\) precisely when the \(n\)th epoch is no later than \(t\). This proves both identities. If the second moment is finite, then the first moment is finite as well, since \(N(t)\le 1+N(t)^2\). The definition of variance therefore gives \(\operatorname{Var}(N(t))=\mathbb{E}[N(t)^2]-(\mathbb{E}[N(t)])^2\), yielding the stated formula. \(\square\)
The proof also explains why these are tail-probability sums rather than sums over the exact values of the count. To recover the distribution itself, use \(\mathbb{P}(N(t)=n)=a_n(t)-a_{n+1}(t)\) for \(n\ge1\), and \(\mathbb{P}(N(t)=0)=1-a_1(t)\). These differences follow by subtracting the event \(N(t)\ge n+1\) from \(N(t)\ge n\). When only the mean and variance are needed, the weighted tail sums are often shorter.
Worked Calculations
Worked Example: A Deterministic Interarrival Time
Suppose every interarrival time is \(X_k=\tfrac32\), and take \(t=\tfrac72\). The first epoch is \(S_1=\tfrac32\), which is at most \(\tfrac72\). The second is \(S_2=\tfrac32+\tfrac32=3\), also at most \(\tfrac72\). The third is \(S_3=3+\tfrac32=\tfrac92\), which is greater than \(\tfrac72\). Since all later epochs are still larger, \(a_1(t)=1\), \(a_2(t)=1\), and \(a_n(t)=0\) for \(n\ge3\).
The first-moment sum is \(1+1=2\). The second-moment sum is \(1\cdot1+3\cdot1=4\). Consequently, \(\operatorname{Var}(N(t))=4-2^2=0\). This matches the direct count: exactly two renewals have occurred by time \(\tfrac72\), so \(N(t)=2\) with probability one.
Check: The epoch at time \(3\) is counted because \(3\le\tfrac72\), while the third epoch is excluded because \(\tfrac92>\tfrac72\). The tail sums therefore give the same fixed count and zero variance as the direct calculation.
Worked Example: Two Possible Interarrival Times
Let each \(X_k\) equal \(1\) or \(2\), each with probability \(\tfrac12\), independently, and take \(t=3\). The first epoch is at most \(3\) in either case, so \(a_1(3)=1\). For two interarrivals, the four equally likely ordered pairs are \((1,1),(1,2),(2,1),(2,2)\). The first three have sum at most \(3\), while the last has sum \(4\); hence \(a_2(3)=\tfrac34\).
For three interarrivals, the sum is at most \(3\) only for \((1,1,1)\), among the eight equally likely triples. Thus \(a_3(3)=\tfrac18\). Four or more interarrivals have sum at least \(4\), so \(a_n(3)=0\) for \(n\ge4\). The mean is \(1+\tfrac34+\tfrac18=\tfrac{15}{8}\). The second moment is \(1+3(\tfrac34)+5(\tfrac18)=1+\tfrac94+\tfrac58=\tfrac{31}{8}\). Therefore the variance is \(\tfrac{31}{8}-(\tfrac{15}{8})^2 =\tfrac{248}{64}-\tfrac{225}{64} =\tfrac{23}{64}\).
Check by the count distribution: The tail probabilities give \(\mathbb{P}(N(3)=1)=1-\tfrac34=\tfrac14\), \(\mathbb{P}(N(3)=2)=\tfrac34-\tfrac18=\tfrac58\), and \(\mathbb{P}(N(3)=3)=\tfrac18\). These probabilities sum to \(\tfrac14+\tfrac58+\tfrac18=1\). Their mean is \(1(\tfrac14)+2(\tfrac58)+3(\tfrac18)=\tfrac{15}{8}\), and their second moment is \(1^2(\tfrac14)+2^2(\tfrac58)+3^2(\tfrac18)=\tfrac{31}{8}\), confirming the tail-sum calculation.
Worked Example: An Endpoint Renewal Changes the Variance
Let \(X_k=1\) with probability \(\tfrac13\) and \(X_k=3\) with probability \(\tfrac23\), independently, and set \(t=4\). The first epoch is at most \(4\) for either interarrival value, so \(a_1(4)=1\). For two interarrivals, the only pair whose sum exceeds \(4\) is \((3,3)\), with probability \((\tfrac23)^2=\tfrac49\). Therefore \(a_2(4)=1-\tfrac49=\tfrac59\).
Three interarrivals sum to at most \(4\) only if all three equal \(1\): if any equals \(3\), the sum is at least \(3+1+1=5\). Thus \(a_3(4)=(\tfrac13)^3=\tfrac1{27}\). Four interarrivals fit by time \(4\) only when all four equal \(1\); in that case the sum is exactly \(4\), so the endpoint is included and \(a_4(4)=(\tfrac13)^4=\tfrac1{81}\). For \(n\ge5\), even the minimum possible sum is \(n>4\), giving \(a_n(4)=0\).
The mean is \(1+\tfrac59+\tfrac1{27}+\tfrac1{81} =\tfrac{81+45+3+1}{81}=\tfrac{130}{81}\). The second moment is \(1+3(\tfrac59)+5(\tfrac1{27})+7(\tfrac1{81}) =\tfrac{81+135+15+7}{81}=\tfrac{238}{81}\). It follows that \(\operatorname{Var}(N(4)) =\tfrac{238}{81}-(\tfrac{130}{81})^2 =\tfrac{19278-16900}{6561} =\tfrac{2378}{6561}\).
Check by probabilities of exact counts: The tail differences give probabilities \(\tfrac{36}{81}\) for \(N(4)=1\), \(\tfrac{42}{81}\) for \(N(4)=2\), \(\tfrac{2}{81}\) for \(N(4)=3\), and \(\tfrac{1}{81}\) for \(N(4)=4\). Their numerators sum to \(36+42+2+1=81\). The mean numerator is \(36+2(42)+3(2)+4(1)=130\); the second-moment numerator is \(36+4(42)+9(2)+16(1)=238\). Both moments agree with the tail sums.
Using and Checking the Formula
At a fixed time, the method is systematic. First determine which epochs can occur by \(t\), including those exactly at \(t\). Next compute each probability \(a_n(t)\), stopping when later epochs are impossible or when the remaining tail probabilities can otherwise be evaluated. Sum the probabilities for the mean and the odd-weighted probabilities for the second moment. Finally subtract the square of the mean. When the probabilities are obtained from a discrete interarrival law, list the possible sums or use their probabilities directly; the \(n\)th epoch is a sum of \(n\) interarrivals.
The second-moment series emphasizes later tails more heavily: the probability of at least \(n\) renewals has weight \(2n-1\). Consequently, two renewal counts with the same mean need not have the same variance. The full set of epoch probabilities, rather than only the average count or the mean interarrival time, determines this fixed-time variance.
Common mistake: using the mean tail sum for the second moment. In the two-point example at \(t=3\), adding the tail probabilities without weights gives \(1+\tfrac34+\tfrac18=\tfrac{15}{8}\), which is the mean, not the second moment. A related error is to use weights \(2n\); that gives \(2(1)+4(\tfrac34)+6(\tfrac18)=\tfrac{23}{4}\), also incorrect. The square identity requires the odd weights \(2n-1\), so the correct second moment is \(1+3(\tfrac34)+5(\tfrac18)=\tfrac{31}{8}\). Subtracting \((\tfrac{15}{8})^2\) then gives the verified variance \(\tfrac{23}{64}\).
Check Your Understanding
Use \(a_n(t)=\mathbb{P}(S_n\le t)\), and check each moment against the count distribution when it is finite.
- If \(N(t)\) is exactly \(m\) with probability one, what do the tail sums give for its mean, second moment, and variance?
- For interarrivals that independently equal \(1\) or \(2\) with equal probabilities, find \(a_1(2)\), \(a_2(2)\), and \(a_3(2)\). Remember that equality at the endpoint counts.
- Why is the weight on \(a_n(t)\) in the second-moment formula \(2n-1\), rather than \(n\) or \(2n\)?
- Explain how the probabilities \(\mathbb{P}(N(t)=n)\) can be recovered from consecutive epoch probabilities.
- What condition must hold for the variance formula involving the two sums to be an ordinary finite variance calculation?