\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{fancybox}
\usepackage{graphicx}
\usepackage{hyperref}

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

\newcommand{\GBB}{\textsf{\sc GetBiasedBit}}
\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}

\begin{document}

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

\noindent {\bf Due:} Sunday November 22, 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}
A \emph{scrabble hand} is a set of 7 tiles, each having one of the english uppercase letters on them, drawn uniformly at random from a bag of 98 tiles. The number of tiles of each letter are as follows:

    E×12,
    A×9, I×9,
    O×8,
    N×6, R×6, T×6,
    L×4, S×4, U×4, D×4,
    G×3,
    B×2, C×2, M×2, P×2, F×2, H×2, V×2, W×2, Y×2,
    K×1, J×1, X×1, Q×1, Z×1

\begin{enumerate}
    \item What is the probability that a scrabble hand contains the word OCTAGON?
    \item What is the probability that a scrabble hand contains the word DOODLES?
    \item What is the probability that a scrabble hand contains the word SMOKO?
\end{enumerate}
\end{question}


\begin{question}
Two villainous professors decide to implement a randomized multiple-choice exam.  Each student receives an exam containing 17 questions each having 4 multiple-choice options.

Behind the scenes is a question bank $B$ containing 200 questions.  Each question $q$ in the question bank $B$ has a set $A_q$ of 10 possible answers, exactly one of which is correct.

For each student $X$, the 17 questions on $X$'s exam are a uniformly random 17-element \emph{ordered} subset of $B$.  For each these questions $q$, the student is presented with a uniformly random 4-element \emph{ordered} subset of $A_q$ that contains the correct answer.

\begin{enumerate}
    \item If two students $X$ and $Y$ write this exam, what is the probability that $X$ writes exactly the same exam as $Y$?  (We consider two exams to be exactly the same if they contain the same questions in the same order with the same multiple-choice options for each question, also in the same order.)

    \item If two students $X$ and $Y$ write this exam, what is the probability that both exams contain exactly the same 17 questions (possibly in a different order and possibly with different multiple-choice options for each question)?

    \item If two students $X$ and $Y$ write this exam, what is the probability that at least one question on $X$'s exam also appears on $Y$'s exam (possibly with different answers).  Give an exact answer as well as a decimal approximation.

    \item 500 students write the exam and student $X$ decides to post the exam on Stack Overflow to ask for help during the exam.  Student $X$ is not dumb so they post it under a pseudonym $\tilde{X}$ so that they can't be identified.  Of course, the professors find the Stack Overflow post.  What is the probability that the professors can uniquely identify the student from the posted exam?  In other words what is the probability that none of the 499 other students received exactly the same exam as $X$?  Is this probability close to 1 or close to 0?
\end{enumerate}
\end{question}

\begin{question}
    Sad that Calypso Water Park is closed, Professor M opens his own backyard water park with only one slide:

    \centerline{\includegraphics{cannonball-loop}}

    Professor M invites 100 Carleton University students to his park;  10 of the students are wearing red bathing suits and the other 90 are wearing black bathing suits.  The students line up in a uniformly random order and slide down the slide one after the other.

    Before he gets bored, Professor M watches the first two students emerge from the slide and notes the colours $c_1$ and $c_2$ of their bathing suits, respectively.



    \begin{enumerate}
        \item Describe the sample space $S$ for this experiment.
        \item For each $\omega\in S$, determine $\Pr(\omega)$.

        \item[] Let $A$ be the event ``$c_1$ is black'' let and $B$ be the event ``$c_2$ is red''
        \item What is $\Pr(A\cap B)$?
        \item What is $\Pr(A\cup B)$?
        \item Are the events $A$ and $B$ independent?  In other words, is $\Pr(A\cap B)=\Pr(A)\cdot\Pr(B)$?
    \end{enumerate}
\end{question}


