Due date: Thursday, Oct 21.
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.
Mergesort is a sorting algorithm. It works as follows. Given a list of numbers L:
Let $L_1$ be the first half of $L$, and the second half of $L$ be the list $L_2$.
Recursively mergesort $L_1$ and $L_2$, yielding two sorted lists $S_1$ and $S_2$.
Merge $S_1$ and $S_2$ together into a new list $S$ as follows. Initialize $S$ to be empty. Move either the first element of $S_1$ or the first element of $S_2$, whichever is smaller, to $S$. Repeat until $S_1$ and $S_2$ are empty.
Return the sorted list $S$.
Analyze the running time of mergesort, assuming that the only operation which takes time is comparing two elements.
The results we proved about branching processes assumed that the offspring distribution had finite mean. What happens if it doesn't? Investigate the branching process with offspring distribution $X$ defined as follows: let $U$ be a random uniform number between 0 and 1, and let $X = \lfloor 1/U \rfloor - 1$.
a. Show that $X$ has infinite mean.
b. Find an expression for the generating function of $X$, and compare your expression to a numerically computed version.
c. Write code that will simulate the branching process with distribution $X$ for a given number of generations. (Note: to avoid bad things happening, you should also ask it to terminate early if a pre-set large number is reached.)
d. Use a large number of runs of your code to estimate the probability that the branching process does not go extinct. Numerically verify the extinction probability is a fixed point of the generating function.
There are a variety of game boards called "snakes and ladders" or "chutes and ladders", but all work like this: the board has 100 squares, some of which are connected by arrows (an arrow that goes from a smaller number to a larger number is a "ladder"; one that goes the other way is a "chute" or "snake"). Each player takes a turn to roll a six-sided die and advance their token the number of squares shown on the die; if their final location is at the base of an arrow then they move to the end of the arrow. The game is begun on square "zero", and finishes when square 100 is reached; a rolls that would move a player past 100 does not move the player. One version of the board has arrows with [start, end] as follows:
sladders = [[1, 38], [4, 14], [9, 31], [21, 42], [28, 84], [36, 44], [51, 67], [71, 91], [80, 100],
[16, 6], [48, 26], [49, 11], [56, 53], [62, 19], [64, 60], [87, 24], [93, 73], [95, 75],
[98, 78]]For instance, on the first roll, the player could end up in the squares 38, 2, 3, 14, 5, or 6. If a player in square 14 rolled a 2, they'd end up at square 6.
(a) Represent possible moves on the board as a directed graph on 101 vertices. Use the adjacency matrix to find the number of distinct paths of length $k$ from 0 to 100 for each $1 \le k \le 50$.
(b) Find the number of distinct paths of length $k$ that start from 0 and have not yet hit 100, and combine this answer with (a) to get the probability of not having yet finished after $k$ moves. (Hint: every possible path is equally likely.)
(c) Let $\alpha(j)$ be the length of the shortest path from square $j$ to square 100, for each $0 \le j \le 100$. Write a program that finds $\alpha(j)$. (Hint: start at $j=100$ and work backwards.)