% LaTeX handouts by Will Monroe
% Based on B. E. Burr's CS 109 problem set template

\documentclass[12pt]{article}

% -----------------------------------
% USE FOR SETTING FLAG
\usepackage{etoolbox}

\providetoggle{soln}
\settoggle{soln}{false}
% -----------------------------------

\usepackage{newtxtext,newtxmath}
\usepackage{xcolor}
\usepackage{amsmath}
\usepackage{amssymb}
	% packages that allow mathematical formatting
\usepackage{comment}
  % comment out sections

\usepackage{graphicx}
\usepackage{float}
\usepackage{subfigure}


\usepackage{tikz}
	% package that allows you to include graphics

\usepackage[hidelinks]{hyperref}
	% and links
\usepackage{algpseudocode}
  % and algorithms
\usepackage{minted}
	% and code

\usepackage[tmargin=0.5in,bmargin=0.5in,lmargin=0.5in,rmargin=0.5in]{geometry}
\frenchspacing
	% one space after periods
\raggedbottom
	% don't put extra space between sections

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\setlength{\headheight}{14.5pt}
	% allows custom headers

\lhead{}
\rhead{}
\cfoot{}
	% page numbering

\usepackage{titlesec}
\titleformat*{\section}{\large\bfseries}
\titleformat*{\subsection}{\large\bfseries}
\titleformat*{\subsubsection}{\normalsize\bfseries}
\titleformat*{\paragraph}{\normalsize\bfseries}
\titleformat*{\subparagraph}{\normalsize\bfseries}
\setlength{\parindent}{0cm}
\setlength{\parskip}{3mm plus 3mm minus 1mm}
\titlespacing*{\section}{0pt}{2mm plus 4mm minus 1mm}{-2mm plus 1mm minus 0mm}
\titlespacing*{\subsection}{0pt}{0mm plus 4mm minus 1mm}{-2mm plus 1mm minus 0mm}
\titlespacing*{\subsubsection}{0pt}{0mm plus 4mm minus 1mm}{-2mm plus 1mm minus 0mm}
\titlespacing*{\paragraph}{0pt}{0mm plus 3mm minus 1mm}{1mm plus 1mm minus 0mm}
  % adjust fonts and spacing

\usepackage[document]{ragged2e}
\usepackage{framed}
\definecolor{shadecolor}{rgb}{0.90,0.90,0.90}
\begin{comment}
\newenvironment{framed}
    {
    \hspace*{-3mm}
    \begin{tabular}{|p{\textwidth}|}
    \hline
    }
    {
    \\[2mm]\hline
    \end{tabular}
    \vspace*{-2mm}
    }
  % boxes around paragraphs with titles
\end{comment}

\usepackage{textpos}
\usepackage[super]{nth}
\usepackage{mathtools}
\usepackage{mathdots}

\usepackage{textcomp}
  % \textonehalf for '8 1/2" x 11"'

\usepackage{enumitem}
% \setlist{nolistsep}
  % configure display of enumerations [a), b), c)...]
\usepackage[normalem]{ulem}
  % \sout{} for strikethrough
\usepackage{booktabs}
\usepackage{diagbox}
  % configure display of tables