\begin{question}
For this problem you have an \href{https://www.google.com/search?q=roll+a+d8}{8-sided die}.  Consider the following two games:

\begin{description}
\item[Game A.] you roll the die 8 times and you win if you roll 8 at least once.
\item[Game B.] you roll the die 24 times and you win if you roll 8 at least three times.
\end{description}
\begin{enumerate}
    \item What is the probability of winning Game A?
    \item What is the probability of winning Game B?
\end{enumerate}
Hint: Review the lecture on the Newton-Pepys Problem
\end{question}

\begin{question}
    You pick $n$ numbers $x_1,\ldots,x_n$. Each $x_i$ is chosen uniformly at random from the set $\{1,\ldots,n\}$, so $(x_1,\ldots,x_n)$ is a uniformly random $n$-vector from $\{1,\ldots,n\}^n$.
    \begin{enumerate}
        \item What is $\Pr(x_1=n)$?
        \item What is $\Pr(\max\{x_1,\ldots,x_n\} = n)$?
        \item What is $\Pr(x_1=\max\{x_1,\ldots,x_n\})$?
        \item For $i\in\{1,\ldots,n\}$, what is $\Pr(\max\{x_1,\ldots,x_n\}=i)$?  (Your formula will depend on $i$)
    \end{enumerate}
\end{question}

\begin{question}
Let $p$ be a real number with $0<p<1$ and consider its infinite binary
representation
\[ p = 0. p_1 p_2 p_3 \cdots .
\]
Note that
\[ \sum_{k=1}^{\infty} \frac{p_k}{2^k} = p .
\]
For example, if $p = 1/\pi$, then
\[ p = 0.010100010111110011 \cdots .
\]
We assume that we know, for any $k \geq 1$, the bit $p_k$.

You would like to generate a \emph{biased} random bit: With probability
$p$, this bit is $1$, and with probability $1-p$, it is $0$. You find
a \emph{fair} coin in your pocket: This coin comes up heads with
probability $1/2$ and tails with probability $1/2$. In this question,
you will show that this coin can be used to generate a biased random bit.

Consider the following algorithm $\GBB$, which does not take any input:

\capsule{Algorithm $\GBB$}{
\begin{quote}
\begin{tabbing}
$//$ all coin flips made are mutually independent \\
repeatedly flip the coin until it comes up heads for the first time; \\
let $k$ be the number of coin flips made (including the one resulting in
heads); \\
let $b = p_k$; \\
return $b$
\end{tabbing}
\end{quote}
}

\begin{itemize}
\item Prove that algorithm $\GBB$ returns $1$ with probability $p$.
\end{itemize}
\end{question}

\begin{question}
Let $n \geq 0$ be an integer, let $x$ be a real number with $0<x<1$, 
and let  
\[ G_n(x) = \left( \sum_{k=0}^{\infty} x^k \right)^{n+1} , 
\]
i.e., 
\[ G_n(x) = 
   \underbrace{\left( 1+x+x^2+x^3+\cdots\right) 
               \left( 1+x+x^2+x^3+\cdots\right) \cdots 
               \left( 1+x+x^2+x^3+\cdots\right)}_{\mbox{$n+1$ times}} .
\]
\begin{enumerate}
\item Let $m \geq 0$ be an integer. Determine the coefficient of $x^m$ 
in the (infinite) expansion of $G_n(x)$. 

\emph{Hint:} You may use a certain result that we have seen in the 
chapter on counting. 
\item Explain, in a few sentences, why 
\[ \frac{1}{(1-x)^{n+1}} = 
    \sum_{m=0}^{\infty} {{m+n} \choose n} x^m . 
\]
\item Explain, in a few sentences, why 
\begin{equation}  \label{eq1} 
   \sum_{k=n}^{\infty} {k \choose n} x^k = \frac{x^n}{(1-x)^{n+1}} .
\end{equation} 

\emph{Remark:} In the winter term of 2019, Question 8 on Assignment 4 
asked to prove (\ref{eq1}); this identity was needed in Question 9
of that assignment. At that time, 
Michiel\footnote{he is not the owner of a backyard water park} 
only knew how to prove this by induction on $n$, and using a lot 
of ugly algebraic manipulation. Joyce took the course and had to 
go through this painful exercise. The situation was even worse for 
Alexa, FX, Yuan, and Zoltan, because they had to mark this assignment. 
After the term was over, Michiel found out that there is a much simpler 
proof; this is the proof in this question. 
The moral of the story is that ``every'' identity has a simple 
combinatorial proof. 
\end{enumerate}
\end{question}

\end{document}
