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$.

Answer 1

1. The die $D_i$ has $\E(D_i)=i\cdot\Pr(D_i=i) + 0\cdot\Pr(D_i=0) = i/20$. Using linearity of expectation, we get \begin{align*} \E\left(\sum_{i=1}^{20} D_i\right) & = \sum_{i=1}^{20} \E(D_i) & \text{(linearity of expectation)} \\ & = \sum_{i=1}^{20} i/20 \\ & = \frac{1}{20}\cdot\sum_{i=1}^{20} i \\ & = \frac{1}{20}\cdot\frac{20(21)}{2} & \text{(Gauß's trick)}\\ & = \frac{21}{2} \enspace . \end{align*}

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.]

Answer 2

1. Again, linearity of expectation makes this easy. $\E(X_i)=\tfrac{1}{2}\cdot -1 + \tfrac{1}{2}\cdot 1 = 0$, so \begin{align*} \E(X) & = \E\left(\sum_{i=1}^n\right) \\ & = \sum_{i=1}^n \E(X_i) & \text{(linearity of expectation)} \\ & = 0 \enspace . \end{align*}
2. For this, we just use the definition of expected value: \[
   \E(X_i^2) = \tfrac{1}{2}\cdot(-1)^2 + \tfrac{1}{2}\cdot 1^2 = 1 \enspace . \]
3. Since $X_i$ and $X_j$ are independent, each of the four outcomes $(X_i,X_j)\in\{-1,1\}^2$ is equally likely, so \[ \E(X_iX_j) = \tfrac{1}{4}(-1\cdot -1) + \tfrac{1}{4}(-1\cdot 1) + \tfrac{1}{4}(1\cdot -1) + \tfrac{1}{4}(1\cdot 1) = 0 \enspace . \]
4. If we follow the hint and expand $X^2 = (X_1+X_2+\cdots+X_n)^2$ we get \[ X^2 = \begin{array}{cccccccccc} X_1^2 & + & X_1X_2 & + & X_1X_3 & + & \cdots & + & X_1X_n & + \\ X_2X_1 & + & X_2^2 & + & X_2X_3 & + & \cdots & + & X_2X_n & + \\ X_3X_1 & + & X_3X_2 & + & X_3^2 & + & \cdots & + & X_3X_n + \\ \vdots & & \vdots & & \vdots & & \ddots & & \vdots \\ X_nX_1 & + & X_nX_2 & + & X_nX_3 & + & \cdots & + & X_n^2 \end{array} \enspace . \] Now we apply linearity of expection and see that each of the off-diagonal terms are $0$ and each of the $n$ terms on the diagonal are $1$, so $\E(X)=n$.

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)$?

Answer 3

1. For each $i\in\{1,\ldots,9\}$, the probability that we roll the die exactly $i$ times is $\Pr(X=i)=(\tfrac{1}{2})^{i}\cdot\tfrac{1}{2}$ since we have to roll $i-1$ odd numbers followed by an even number, and each of these happens independently with probability $\tfrac{1}{2}$. The probability that we roll the die exactly $10$ times is just $\Pr(X=10)=(\tfrac{1}{2})^{9}$ since this happens whenever we roll 9 odd numbers in a row. Therefore, \begin{align*} \E(X) & = \sum_{i=1}^{10} i\cdot \Pr(X=i) \\ & = \left(\sum_{i=1}^9 i\cdot(\tfrac{1}{2})^{i}\right) + 10\cdot(\tfrac{1}{2})^9 \\ & = \frac{1023}{512} & \text{(Python code, below)} \\ & \approx 1.998046875 \end{align*} There is another way to get the same result. For each $i\in\{1,\ldots,10\}$, define the indicator random variable \[ I_i = \begin{cases} 1 & \text{if the first $i-1$ rolls come up odd (or $i=1$)} \\ 0 & \text{otherwise} \end{cases} \] Now notice that $X=\sum_{i=1}^{10} I_i$, so \begin{align*} \E(X) & = \E\left(\sum_{i=1}^{10} I_i\right) \\ & = \sum_{i=1}^{10} \E(I_i) & \text{(linearity of expectation)} \\ & = \sum_{i=1}^{10} (\tfrac{1}{2})^{i-1} \\ & = \sum_{i=0}^{9} (\tfrac{1}{2})^{i} & \text{(move $-1$ into counter)} \\ & = \frac{1-(\tfrac{1}{2})^{10}}{1-\tfrac{1}{2}} & \text{(from Lecture 16)} \\ & = \frac{1023}{512} \enspace . \end{align*} This uses the result from the lecture on infinite probability spaces which states that, for $x\in(0,1)$, $\sum_{i=0}^{N} x^i = (1-x^{N+1})/(1-x)$.
2. This is similar to the previous question except that for each $i\in\{1,\ldots,9\}$ we have $\Pr(Y=i)=(\tfrac{1}{2})^{i+1}$ since we have to roll $i$ odd numbers followed by one even number. For $i=10$ we have $\Pr(Y=10)=(\tfrac{1}{2})^{10}$ since we have to roll $10$ odd numbers. This gives \begin{align*} \E(Y) & = \sum_{i=1}^{10} i\cdot \Pr(Y=i) \\ & = \left(\sum_{i=1}^9 i\cdot(\tfrac{1}{2})^{i+1}\right)
   • 10\cdot(\tfrac{1}{2})^{10} \\ & = \frac{1023}{1024} \enspace . \end{align*}

Here is the Python code that evaluates this exactly:

    from fractions import Fraction
    p = Fraction(1, 2)
    one = sum([(1-p)**(i-1) * p for i in range(1, 10)]) + (1-p)**9
    print(one) # sanity check
    ex = sum([i*(1-p)**(i-1) * p for i in range(1, 10)]) + 10*(1-p)**9
    print(ex)
    xe2 = sum([(1-p)**(i-1) for i in range(1, 11)])
    print(xe2)

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)$?

