\documentclass[letterpaper,11pt]{article}
\newcommand{\removefromfile}[1]{}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage[most]{tcolorbox}
\begin{document}
\title{{\bf Problem Set 4 Solutions} }
\author{Name: TODO}
\date{}
\maketitle
\section*{Collaborators}
TODO: List collaborators, if any.
\newpage
\section*{Problem 1 (More Heads than Tails?) Solution}
Let $X$ represent the difference between the number of heads and
the number of tails obtained when a coin with probability 0.6 of coming up Heads is tossed
independently $200$ times.
\begin{enumerate}
\item (5 points) What are the possible values of $X$?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item (5 points) What is the probability that $X=4$?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}
\noindent (Note: $X = H - T$, not $X = |H - T|$, where $H$ is the number of head and $T$ is the number of tails. That is, if you have more tails than heads, then the difference is negative, not positive.)
\newpage
\section*{Problem 2 (Busy 312 Students) Solution}
CSE 312 students sometimes delay laundry for a few days (to the chagrin of their roommates).
\noindent Suppose a {\bf\em busy} 312 student must complete 3 problem sets before doing laundry. Each problem set requires 1 day with probability 2/3 and 2 days with probability 1/3. (The time it takes to complete different problem sets is independent.) Let $B$ be the number
of days a busy student delays laundry. What is the probability mass function for $B$?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\newpage
\section*{Problem 3 (CDF to PMF) Solution}
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 \lfloor x+1 \rfloor}{10100} \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(1) = 1\cdot 2/10100$ and $F(2) = 2 \cdot 3/10100$ and so on. Also note that the $\lfloor x \rfloor$ (floor of $x$) is the largest integer less than or equal to $x$.)
\noindent 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\}$.
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\newpage
\section*{Problem 4 (Investment Strategies) Solution}
Consider three different investment strategies.
\begin{enumerate}
\item[1.] You buy one share in each of $n$ different stocks. Each share of a different stock ``pays off'' independently with probability $p$;
\item[2.] You buy $n$ shares of the same stock. A share of that stock pays off with probability $p$. Since all the shares are of the same stock, either all of them pay off (probability $p$) or none of them pay off.
\item[3.] You buy $n/2$ shares of stock $A$ and $n/2$ shares of stock $B$. A share of stock $A$ and a share of stock $B$ each independently pay off with probability $p$. All shares of the same stock either all pay off (probability $p$) or none of them pay off (probability $1-p$).
\end{enumerate}
Let $X_i$ be the number of shares that pay off in strategy $i$, for $i = 1, 2, 3$. Write down the probability mass function, the expectation of $X_i$ and the variance of $X_i$ when ...
\begin{enumerate}
\item (6 points) $i = 1$
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item (6 points) $i = 2$
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\item (6 points) $i = 3$
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}
\newpage
\section*{Problem 5 (Triple fun) Solution}
A \emph{complete graph on
$n$ vertices} has a set $V$ of vertices with $|V|=n$ and a set $E$ of $n \choose 2$ \emph{edges}, one edge for each pair of elements of $V$. The graph is denoted by $K_n$. Suppose that we independently flip fair coins, one per edge of $K_n$, and color each edge \emph{red}
if its coin is heads and \emph{blue} if the coin is tails.
What is the expected number of \emph{triangles} (unordered triples of vertices) that have their edges colored the same (all blue or all red)?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\newpage
\section*{Problem 6 (Lefties and righties) Solution}
Suppose that there are 250 students taking CSE 312 and they are partitioned into pairs at random to work together on the problem set, with each partition being equally likely. If the class has 200 people that are right-handed and 50 people that are left-handed, what is the expected number of pairs that are different-handed, that is pairs where one person in the pair is left-handed and the other person in the pair is right handed?
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\newpage
\section*{Problem 7 (Runs in a Sequence of Coin Flips) Solution}
A coin with probability $p$ of coming up heads is tossed independently $n$ times. What is the
expected number of maximal ``run'', where a maximal ``run'' is a maximal sequence of consecutive flips that are the same? For example, the sequence HHHTTHTHHH has 5 maximal runs: HHH, TT, H, T, and HHH. Use linearity of expectation, carefully define indicator rvs, and justify your work.
\begin{tcolorbox}
TODO: Your solution here.
\end{tcolorbox}
\newpage
\section*{Problem 8 (For Fun Problem - only if you're interested) Solution}
\textbf{This is a not-too-difficult challenge problem for those of you that would enjoy proving a cool probabilistic fact. You will not be turning anything in for this. It's just for fun.}
\noindent You are shown two envelopes and told the following facts:
\begin{itemize}
\item Each envelope has some number of dollars in it, but you don't know how many.
\item The amount in the first envelope is different from the amount in
the second.
\item Although you don't know exactly how much money is in each envelope, you are told that it is an integer number of dollars that is at least 1 and at most 100.
\item You are told that you can pick an envelope, look inside, and then you will be given a one-time option to switch envelopes (without looking inside the new envelope). You will then be allowed to keep the money in envelope you end up with.
\end{itemize}
\noindent Your strategy is the following:
\begin{enumerate}
\item You pick an envelope uniformly at random.
\item You open it and count the amount of money inside. Say the result is $x$.
\item You then select an integer $y$ between 1 and 100 uniformly at random.
\item If $y > x$, you switch envelopes, otherwise you stay with the envelope you picked in step (a)
\end{enumerate}
Show that you have a better than 50-50 chance of taking home the envelope with the larger amount of money in it. More specifically, suppose the two envelopes have $i$ and $j$ dollars in them respectively, where $i < j$.
Calculate the probability that you take home the envelope with the larger amount of money.
\begin{tcolorbox}
Optional: Nothing to write for this question
\end{tcolorbox}
\end{document}