Due date: Thursday, Oct 14.
Please submit your solutions by upload on Canvas.
It's absolutely OK if you work together on these problems - and this is especially true for the programming problems, when encourage you to work in pairs at one computer, with one person typing and one person thinking.
We do want everyone to write up each assignment on their own.
Let $T_n$ be the number of rooted trees of depth $n$ with the property that each node except the last has either $1$ or $m$ children. Concretely, we can build these as follows: begin with a single node at level 0 (the root), and then form level $k+1$ by attaching either 1 or $m$ children to each node of level $k$. Order does not matter, so $T_0 = 1$ (by convention?); $T_1 = 1$ (the root); $T_2 = 2$ (the root could have either 1 or $m$ children); and $T_3 = 2 + (m + 1)$ (either the root has one child, or the root has $m$ children, and the number of these children that has $m$ children is between 0 and $m$).
Consider the following badly written recursive program to compute the Fibonnacci numbers:
def f(n):
if n <= 1:
return n
else:
return f(n-1) + f(n-2)(a) Analyze its run time.
(b) Write a iterative program to do the same thing, starting with f(0), etc.
Recall that with $C_n$ the number of "mountain ranges" of length $2n$ we found the recursive formula $$ C_n = \sum_{j=0}^{n-1} C_j C_{n-j-1} $$ by decomposing a mountain range into the first mountain (of length $2(j+1)$) and everything else. Write a recursive function that generates all mountain ranges of length $2n$ using this same decomposition, and compare the results to the iterative method we wrote in office hours (see the website for the notebook).
Consider an outbreak of a disease with $R_0 \le 1$: suppose the mean number of new cases per case is $\xi$ with $\mathbb{E}[\xi] = R_0 \le 1$. We'd like to learn about the total number of cases in the outbreak: suppose $(N_t)_{t \ge 0}$ is the branching process driven by $\xi$ and let $W_t = N_0 + N_1 + \cdots + N_t$, and $W = \lim_t W_t$. Suppose the outbreak has $N_0 = 1$, and to agree with previous notation let $\mu = R_0$.
(a) Find $\mathbb{E}[W]$.
(b) Let $G_t(u) = \mathbb{E}[u^{W_t}]$, and $\phi(u) = \mathbb{E}[u^\xi]$, and show that $G_{t+1}(u) = u \phi(G_t(u))$, and so $G(u) = \mathbb{E}[u^{W}] = u \phi(G(u))$. (Hint: split it into the families of the first set of children.)
(c) Find the variance of $W$ in terms of $mu$ and $V = \mathbb{E}[\xi^2]$.
(d) Write a function that simulates from the branching process in the case where $\xi \sim \text{Poisson}(\lambda)$, and use it to check your answers to (a) and (c) at a few values of $\mu < 1$.
(e) What happens when you use your simulation to try to estimate the mean of $W$ at $\mu = 1$? Plot the mean of $n$ independent trials against $n$ at $\mu=0.95$ and at $\mu=1$.