\documentclass{article}
\usepackage{amsmath}
\usepackage{xcolor}
\usepackage{paralist}
\usepackage{amsfonts}
\usepackage{url}
\usepackage{listings}

% \usepackage{listings}
% \usepackage{minted}

\usepackage[utf8]{inputenc}

\usepackage[margin=1in]{geometry}
\setlength{\parskip}{1em}

\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

\DeclareMathOperator{\E}{\mathbf{E}}
\newcommand{\N}{\mathbb{N}}

\title{Assignment 4 Solutions}
\author{COMP2804 Fall 2019}

\begin{document}
\maketitle

\newcommand{\Z}{\mathbb{Z}}

Name: Lenny Learning Combinatorics \\
Student ID: 100000000

\section{Rolling two D20}

For these questions we're working in a uniform sample space $S=\{(d_1,d_2): d_1,d_2\in \{1,\ldots,20\}\}$ of size $20\cdot 20=400$ and it helps to explicitly know what $A$, $B$, and $C$, are.
\[ A=\{(13,1),(13,2),(13,3),\ldots,(13,19),(13,20)\} \]
\[ B=\{(1,14),(2,13),(3,12),\ldots,(13,2),(14,1)\} \]
\[ C=\{(1,20),(2,19),(3,18),\ldots,(19,2),(20,1)\} \]
We see that $|A|=20$, $|B|=14$, and $|C|=20$.
\[  \Pr(A) = \frac{|A|}{|S|} = \frac{20}{400} = \frac{1}{20}  \]
\[  \Pr(B) = \frac{|B|}{|S|} = \frac{14}{400} = \frac{7}{200}  \]
\[  \Pr(C) = \frac{|C|}{|S|} = \frac{20}{400} = \frac{1}{20}  \]

\begin{enumerate}
  \item $A\cap B = \{(13,2)\}$ so $|A\cap B|=1$ and
  \[  \Pr(A\cap B) = \frac{|A\cap B|}{|S|} = 1/400
       \neq \Pr(A)\cdot\Pr(B) = \frac{1}{20}\frac{7}{200} = \frac{7}{4000} \enspace .
  \]
  Therefore $A$ and $B$ are not independent.
  
  
  \item $A\cap C = \{(13,8)\}$ so $|A\cap C|=1$ and 
  \[  \Pr(A\cap C) = \frac{|A\cap C|}{|S|} = 1/400
       = \frac{1}{20}\cdot\frac{1}{20}=\Pr(A)\cdot\Pr(B) \enspace .
  \]
  Therefore $A$ and $C$ are independent.
\end{enumerate}

\section{Randomized Leader Election}

