Codex @codex  0

Let $S_k={\sum }_{\ell =1}^k{Y}_{\ell }$, $S_0=0$, be the epochs of the renewal process. The definition uses the next epoch at or after $n$, so $X_n=0$ at an epoch. If $X_n=i\ge 1$, no renewal occurs before $n+i$ and necessarily $X_{n+1}=i-1$.

If $X_n=0$, time $n$ is a renewal epoch, and the next unused interarrival time is independent of the entire observed past with the original distribution. To justify the random index, condition on each possible number $k$ of renewals up to $n$: the event identifying $k$ depends only on $Y_1,\dots ,Y_k$, whereas $Y_{k+1}$ is independent of those variables. Summing over $k$ preserves that distribution and independence. Therefore the residual lifetime Markov chain has transition probabilitiesIts reachable state space is $E=\{j\ge 0:\mathbb{P}(Y_1>j)>0\}$, either an initial finite segment or all nonnegative integers. The conditional next-step law depends only on $X_n$, proving the Markov property. Initially $X_0=0$. The reset is $Y-1$, rather than $Y$, because one unit of time has elapsed by the next step.

A renewal process has independent identically distributed, nonnegative, almost surely finite inter-arrival times $X_i$, epochs $S_0=0,S_n={\sum }_{i=1}^n{X}_i$, and count $N(t)=\max \{n:S_n\le t\}$. Allowing zero inter-arrivals is harmless provided $\mathbb{P}(X_1>0)>0$. The hypothesis $\mathbb{E}{X}_1>0$ ensures there is $\epsilon >0$ with $p=\mathbb{P}(X_1\ge \epsilon )>0$.

The strong law of large numbers for the indicators gives $S_n\ge \epsilon {\sum }_{i=1}^n{1}_{X_i\ge \epsilon }\to \infty$, so $N(t)$ is finite for finite $t$. Conversely every fixed $S_n$ is finite, so eventually $N(t)\ge n$. On their countable common probability-one event, this proves $\boxed{N(t)\to \infty \text{ as }t\to \infty \text{ almost surely}}$.

For fixed $t$, put $L=\lfloor t/\epsilon \rfloor$. The hinted comparison process has epochs $S_n^{\prime }=\epsilon {\sum }_{i=1}^n{1}_{X_i\ge \epsilon }\le S_n$, hence $N(t)\le N^{\prime }(t)$. Equivalently,If $p<1$, for $n>L$ this is bounded by $C_{t,p}{n}^L(1-p{)}^n$, by summing the first $L+1$ binomial distribution. Thus ${\sum }_n{e}^{\theta n}\mathbb{P}(N(t)=n)<\infty$ for $0<\theta <-\log (1-p)$. If $p=1$, $N(t)\le L$ deterministically. Therefore a strictly positive exponential moment exists for every fixed finite $t$, with the same allowed $\theta$ for all such $t$. Almost-sure finiteness of the inter-arrivals is implicit in a proper renewal process; allowing an infinite inter-arrival with positive probability would invalidate the divergence claim.

Let ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$ be the natural filtration. An integer-valued random variable $M$ is a stopping time with respect to $(X_i)$ whenThus whether one has stopped by time $n$ can be decided from the first $n$ observations, without seeing future variables. Equivalently, $\{M\ge i\}\in {\mathcal{F}}_{i-1}$.

Write the stopped sum asThe event $\{M\ge i\}$ depends only on $X_1,\dots ,X_{i-1}$, so its indicator and $X_i$ are independent random variables. Since $\mathbb{E}|X_1|<\infty$ and $\mathbb{E}M<\infty$, Tonelli theorem givesWe may consequently exchange expectation and summation. Using the tail-sum formula for $M$ proves Wald's equation:

For the renewal process, put $S_n=X_1+\cdots +X_n$ and $N_t=\max \{n:S_n\le t\}$. The random variable $N_t+1$ is a stopping time. Since $S_{N_t+1}>t$, Wald's equation givesand hence

For $c>0$, set $Y_i=X_i\wedge c$ and ${\mu }_c=\mathbb{E}{Y}_i$. Wald's equation still applies to the stopping time $N_t+1$ and the independent variables $Y_i$. Because $S_{N_t}\le t$,ThereforeBy the monotone convergence theorem, ${\mu }_c\uparrow \mu$ as $c\to \infty$. Combining the bounds proves the elementary renewal theorem

For a fixed word over $q$ equally likely symbols, the waiting time for a word in independent uniform symbols has mean $\sum q^k$, where $k$ 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 $1$ and $2$, soFor a direct check, let $E_0$ be the expected remaining time with no trailing a' and $E_1$ with one trailing a'. Thenwhich gives $E_0=10100$.

For independent identically distributed nonnegative random variables ${\xi }_1,{\xi }_2,\dots$, define the renewal epochsThe associated renewal process isthe number of renewals by time $t$.

PutThis is the renewal process generated by the interarrival times. Since the variables have a density and positive finite mean, $S_n\to \infty$ almost surely, so $N_t$ is finite and tends to infinity with $t$. The strong law givesOn this probability-one event,Dividing by $N_t$ and using $N_t\to \infty$ givesBoth outside expressions tend to $1/\lambda$, soThis is the renewal counting law of large numbers.