Answer 4

1. For this, we just apply the definition of expected value. Let $v$ be a uniformly random vertex, so $\Pr(v=v_i)=1/n$ for each $i\in\{1,\ldots,n\}$. Then \begin{align*} \E(X) & = \sum_{i=1}^n \Pr(v=v_i)\cdot\deg(v_i) \\ & = \frac{1}{n}\sum_{i=1}^{n} \deg(v_i) \\ & = \frac{2m}{n} \end{align*} so the expected degree of $v$ is the average degree of $G$.
2. The probability that we pick a pair $v_iv_j$ that form an edge of $G$ is exactly the number, $m$, of edges of $G$ divided by the number, $\binom{n}{2}$, of pairs of vertices of $G$. So \begin{align*} \E(Y) & = (n-1)\cdot\frac{m}{\binom{n}{2}} \\ & = (n-1)\cdot\frac{2m}{n(n-1)} \\ & = \frac{2m}{n} \enspace . \end{align*}
3. For each $i\in\{1,\ldots,n\}$, define \[ Z_j = \begin{cases} \deg(v_j) & \text{if $a_ib_i$ is incident to $v_j$} \\ 0 & \text{otherwise} \enspace . \end{cases} \] Then $Z=m\cdot \sum_{j=1}^n Z_j$. Furthermore, $\Pr(Z_j=\deg(v_j))=\deg(v_j)/m$ since $a_ib_i$ is chosen uniformly at random from all $m$ edges and exactly $\deg(v_j)$ edges are incident to $v_j$. Therefore, \begin{align*} \E(Z_j) & = \deg(v_j)\cdot \Pr(Z_j=\deg(v_j)) + 0\cdot\Pr(Z_j=0) \\ & = \frac{(\deg(v_j))^2}{m} \enspace . \end{align*} Now we can finish with \[ \E(Z) = \E(m\cdot \sum_{j=1}^n Z_j) = m\cdot \sum_{j=1}^n \E(Z_j) = \sum_{j=1}^n (\deg(v_j))^2 \enspace . \]

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"?

Answer 5

1. For each $j\in\{1,\ldots,n\}$, let \[ X_j = \begin{cases} 1 & \text{if we print "hello" when $i=j$} \\ 0 & \text{otherwise} \end{cases} \] Any time we print hello, $i$ has a value in $\{1,\ldots,n\}$ and any time we print hello the value of $i$ increases during the next iteration (if any) so if $X$ is the number of times we print hello, then $X=\sum_{j=1}^n X_j$. To finish, all we need to know is $\Pr(X_j=1)$ for each $j\in\{1,\ldots,n\}$. To figure out this probability, consider the first iteration of the while look in which the algorithm chooses a value $i\in\{j,\ldots,n\}$. When this happens, the value $i$ was chosen uniformly at random from a the set $\{i',\ldots,n\}$ for some $i' \le j$. The set $\{i',\ldots,n\}$ has size $n-i'+1$ and the set $\{j,\ldots,n\}$ has size $n-j+1$, so \begin{align*} \Pr(i=j\mid i\in\{j,\ldots,n\}) & = \frac{\Pr(i=j\cap i\in\{j,\ldots,n\})}{\Pr(i\in\{j,\ldots,n\})} \\ & = \frac{1/(n-i'+1)}{(n-j+1)/(n-i'+1)} \\ & = \frac{1}{n-j+1} \enspace , \end{align*} so $\E(X_j) = 1/(n-j+1)$. Now we can finish with: \begin{align*} \E(X) = E\left(\sum_{j=1}^n X_j\right) & = \sum_{j=1}^n \E(X_j) \\ & = \sum_{j=1}^n \frac{1}{n-j+1} \\ & = \sum_{k=1}^n \frac{1}{k} \\ & = H_n \enspace . \end{align*}

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$.

Answer 6

1. If we take $G$ to be a star (a tree with $n$ nodes, one of which the root and the other $n-1$ of which are leaves) then \[ \E((\deg(v_1))^2) = \tfrac{1}{n}\cdot (n-1)^2 + \tfrac{n-1}{n}\cdot 1^2 = \frac{n(n-1)}{n} = n-1 \enspace . \]
2. We've seent already (in question 4.1) that $\E(\deg(v_1)) = 2m/n = 2(n-1)/n=2-1/n$. Therefore, by Markov's Inequality \[ \Pr(\deg(v_1) \ge r) \le \frac{\E(\deg(v_1))}{r} = \frac{2-\tfrac{1}{n}}{r} < \frac{2}{r} \enspace . \]
3. For each $i\in\{1,\ldots,4\}$, let $A_i$ be the event ``$\deg(v_r)\ge r$''. Then $Z\ge r$ if and only if $A_1\cap A_2\cap A_3\cap A_4$. Since each of $v_1,\ldots,v_4$ is chosen independently, the events $A_1,\ldots,A_4$ are mutually independent, so \[ \Pr(A_1\cap\cdots\cap A_4) = \Pr(A_1)\cdot\cdots\cdot\Pr(A_4) \le \left(\frac{2}{r}\right)^4 = \frac{16}{r^4} \enspace . \]
4. From the hint, we have \begin{align*} \E(R) & = \sum_{k=1}^\infty \Pr(R\ge k) \\ & = \sum_{k=1}^\infty \Pr(Z \ge \sqrt{k}) & \text{(since $Z=\sqrt{R}$)} \\ & \le \sum_{k=1}^\infty \frac{16}{k^2} & \text{(from previous answer, with $r=\sqrt{k}$)}\\ & = 16\cdot \sum_{k=1}^\infty \frac{1}{k^2} \\ \end{align*}