\newcommand{\vocab}[1]{\textbf{#1}}
\renewcommand{\|}{\mid}

\newcommand{\ra}[1]{\renewcommand{\arraystretch}{#1}}
\newcommand\tab[1][1cm]{\hspace*{#1}}
\newcommand\tabhead[1]{\small\textbf{#1}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\E}{E}
\newcommand{\Var}{\operatorname{Var}}
\newcommand{\SD}{\operatorname{SD}}
\newcommand{\Cov}{\operatorname{Cov}}
\newcommand{\bigO}{O}

\newcommand{\Uni}{\operatorname{Uni}}
\newcommand{\Ber}{\operatorname{Ber}}
\newcommand{\Bin}{\operatorname{Bin}}
\newcommand{\Geo}{\operatorname{Geo}}
\newcommand{\NegBin}{\operatorname{NegBin}}
\newcommand{\Zipf}{\operatorname{Zipf}}
\newcommand{\HypG}{\operatorname{HypG}}
\newcommand{\Poi}{\operatorname{Poi}}
\newcommand{\Beta}{\operatorname{Beta}}
\newcommand{\N}{\operatorname{N}}
\newcommand{\Exp}{\operatorname{Exp}}

\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}

\makeatletter
\newcommand{\ack}[1]{\def \@ack {#1}}
\newcommand{\handoutid}[1]{\def \@handoutid {#1}}
\newcommand{\spaceadjust}[1]{\def \@spaceadjust {#1}}
\makeatother

\ack{Problems by Tim Gianitsos, Alex Tsun, and Jerry Cain}
\handoutid{}
\spaceadjust{0mm}

\title{Section  01: Analytic Probability}
\handoutid{Section 01}

\author{Jerry Cain,  Chris Piech}
\date{January 19, 2021}

\begin{document}

\makeatletter
% the handout title goes here
\begin{textblock*}{0.5\textwidth}(0\textwidth,0mm)
\@author
\end{textblock*}

\begin{textblock*}{0.5\textwidth}(0\textwidth,5mm)
CS109
\end{textblock*}

\begin{textblock*}{0.5\textwidth}(.5\textwidth,0mm)
\hfill
\@handoutid
\end{textblock*}

\begin{textblock*}{0.5\textwidth}(.5\textwidth,5mm)
\hfill
\@date
\end{textblock*}

\begin{center}
\vspace*{2mm}
{\Large \@title} \\
\end{center}
\vskip -9mm
\vskip \@spaceadjust
\rule{\textwidth}{0.5pt}

\vspace*{-4mm}
\hfill {\footnotesize \@ack}
\makeatother

\section*{Overview of Section Materials}
The warmup questions provided will help students practice concepts introduced in lectures. The section problems are meant to apply these concepts in more complex scenarios similar to what you will see in problem sets and quizzes.

\section{Warmups}
\vspace{2mm}
\subsection{Lecture 1: Counting}
\vspace{2mm}
The Inclusion Exclusion Principle for three sets is: $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
Explain why in terms of a venn-diagram.
\begin{center}\includegraphics[width=0.25\textwidth]{iu.png}\end{center}

\iftoggle{soln}{
\begin{shaded}
We want a, b, c, d, e, f, \& g to each be accounted for exactly once. If we add A, B, and C together, we properly count a, b, \& c exactly once. However we will double count d, e, \& f, and triple count g. Removing $A \cap B$, $A \cap C$, \& $B \cap C$ will reduce the counts for d, e, \& f down to one. However, g went from being counted 3 times too many to being counted zero times. The expression corresponding to g is $A \cap B \cap C$, so we add it in to allow g to have a count of exactly one.
\end{shaded}
}

\subsection{Lecture 2 Warmup: Permutations and Combinations}
\vspace{2mm}
Suppose there are 7 blue fish, 4 red fish, and 8 green fish in a large fishing
tank. You drop a net into it and end up with 6 fish. What is the probability you
get 2 of each color?

\iftoggle{soln}{
\begin{shaded}
For our event space, we consider the number of ways we can select 2 of then 7 blue fish, independently select 2 of the 4 red fish, and independently choose 2 of the 8 green fish. For the full sample space, we consider the number of ways we can select a 6 fish from all 19 fish without regard for blue, red, or green. Therefore:\\
$$p = \frac{\binom{7}{2}\binom{4}{2}\binom{8}{2}}{\binom{19}{6}}$$
\end{shaded}
}

\subsection{Lecture 3 Warmup: Axioms of Probability}
\vspace{2mm}
Decide whether each of the three statements below is true or false.
\begin{center}
\begin{tabular}{ c c c }
 $P(A) + P(A^C) = 1$, & $P(A \cap B) + P(A \cap B^C) = 1$,
  & $P(A) = 0.4 \land P(B) = 0.6 \implies A = B^C$
\end{tabular}
\end{center}

\iftoggle{soln}{
\begin{shaded}
\begin{center}
\begin{tabular}{ c c c }
 T & F & F
\end{tabular}
\end{center}
The first one is simply saying that an event either falls inside of an event space $A$ or outside of it. The second is false, as the left hand side, in general, is $P(A)$, which isn't guaranteed to be 1. And the fact that $P(A)$ and $P(B^C)$ are each $0.4$ doesn't require the event spaces to be the same.
\end{shaded}
}

\section{Problems}
\vspace{2mm}
\subsection{Lecture 1 Generative Processes: The Birthday Problem}
\vspace{2mm}
When solving a counting problem, it can often be useful to come up with a generative process, a series of steps that ``generates" examples. A correct generative process to count the elements of set $A$ will (1) \textit{generate every element of $A$} and (2) \textit{not generate any element of $A$ more than once}. If our process has the added property that (3) \textit{any given step always has the same number of possible outcomes}, then we can use the product rule of counting.

\textbf{Example: }Say we want to count the number of ways to roll two (distinct) dice where one die is even and one die is odd. Our process could be: (1) roll the first die and note if the value is even or odd, then (2) count the number of ways the second die can be rolled for a value of the opposite parity. Since the first step has 6 options and the second step has 3 options regardless of the outcome of the first step, the number of possibilities is $6*3 = 18$.

\textbf{Problem: }Assume that birthdays happen on any of the 365 days of the year with equal likelihood (we'll ignore leap years).
 \begin{enumerate}[label=\alph*.]
\item What is the probability that of the $n$ people in class, at least two people share the same birthday?

\iftoggle{soln}{
\begin{shaded}
It is much easier to calculate the probability that no one shares a birthday. Let our sample space, $S$ be the set of all possible assignments of birthdays to the students in section. By the assumptions of this problem, each of those assignments is equally likely, so this is a good choice of sample space. We can use the product rule of counting to calculate $|S|$:
\begin{align*}
   & |S| = (365)^n
 \end{align*}
Our event $E$ will be the set of assignments in which there are no matches (i.e. everyone has a different birthday). We can think of this as a generative process where there are 365 choices of birthdays for the first student, 364 for the second (since it can't be the same birthday as the first student), and so on. Verify for yourself that this process satisfies the three conditions listed above. We can then use the product rule of counting:
\begin{align*}
   & |E| = (365) \cdot (364)\cdot \dots \cdot(365 - n + 1)
\end{align*}
\begin{align*}
    P(\text{birthday match}) &= 1 - P(\text{no matches}) \\
&= 1 - \frac{|E|}{|S|}\\
& = 1 - \frac{(365) \cdot (364) \dots (365 - n + 1)}{(365)^n}
\end{align*}

A common misconception is that the size of the event $E$ can be computed as $|E|={365 \choose n}$ by choosing $n$ distinct birthdays from $365$ options. However, outcomes in this event ($n$ unordered distinct dates) cannot recreate any outcomes in the sample space $|S|=365^n$ ($n$ distinct dates, one for each distinct person). However if we compute the size of event $E$ as $|E|={365 \choose n} n!$ (equivalent to the number above), then we can assign the $n$ birthdays to each person in a way consistent with the sample space.

Interesting values: $(n=13: p\approx 0.19)$, $(n=23: p\approx 0.5)$, $(n=70:p\geq  0.99)$.
\end{shaded}
}

\item What is the probability that this class contains exactly one pair of people who share a birthday?
\end{enumerate}

\iftoggle{soln}{
\begin{shaded}
We can use the same sample space, but our event is a little bit trickier. Now $E$ is the set of birthday assignments in which exactly two students share a birthday and the rest have different birthdays. One generative process that works for this is (1) choose the two students who share a birthday, (2) choose $n - 1$ birthdays in the same manner as in part a (i.e. one for the pair of students and one for each of the remaining students). We then have:
$$P(\text{exactly one match}) = \frac{|E|}{|S|} = \frac{{n \choose 2}(365)\cdot (364)\cdot...\cdot(365 - n + 2)}{(365)^n}$$
Many other generative processes work for this problem. Try to think of some other ones and make sure you get the same answer!

\end{shaded}
}

\subsection{Lecture 2: Flipping Coins}
\vspace{2mm}
One thing that students often find tricky when learning combinatorics is how to figure out when a problem involves permutations and when it involves combinations. Naturally, we will look at a problem that can be solved with both approaches. Pay attention to what parts of your solution represent distinct objects and what parts represent indistinct objects.

\textbf{Problem: }We flip a fair coin $n$ times, hoping (for some reason) to get $k$ heads.
\begin{enumerate}[label=\alph*.]
\item How many ways are there to get exactly $k$ heads? Characterize your answer as a \textit{permutation} of H's and T's.

\iftoggle{soln}{
\begin{shaded}
We want to know the number of sequences of $n$ H's and T's such that there are $k$ H's and $n - k$ T's. This is the same as permuting $n$ objects of which one set of $k$ is indistinguishable and one set of $n - k$ is indistinguishable. Using our formula for the permutation of indistinguishable objects, we get $\frac{n!}{k!(n - k)!}$
\end{shaded}
}

\item For what $x$ and $y$ is your answer to part a equal to ${x \choose y}$? Why does this \textit{combination} make sense as an answer?
\iftoggle{soln}{
\begin{shaded}
Our answer to part a is equal to ${n \choose k}$. This makes sense because we can come up with a valid sequence by \textit{choosing} $k$ flips to come out to heads (and implicitly define the other $n - k$ to be tails). The answer is also equivalent to ${n \choose n - k}$ for which the same logic applies except with choosing flips to be tails.
\end{shaded}
}

\item What is the probability that we get exactly $k$ heads?
\iftoggle{soln}{
\begin{shaded}
If we define our sample space to be all possible sequences of flips, then our event is the number of sequences where we get exactly $k$ heads, meaning that $|E|$ is (conveniently) the answer to the previous two parts. Our probability is then $\frac{|E|}{|S|} = \frac{{n \choose k}}{2^n}$.
\end{shaded}
}

\end{enumerate}
\subsection{Lecture 2: Combinatorial Proofs}
\vspace{2mm}
\textbf{Example: }Prove why ${n \choose k} = {n \choose n - k}$. 
\begin{shaded}
A fully algebraic proof is possible by simply showing the left hand side is equivalent to the right, as with: \\
\begin{align*}
    {n \choose n - k} = \frac{n!}{(n - k)!(n - (n - k))!} = \frac{n!}{(n - k)!((n - n) + k)!} = \frac{n!}{(n - k)!k!} = {n \choose k}
\end{align*}
An equally compelling proof is a combinatorial one, which relies on our ability to describe the counting problem in two, equivalent ways. In this case, we can simply say the above is true because choosing $k$ items from a set of $n$ items is equivalent to choosing the $n - k$ items to be excluded.  These types of proofs are called \textbf{combinatorial proofs}, or \textbf{story proofs}.
\end{shaded}

\begin{enumerate}[label=\alph*.]
\item Present a combinatorial proof arguing that ${r \choose m}{m \choose k} = {r \choose k}{r - k \choose m - k}$.
\iftoggle{soln}{
\begin{shaded}
\textit{We'll contrive a college admissions backstory for our combinatorial proof.} \\
The left hand side count the number of ways we can admit $m$ applicants from a pool of $r$ applications, and then from those $m$ admits choose $k$ to receive a full academic scholarship. The right hand side counts the same set of possibilities by choosing the $k$ applicants to admit \textit{and} award a full scholarship and then choosing $m - k$ other applicants from the remaining $r - k$ to round out the full set of $m$ admitted students.  This can also be proved algebraically, but the above argument is much more illuminating and would be considered a valid proof unless the problem specifically asked for a strictly mathematical one.
\end{shaded}
}

\item Present a combinatorial proof arguing that $\sum_{k}{{r \choose m + k}{s \choose n - k}} = {r + s \choose m + n}$ for all integer values of $k$, assuming $r$, $s$, $m$, and $n$ are integer constants.
\iftoggle{soln}{
\begin{shaded}
The right hand side counts the number of ways we can choose a total of $m + n$ items from two sets of size $r$ and $s$. The left hand side counts the number of ways one can select $m + k$ items from the first set and the remaining $n - k$ items from the second set, so that the total number of selected items is still $m + n$.  This combinatoric identity, as it turns out, is related to the idea of a convolution, and we'll study them more in a few weeks.
\end{shaded}
}

\end{enumerate}

\end{document}