Assignment 4

Question 1

You have a collection of $20$ $20$-sided dice $D_1,\ldots,D_{20}$. For each $i\in\{1,\ldots,20\}$, $D_i$ has the integer $i$ written on exactly one of its faces and has a zero written on each of its $19$ other faces.

You roll each of these dice once. Consider the random variable $X$ whose value is the sum of these $20$ rolls.

1. Determine $\E(X)$, the expected value of $X$.

Question 2

Let $X_1,\ldots,X_n$ be a sequence of mutually independent random variables each taking on a value in the set $\{-1,+1\}$ with equal probability. Let $X=\sum_{i=1}^n X_i$.

1. What is $\E(X)$?
2. Let $1\le i\le n$. What $E(X_i^2)$?
3. Let $1\le i< j\le n$. What is $\E(X_iX_j)$?
4. What is $\E(X^2)$? [Hint: Expand $X^2=(X_1+\cdots+X_n)^2$ and then use linearity of expectation.]

Question 3

We roll a normal $6$-sided die until we get an even number or until we have rolled it 10 times. Let \[ X = \text{the number of times we roll the die} \] \[ Y = \text{the number of odd numbers we roll} \]

1. What is $\E(X)$?
2. What is $\E(Y)$?

Question 4

Let $G$ be a graph with $n$ vertices $v_1,\ldots,v_n$ and a total of $m$ edges $a_1b_1,\ldots,a_mb_m$. Recall that the degree $\deg(v)$ of a vertex $v$ in $G$ is the number of edges of $G$ that are incident to $v$. The total degree of $G$ is $\sum_{i=1}^n \deg(v_i) = 2m$ and the average degree of $G$ is $\tfrac{1}{n}\sum_{i=1}^n \deg(v_i)=2m/n$.

1. Choose a random vertex $v_i$ and let $X=\deg(v_i)$. What is $\E(X)$?
2. Let $\{v_i,v_j\}$ be a random $2$-element subset of $\{v_1,\ldots,v_n\}$ and define \[ Y=\begin{cases} n-1 & \text{if $v_iv_j$ is an edge of $G$} \\ 0 & \text{otherwise} \end{cases} \] What is $\E(Y)$?
3. Choose a uniformly random edge $a_ib_i$ of $G$ and let $Z=m\cdot(\deg(a_i)+\deg(b_i))$. What is $\E(Z)$?

Question 5

This question is closely related to the analysis of FindMax in Lecture 18.

Consider the following piece of python code:

    from random import randrange

    def racer(n):
        i = 0
        while i < n:
            i = randrange(i+1, n+1)   # random integer in {i+1,...,n}
            print("hello")

1. Let $n>0$ be an integer. What is the expected number of times $\operatorname{racer}(n)$ prints "hello"?

Question 6

Let $G$ be a graph with $n$ vertices $v_1,\ldots,v_n$ and $m=n-1$ edges. Two examples of this kind of graph are a path in which $v_i$ is adjacent to $v_{i-1}$ and $v_{i+1}$ for each $i\in\{2,\ldots,n-1\}$ and a star in which each of $v_2,\ldots,v_n$ is adjacent to $v_1$.

Let $v_1,\ldots,v_4$ be four vertices of $G$ chosen independent and uniformly at random.

1. Let $X=(\deg(v_1))^2$. How large can $\E(X)$ be? Describe a graph with $n$ vertices and $n-1$ edges that makes $\E(X)$ as large as possible.
2. Markov's Inequality says that, for any non-negative random variable $Y$ and any $r>0$, $\Pr(Y\ge k) \le \E(Y)/r$. Let $Y=\deg(v_1)$. Use Markov's Inequality to show that $\Pr(Y\ge r) \le 2/r$.
3. Let $Z=\min\{\deg(v_i):i\in\{1,2,3,4\}\}$. Prove that $\Pr(Z\ge r) \le 16/r^4$.
4. Recall that, for a non-negative integer-valued random variable $R$, $\E(R)=\sum_{k=1}^\infty \Pr(R\ge k)$. Let $R=(\min\{\deg(v_i):i\in\{1,2,3,4\}\})^2$. Prove that $\E(R) \le 16\cdot\sum_{k=1}^\infty 1/k^2$.

The solution to the Basel Problem shows that this means $\E[R] \le 8\pi^2/3$.