Elementary renewal theorem (source code)

= Elementary renewal theorem

For strictly positive <independent and identically distributed> interarrival times with finite <mean> $\mu>0$, the <elementary renewal theorem> states
$$
\lim_{t\to\infty}\frac{\mathbb EN_t}{t}=\frac1\mu.
$$
This is a limit of expected counts. The <renewal counting law of large numbers> gives the almost-sure version, but <almost sure convergence>[almost-sure convergence] alone does not justify moving the limit through an <expected value>[expectation].

An elementary proof uses <Wald's equation>. The first index $N_t+1$ for which the renewal sum exceeds $t$ is a <stopping time>; $N_t$ itself generally is not. The <exponential moment of a renewal count> ensures that its <expected value>[expectation] is finite. Since $S_{N_t+1}>t$, <Wald's equation> gives $\mu(\mathbb EN_t+1)>t$, proving the lower asymptotic bound.

For the upper bound, truncate each interarrival to $\xi_i^{(a)}=\min(\xi_i,a)$, with <mean> $\mu_a$. The truncated process has at least as many <renewal process>[renewals], $N_t^{(a)}\geq N_t$, and its first sum exceeding $t$ is at most $t+a$. Hence
$$
\mu_a(\mathbb EN_t+1)\leq\mu_a(\mathbb EN_t^{(a)}+1)\leq t+a.
$$
For fixed $a$, this gives $\limsup_t\mathbb EN_t/t\leq1/\mu_a$. Finally $\mu_a\uparrow\mu$ by <monotone convergence theorem>[monotone convergence]. The two bounds prove the theorem without an unjustified interchange of <expected value>[expectation] and limit.