\begin{enumerate}
    \item Person $x_i$ leaves the circle in the first round if they toss heads and their two neighbours $x_{i-1}$ and $x_{i+1}$ toss tails.  Therefore, no two adjacent people leave the circle in the first round.  Therefore, the maximum number of people who leave the circle in the first round is not more than $\floor{n/2}$.  On the other hand, if the coin tosses alternate between tails and heads so that $c_0,\ldots,c_{n-1}=T,H,T,H,T,\ldots$ then persons $x_{1},x_{3},x_{5},x_{7},\ldots,x_{2\floor{n/2}-1}$ will all leave the circle, so the maximum number of people who can leave the circle in the first round is not less than $\floor{n/2}$.
    
    \item  Since the coin tosses are independent 
    \[
       \Pr(\text{``$x_i$ survives''}) = 1-\Pr(\text{``$c_{i-1}=T$ and $c_i=H$ and $c_{i+1}=T$''}) = 1-\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2} = 7/8 \enspace .
    \]
    
    \item Person $x_i$ survives the first $r$ rounds if they survive round 1 and they survive round 2 and then they survive round 3,\ldots, and then they survive round $r$.  From the first question, we know that the number of people who survive up to the beginning of round $r'$ is at least $n/2^{r'-1} > 3$ for $r'-1 < \log_2(n/3)$.  Therefore, if $x_i$ survives to the beginning of Round~$r'$ then round $r'$ proceeds under the same assumptions we used for the previous question.  Therefore,
    \[  \Pr(\text{``$x_i$ survives round $r'$''}\mid\text{``$x_i$ survives rounds $1,\ldots,r'-1$''}) = 7/8 \enspace . \]
    Therefore,
    \begin{align*}  \Pr(\text{``$x_i$ survives rounds $1,\ldots,r$''})
         & = \prod_{r'=1}^r\Pr(\text{``$x_i$ survives round $r'$''}\mid\text{``$x_i$ survives rounds $1,\ldots,r'-1$''}) \\
         & = \prod_{r'=1}^r 7/8 = (7/8)^r \enspace . 
     \end{align*}
     If we let $I_i$ be the indicator variable
     \[
        I_i = \begin{cases}
          1 & \text{if $x_i$ survives rounds $1,\ldots,r$} \\
          0 & \text{otherwise}
      \end{cases}
     \]
     then $\E(I_i)=\Pr(I_i=1)=(7/8)^r$.
     Then the expected number of people who survive the first $r$ rounds is
     \[  \E\left(\sum_{i=1}^n I_i\right) = \sum_{i=1}^n \E(I_i) = n(7/8)^r \enspace . \] 
  \end{enumerate}
  
  \section{Sampling With Replacement}
  
  For this one, recall the sum that we used to analyze geometric random variables:  For any $0<p<1$,
  \[
    \sum_{k=1}^\infty k\cdot(1-p)^{k-1}\cdot p = \frac{1}{p}
  \]
  \begin{enumerate}
    \item For each $k\in\N$, $X=k$ if and only if $\pi_1=\pi_2=\cdots=\pi_{k-1}=T$ and $\pi_k=H$.  Since the coin tosses are independent:
    \begin{align*}
      \Pr(X=k)&=\Pr(\text{$\pi_1=\pi_2=\cdot=\pi_{k-1}=T$ and $\pi_k=H$}) \\
       &=\Pr(\pi_1=T)\cdot\Pr(\pi_2=T)\cdot\cdots\cdot\Pr(\pi_{k-1}=T)\cdot\Pr(\pi_k=H) \\
       &= (2/n)^{k-1}\cdot (1-2/n) \enspace .
    \end{align*}
    Now, using the definition of expected value, we get
    \[ \E(X) = \sum_{k=1}^\infty k\Pr(X=k)
    = \sum_{k=1}^\infty k\cdot(2/n)^{k-1}\cdot(1-2/n) = \frac{1}{1-2/n} = \frac{n}{n-2} \enspace . \]
    (Or we can observe that $X$ is a $\mathrm{gemetric}(1-2/n)$ random variable to get the same result.)
    
    \item To compute $\E(Y)$, we proceed exactly as above except reversing the roles of $1-2/n$ and $2/n$ to finish with
    \[  \E(Y) = \sum_{k=1}^\infty k\cdot(1-2/n)^{k-1}\cdot(2/n) = \frac{n}{2} \enspace . \]
  \end{enumerate}
  
  \section{Sampling without Replacement}
  
  \begin{enumerate}
    \item Computing $\E(X)$ is not too difficult because $X$ has only three possible values:
    \begin{enumerate}
      \item $X=1$ and this happens when $\pi_1$ is a beer bottle.  There are $n-2$ choices for $\pi_1$ and $(n-1)!$ choices for the permutation $\pi_2,\ldots,\pi_n$ of the remaining $n-1$ bottles. So,
      \[ \Pr(X=1) = \frac{(n-2)\cdot(n-1)!}{n!} = \frac{n-2}{n} \]
      
      \item $X=2$ and this happens when $\pi_1$ is a cider bottle and $\pi_2$ is a beer bottle. There are $2$ choices for the cider bottle $\pi_1$, there are $n-2$ choices for the beer bottle $\pi_2$, and then there are $(n-2)!$ choices for the permutation $\pi_3,\ldots,\pi_n$ of the remaining $n-2$ bottles.  So
      \[  \Pr(X=2) = \frac{2\cdot (n-2)\cdot (n-2)!}{n!} = \frac{2(n-2)}{n(n-1)} \]

      \item $X=3$ and this happens when $\pi_1$ and $\pi_2$ are cider bottles and $\pi_3$ is a beer bottle.  There are $2!=2$ choices for the ordering of the cider bottles (either $\pi_1\pi_2=c_1c_2$ or $\pi_1\pi_2=c_2c_1$) and then there are $(n-2)!$ choices for the ordering $\pi_3,\ldots,\pi_n$ of the remaining $n-2$ beer bottles.  So,
      \[  \Pr(X=3)= \frac{2\cdot(n-2)!}{n!} = \frac{2}{n(n-1)} \]
    \end{enumerate}
    Applying the definition of expected value, we get
    \begin{align*} \E(X) 
      & = \sum_{k\in\{1,2,3\}} k\cdot\Pr(X=k) \\
      & = \frac{n-2}{n} + \frac{4(n-2)}{n(n-1)} + \frac{6}{n(n-1)} \\
      & = \frac{n+1}{n-1} \enspace .
    \end{align*}
    
    \item To compute $\E(Y)$ we should figure out $\Pr(Y=k)$ for each $k\in\{1,\ldots,n\}$.  Now, $X=k$ exactly when $\pi_1,\ldots,\pi_{k-1}$ are beer bottles and $\pi_k$ is a cider bottle.  We can count the number of such permutations using the Product Rule:
    \begin{enumerate}
      \item Select the beer bottles $\pi_1,\ldots,\pi_{k-1}$.  There are $n-2$ choices for $\pi_{1}$ and $n-3$ choices for $\pi_2$,\ldots, and $n-2-(k-2)=n-k$ choices for $\pi_{k-1}$, for a total of $(n-2)!/(n-k-1)!$ ways to execute this step.
      \item Select a cider bottle $\pi_k$ from $c_1$ or $c_2$.  There are two ways to execute this step. 
      \item Select a permutation $\pi_{k+1},\ldots,\pi_n$ of the remaining $n-k$ bottles.  There are $(n-k)!$ ways to perform this step.
    \end{enumerate}
    Therefore, there are
    \begin{align*}  
      \frac{(n-2)!}{(n-k-1)!}\cdot 2\cdot (n-k)! 
      & = (n-2)(n-3)\cdots(n-k+1)(n-k)\cdot2\cdot (n-k)(n-k-1)\cdots 1 \\
      & = (n-2)!\cdot 2\cdot (n-k)
    \end{align*}
    permutations $\pi_1,\ldots,\pi_n$ for which $Y=k$.  Therefore,
    \[
       \Pr(Y=k)=\frac{(n-2)!\cdot 2\cdot (n-k)}{n!}
       = \frac{2(n-k)}{n(n-1)}
    \]
    
    Finally, we finish by applying the definition of expected value
    \begin{align*}
       \E(Y) & = \sum_{k=1}^n k\cdot \Pr(X=k) \\
            & =  \sum_{k=1}^n k\cdot \frac{2(n-k)}{n(n-1)} \\
            & =  \frac{1}{n(n-1)}\cdot \sum_{k=1}^n k\cdot 2(n-k) \\
            & =  \frac{1}{n(n-1)}\cdot \left(\sum_{k=1}^n 2kn -\sum_{k=1}^n 2k^2\right) \\
            & =  \frac{1}{n(n-1)}\cdot \left(2n\sum_{k=1}^n k -\sum_{k=1}^n 2k^2\right) \\
            & =  \frac{1}{n(n-1)}\cdot \left(n^2(n+1) - \sum_{k=1}^n 2k^2\right) \\
            & =  \frac{1}{n(n-1)}\cdot \left(n^2(n+1) - \sum_{k=1}^n 2k^2\right) \\
            & =  \frac{1}{n(n-1)}\cdot \left(n^2(n+1) - 2\sum_{k=1}^n k^2\right) \\
            & =  \frac{1}{n(n-1)}\cdot \left(n^2(n+1) - \frac{n(n+1)(2n+1)}{3}\right) \\
            & =  \frac{1}{n(n-1)}\cdot n(n+1)\left(n - \frac{(2n+1)}{3}\right) \\
            & =  \frac{1}{n(n-1)}\cdot n(n+1)\left(\frac{n-1}{3}\right) \\
            & = \frac{n+1}{3}
    \end{align*}
    Notice that, although this random variable $Y$ looks a lot like the one in Question~3.1, its expected value is quite a bit different.
  \end{enumerate}
    
    
\section{Doing (much) Better by Taking the Minimum}

\begin{enumerate}
  \item We are told that $\Pr(X\ge i) \le a/i$, so
  \[ \E(X) = \sum_{i=1}^n i\cdot\Pr(X=i) = \sum_{i=1}^n \Pr(X\ge i) \le \sum_{i=1}^n a/i = aH_n \enspace, \]
  where $H_n=\sum_{i=1}^n 1/i$ is the $n$-th harmonic number.
  
  \item Since $X_1$ and $X_2$ are independent,
  \[  \Pr(Z\ge i) = \Pr(\text{$X_1\ge i$ and $X_2\ge i$}) = \Pr(X_1\ge i)\cdot\Pr(X_2\ge i) \le (a/i)^2 \enspace . \]
  
  \item Following the same procedure we used for $\E(X)$.
  \[ \E(Z) = \sum_{i=1}^n \Pr(Z\ge i) \le \sum_{i=1}^n(a/i)^2 = a^2 \sum_{i=1}^n 1/i^2 \enspace . \]
  Now we're stuck until we can say something about $\sum_{i=1}^n 1/i^2$. 
  
  \item Following the link provided to the Basel Problem explains that $\sum_{i=1}^\infty 1/i^2 = \pi^2/6$.  We can use this by continuing from the previous derivation:
  \[ \E(Z) \le a^2 \sum_{i=1}^n 1/i^2 \le a^2 \sum_{i=1}^\infty 1/i^2 = \frac{(a\pi)^2}{6} \enspace . \]
\end{enumerate}

Notice that, by taking the minimum of two samples we went from a random variable whose expected value was $H_n\approx \ln n$ to a random variable whose expected value is at most $(a\pi)^2/6$---a constant that doesn't depend on $n$.  This idea of taking the best of 2 (or more) samples has useful applications in randomized algorithms. 


  
\end{document}


\end{document}
