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 statesThis 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 . HenceFor fixed , this gives . Finally by monotone convergence. The two bounds prove the theorem without an unjustified interchange of expectation and limit.
Past exam of the mathematics course of the University of Cambridge 2006 ii Paper 2 26J a Solution Created 2026-09-24 Updated 2026-10-14
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.
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 4 27J Solution Created 2026-09-24 Updated 2026-10-03
Let be the natural filtration. An integer-valued random variable is a stopping time with respect to whenThus whether one has stopped by time can be decided from the first observations, without seeing future variables. Equivalently, .
Write the stopped sum asThe event depends only on , so its indicator and are independent random variables. Since and , Tonelli theorem givesWe 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 givesand hence
For , set and . Wald's equation still applies to the stopping time and the independent variables . Because ,ThereforeBy 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 , soFor a direct check, let be the expected remaining time with no trailing a' and $E_1$ with one trailing a'. Thenwhich gives .