Elementary renewal theorem Created 2026-10-03 Updated 2026-11-05
For strictly positive independent and identically distributed interarrival times with finite mean , the elementary renewal theorem states
This is a limit of expected counts. The renewal counting law of large numbers gives the almost-sure version, but almost-sure convergence alone does not justify moving the limit through an expectation.
An elementary proof uses Wald's equation. The first index for which the renewal sum exceeds is a stopping time; itself generally is not. The exponential moment of a renewal count ensures that its expectation is finite. Since , Wald's equation gives , proving the lower asymptotic bound.
For the upper bound, truncate each interarrival to , with mean . The truncated process has at least as many renewals, , and its first sum exceeding is at most . Hence
For fixed , this gives . Finally by monotone convergence. The two bounds prove the theorem without an unjustified interchange of expectation and limit.
For independent identically distributed positive holding times , define , and the renewal count . With , the renewal strong law is almost surely. The elementary renewal theorem is , where . More generally the rate is zero when the mean holding time is infinite, under the usual nonexplosion assumptions.
Let be the natural filtration. An integer-valued random variable is a stopping time with respect to when
Thus whether one has stopped by time can be decided from the first observations, without seeing future variables. Equivalently, .
Write the stopped sum as
The event depends only on , so its indicator and are independent random variables. Since and , Tonelli theorem gives
We may consequently exchange expectation and summation. Using the tail-sum formula for proves Wald's equation:
For the renewal process, put and . The random variable is a stopping time. Since , Wald's equation gives
and hence
For , set and . Wald's equation still applies to the stopping time and the independent variables . Because ,
Therefore
By the monotone convergence theorem, as . Combining the bounds proves the elementary renewal theorem
For a fixed word over equally likely symbols, the waiting time for a word in independent uniform symbols has mean , where runs through the lengths of the borders of a word, including the full word. The word lava' has no proper nonempty border, so $$ \boxed{\mathbb E\tau_{\mathtt{lava}}=100^4=100\,000\,000}. $$ The word aa' has borders of lengths and , so
For a direct check, let be the expected remaining time with no trailing a' and $E_1$ with one trailing a'. Then
which gives .