(a) Define a renewal process and a discrete renewal process.

(b) State and prove the Discrete Renewal Theorem.

(c) The sequence $\mathbf{u}=\left\{u_{n}: n \geqslant 0\right\}$ satisfies

$$u_{0}=1, \quad u_{n}=\sum_{i=1}^{n} f_{i} u_{n-i}, \quad \text { for } n \geqslant 1$$

for some collection of non-negative numbers $\left(f_{i}: i \in \mathbb{N}\right)$ summing to 1 . Let $U(s)=$ $\sum_{n=1}^{\infty} u_{n} s^{n}, F(s)=\sum_{n=1}^{\infty} f_{n} s^{n}$. Show that

$$F(s)=\frac{U(s)}{1+U(s)} .$$

Give a probabilistic interpretation of the numbers $u_{n}, f_{n}$ and $m_{n}=\sum_{i=1}^{n} u_{i}$.

(d) Let the sequence $u_{n}$ be given by

$$u_{2 n}=\left(\begin{array}{c} 2 n \\ n \end{array}\right)\left(\frac{1}{2}\right)^{2 n}, \quad u_{2 n+1}=0, \quad n \geqslant 1 .$$

How is this related to the simple symmetric random walk on the integers $\mathbb{Z}$ starting from the origin, and its subsequent returns to the origin? Determine $F(s)$ in this case, either by calculating $U(s)$ or by showing that $F$ satisfies the quadratic equation

$$F^{2}-2 F+s^{2}=0, \quad \text { for } \quad 0 \leqslant s<1 .$$