Janet_additions.tex

Cards in a deck: 52.  \hfill \\
Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King \hfill \\

\section{Problem solving tips}
Recognize complicated versions of simple formulas.  E.g. $P(A \mid B) = P(A \cap B)/P(B)$ with an $A$ or $B$ like $(A \cup B^c)$ \hfill \\
\textbf{At least} is a trigger for 1 $-$ probability of all items.  E.g. probability you will roll at least one 6 in 3 die rolls $= 1 - P(\mbox{no 6s rolled}) = 1 - (5/6)^3$. 


\section{Probability Formulas}
\smallskip \hrule height 2pt \smallskip

\begin{description}
	\item[Misc.] 
		\begin{align*}
		\Phi &= \Omega^c   \mbox{\tiny{(Lecture 4)}}  \\
		\cap E_i &= (\cup E_i^c)^c       \mbox{\tiny{(Lecture 4)}}  \\
		%\[ A \cup A^{c} =U  \]
		%\[ A \cap A^{c} =\Omega  \]
		A \cup A^{c} &= \Phi  
		\end{align*}

		
		\textbf{DeMorgan's laws}, pg 26:  You can distribute/factor a complement if you switch the $\cup$ or $\cap$ \\
		\[  (A \cup B)^c = A^c \cap B^c  \]
		\begin{center} \tiny{so $P((A \cup B)^c) = P(A^c \cap B^c)$}   \end{center}  
		\[   (A \cap B)^c = A^c \cup B^c  \]
		
		Goal: you have one complement in your "and" space and don't want it.  $A \cap B^c = A -(A \cap B)$  Use Venn diagrams to see.   (in pg 37 proof)
		
		What about $A \cup B^c$?  ???
		\hfill \\
		\begin{align*}
		P(A \cap B) + P(A^c \cap B) &= P(B)  \mbox{   \tiny{(in prob 2.4.5 pg 37)}}   \\
		P(A \cup B) + P(A^c \cup B) &= 1  \mbox{   \tiny{(logically b/c $P(A) + P(A^c) = 1$}}  \\
		\end{align*}
		
\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Mutually exclusive and/or exhaustive}
    \begin{description}
    
    	\item[Mutually exclusive] ${E_1}, {E_2}$ are \textit{mutually exclusive} if 
        		$P({E_1} \cup {E_2} \cup {E_3} \cup ...) = P({E_1}) + P({E_2}) + P({E_3}) + ...$   \\
		%\begin{flushright} \tiny{(Lec 2, L\&M 2.3)} \end{flushright}
		{ \tiny (Lec 2, L\&M 2.3)}.   \\
		Note that then $ P(E_i \cap E_j) = 0 $
    
    
    	\item[Mutually exclusive and exhaustive] 
	\[ \mbox{For } E_1, E_2, \dots:  \]
	\[ E_i \cap E_j = \Phi \mbox{, } P(E_i \cap E_j) = 0 \mbox{, and } \Omega = E_1 \cup E_2 \cup \dots \]
	\[ \mbox{ Mutually exclusive + exhaustive = partition } \]
    \end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%    
\subsection{The fundamental laws of set algebra} {\tiny (Wikipedia)}

	\textbf{Commutative Laws}
		\begin{align*}
			A \cup B = B \cup A   \\
			A \cap B = B \cap A   \\
		\end{align*}
     \textbf{Associative Laws}
		\begin{align*}
			(A \cup B) \cup C = A \cup (B \cup C) \\
			(A \cap B) \cap C = A \cap (B \cap C) \\
		\end{align*}
	\textbf{Distributive laws}
		\[ A \cup (B \cap C) = (A \cup B) \cap (A \cup C)   \]
		\[ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \]
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%			
	
\subsection{Basic probability formulae}
           \begin{gather*} 
        		\Omega = E \cup E^c \\
        		E \cap E^c = \Phi \\
      		\mbox{ so }  P(E^c) + P(E) = P(\Omega) = 1, or P(E^c) = 1-P(E) \\
        		\mbox{ and} P(D)  \leq 1 \mbox{, since all probabilities are non-negative} \\
           E \cup F = E \cup (E^c \cap F)  \\
            \mbox{and E and $E^c$ are disjoint, so you can break them apart} \\            
           P(E \cup F) = P(E) + P(E^c) \cap F \\
           \mbox{so } P(E \cup F) + P(E \cap F) =  \\ P(E) + P(E^c \cap F) + P(E \cap F) = P(E) + P(F) \\
           \mbox{restated: } P(E \cup F) + P(E \cap F) = P(E) + P(F) \\
           \end{gather*}  
    
\begin{description}
\item[Law of total probability] See Lec2, L\&M 2.3 \newline
For events E, F of a partition, you can build F or P(F) from the overlaps of the events E with P.
	\[ F = U_i(F \cap E_i)  \]
	\[ P(F) = \sum_{n=1} P(F \cap E_i) \]
Special case: If $E_i$ is the \textit{i}th outcome in a countable $\Omega$, $F \cap E_i = Ei$ 
or $F \cap E_i = \Phi$ and $P(F) = \sum_{i \in F} P(E_i)$.  \hfill \\
\hfill \\

\item[The inclusion and exclusion formula] (The overlapping tiles sum)
If you want to get the $\cup$ of some events, sum all the areas, subtract out the singly over lapping bits, add back the tripply overlapping bits, subtract off the quadruply overlapping bits, etc.  Go as far as the number of Es you have. 
All cups on the left side and caps on the right. 
	\[\mbox{2 items: } P(D \cup E) = P(D) + P(E) - P(D \cap E) \]
	\begin{align*}
	\mbox{3 items: }   
	P(C \cup D \cup E) = P(C) + P(D) + P(E) \\
	\quad - P(C \cap D) - P(D \cap E) - P(E \cap C) \\
	\quad + P(C \cap D \cap E) \\
	\end{align*}

\item[Review ways of breaking apart $\cup$ \& and $\cap$] \hfill \\

 You can relate cap and cup {\tiny by Theorem 2.3.6 (pg 28)}:
$P(A \cup B) = P(A) + P(B) - P(A \cup B)$, which can be re-arranged.  \hfill \\
\hfill \\
$\cup$ covers two areas.  If they are independent you can separate them with pluses.  If you know about their $\cap$ you can deduce their $\cup$.  \hfill \\
\hfill \\
$\cap$ is the

\end{description}

%%%%%%%%%%%%%%%%%%%%%
\section{Conditional probability}
\smallskip \hrule height 2pt \smallskip

\begin{description}
\item[Relating conditional probability \& intersection]     L\&M pg 34, L5. \hfill \\
If P(B) \textgreater 0:
	\begin{align*}
		P(A \mid B) = \frac{ P(A \cap B) }{ P(B) }   \hfill \\
	\end{align*}
How to remember if you got the $\mid$ and $\cap$ in the right order: visualize the and inside the circle.

\hfill \\
This gives you a way to relate intersections and conditional probabilities:
$P(A \cap B) = P(A \mid B)P(B)$  (pg. 34)

\item[Some more tricks]
	%\begin{align*}
	Recognize the relation between $A \cup B$  and $A \cap B$ even if there is something like $(A \cup B) \cap (A \cup B)^c$.  You can pull the c inside and write the $P(A) + P(B)$ type statement.
	%\end{align*}
	
\item[A+B and A-B without P involved]
Generally avoid adding sets.  Adding and subtracting probability of sets is great though. \hfill \\
With that warning, The definition of $A-B$ is $A \cap B^c$.  Note that $P(A-B) \neq P(A) - P(B)$.  Wikipedia uses \textbackslash  for $-$ in sets. \hfill \\ 
E suggests always avoiding + when doing math of sets.  It's fine to have + when probability is involved, but adding sets doesn't make a lot of sense.  You could call $\cup$ addition, but that is confusing.  
\end{description}

\subsection{The chain rule}
If you don't want to use intersections, you can use only conditional probabilities to calculate an intersection.  {\tiny L\&M pg 43.}
If $P(E_1 \cap E_2 \cap \dots \cap E_n) > 0$, \hfill \\
$P(E_1 \cap E_2 \cap \dots \cap E_n)$  \hfill \\ 
$= P(E_1)P(E_2 \mid E1)P(E_3 \mid E1 \cap E2) \dots P(E_n \mid E_1 \cap E_2 \cap \dots \cap E_n)$.
 Note you could put $E_1, E_2, \dots$ in any order you want (commutative rule).  Also note that there is no cool rul for $P(A \cup B \cup C)$  \hfill \\ \hfill \\ 
 
 E.g. $P(\mbox{3 face cards in a row}) = P(F_1 \cap F_2 \cap F_3) = P(F_1) \cdot P(F_2 \mid F_1) \cdot P(F_3 \mid F_1 \cap F_2) = \frac{12}{52} \cdot \frac{11}{51} \cdot \frac{10}{50}$
 
Review: if you want to break apart unions, you think of the tiles overlapping and subtracting/adding sections intersections back.  If you want to break apart intersections, you can use the chain rule to break it into conditional probabilities.   \hfill \\
 \hfill \\
 
 {\tiny Covered later:} If the events are independent then you can break them apart: $P(E_1 \cap E_2 \cap \dots \cap E_n) = P(E_1)\cdot P(E_2)\cdot \dots P(E_n)$.   \hfill \\
 E.g. odds of getting three odd rolls in a row with a die:  $P(odd_1 \cap odd_2 \cap \dots \cap odd_3) = P(odd_1)\cdot P(odd_2)\cdot P(odd_3) = (1/2)^3$.
 
 \subsection{Law of total probability} {\tiny Lecture 5, L\&M pg 43}   \hfill \\
 If you have mutually exclusive and exhaustive events $H_i$, and $i = 1, \dots k$.  Mutually exclusive \& exhaustive means $\sum_{i=1}^k P(H_i) = 1$.  Note also $H_i \cap H_j = \Phi$, $P(H_i \cap H_j) = 0$  
 Since $D = (D \cap H_1) \cup (D \cap H_2) \cup \dots \cup  (D \cap H_k)$
	\begin{align*}
 		P(D) = \sum_{j=1}^k P(D \mid H_j) P(H_j) 
  	\end{align*}
We are summing across outcomes, and weighting the sums by the likelyhood of the sub-outcomes.
 
 \subsection{Bayes' formula} {\tiny L\&M p48, Lecture 5}
 Assume $H_i$, $i = 1, \dots, k$ as above (mutually exclusive and exhaustive), and $D$ with $P(D) > 0$.
 	\begin{align*}
		P(H_j \mid D) = \frac{P(H_j \cap D)}{P(D)} = \frac{P(D \mid H_j) P(H_j) }{\sum_{i=1}^k P(D \mid H_j) P(H_j) }
	\end{align*}
$P(\mbox{have antigen A} \mid \mbox{have antigen B}) = P(AB)/(P(B) + P(AB)) $  \hfill \\
 \hfill \\
 
 Example {\tiny (J's Lecture 1)}.  Coin $C_1$ has probability $1/4$ of giving heads.  Coin $C_2$ has probability $1/2$ of giving heads.  What is $P(C_1 \mid H)$?  Bayes theorem.   
 	\begin{align*}
	P(C_1 \mid H) &= P(C_1 \cap H)/P(H) \\
		&\mbox{use } P(C_1 \cap H) = P(H \mid C_1) \cdot P(C_1) \\
		&\mbox{use } P(H) = P(H \mid C_1) \cdot P(C_1) + P(H \mid C_2) \cdot P(C_2) \\
			& = \frac{P(H \mid C_1) \cdot P(C_1)}{P(H \mid C_1) \cdot P(C_1) + P(H \mid C_2) \cdot P(C_2)} \\
			&= \frac{(1/4)\cdot (1/2)}{(1/4)\cdot (1/2) + (3/4)\cdot (1/2) } = \frac{1}{4}\\
	\end{align*}
If you get heads again, what is your probability of coin 1? Call your $P(C_1)$ from above $P^*(C_1)$.  Now $P(H_2)$ (probability of a 2nd heads) is:
	\begin{align*}
	P(C_1 \mid H_2) &= P(C_1 \cap H_2)/P(H_2) \\
		&\mbox{use } P(C_1 \cap H_2) = P(H_2 \mid C_1) \cdot P^*(C_1) \\
		&\mbox{use } P(H_2) = P(H_2 \mid C_1) \cdot P^*(C_1) + P(H_2 \mid C_2) \cdot P^*(C_2) \\
			& = \frac{P(H_2 \mid C_1) \cdot P^*(C_1)}{P(H_2 \mid C_1) \cdot P^*(C_1) + P(H_2 \mid C_2) \cdot P^*(C_2)} \\
			&= \frac{(1/4)\cdot (1/4)}{(1/4)\cdot (1/4) + (3/4)\cdot (3/2) } = \frac{1}{10}\\
	\end{align*}
We could have done it without Bayes: Instead use $P(HH)$ which is P(two heads).  
	\begin{align*}
	P(C_1 \mid HH) &= P(C_1 \cap HH)/P(HH) \\
		&\mbox{use } P(C_1 \cap HH) = P(HH \mid C_1) \cdot P(C_1) \\
		&\mbox{use } P(HH) = P(HH \mid C_1) \cdot P(C_1) + P(HH \mid C_2) \cdot P(C_2) \\
		&\mbox{use } P(HH \mid C_1) = P(H_2 \cap H_1 \mid C_1) \\
			& = \frac{P(HH \mid C_1) \cdot P(C_1)}{P(HH \mid C_1) \cdot P(C_1) + P(HH \mid C_2) \cdot P(C_2)} \\
		&\mbox{use Conditional Independence: } P(H_2 \cap H_1 \mid C_1) = \frac{1}{4} \cdot \frac{1}{4} \\
		&\mbox{use Conditional Independence: } P(H_2 \cap H_1 \mid C_2) = \frac{3}{4} \cdot \frac{3}{4} \\
			&= \frac{(1/4)^2\cdot (1/2)}{(1/4)^2\cdot (1/2) + (3/4)^2\cdot (1/2) } = \frac{1}{10}\\
	\end{align*}

	
%	\begin{align*)
%		$A \cap B$
		%P(H_j \mix D) = \frac{P(H_j \cap D)}{P(D}
%	\end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Independent and disjoint are not equivalent}
The definition of independence is $P(A \cap B) = P(A) \cdot P(B)$.  The definition of mutually exclusive is $P(A \cap B) = 0$.   If $A$ and $B$ have nonzero probability then these can't both be true.  \hfill \\
\hfill \\

\textbf{Independent}: Two events A and B are said to be independent if $P(A \cap B) = P(A) \cdot P(B)$ {\tiny (pg 53)} Note that if $A$ and $B$ are independent, $A^c$ and $B^c$ are independent. {\tiny pg54 ex 2.5.2.}  I don't believe you can visualize independence in a Venn diagram. \hfill \\ 
$P(A \cup B) = P(A) + P(B) - P(A \cap B) = P(A) + P(B) - P(A) \cdot P(B)$ \hfill \\
$P(A \mid B) = P(A \cap B)/P(B) = P(A) \cdot P(B)/P(B) = P(A)$ \hfill \\
 \hfill \\ 
 
 \textit{Example:} {\tiny (Friday 10/9 lecture)} Two coins: $C_1$ gives heads $1/4$ of the time and $C_2$ gives heads $3/4$ of the time.  You get one of the two coins randomly and toss it twice.  Are the two coin tosses independent?  \textit{Answer:} given the coin, they are independent.  Allows for $P(H_1 \cap H_2 | C_1) =  \left(\frac{1}{4}\right)^2$.    \hfill \\
 \textit{Separate question: } without knowing what coin you have, $P(H_1 \cap H_2) = \frac{1}{2}  \cdot  \left(\frac{1}{4}\right)^2 + \frac{1}{2}  \cdot  \left(\frac{3}{4}\right)^2 = \frac{10}{32} =\frac{5}{16} $.   \hfill \\
 But if you calculate the probabilities separately: $P(H_1) = \frac{1}{2}\cdot \frac{1}{4} + \frac{1}{2}\cdot \frac{3}{4} = \frac{1}{2} $.   \hfill \\
 If $H_1$ and $H_2$ were independent, $P(H_1) = P(H_2)$ and $P(H_1 \cap H_2) = P(H_1) \cdot P(H_2)$.    \hfill \\
 Since $P(H_1) \cdot P(H_2) = P(H_1)^2 = \frac{1}{4}$ and $P(H_1 \cap H_2) = 5/16$ we know  $P(H_1 \cap H_2) \neq P(H_1)\cdot P(H_2) $


\hfill \\
\textbf{Mutually exclusive}: Two events A and B are said to be mutually exclusive if $P(A \cap B) = 0$ {\tiny (pg 22)} and $P(A \cup B) = P(A) + P(B)$  {\tiny (E confirmed.)}
\textbf{Disjoint}: mutually exclusive sets. \hfill \\
$P(A \cup B) = P(A) + P(B) - P(A \cap B) = P(A) + P(B) $ \hfill \\
$P(A \mid B) = P(A \cap B)/P(B) = 0/B = 0 $ \hfill \\
If you assume mutual exclusivity when it isn't true, you get too high of a number for $P(A \cup B)$.  Vizualize the Venn diagram for that: need to have $A \cap B = \emptyset$ \hfill \\
If you are adding probabilities, they must be for mutually exclusive events. \hfill \\

\hfill \\
\textbf{Independence of More than Two events}:
Events $A_1, A_2, \dots  A_n$ are said to be \textit{independent} if for every set of indices $i_1, i_2, \dots, i_n$ between 1 and $n$, inclusive,  {\tiny pg 59, Sect 2.5, Lec6}
	\[ P(A_{i1} \cap A_{i2} \cap \dots \cap A_{ik}) = P(A_{i1}) \cdot P(A_{i2}) \dots P(A_{ik}) \]
Note that the k is different than the n.  You have to get the doubles and the triples, etc. 
For the sets A, B, C, D, you have 11: $(A, B), (A, C), (A, D), (B, C), (B, D), (C, D),$ \\
$(A, B, C), (B, C, D), (A, C, D), (A, B, D), (A, B, C, D)$ \hfill \\

\hfill \\

If you only know single probabilities, how do you decompose $P((A_1 \cap A_2) \cup (A_3 \cap B_4))$?  You can't break apart the cups {\tiny that requires mutual exclusivity}, so convert it to $P(A_1 \cap A_2) + P(A_3 \cap A_4) + P((A_1 \cap A_2) \cap (A_3 \cap A_4))$ \hfill \\

Trickier: how do you simplify $P(A_2 \cup A_3) \cap A_4 $ if you only know $A_2$, $A_3$, and $A_4$ are independent?  Factor out the $P(A_4)$ and do the same thing. $[P(A_2) + P(A_3) - P(A_2 \cap A_3)]\cdot P(A_4)$\hfill \\
\hfill \\

\textbf{Conditional Independence} {\tiny (I don't believe we covered this in class; from E)} ${A}$ and ${B}$ are conditionally independent given ${C}$ if $P({A}\cap {B}|{C}) = P({A}|{C})P({B}|{C})$.  E.g. the Bayes coin flip example where you can say $P(\mbox{Heads 1} \cap \mbox{Heads 2} \mid \mbox{Coin 1}) = P(\mbox{Heads 1}|Coin_1) \cdot P(\mbox{Heads 1}|Coin_1) = 2 \cdot P(\mbox{Heads}|Coin_1)$ Conditional independence does not imply independence, and independence does not imply conditional independence.


%%%%%%%%%%%%
\section{Combinatorics}
\smallskip \hrule height 2pt \smallskip

\subsection{Multiplication Rule} for counting ordered sequences
If A can be performed in $m$ different ways and operation B in $n$ different ways, the sequence (operation A, operation B) can be performed in $m*n$ different ways. {\tiny pg 68}

\subsection{Permutations} for when all objects are distinct.
The number of permutations of length $k$ that can be formed from a set of $n$ distinct elements, repetitions NOT allowed, is denoted by the symbol ${_n}P_k$ where ${_n}P_k = n(n-1)(n-2) \dots (n - k - 1) = \frac{n!}{(n-k)!}$  {\tiny (pg 74) }\hfill \\
\[  {_n}P_k = \frac{n!}{(n-k)!} \]

Corollary: the number of ways to permute an entire set of n distinct objects in ${_n}P_n = n!$    {\tiny (pg 74) }\

When all objects are NOT distinct.  The number of ways to arrange $n$ objects, $n_1$ being of one kind, $n_2$ of a second kind, $\dots$, and $n_r$ of an $r^{th}$ kind is 
\[ \mbox{not distinct: } \frac{n!}{n{_1}!n{_2} \dots !n{_r!}} \]
Note: ratios like this are called \textit{multinomial coefficients} because the general term in the expansion of $(x_1 + x_2 + \dots + x_n$ is $\frac{n!}{n_1!n_2!\dots n_r!}x_1^{n1}x_2^{n2} \dots x_r^{nr}$  {\tiny (pg 81) }\hfill \\
\hfill \\
\textbf{Sterling's formula} for evaluating big factorials {\tiny (pg 77)}: $log_{10}(n!) = log_{10}(\sqrt{2*\pi}) + (n + \frac{1}{2}) \cdot log_{10}(n) - n*log_{10}(e)$ \hfill \\
\hfill \\

\subsection{Combinations}
\textbf{(Order doesn't matter.)} The number of ways to form combinations of size $k$ from a set of $n$ \textbf{distinct} objects, repetitions not allowed, is denoted by the symbols $\binom{n}{k}$ or ${_n}C_k$, where   {\tiny (pg 86)}
	\[ {n \choose k} = {_n}C_k = \frac{n!}{k!(n-k)!} \]
This is the number of permutations ($\frac{n!}{(n-k)!}$) divided by the number of ways to order those k selections (so divide by $k$).
(Leaving $(n-k)$ items out of the selection.  Order doesn't matter so reduce the number of sets by $k!$) \hfill \\
Note: ${n \choose k} = {n \choose n - k}$  (Lec 10/12/2015)

\hfill \\
Classic example:  How many unique hand shakes in a room of 8 people?  ${_8}C_2$ applies \hfill \\
\hfill \\
\hfill \\
What about when objects are \textbf{not} distinct but you still want combinations? \hfill \\
\hfill \\

\textbf{Combinations/permutations on tests}: First decide whether the objects are distinguishable.  If they are distinguishable try to think of it as a permutation problem.  If not, try to think of it as a combination problem.  E.g. ways to order 4 blue chips and 4 red chips.  \hfill \\
\hfill \\

\textbf{Differentiating permutations from permutations with repeats from combinations}:
For the set $(0, 1, 2, 2)$, the number of permutations of length two are ${_n}P_k = \frac{2!}{(4-1)!}$.
The number of permutations if they are not distinct...??
The number of combinations:  \hfill \\
\hfill \\

Note: ALL CHAPTER 2 PROBLEMS ASSUME EQUAL PROBABILITY FOR DIFFERENT OUTCOMES.