\documentclass[letterpaper,11pt]{article}
\newcommand{\removefromfile}[1]{}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage[legalpaper, portrait, margin=1in]{geometry}
\begin{document}
\title{{\bf Problem Set 4 Solutions} }
\author{insert your name here}
\date{}
\maketitle
\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 fair coin is tossed
independently $100$ times. What are the possible values of $X$? What
is the probability that $X=4$? (Note: $X = H - T$, not $X = |H - T|$. That is, if you have more tails than heads, then the difference is negative, not positive.)\\
\newline
\textbf{Solution:}
\newpage
\section*{Problem 2 (Busy 312 Students) Solution}
CSE 312 students sometimes delay laundry for a few days (to the chagrin of their roommates).\\
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$?\\
\newline
\textbf{Solution:}
\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.)\\
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\}$.\\
\newline
\textbf{Solution:}
\newpage
\section*{Problem 4 (Fair Game) Solution}
Consider the following game, defined by a parameter $k$: Roll a fair, 6-sided die three times independently. If you roll a six
\begin{itemize}
\item no times, then you lose 1 dollar.
\item exactly once, you win 1 dollar.
\item exactly twice, then you win 2 dollars.
\item all three times, then you win $k$ dollars
\end{itemize}
For what value of $k$ is this game fair? (The game is fair if your expected payoff is 0.)\\
\newline
\textbf{Solution:}
\newpage
\section*{Problem 5 (Packet Failures) Solution}
Consider three different models for sending $n$ packets over the Internet:\\
\begin{enumerate}
\item[1.] each packet takes a different path. Each path fails independently with probability p;
\item[2.] all packets take the exact same path which fails with probability p. Thus, either all the packets get through or none get through;
\item[3.] half the packets take one path, and half take the other (assume n 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$.\\
\newline
\textbf{Solution:}
\newpage
\section*{Problem 6 (Doggies and Koalas) Solution}
Suppose that $4n$ animals are partitioned into pairs at random, with each partition being equally likely. If the set consists of $n$ doggies and $3n$ koalas, what is the expected number of doggie-koala couples?\\
\newline
\textbf{Solution:}
\newpage
\section*{Problem 7 (Friends) Solution}
Consider a group of $n$ people where each pair of people is friends independently with probability $1/2$. What is the expected number of triples of people that are all friends, i.e. triples $A,B,C$ such that $A$ is friends with $B$ and $B$ is friends with $C$ and $A$ is friends with $C$. Use linearity of expectation and carefully define indicator random variables (0/1 valued random variables) and justify your work.\\
\newline
\textbf{Solution:}
\newpage
\section*{Problem 8 (More Coin Flipping) Solution}
A coin with probability $p$ of coming up heads is tossed independently $n$ times. What is the expected number of maximal "runs", where a "run" is a maximal sequence of consecutive flips that are the same? For example, the sequence HHHTTHTHHH has 5 runs, the first three H, the following two T, and so on. Use linearity of expectation and carefully define indicator rvs and justify your work.\\
\newline
\textbf{Solution:}
\newpage
\section*{Problem 10 (Extra Credit Problem) Solution [OPTIONAL]}
Full spec in pset problem.\\
\newline
\textbf{Solution:}
\newpage
\end{document}