\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}}
\begin{document}
\title{{\bf Problem Set 4 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 Problems (34 points)}
\begin{tcolorbox}
    Nothing to write for this question.
\end{tcolorbox}

\newpage
\section{CDF to PMF (10 points)}
Suppose that $X$ is a discrete random variable that takes integer values from 1 to 100 (both inclusive), and has cumulative distribution function (CDF) 
\[ F_X (x)=\Pr(X \le x) = \frac{\lfloor x \rfloor^2}{10000} \quad\quad  1 \le x \le 100 \]
and 
\[ F_X(x) = 0 \quad\text{ for }x < 1\quad\text{ and }\quad F_X(x) = 1 \quad \text{ for }x > 100 \]
(Thus, for example, $F_X(1) = 1/10000$ and $F_X(2) = 4/10000$ and so on. Also note that the $\lfloor x \rfloor$ (floor of $x$) is the largest integer less than or equal to $x$.)

Find the probability mass function (pmf) for $X$.
In other words, provide a formula for $p_X(x)$ that is correct for any integer $x$ in $\{1, 2, \ldots, 100\}$. Simplify it as much as possible.
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

\newpage

\section{Just double your bet! (12 points)}

You go to a casino and make a bet that pays 1:1.
In other words, if you bet \$$n$, then with probability 1/2 you win \$$n$ dollars (i.e., you came into the casino with \$$n$ and leave with \$2$n$).
If you lose the bet (which happens with probability 1/2), you lose the \$$n$ that you originally bet.
\begin{enumerate}[label=\alph*)]
    \item (2 points) What is your expected payoff for this wager (money earned - money spent)?
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}

    You decide to try out the following \textbf{"Doubling Strategy"}. 
    You bet \$1. If you win, you walk away. If you lose, you bet again, doubling your bet.
    You continue doing this until you win.

    \item (1 point)
    Let $X$ be the number of rounds until you win. What is $\Omega_X$?
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
    
    \item (4 points)
    Let $g(k)$ be your payoff (earnings - money spent on the bets) if you win on the $k$-th round . What is $g(k)$?
    (You may use the fact that $\sum_{j=0}^{k-1} 2^j = 2^k - 1$.)
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
    
    \item (3 points) What is $\mathbb{E}[g(X)]$?
    You may find the following formula useful:
    \[\sum_{k=0}^\infty a^k = \frac{1}{1-a}\]
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
    
    \item (2 points) As you will find, using the above strategy, your expected payoff is strictly positive.
    Why doesn't this work in real life?
    \begin{tcolorbox}
        TODO: Your solution here.
    \end{tcolorbox}
\end{enumerate}

\newpage
\section{Packet Failures (18 points)}

Consider three different models for sending $n$ packets over the Internet:
\begin{enumerate}[label=\alph*)]
    \item (6 points) each packet takes a different path.
    Each path fails independently with probability $p$; 
    \item (6 points) all packets take the exact same path which fails with probability $p$.
    Thus, either all the packets get through or none get through;
    \item (6 points) half the packets take one path, and half take the other (assume $n$ is even), and each of the two paths fails independently with probability $p$.
\end{enumerate}
Let $X_i$ be the number of packets lost in case $i$, for $i = 1, 2, 3$.
Write down the probability mass function, the expectation of $X_i$, and the variance of $X_i$ for $i = 1, 2, 3$.
\begin{enumerate}[label=\alph*)]
    \item (6 points) each packet takes a different path.
    Each path fails independently with probability $p$.
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}
    \item (6 points) all packets take the exact same path which fails with probability $p$.
    Thus, either all the packets get through or none get through.
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}
    \item (6 points) half the packets take one path, and half take the other (assume $n$ is even), and each of the two paths fails independently with probability $p$.
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}

\newpage
\section{Coin tossing fun (12 points)}
A group of $n$ friends get together for a party.
Each person tosses a fair coin independently. Say that a triple, i.e., a group of 3 people, is a ``mixed" triple if at least one of their coins came up heads and at least one came up tails.
What is the expected number of mixed triples at the party?
So, for example, if $n=4$, and A's toss came up heads, B's toss came up heads, C's toss came up tails and D's toss came up heads, then the mixed triples are ABC, BCD, ACD.
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

\newpage
\section{Tennis Tournament (10 points)}
     Consider a tennis tournament in which each of the $n$ people participating plays a match against every other person participating.
(So there are $\binom{n}{2}$ matches.)
     Suppose that every match is equally likely to be won by either player, and the outcomes of different matches are independent.
For a fixed permutation $\pi = (\pi_1, \pi_2, \pi_3, ..., \pi_n)$  of the $n$ people, we say that ``$\pi$ is ordered" if person $\pi_1$ wins their match against person $\pi_2$, and person $\pi_2$ wins their match against person $\pi_3$ and person $\pi_3$ wins their match against person $\pi_4$ and so on.
What is the expected number of ``ordered" permutations (see definition above for ``ordered" permutations)?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

\end{document}
