\documentclass[letterpaper,11pt]{article}

\newcommand{\removefromfile}[1]{}

\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage[most]{tcolorbox}
\renewcommand{\theenumi}{\alph{enumi}}
\providecommand{\Exp}{\mathbb{E}}
\providecommand{\Var}{\text{Var}}


\begin{document}
\title{{\bf Problem Set 5 Solutions}}
\author{Name: TODO}
\date{}
\maketitle

\section*{Collaborators}
\begin{tcolorbox}
List collaborators, if any.
\end{tcolorbox}

\section*{Use of 312 Learning Assistant}
\begin{tcolorbox}
List which problems you used the 312 Learning Assistant on.
\end{tcolorbox}

\newpage
\section{Gradescope Questions (22 points)}
Please do these questions on Gradescope.
\begin{tcolorbox}
Nothing to write for this question.
\end{tcolorbox}

\newpage
\section{A simple investing strategy (10 points)}

A certain investor buys $n$ different stocks, with each independently having probability $p$ of going up in value each day, where $0 < p < 1$.
At the end of each day, he keeps all the stocks that went up and sells all of the others.
He repeats this process each day, until he has sold all of his stocks.
We assume that each stock has probability $p$ of going up on any given day and whether or not that happens is independent of what happens on other days or what happens with other stocks.

\begin{enumerate}[label=\alph*)]
\item What is the distribution of $X_t$ for an arbitrary integer $t$?
In other words, what is $\Pr(X_t = k)$? What distribution in our zoo is this, and what are its parameters?

\textbf{Hint:} Think about the probability that a particular stock “survives” until after day $t$.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item What is the probability that he owns at least one stock after $t$ days?
Your answer should not have any summations in it.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}

\newpage
\section{$X$ and $Y$ (15 points)}

Let $X$ be a Geometric RV with parameter $p$, let $Y$ be a Poisson RV with parameter $\lambda$, and $Z = \max(X,Y)$.
Assume that $X$ and $Y$ are independent.
For each of the following problems, your final answers should not have summations.
You may want to use the Taylor series expansion of $e^x$, that is, that for any $x$,
\[e^x = \sum_{k=0}^\infty \frac{x^k}{k!}\]

\begin{enumerate}[label=\alph*)]

\item What is $\Pr(X > k)$?
(Think about it from first principles.)

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item Compute $\Pr(X > Y)$.
(Consider the Law of Total Probability)
\[\Pr(X > Y) = \sum_{k=0}^\infty \Pr(X > Y \mid Y = k)\cdot \Pr(Y = k).\]

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item Compute $\Pr(Z \ge X)$.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item Compute $\Pr(Z \le Y)$.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\end{enumerate}

\newpage
\section{Round-Robin Tennis (12 points)}

A random number of $N$ tennis players show up for a local round-robin tournament.
To complete the tournament, each player must play exactly one match against every other player.
Thus, a total of $M=\binom{N}{2} = \frac{N(N-1)}{2}$ matches are played.

\medskip
Answer each of the following questions (4 points each).
Make sure that each of your answers are \textbf{not} in the form of a summation.
\textbf{In each case include the expectation and variance of $N$ as part of your answer.}

It may be useful to recall that for any random variable $E(X^2) = \Var(X) + [E(X)]^2$.

\begin{enumerate}[label=\alph*)]

\item What is the expected value of $M$ if $N$ equals some fixed positive integer $c$ with probability 1?
(Some parts of your answer may depend on $c$.)

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item What is the expected value of $M$ if $N$ has a Poisson distribution with parameter $\lambda$?
(Your answer will be a function of $\lambda$.)

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item What is the expected value of $M$ if $N= 10 X + 7$, where $X$ is a Bernoulli random variable with parameter $p$?
(Your answer will be a function of $p$.)

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\end{enumerate}

\newpage
\section{Sample Sampling Algorithm (18 points)}

Consider the following algorithm for generating a random sample $S$ of size $n$ from the set of integers $\{1, 2, \ldots, N\}$, where $0 < n < N$.

\medskip
\noindent\textbf{sample$(N, n)$}

\begin{algorithmic}
\item $S \leftarrow \emptyset$ \hfill // $S$ is a set of distinct integers, initially an empty set
\item \textbf{while} $|S| < n$ \textbf{do}
\item \quad $x \leftarrow$ RollDie($N$) \hfill // $x$ is the outcome of rolling a fair $N$-sided die
\item \quad $S \leftarrow S \cup \{x\}$ \hfill // if $x$ is already in $S$ it doesn't change
\item \textbf{return} $S$
\end{algorithmic}


\medskip
Let $I$ be the number of die rolls until $S$ is returned.
Also, let $I_i$ be the random variable which describes the number of rolls it takes from the time the set $S$ has $i - 1$ values to the first time a new value is added after that (i.e., the set $S$ has $i$ values).

\begin{enumerate}[label=\alph*)]

\item What type of random variable from our zoo is $I_i$ and what is/are the relevant parameter(s) for that random variable?

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item What is $I$ in terms of the random variables $I_i$?
Calculate $\mathbb{E}[I]$, expressing the result as a summation that depends on both $N$ and $n$.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\item What is $\mathrm{Var}(I)$? You can leave your answer in summation form.

\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}

\end{enumerate}

\end{document}