\documentclass[11pt, letter]{article}
\usepackage[inner=1.5cm,outer=1.5cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage{enumitem}
\usepackage[most]{tcolorbox}
\usepackage{amsmath}
\usepackage{hyperref}
\setcounter{section}{-1} 

\begin{document}
    \textbf{Submission instructions are in the homework handout. The handout is the final source of truth for instructions and question statements over this template file, which exists only for your convenience.}

    \section{Collaborators}
    \begin{tcolorbox}
        TODO: Add collaborators here.
    \end{tcolorbox}

    \newpage
    \section{Distribution Description [7 points]}
    Let $X$ be a discrete random variable that takes integer values from 1 to 11 (both inclusive). $X$ has the following cumulative distribution function (CDF):
    $$
    F_X(n) = 
    \begin{cases}
        0 &\mbox{if } n < 1 \\
        \frac{\lfloor(n)\rfloor \cdot \lfloor(n +2)\rfloor}{143} &\mbox{if } 1 \leq n \leq 11 \\
        1 &\mbox{if } n > 11
    \end{cases}
    $$
    Find the probability mass function (PMF) for $X$.
    \begin{tcolorbox}
    
    \begin{enumerate}[label=(\alph*)]
    TODO: Your solution here
    \end{enumerate}
\end{tcolorbox}

    \newpage
    \section{Turnabout is Fair Play [7 points]}
      
      You want to open a casino with a new card game. In the game, a dealer will shuffle a (full) deck of (standard) cards so they are fully-shuffled (i.e. every ordering is equally likely). The dealer then flips over the top three cards. 

      To play, a player pays $\$5$.
      \begin{itemize}
          \item If all three cards are spades, the player gets a payout of $\$20$ (not including the five dollars they already paid)
          \item If exactly two cards are spades, the player gets a payout of $z$
          \item If exactly one of the cards is a spades, the player gets a payout of $\$10$. 
          \item If none of the cards are spades, the player gets no payout.
      \end{itemize}

      You want all the games in your casino to be \textbf{fair games} -- the expected profit (payout minus cost) of your game should be $\$0$.
      What should the value of $z$ be?
      Give your answer as a simplified fraction (don't worry if your number couldn't be paid out with standard U.S. currency)

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

      \newpage
      \section{Play It by Ear [14 points]}
      You have 12 pairs of earrings. 4 pairs are hoops, 5 pairs are studs, and 3 pairs are drops. Both earrings in a pair are identical (i.e., there is no difference between earrings for the left and right ear). However, each pair of earrings has a different design from the others.

      A pair of earrings is ``properly matched'' if they are from the same set. A pair of earrings is ``fashionably mismatched'' if they are from different sets, but from the same type. For instance, 2 earrings from different stud designs are ``fashionably mismatched". However, a stud and a hoop are not. 

      You (uniformly) randomly pair the earrings with each other. In each of these problems clearly define any random variables you need.
      
      \begin{enumerate}[label=(\alph*)]
          \item What is the expected number of pairs of properly matched earrings? [7 points]
          \item What is the expected number of pairs of fashionably mismatched earrings? [7 points]
    \end{enumerate}

    \begin{tcolorbox}
    \begin{enumerate}[label=(\alph*)]
        \item     TODO: Your solution here

        \item     TODO: Your solution here
    \end{enumerate}
    \end{tcolorbox}

    \newpage
    \section{Better Drinks [11 points]}
        You just bought a set of $n$ flavored syrups\footnote{vanilla, french vanilla, peppermint, caramel, hazelnut, pumpkin spice, etc.} to mix into coffee. Since you need the caffeine, but hate the taste of coffee, you mix in exactly four different syrup flavors into your drink.

        Your coffee will taste good only if the four flavors you mix in are pairwise compatible -- that is, if for every pair in the four flavors, those two are compatible. Each pair of flavors is compatible (independently) with probability $p$. What is the expected number of $4$-flavor-combinations that will taste good?
        
         \begin{enumerate}[label=(\alph*)]
             \item Carefully define random variables for this problem. [4 points]
             \item Calculate the expected number of $4$-flavor-combinations that will taste good. [7 points]
        \end{enumerate}

    \begin{tcolorbox}
    \begin{enumerate}[label=(\alph*)]
        \item     TODO: Your solution here

        \item     TODO: Your solution here
    \end{enumerate}
    \end{tcolorbox}

    \newpage
    \section{Geometric Fish, Mon Dieu! [18 points]}
    Let $X$ be Geometric with parameter $p$, let $Y$ be Poisson 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 (3 points) What is $\mathbb{P}(X > k)$? [Think about it from first principles]
    \item (5 points) Compute $\mathbb{P}(X> Y)$. Hint: Use the law of total probability to obtain that $$\mathbb{P}(X > Y) = \sum_{k=0}^\infty \mathbb{P}(X >Y | Y=k)\cdot \mathbb{P}(Y=k).$$ 
    \item (5 points) Compute $\mathbb{P}(Z \ge X)$.
    \item (5 points) Compute $\mathbb{P}(Z \le Y)$.
    \end{enumerate}

    \begin{tcolorbox}
    \begin{enumerate}[label=(\alph*)]
        \item     TODO: Your solution here

        \item     TODO: Your solution here

        \item     TODO: Your solution here

        \item     TODO: Your solution here
    \end{enumerate}
    \end{tcolorbox}

    \newpage
    \section{Animal Crossing: 312 Horizons [16 points]}
    Answer each of the following questions. Make sure that each of your answers is \textbf {not} in the form of a summation for this problem. {\em In each case, include the expectation and variance of $N$ as part of your answer.}\\
    
    \begin{enumerate}[label=(\alph*)]
    \item Let $M = \frac{N^2 - N + 4}{3}$. What is the expected value of $M$ if $N$ equals some fixed positive integer $c$ with probability 1? (Your answer will be a function of $c$.)
    \item  Let $M = \frac{N^2 - N}{3}$. What is the expected value of $M$ if $N$ has a geometric distribution with parameter $p$? (Your answer will be a function of $p$.)
    \item  What is the expected value of $M = \binom{N}{2}$ if $N= 7X + 9$, where $X$ is a Bernoulli random variable with parameter $p$?  (Your answer will be a function of $p$.)
    \item What is the expected value of $M = (N-\frac{1}{2})^2$ if $N = X_1 + X_2 + 2X_3$ where $X_1, X_2, X_3$ are independent Poission random variables with parameters $\lambda_1, \lambda_2, \lambda_3$? (Your answer should be a function of $\lambda_1, \lambda_2, \lambda_3$).
    \end{enumerate}

    \begin{tcolorbox}
    \begin{enumerate}[label=(\alph*)]
        \item     TODO: Your solution here

        \item     TODO: Your solution here

        \item     TODO: Your solution here

        \item     TODO: Your solution here
    \end{enumerate}
    \end{tcolorbox}

\newpage
\section{Bloom Filters [Extra Credit]} 
\textit{The text of this question has been omitted from the template file. Please refer to the actual homework document.}
\begin{enumerate}[label=(\alph*)]
    \item Implement the functions \code{add} and \code{contains} in the \code{BloomFilter} class of  \code{bloom.py}.
    To solve this task, we have set up a corresponding edstem lesson \href{https://edstem.org/us/courses/40645/lessons/66307/slides/363115}{here}. Press the Mark button above the terminal to run the unit tests we have written for you. Passing these unit tests is not enough. We have written a number of different tests for the Gradescope autograder. Your score on Gradescope will be your actual score - you have unlimited attempts to submit.
    
    \item Let's compare this approach to using a typical \code{Set} data structure. Google wants to store 1 million URLs, with each URL taking (on average) 23 bytes. 
    
    \begin{itemize}
    \item How much space (in MB, 1 MB = 1 million bytes) is required if we store all the elements in a set?
    \item How much space (in MB) is required if we store all the elements in a Bloom filter with $k=10$ hash functions and $m=800,000$ buckets? Recall that 1 byte = 8 bits. 
    \end{itemize}
    
    \item Let's analyze the time improvement as well. Let's say an average Chrome user attempts to visit 36,500 URLs in a year, only 1,000 of which are actually malicious. Suppose it takes half a second for Chrome to make a call to the database (the \code{Set}), and only 1 millisecond for Chrome to check containment in the Bloom filter. Suppose the false positive rate on the Bloom filter is $4\%$; that is, if a website is not malicious, the Bloom filter will incorrectly report it as malicious with probability $0.04$. What is the time (in seconds) taken if we only use the database, and what is the \textit{expected} time taken (in seconds) to check all 36,500 strings if we used the Bloom filter + database combination described earlier?
\end{enumerate}

\begin{tcolorbox}
    \begin{enumerate}[label=(\alph*)]
        \item     Submit code to Gradescope.

        \item     TODO: Your solution here

        \item     TODO: Your solution here
    \end{enumerate}
    \end{tcolorbox}

\end{document}