\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{fancybox}
\usepackage{amsmath}
\usepackage{paralist}

\newcommand{\IE}{\mathbb{E}}
\newcommand{\Mystery}{\textsf{\sc Mystery}}
\newcommand{\EULER}{\textsf{\sc Euler}}
\newcommand{\TOTAL}{\mathord{\it total}}
\newcommand{\DEG}{\mathord{\it deg}}

%%%%%%%%%%%%%% Capsule %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\capsule}[2]{\vspace{0.5em}
  \shadowbox{%
    \begin{minipage}{.90\linewidth}%
      \textbf{#1:}~#2%
    \end{minipage}}
  \vspace{0.5em} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}

\begin{document}

\begin{center} \Large\bf
COMP 2804 --- Assignment 4
\end{center}

\noindent {\bf Due:} Sunday December 6, 11:55 pm.

\vspace{0.5em}

\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
      cuLearn.
\item {\bf Late assignments will not be accepted. I will not reply to
      emails of the type ``my internet connection broke down at
      11:53pm'' or ``my scanner stopped working at 11:54pm'', or
      ``my dog ate my laptop charger''.}
\item You are encouraged to collaborate on assignments, but at the level
      of discussion only. When writing your solutions, you must do so
      in your own words.
\item Past experience has shown conclusively that those who do not put
      adequate effort into the assignments do not learn the material and
      have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
      \begin{itemize}
      \item You must justify your answers.
      \item The answers should be concise, clear and neat.
      \item When presenting proofs, every step should be justified.
      \end{itemize}
\end{itemize}

\vspace{1em}

\begin{question}
\begin{itemize}
\item Write your name and student number.
\end{itemize}
\end{question}

\begin{question}
Consider six fair dice $D_1,\ldots,D_6$, each one having six faces. 
For each $i$ with $1 \leq i \leq 6$, the die $D_i$ has one face labeled 
$i$, whereas its other five faces are labeled zero. 

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

Determine the expected value $\IE(X)$ of $X$. 
\end{question}

\begin{question}
Consider a standard red die and a standard blue die; both of them are 
fair. You roll each die once. Consider the random variables 
\begin{eqnarray*} 
 X & = & \mbox{the result of the red die plus the result of the 
             blue die,} \\ 
 Y & = & \mbox{the result of the red die minus the result of the 
             blue die.} \\ 
\end{eqnarray*} 

\begin{enumerate}
\item Prove that $\IE(X \cdot Y) = \IE(X) \cdot \IE(Y)$. 
\item Are $X$ and $Y$ independent random variables? As always, justify 
your answer. 
\end{enumerate} 
\end{question}

\begin{question}
When FX and his girlfriend XF have a child, this child is a boy with 
probability $1/2$ and a girl with probability $1/2$, independently of 
the sex of their other children. FX and XF stop having children as soon 
as they have a girl or four children. 


Consider the random variables 
\begin{eqnarray*} 
 C & = & \mbox{the number of children that FX and XF have,} \\ 
 B & = & \mbox{the number of boys that FX and XF have.} \\ 
\end{eqnarray*} 
Determine the expected values $\IE(C)$ and $\IE(B)$. 
\end{question}


\begin{question}
Consider the following algorithm, which takes as input an integer 
$n \geq 1$:

\capsule{Algorithm $\Mystery(n)$}{
\begin{quote}
\begin{tabbing}
$//$ all random choices made are mutually independent \\
$X=0$; \\ 
{\bf for} $i=1$ {\bf to} $n$ \\
{\bf do} \= $a=$ random real number between $-1$ and $1$; \\
         \> $b=$ random real number between $-1$ and $1$; \\
         \> {\bf if} $a^2 + b^2 \leq 1$ \\
         \> {\bf then} $X = X+1$ \\
         \> {\bf endif} \\
{\bf endfor}; \\
$Y = \frac{4}{n} \cdot X$; \\ 
return $Y$ 
\end{tabbing}
\end{quote}
}

The output $Y$ of this algorithm is a random variable. Determine the 
expected value $\IE(Y)$ of this random variable.

\vspace{0.5em} 

\noindent 
\emph{Hint:}  
If you implement this algorithm and run it several times for large 
values of $n$, then you may recognize the output. For the derivation 
of your value of $\IE(Y)$, use indicator random variables. 
\end{question}

\begin{question}
In the Lotto 6/49 lottery, you pick a $6$-element subset $X$ from the 
set $N=\{1,...,49\}$ and then a machine picks, uniformly at random, a 
$6$-element subset $Y$ from $N$.

\begin{enumerate}
\item The number $|X\cap Y|$ of numbers you picked correctly is a 
random variable. What is the expected value of this random variable?  
Give an exact answer, some Python code is provided below that can help 
you with the calculation.
\item \ [Warning: The following is an oversimplification, don't use it 
to make life choices.] The payout in Lotto 6/49 is relative to the 
Jackpot, which we will call $x$.  The payout is defined as follows:   
    \begin{compactitem}
        \item 6 correct numbers: $x$   
        \item 5 correct numbers $x/95$   
        \item 4 correct numbers $x/4365$   
        \item 3 correct numbers $10$   
        \item 2 correct numbers $3$
    \end{compactitem}
If you are given one Lotto 6/49 ticket, what is your expected payout? 
Give an exact answer (which will include the variable $x$).
\item A Lotto 6/49 ticket costs $\$3$. What is the minimum jackpot value 
$x$ that gives a payout of at least $\$3$?
\end{enumerate}

Useful Python Code
\begin{verbatim}
morin@lauteschwein:~$ python3
Python 3.8.5 (default, Jul 28 2020, 12:59:40)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from fractions import Fraction
>>> from math import factorial
>>> binom=lambda n,k: Fraction(factorial(n),factorial(k)*factorial(n-k))
>>> n = 5
>>> print(binom(n,3)/2**n)
5/16
>>> sum([binom(n,k) for k in range(n+1)])
Fraction(32, 1)
>>> sum([binom(n,k)/2**n for k in range(n+1)])
Fraction(1, 1)
\end{verbatim}
\end{question}

\begin{question}
Consider the following algorithm, which takes as input an integer 
$n \geq 1$:

\capsule{Algorithm $\EULER(n)$}{
\begin{quote}
\begin{tabbing}
$//$ all random choices made are mutually independent \\
$\TOTAL = 0$; \\ 
$i=0$; \\
{\bf while} $\TOTAL \leq n$ \\ 
{\bf do} \= $i=i+1$; \\ 
         \> $x_i = $ uniformly random element in $\{1,2,\ldots,n\}$; \\ 
         \> $\TOTAL = \TOTAL + x_i$ \\
{\bf endwhile}; \\ 
return $i$ 
\end{tabbing}
\end{quote}
}

The output $i$ of this algorithm is a random variable, which we denote 
by $X$. 

\begin{enumerate} 
\item What are the possible values that $X$ can take? As always, justify 
your answer. 
\item Let $k$ be an integer with $0 \leq k \leq n$. Prove that 
\[ \Pr ( X \geq k+1 ) = {n \choose k} \cdot (1/n)^k . 
\]

\noindent 
\emph{Hint:} What is the number of solutions of the inequality 
$x_1 + x_2 + \cdots + x_k \leq n$, where $x_1,x_2,\ldots,x_k$ are 
strictly positive integers? 
\item Determine $\IE(X)$. 

\noindent 
\emph{Hint:} You may use the fact that 
$\IE(X) = \sum_{k=0}^n \Pr(X \geq k+1)$. 

\item Determine $\lim_{n \rightarrow \infty} \IE(X)$. 
\end{enumerate} 
\end{question}

\begin{question}
Let $G$ be an undirected graph with $n$ vertices and $m$ edges. 
This graph is not necessarily connected.
Recall that the degree of a vertex $u$, denoted $\DEG(u)$, is the 
number of edges that are incident on $u$. We assume that every vertex 
has degree at least one. If $u$ and $v$ are two vertices that are 
connected by an edge, then we say that $v$ is a neighbor of $u$.   

Consider the following experiment: 
\begin{itemize}
\item Let $x$ be a uniformly random vertex. 
\item Let $y$ be a uniformly random neighbor of $x$. 
\item Let $X = \DEG(x)$ and $Y = \DEG(y)$. 
\end{itemize} 

\begin{enumerate}
\item Let $a>0$ and $b>0$ be real numbers. Prove that 
\[ \frac{a}{b} + \frac{b}{a} \geq 2 ,  
\]
with equality if and only if $a=b$. 

\noindent 
\emph{Hint:} Rewrite this inequality until you get an equivalent
inequality which obviously holds.
\item Prove that the expected value $\IE(X)$ of the random variable 
$X$ satisfies 
\[ \IE(X) = \frac{2m}{n} . 
\] 
\item Prove that the expected value $\IE(Y)$ of the random variable 
$Y$ satisfies 
\[ \IE(Y) = \frac{1}{n} \cdot  
    \sum_{\scriptsize{\mbox{$u$: vertex in $G$}}} 
    \left( \sum_{\scriptsize{\mbox{$v$: neighbor of $u$}}} 
              \frac{\DEG(v)}{\DEG(u)} 
    \right) . 
\] 
\item Prove that 
\[ \sum_{\scriptsize{\mbox{$u$: vertex in $G$}}} 
    \left( \sum_{\scriptsize{\mbox{$v$: neighbor of $u$}}} 
              \frac{\DEG(v)}{\DEG(u)} 
    \right) = 
   \sum_{\scriptsize{\mbox{$\{u,v\}$: edge in $G$}}} 
     \left( \frac{\DEG(v)}{\DEG(u)} + \frac{\DEG(u)}{\DEG(v)} 
     \right) . 
\]
\item Prove that 
\[ \IE(Y) \geq \IE(X) ,
\]
with equality if and only if each connected component of $G$ is 
regular (i.e., all vertices in the same connected component have the 
same degree).           
\end{enumerate} 
\end{question}

\end{document}
