Due date: Tuesday, Oct 5.
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.
Suppose that we have $N$ things, that each thing has some integer label, that $a_n$ is the number of these that have the label $n$, and that $$ G(x) = \sum_n x^n a_n $$ is the generating function of the sequence $a$. Let $X$ be the label of a thing drawn uniformly at random, and explain how to find the mean and variance of $X$ by algebraic manipulations of $G$. (If you don't know what the variance is, please look it up or ask us.)
Let $(X_1, \ldots, X_n)$ be a collection of integer-valued random variables with joint distribution $$ \mathbb{P}\{ X_1 = k_1, \; \ldots,\; X_n = k_n \} = p_{k_1, \ldots, k_n} . $$ For each $1 \le i \le n$ define the marginal distribution of $X_i$ to be $$ q^{(i)}_k = \mathbb{P}\{ X_i = k \} . $$
(a) Show that for any function $f$ for which the following makes sense, $$ \mathbb{E}[f(X_i)] = \sum_k f(k) q^{(i)}_k .$$
(b) Show that $$ \mathbb{E}[f(X_1) + \cdots + f(X_n)] = \mathbb{E}[f(X_1)] + \cdots + \mathbb{E}[f(X_n)] . $$
Let $\pi$ be a permutation on $n$ letters. An inversion of pi is a pair $(i,j)$ with $1 \leq i < j \leq n$ such that $\pi(i) > \pi(j)$. Let $I(n,k)$ denote the number of permutations on $n$ letters which have $k$ inversions.
(a) Compute the generating function $G_n(k) = \sum_k \frac{I(n,k)}{n!} x^k$.
(b) What is the expected number of inversions in a randomly chosen permutation on $n$ letters?
(c)
Check your answer by simulation. To do this, write a function that returns a uniformly random permutation of length n;
another function that computes the number of inversions in a permutation;
and another that takes N random permutations and returns the mean number of inversions across all of them
Then make a plot with n on the x-axis and the mean number of inversions
across N=1000 random draws, for n between 1 and 20.
Plot your equation from (b) on top of these points.
(d) Compute (b) in a different way: let $\pi$ be a uniformly random permutation of length $n$, and given $\pi$, for each $1 \le i < j \le n$ let $\theta_{ij} = 1$ if $\pi(i) > \pi(j)$. Let $X$ be the number of inversions in $\pi$ and note that $$ X = \sum_{i < j} \theta_{ij} . $$ Now use linearity of expectation, which implies that $$ \mathbb{E}[X] = \sum_{i < j} \mathbb{E}[\theta_{ij}] . $$
Consider two six-sided dice with sides marked as follows:
We roll these two dice and add the values to get a random number between 2 and 12.
(a) Show that the random number we get has the same distribution as rolling two ordinary dice and adding the values. This part doesn't need generating functions, but the third part does, so you might as well use them.
(b) Simulate at least 10,000 times the sum of the two weird dice, and also the sum of two normal dice. Compare the proportion of the times you get each number between 2 and 12 in the two situations (just reporting the ten proportions is OK - note that with 10,000 rolls you expect these to be off by a few percent).
(c) Show that
are the only labellings with the property described in part (a), subject to the conditions that each die has six sides and the smallest number on each die is 1.