Title: IA Probability

Q: $4$ most common ways of counting
A: In choosing $n$ elements from $x$ elements we can have
\begin{itemize}
  \item Replacement + with ordering: the number of ways is $x^n$.
  \item Without replacement + with ordering: the number of ways is $x_{(n)} = x^{\underline{n}} = x(x - 1)\cdots (x - n + 1)$.
  \item Without replacement + without order: we only care which items get selected. The number of ways is $\binom{x}{n} = C^x_n = x_{(n)}/n!$.
  \item Replacement + without ordering: we only care how many times the item got chosen. This is equivalent to partitioning $n$ into $n_1 + n_2 + \cdots + n_k$. Say $n = 6$ and $k = 3$. We can write a particular partition as
    \[\]
      **\mid *\mid ***
  So we have $n + k - 1$ symbols and $k - 1$ of them are bars. So the number of ways is $\binom{n + k - 1}{k - 1}$.
\end{itemize}

Q: Multinomial coefficient
A: A \emph{multinomial coefficient} is
  \[
    \binom{n}{n_1, n_2, \cdots, n_k} = \binom{n}{n_1}\binom{n - n_1}{n_2}\cdots \binom{n - n_1\cdots - n_{k - 1}}{n_k} = \frac{n!}{n_1!n_2!\cdots n_k!}.
  \]
  It is the number of ways of partitioning a set of size $n$ into $k$ partitions of sizes $n_i$ ($\sum_i n_i =k$).

Q: Stirling's formula: weaker version
A: \begin{prop}
  $\log n!\sim n\log n$
\end{prop}
\begin{proof}
  Note that
  \[
    \log n! = \sum_{k=1}^n \log k.
  \]
  Now by considering the upper and lower sums
  \[
    \int_1^n \log x\;\d x \leq \sum_1^n \log k\leq \int_1^{n + 1}\log x\;\d x.
  \]
  We actually evaluate the integral to obtain
  \[
    n\log n - n + 1 \leq \log n! \leq (n+ 1)\log (n + 1) - n;
  \]
  Divide both sides by $n\log n$ and let $n\to \infty$. Both sides tend to $1$. So by sandwich theorem
  \[
    \frac{\log n!}{n\log n} \to 1.
  \]
\end{proof}

Q: Stirling's formula
A: \begin{thm}[Stirling's formula]
  As $n\to \infty$,
  \[
    \log\left(\frac{n! e^n}{n^{n + \frac{1}{2}}}\right) = \log \sqrt{2\pi} + O\left(\frac{1}{n}\right)
  \]
\end{thm}
\begin{cor}$ n!\sim \sqrt{2\pi}n^{n + \frac{1}{2}} e^{-n} $
\end{cor}
\begin{proof}(non-examinable)
  Define
  \begin{align*}
    d_n &= \log \left(\frac{n!e^n}{n^{n + 1/2}}\right) = \log n! - (n + 1/2)\log n + n \\
 \Rightarrow d_n - d_{n + 1} &= (n + 1/2)\log\left(\frac{n + 1}{n}\right) - 1.
  \end{align*}
  Write $t = 1/(2n + 1)$. Then
  \[
    d_n - d_{n + 1} = \frac{1}{2t}\log\left(\frac{1 + t}{1 - t}\right) - 1.
  \]
\vspace{-1cm}
  \begin{align*}
   \textrm{Observe } \log (1 + t) - t &= -\frac{1}{2}t^2 + \frac{1}{3}t^3 - \frac{1}{4}t^4 + \cdots\\
    \log (1 - t) + t &= -\frac{1}{2}t^2 - \frac{1}{3}t^3 - \frac{1}{4}t^4 - \cdots
  \end{align*}
  Then subtract and divide by $2t$ to obtain
  \begin{align*}
    d_n - d_{n + 1} &= \frac{1}{3}t^2 + \frac{1}{5}t^4 + \frac{1}{7}t^6 + \cdots\\
    &< \frac{1}{3}t^2 + \frac{1}{3}t^4 + \frac{1}{3}t^6 + \cdots\\
    &= \frac{1}{3}\frac{t^2}{1 - t^2}= \frac{1}{3}\frac{1}{(2n + 1)^2 - 1}\\
    &= \frac{1}{12}\left(\frac{1}{n} - \frac{1}{n + 1}\right) \\
\Rightarrow d_1 - d_n &< \frac{1}{12}\left(1 - \frac{1}{n}\right)
  \end{align*}
  Then we know that $d_n$ is bounded below and decreasing, so $d_n\to A$ and $A$ is a LB.
  Suppose $m > n$. Then $d_n - d_m < \left(\frac{1}{n} - \frac{1}{m}\right)\frac{1}{12}$. So letting $m\to \infty$, $d_n < A + 1/(12n)$ (an UB). Hence
  \[
    A < d_n < A + \frac{1}{12n}.
  \]
   Take $I_n = \int_0^{\pi/2} \sin^n\theta\;\d \theta$. Then $I_n$ is decreasing, $I_n = \frac{n - 1}{n}I_{n - 2}$, $I_{2n} =\frac{(2n)!}{(2^nn!)^2}\frac{\pi}{2}, I_{2n + 1}= \frac{(2^nn!)^2}{(2n + 1)!}$, so
  \[
    1 \leq \frac{I_{2n}}{I_{2n + 1}} \leq \frac{I_{2n - 1}}{I_{2n + 1}} = 1 + \frac{1}{2n} \to 1.
  \]
 As $n!\sim n^{n + 1/2}e^{-n + A}$, we obtain
  \[
    \frac{I_{2n}}{I_{2n + 1}} = \pi(2n + 1)\left[\frac{( (2n)!)^2}{2^{4n + 1}(n!)^4}\right] \sim \pi(2n + 1)\frac{1}{ne^{2A}}\to \frac{2\pi}{e^{2A}}.
  \]
\end{proof}
\begin{prop}[non-examinable]
  \[
    \sqrt{2\pi}n^{n + 1/2}e^{-n} + \frac{1}{12n + 1} \leq n! \leq \sqrt{2\pi} n^{n + 1/2} e^{-n} + \frac{1}{12n}.
  \]
\end{prop}

Q: Probability space
A: \begin{defi}[Probability space]
  A \emph{probability space} is a triple $(\Omega, \mathcal{F}, \P)$. $\Omega$ is the \emph{sample space}, $\mathcal{F}$ is a collection of subsets of $\Omega$, and $\P: \mathcal{F}\to [0, 1]$ is the \emph{probability measure}.
  $\mathcal{F}$ has to satisfy the following axioms:
  \begin{enumerate}
    \item $\emptyset, \Omega\in \mathcal{F}$.
    \item $A\in \mathcal{F} \Rightarrow A^C\in \mathcal{F}$.
    \item $A_1, A_2, \cdots \in \mathcal{F} \Rightarrow \bigcup_{i = 1}^\infty A_i \in \mathcal{F}$.
  \end{enumerate}
  And $\P$ has to satisfy the following \emph{Kolmogorov axioms}:
  \begin{enumerate}
    \item $0 \leq \P(A) \leq 1 $ for all $A\in \mathcal{F}$
    \item $\P(\Omega) = 1$
    \item For any countable collection of events $A_1, A_2, \cdots$ which are disjoint, ie. $\forall i\neq j: A_i\cap A_j = \emptyset$, we have
      \[
        \P\left(\bigcup_i A_i\right) = \sum_i \P(A_i).
      \]
  \end{enumerate}
  Items in $\Omega$ are known as the \emph{outcomes}, items in $\mathcal{F}$ are known as the \emph{events}, and $\P(A)$ is the \emph{probability} of the event $A$.
\end{defi}

Q: Probability distribution
A: \begin{defi}[Probability distribution]
  Let $\Omega = \{\omega_1, \omega_2, \cdots\}$. Choose $\{p_1, p_2, \cdots \}$ such that $\sum_{i = 1}^\infty p_i= 1$. Let $p(\omega_i) = p_i$. Then define
  \[
    \P(A) = \sum_{\omega_i\in A} p(\omega_i).
  \]
  This $\P(A)$ satisfies the necessary axioms, and $p_1, p_2, \cdots$ is the \emph{probability distribution}
\end{defi}

Q: Probability of the empty set
A: \[ \P(\emptyset) = 0 \]
\begin{proof}
$\Omega$ and $\emptyset$ are disjoint. So
\begin{align*}
\P(\Omega) + \P(\emptyset) &=1+\P(\emptyset) \\
&= \P(\Omega \cup \emptyset) \\
&= \P(\Omega) \\
&=1. \\
\textrm{Then }\P(\emptyset) &= 0.
\end{align*}
\end{proof}

Q: Probability of complement
A: $$\P(A^C) = 1 - \P(A)$$
\begin{proof}
$\P(A) + \P(A^C) =\P(A\cup A^C)= \P(\Omega) = 1$ since $A$ and $A^C$ are disjoint.
\end{proof}

Q: Monotonicity
A: $$A\subseteq B \Rightarrow \P(A) \leq \P(B)$$
\begin{proof}
Write $B = A\cup (B\cap A^C)$. Then $\\P(B) = \P(A) + \P(B\cap A^C) \geq \P(A)$.
\end{proof}

Q: Boole's inequality
A: \begin{thm}
For any $A_1, A_2, \cdots$
  \[
    \P\left(\bigcup_{i=1}^\infty A_i\right) \leq\sum_{i=1}^\infty \P(A_i).
  \]
\end{thm}
\begin{proof}
  Take $B_1 = A_1$, $B_2 = A_2\setminus A_1$. In general,
  \[
    B_n = A_n\setminus\bigcup_1^{n - 1}A_i.
  \]
  Then $B_i$ are disjoint and
  \[
   \bigcup_1^\infty B_i = \bigcup _1^\infty A_i.
  \]
  Then
  \begin{align*}
 \P\left(\bigcup_1^\infty A_i\right) &= \P\left(\bigcup_1^\infty B_i\right)\\
  &=\sum_1^\infty \P(B_i) \\
  &\leq \sum_{i = 1}^\infty \P(A_i) \textrm{ by monotonicity.}\\
  \end{align*}
\end{proof}

Q: Inclusion-exclusion formula
A: \begin{thm}[Inclusion-exclusion formula]
  \begin{align*}
    \P\left(\bigcup_i^n A_i\right) &= \sum_1^n \P(A_i) - \sum_{i_1 < i_2} \P(A_{i_1}\cap A_{j_2}) \\
&+ \sum_{i_1 < i_2 < i_3}\P(A_{i_1}\cap A_{i_2} \cap A_{i_3}) - \cdots\\
    &+ (-1)^{n - 1} \P(A_1\cap \cdots \cap A_n).
  \end{align*}
\end{thm}
\begin{proof}
  Perform induction on $n$. For the basis $n = 2$ we have
\begin{align*}
\P(A\cup B) &= \P(A) + \P(B\cap A^C) \\
\P(B) &= \P(A\cap B) + \P(B\cap A^C) \\
\implies \P(A\cup B)-\P(B) &=\P(A)-\P(A\cap B).
\end{align*}
  Then assuming the result for $n-1$ gives
\begin{align*}
&\P(A_1\cup A_2\cup \cdots A_n) \\
= & \P(A_1\cup (A_2\cup \cdots A_n)) \\
= & \P(A_1) + \P(A_2\cup\cdots\cup A_n) \\
&-\P\left(\bigcup_{i = 2}^n (A_1\cap A_i)\right) \\
= & \P(A_1) + \sum_{i=2}^n \P(A_i) -\sum_{i<j\leq n} \P(A_i\cap A_j) +\dots \\
&+(-1)^{n-2}\P(A_2\cap\dots\cap A_n) \\
&-\sum_2^n \P(A_1\cap A_i)+ \sum_{i < j\leq n} \P(A_1\cap A_{i}\cap A_{j})) +\dots \\
&+(-1)^{n-1} \P(A_1\cap A_2\cap \cdots \cap A_n).
\end{align*}
\end{proof}

Q: Poisson approximation to binomial
A: Suppose $n\to \infty$ and $p\to 0$ such that $np = \lambda$. Then
  \[
    \binom{n}{k}p^k(1 -p)^{n - k} \to \frac{\lambda^k}{k!}e^{-\lambda}.
  \]
\begin{proof}
\begin{align*}
&\binom{n}{k}p^k(1 - p)^{n - k}\\
  &= \frac{1}{k!} \frac{n(n - 1)\cdots(n - k + 1)}{n^k}(np)^k \left(1 - \frac{np}{n}\right)^{n - k}\\
  &\to \frac{1}{k!}\lambda^ke^{-\lambda}
\end{align*}
since $(1 - a/n)^n \to e^{-a}$.
\end{proof}

Q: Probability measure conditioned on an event
A: The function $\P(\ph \mid B)$ restricted to subsets of $B$ is a probability function (or measure).
\begin{proof}
We check the axioms.
  \begin{enumerate}
    \item Let $A\subseteq B$. Then $\P(A\mid B) = \frac{\P(A\cap B)}{\P(B)} \leq 1$.
    \item $\P(B\mid B) = \frac{\P(B)}{\P(B)} = 1$.
    \item Let $A_i$ be disjoint events. Then
      \begin{align*}
        \P\left(\left.\bigcup_i A_i\right\vert B\right) &= \frac{\P(\bigcup_i A_i\cap B)}{\P(B)}\\
        &= \frac{\P\left(\bigcup_i A_i\right)}{\P(B)}\\
        &= \sum_i \frac{\P(A_i)}{\P(B)}\\
        &=\sum_i \frac{\P(A_i\cap B)}{\P(B)}\\
        &= \sum_i \P(A_i \mid B).
      \end{align*}
  \end{enumerate}
\end{proof}

Q: Hypergeometric distribution
A: Suppose we have an urn with $n_1$ red balls and $n_2$ black balls. We choose $n$ balls. The probability that there are $k$ red balls is
  \[
    \P(k\text{ red}) = \frac{\binom{n_1}{k}\binom{n_2}{n - k}}{\binom{n_1 + n_2}{n}}.
  \]

Q: Expectation
A: Given absolute convergence
  \begin{align*}
    \E[X] &=\sum_{\omega\in \Omega}p_\omega X(\omega) \\
&= \sum_{x\in \Omega_X}\sum_{\omega | X(\omega) = x}p_\omega X(\omega)\\
    &= \sum_{x\in \Omega_X}x\sum_{\omega | X(\omega) = x}p_\omega\\
    &= \sum_{x\in \Omega_X}xP(X = x).
  \end{align*}
This has the important property that
 \begin{align*}
        \E[(X - c)^2] &= \E[(X - \E[X] + \E[X] - c)^2]\\
        &= \E[(X - \E[X])^2 + 2(\E[X] - c)\underbrace{(X - \E[X])}_{=0} + (\E[X] - c)^2]\\
        &= \E(X - \E[X])^2 + (\E[X] - c)^2.
      \end{align*}
      is minimised when $c = \E[X]$.

Q: Variance
A: The \emph{variance} of a random variable $X$ is
\begin{align*}
\var(X) &= \E[(X - \E[X])^2] \\
&= \E[X^2-2X\E[X]+\E[X]^2] \\
&= \E[X^2]-2\E[X]^2+\E[X]^2] \\
&= \E[X^2] - \E[X]^2.
\end{align*}

Q: Indicator function
A: The \emph{indicator function} or \emph{indicator variable} $I[A]$ (or $I_A$) of an event $A\subseteq \Omega$ is
  \[
    I[A](\omega) =
    \begin{cases}
      1 & \omega\in A\\
      0 & \omega\not\in A.
    \end{cases}
  \]
It has the following properties:
  \begin{itemize}
    \item $\E[I[A]] = \sum_\omega p(\omega) I[A](\omega) = \P(A)$.
    \item $I[A^C] = 1 - I[A]$.
    \item $I[A\cap B] = I[A]I[B]$.
    \item $I[A\cup B] = I[A] + I[B] - I[A]I[B]$.
    \item $I[A]^2 = I[A]$.
  \end{itemize}

Q: Inclusion-exclusion formula by indicator functions
A: \begin{align*}
    \P\left(\bigcup_i^n A_i\right) &= \sum_1^n \P(A_i) - \sum_{i_1 < i_2} \P(A_{i_1}\cap A_{j_2}) + \sum_{i_1 < i_2 < i_3}\P(A_{i_1}\cap A_{i_2} \cap A_{i_3}) - \cdots\\
    &+ (-1)^{n - 1} \P(A_1\cap \cdots \cap A_n).
  \end{align*}
\begin{proof}
  Let $I_j$ be the indicator function for $A_j$. Write
  \[
    S_r = \sum_{i_1 < i_2 < \cdots < i_r}I_{i_1}I_{i_2}\cdots I_{i_r},
  \]
  and
  \[
    s_r = \E[S_r] = \sum_{i_1 < \cdots < i_r}\P(A_{i_1}\cap \cdots \cap A_{i_r}).
  \]
  Then
  \[
    1 - \prod_{j = 1}^n(1 - I_j) = S_1 - S_2 + S_3 \cdots + (-1)^{n - 1}S_n.
  \]
  So
  \[
    \P\left(\bigcup_1^n A_j\right) = \E\left[1 - \prod_1^n(1 - I_j)\right] = s_1 - s_2 + s_3 - \cdots + (-1)^{n - 1}s_n.
  \]
\end{proof}

Q: Independent random variables
A: Let $X_1, X_2, \cdots, X_n$ be discrete random variables. They are \emph{independent} iff for any $x_1, x_2, \cdots, x_n$,
  \[
    \P(X_1 = x_1, \cdots, X_n = x_n) = \P(X_1 = x_1)\cdots \P(X_n = x_n).
  \]

Q: Closure of independence
A: \begin{thm}
  If $X_1, \cdots, X_n$ are independent random variables, and $f_1, \cdots, f_n$ are functions $\R \to \R$, then $f_1(X_1), \cdots, f_n(X_n)$ are independent random variables.
\end{thm}
\begin{proof}
  We have
  \begin{align*}
    \P(f_1(X_1) = y_1, \cdots f_n(X_n) = y_n) &= \sum_{\substack{x_1: f_1(x_1) = y_1\\\cdot\vspace{-2pt}\\\cdot\\x_n: f_n(x_n) = y_n}} \P(X_1 = x_1, \cdots, X_n = x_n)\\
    &= \sum_{\substack{x_1: f_1(x_1) = y_1\\\cdot\vspace{-2pt}\\\cdot\\x_n: f_n(x_n) = y_n}} \prod_{i = 1}^n \P(X_i = x_i)\\
    &= \prod_{i = 1}^n \sum_{x_i:f_i(x_i) = y_i} \P(X_i = x_i)\\
    &= \prod_{i = 1}^n \P(f_i(x_i) = y_i).
  \end{align*}
  Note that the switch from the second to third line is valid since they both expand to the same mess.
\end{proof}

Q: Expectation of a product
A: \begin{thm}
  If $X_1, \cdots, X_n$ are independent random variables and all the following expectations exists, then
  \[
    \E\left[\prod_i X_i\right] = \prod_i \E[X_i].
  \]
\end{thm}
\begin{proof}
  Write $R_i$ for the range of $X_i$. Then
  \begin{align*}
    \E\left[\prod_1^n X_i\right] &= \sum_{x_1\in R_1}\cdots \sum_{x_n\in R_n}x_1x_2\cdots x_n\times \P(X_1 = x_1, \cdots, X_n = x_n)\\
    &= \prod_{i = 1}^n \sum_{x_i \in R_i}x_i\P(X_i = x_i)\\
    &= \prod_{i = 1}^n \E[X_i].
  \end{align*}
\end{proof}

Q: Variance of a sum
A: If $X_1, X_2, \cdots X_1$ are independent random variables, then
  \[
    \var\left(\sum_i X_i\right) = \sum_i \var (X_i).
  \]
In general
\begin{align*}
\operatorname{Var}\left(\sum_{i=1}^n X_i\right) &= \sum_{i=1}^n \sum_{j=1}^n \operatorname{Cov}(X_i, X_j) \\
&= \sum_{i=1}^n \operatorname{Var}(X_i) + 2\sum_{1\le i}\sum_{<j\le n}\operatorname{Cov}(X_i,X_j).
\end{align*}
\begin{proof}
  \begin{align*}
    \var\left(\sum_i X_i\right) &= \E\left[\left(\sum_i X_i\right)^2\right] - \left(\E\left[\sum_i X_i\right]\right)^2\\
    &= \E\left[\sum_i X_i^2 + \sum_{i \not =j} X_iX_j\right] - \left(\sum_i\E [X_i]\right)^2\\
    &= \sum_i \E[X_i^2] + \sum_{i\not= j}\E[X_i]\E[X_j] - \sum_i(\E[X_i])^2 - \sum_{i\not= j}\E[X_i]\E[X_j]\\
    &= \sum_i \left(\E[X_i^2] - (\E[X_i])^2\right) \\
&= \sum_i \var (X_i).
  \end{align*}
\end{proof}

Q: Variance of sample mean
A: Let $X_1, X_2, \cdots X_n$ be iid rvs with variance $\sigma$. Then
 \[
   \var\left(\frac{1}{n}\sum X_i\right) = \frac{\sigma}{n}.
 \]
\begin{proof}
We have
  \begin{align*}
    \var\left(\frac{1}{n}\sum X_i\right) &= \frac{1}{n^2}\var\left(\sum_i X_i\right)\\
    &= \frac{1}{n^2}\sum_i \var(X_i)\\
    &= \frac{1}{n^2} (n \sigma)\\
    &= \frac{\sigma}{n},
  \end{align*}
which vanishes as $n\to\infty$.
\end{proof}

Q: Convex and concave functions
A: A function $f: (a, b) \to \R$ is \emph{convex} if for all $x_1, x_2\in (a, b)$ and $0\leq\lambda\leq 1$
\[
   (1-\lambda)  f(x_1) +  \lambda f(x_2) \geq f((1-\lambda)  x_1 + \lambda x_2).
  \]
  It is \emph{strictly convex} if the inequality above is strict (except when $x_1 = x_2$, $\lambda=0$ or $\lambda=1$). \\
 A function is \emph{concave} if $-f$ is convex.

Q: Jensen's inequality
A: If $f:(a, b) \to \R$ is convex, then
  \[
    \sum_{i = 1}^n p_i f(x_i) \geq f\left(\sum_{i = 1}^n p_ix_i\right)
  \]
  for all $p_1, p_2, \cdots, p_n$ such that $p_i \geq 0$ and $\sum p_i = 1$, and $x_i \in (a, b)$.
If $X$ takes finitely many values, then the theorem says $\E[f(X)] \geq f(\E[X])$.
  If $f$ is strictly convex, then equalities hold only if all $x_i$ are equal, ie. $X$ takes only one possible value.
\begin{proof}
  Induct on $n$. It is true for $n = 2$ by the definition of convexity. Then using the definition of convexity followed by the assumption for $n-1$ gives
  \begin{align*}
    \textrm{RHS}&=f(p_1x_1 + \cdots + p_nx_n) \\
 &= f\left(p_1x_1 + (p_2 + \cdots + p_n)\frac{p_2x_2 + \cdots + p_nx_n}{p_2 + \cdots + p_n}\right)\\
    &\leq p_1f(x_1) + (p_2 + \cdots p_n)f\left(\frac{p_2x_2 + \cdots + p_n x_n}{p_2 + \cdots + p_n }\right)\\
    &\leq p_1f(x_1) + \left(\sum_{i\neq 1} p_i \right) \left[\frac{p_2}{(\sum_{i\neq 1} p_i)}f(x_2) + \cdots + \frac{p_n}{(\sum_{i\neq 1} p_i)}f(x_n)\right]\\
    &= p_1f(x_1) + \cdots + p_n(x_n) \\
&=\textrm{LHS}.
  \end{align*}
  Strictly convex case is proved with $\leq$ replaced by $<$ by definition of strict convexity.
\end{proof}

Q: AM-GM inequality
A: Given $x_1, \cdots, x_n$ positive reals, then
  \[
    \left(\prod x_i\right)^{1/n} \leq \frac{1}{n}\sum x_i.
  \]
\begin{proof}
  Apply Jensen's inequality to $-\log x$.
  Take $\P(x = x_i) = 1/n$. Then
  \[
    \E[f(x)] = \frac{1}{n}\sum_i (-\log x_i )= -\log \text{GM}
  \]
  and
  \[
    f(\E[X]) = -\log\left( \frac{1}{n}\sum x_i \right) = -\log\text{AM}
  \]
  Since $f(\E[x]) \leq \E[f(x)]$, AM $\geq$ GM. Since $-\log x$ is strictly convex, AM $=$ GM only if all $x_i$ are equal.
\end{proof}

Q: Cauchy-Schwarz inequality for expectation
A: For any two random variables $X, Y$,
  \[
    (\E[XY])^2 \leq \E[X^2]\E[Y^2].
  \]
\begin{proof}
  If $Y = 0$, then both sides are $0$. Otherwise, $\E[Y^2] > 0$. Let
  \[
    w = X - Y\cdot \frac{\E[XY]}{\E[Y^2]}.
  \]
  Then
  \begin{align*}
    \E[w^2] &= \E\left[X^2 - 2XY\frac{\E[XY]}{\E[Y^2]} + Y^2\frac{(\E[XY])^2}{(\E[Y^2])^2}\right]\\
    &= \E[X^2] - 2\frac{(\E[XY])^2}{\E[Y^2]} + \frac{(\E[XY])^2}{\E[Y^2]}\\
    &= \E[X^2] - \frac{(\E[XY])^2}{\E[Y^2]} \\
&\geq 0.
  \end{align*}
\end{proof}

Q: Markov and Chebyshev inequalities
A: If $X$ is a random variable with $\E|X|^n < \infty$, $n\in\N$ and $\varepsilon > 0$, then
  \[
    \P(|X| \geq \varepsilon) \leq \frac{\E|X|^n}{\varepsilon^n}.
  \]
$n=1$ is Markov's inequality and $n=2$ is Chebyshev's inequality.
Letting $\mu=\E X, \sigma=\var X$, $X\to X-\mu$ in Chebyshev  gives
\[
  \P(|X - \mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2}.
\]
\begin{proof}
We claim
  \[
    I[|X|\geq \varepsilon] \leq \frac{|X|^n}{\varepsilon^n}.
  \]
  This is proved by exhaustion: if $|X| \geq \varepsilon$, then LHS = 1 and RHS $>$ 1; if $|X| \leq \varepsilon$, then LHS $= 0$ and RHS $> 0$.
  Take the expected value to obtain
  \[
    \P(|X| \geq \varepsilon) \leq \frac{\E |X|^n}{\varepsilon^n}.
  \]
\end{proof}

Q: Weak law of large numbers
A: Let $X_1, X_2, \cdots X_n$ be iid random variables, with mean $\mu$ and variance $\sigma^2$.
  Let $S_n = \sum_{i = 1}^n X_i$.
  Then for all $\varepsilon > 0$
  \[
    \P\left(\left|\frac{S_n}{n} - \mu\right| \geq \varepsilon\right) \to 0
  \]
  as $n\to \infty$.
  We say, $\frac{S_n}{n}$ tends to $\mu$ (in probability), or
  \[
    \frac{S_n}{n}\to_p \mu.
  \]
\begin{proof}
  By Chebyshev
  \begin{align*}
    \P\left(\left|\frac{S_n}{n} - \mu\right| \geq \varepsilon\right)&\leq \frac{\E\left(\frac{S_n}{n} - \mu\right)^2}{\varepsilon^2}\\
    &= \frac{1}{n^2}\frac{\E(S_n -n\mu)^2}{\varepsilon^2}\\
    &= \frac{\var (S_n)}{n^2\varepsilon^2}\\
    &= \frac{n\sigma^2}{n^2\varepsilon^2}\\
    &= \frac{\sigma^2}{n\varepsilon^2} \to 0 \textrm{ as }n\to\infty.
  \end{align*}
\end{proof}

Q: Strong law of large numbers
A: Let $X_1, X_2, \cdots$ be iid random variables, with mean $\mu$ and variance $ \sigma^2$.
  Let $S_n = \sum_{i = 1}^n X_i$.
  Then
  \[
    \P\left(\frac{S_n}{n}\to \mu\text{ as }n\to \infty\right) = 1.
  \]
  We say
  \[
    \frac{S_n}{n}\to_{\mathrm{as}} \mu,
  \]
  where ``as'' means ``almost surely''.

Q: Covariance
A: Given two random variables $X, Y$, the \emph{covariance} is
  \begin{align*}
    \cov(X, Y) &= \E[(X - \E[X])(Y - \E[Y])] \\
 &=\E[XY] - \E[X]\E[Y].
  \end{align*}

Q: Correlation coefficient
A: The \emph{correlation coefficient} of $X$ and $Y$ is
  \[
    \corr(X, Y) = \frac{\cov (X, Y)}{\sqrt{\var (X)\var (Y)}}.
  \]
  Applying Cauchy-Schwarz to $X - \E[X]$ and $Y - \E[Y]$ gives that $|\corr(X, Y)| \leq 1$.

Q: Joint distribution of discrete rvs
A: Let $X$ and $Y$ be random variables  with joint distribution $\P(X = x, Y = y)$. Then the \emph{marginal distribution} (or simply \emph{distribution}) of $X$ is
  \[
    \P(X = x) = \sum_{y\in \Omega_y}\P(X = x, Y = y).
  \]
  The \emph{conditional distribution} of $X$ given $Y$ is
  \[
    \P(X = x\mid Y = y) = \frac{\P(X = x, Y = y)}{\P(Y = y)}.
  \]
  The \emph{conditional expectation} of $X$ given $Y$ is
  \[
    \E[X\mid Y = y] = \sum_{x\in \Omega_X}x\P(X = x\mid Y = y).
  \]
  We can view $\E[X\mid Y]$ as a random variable in $Y$: given a value of $Y$, we return the expectation of $X$.

Q: Tower property of conditional expectation (Law of total expectation)
A: \begin{thm}
  \[
    \E_Y[\E_X[X\mid Y]] = \E_X[X]
  \]
\end{thm}
\begin{proof}
  \begin{align*}
    \E_Y[\E_X[X\mid Y]] &= \sum_y \P(Y = y)\E[X\mid Y = y]\\
    &= \sum _y \P(Y = y) \sum_{x}x\P(X = x\mid Y = y)\\
    &= \sum_x\sum_y x\P(X = x, Y = y)\\
    &= \sum _x x\sum_y \P(X = x, Y = y)\\
    &= \sum_x x\P(X = x)\\
    &= \E[X].
  \end{align*}
\end{proof}

Q: Probability generating function
A: The \emph{probability generating function (pgf)} of $X$ is
  \[
    p(z) = \E[z^X] = \sum_{r = 0}^\infty \P(X = r)z^r = p_0 + p_1z + p_2z^2\cdots = \sum_0^\infty p_rz^r.
  \]
  This is a power series (or polynomial), and converges if $|z| \leq 1$, since
  \[
    |p(z)| \leq \sum_r p_r |z^r| \leq \sum_r p_r = 1.
  \]
  We sometimes write as $p_X(z)$ to indicate what the random variable.

Q: Abel's lemma
A: \[
    \E[X] = \lim_{z\to 1}p'(z)
  \]
\begin{proof}
  For $z < 1$, we have
  \[
    p'(z) = \sum_1^\infty rp_r z^{r - 1} \leq \sum_1^\infty rp_r = \E[X].
  \]
  So we must have
  \[
    \lim_{z\to 1}p'(z) \leq \E[X].
  \]
  On the other hand, for any $\varepsilon$, if we pick $N$ large, then
  \[
    \sum_{1}^N rp_r \geq \E[X] - \varepsilon
  \]
  and
  \[
    \E[X] - \varepsilon \leq \sum_1^N rp_r = \lim_{z\to 1}\sum _1^N rp_r z^r\leq \lim_{z \to 1} \sum_1^\infty rp_r z^r = \lim_{z\to 1} p' (z).
  \]
  So $\E[X] \leq \lim\limits_{z \to 1}p'(z)$.
\end{proof}

Q: pgf of a sum
A: Suppose $X_1, X_2, \cdots, X_n$ are independent rvs with pgfs $p_1, p_2, \cdots, p_n$. Then the pgf of $X_1 + X_2 + \cdots + X_n$ is $p_1(z)p_2(z)\cdots p_n(z)$.
\begin{proof}
  \begin{align*}
    \E[z^{X_1 + \cdots + X_n}] &= \E[z^{X_1}\cdots z^{X_n}] \\
& = \E[z^{X_1}]\cdots\E[z^{X_n}] \\
& = p_1(z)\cdots p_n(z).
  \end{align*}
\end{proof}
Let $X_1, X_2, \cdots, X_n$ be iid with pgf $p(z) = \E[z^X]$. Let $N$ be a random variable independent of $X_i$ with pgf $h(z)$. The pgf of $S = X_1 + \cdots + X_N$ is
\begin{align*}
  \E[z^{S}] &= \E[z^{X_1 + \cdots + X_N}]\\
  &= \E_N[\underbrace{\E_{X_i}[z^{X_1 + \ldots + X_N}\mid N]}_{\text{assuming fixed }N}]\\
  &= \sum_{n = 0}^\infty \P(N = n) \E[z^{X_1 + X_2 + \cdots + X_n}]\\
  &= \sum_{n = 0}^\infty \P(N = n) \E[z^{X_1}] \E[z^{X_2}]\cdots\E[z^{X_n}]\\
  &= \sum_{n = 0}^\infty \P(N = n) (\E[z^{X_1}])^n\\
  &= \sum_{n = 0}^\infty \P(N = n) p(z)^n \\
  &= h(p(z)).
\end{align*}

Q: Branching process
A: Let $X_n$be the number of individuals in the $n$th generation such that $X_0 = 1$ and $X_{n + 1} = Y_1^n + Y_2^n + \cdots + Y_{X_n}^n$ where $Y_i^n$ are iid random variables with pgf $F(z)$, mean $\mu$ and variance $\sigma^2$.
Define
\[
  F_n(z) = E[z^{X_n}].
\]
\begin{thm}
  \[
    F_{n + 1}(z) = F_n(F(z)) = F(F(F(\cdots F(z) \cdots )))) = F(F_n(z)).
  \]
\end{thm}
\begin{proof}
  \begin{align*}
    F_{n + 1}(z) &= \E[z^{X_{n + 1}}]\\
    &= \E[\E[z^{X_{n + 1}}\mid X_n]]\\
    &= \sum_{k = 0}^\infty \P(X_n = k)\E[z^{X_{n + 1}}\mid X_n = k]\\
    &= \sum_{k = 0}^\infty \P(X_n = k)\E[z^{Y_1^n + \cdots + Y_k^n}]\\
    &= \sum_{k = 0}^\infty \P(X_n = k)\E[z^{Y_1}]\E[z^{Y_2}]\cdots\E[z^{Y_k}]\\
    &= \sum_{k = 0}^\infty\P(X_n = k)F(z)^k\\
    &= F_n(F(z)).
  \end{align*}
\end{proof}
\begin{thm}
  \[
    \E[X_n] = \mu^n,\quad \var X_n = \sigma^2\mu^{n - 1}(1 + \mu + \mu^2 + \cdots + \mu^{n - 1}).
  \]
\end{thm}
\begin{proof}
\begin{align*}
  \E[X_n] &= \E[\E[X_n\mid X_{n - 1}]]\\
  &= \E[\mu X_{n - 1}]\\
  &= \mu \E[X_{n - 1}] \\
\E[X_n^2] &= \E[\E[X_n^2\mid X_{n - 1}]]\\
  &= \E[\var(X_n) + (\E[X])^2 \mid X_{n - 1}]\\
  &= \E[X_{n - 1}\var (X_1) + (\mu X_{n - 1})^2]\\
  &= \E[X_{n - 1}\sigma^2 + (\mu X_{n - 1})^2]\\
  &= \sigma^2 \mu^{n - 1} + \mu^2 \E[X_{n - 1}^2] \\
\var [X_n] &= \E[X_n^2] - (\E[X_n])^2 \\
  &= \mu^2 \E[X_{n -1}^2] + \sigma^2 \mu^{n - 1} - \mu^2 (\E[X_{n - 1}])^2\\
  &= \mu^2(\E[X_{n - 1}^2] - \E[X_{n - 1}]^2) + \sigma^2\mu^{n - 1} \\
  &= \mu^2 \var (X_{n - 1}) + \sigma^2 \mu^{n -1 }.
\end{align*}
\end{proof}

Q: Extinction probability
A: Let
\begin{align*}
A_n &= ``X_n=0" \\
  A &= \bigcup_{n = 1}^\infty A_n \\
\P(A)&=q .
\end{align*}
Since $A_1 \subseteq A_2 \subseteq A_3 \subseteq \cdots$, we know that
\begin{align*}
  q &= \P(A) \\
& = \lim_{n\to \infty} \P(A_n) \\
& = \lim_{n \to \infty} \P(X_n = 0) \\
& = \lim_{n \to \infty} F_n(0) .
\end{align*}
So
\[
  F(q) = F\left(\lim_{n\to \infty} F_n(0)\right) = \lim_{n\to \infty} F(F_n(0)) = \lim_{n\to \infty}F_{n + 1}(0) = q.
\]
So
\[
  F(q) = q.
\]
Alternatively, using the law of total probability
\[
  q = \sum_k \P(X_1 = k) \P(A \mid X_1 = k) = \sum_k p_k q^k = F(q).
\]
\begin{thm}
 $q$ is the smallest root of $x = F(x)$. Also if $\mu \leq 1$, then $q = 1$; if $\mu > 1$, then $q < 1$.
\end{thm}
\begin{proof}
Let $\alpha$ be the smallest root. Then note that $0 \leq \alpha \Rightarrow F(0) \leq F(\alpha) = \alpha$ since $F$ is increasing. Hence $F(F(0)) \leq \alpha$. Continuing inductively, $F_n(0) \leq \alpha$ for all $n$. So
  \[
    q = \lim_{n \to \infty}F_n(0) \leq \alpha.
  \]
Hence $q = \alpha$ by minimality.
Obviously $F'(z), F''(z) \geq 0$ for $z\in (0, 1)$, so $F$ is increasing and convex. Since $F(1)=1, F'(1) = \mu \leq 1$, the curve must approach $(1, 1)$ from above the $F = z$ line. So $z = 1$ is the only root.
\end{proof}

Q: Random walk
A: Let $X_1, \cdots, X_n$ be iid rvs such that \[
X_n =\begin{cases} +1 \textrm{ with probability }p \\ -1 \textrm{ with probability }q=1-p. \end{cases}
\]
Let $S_n = S_0 + X_1 + \cdots + X_n$. Then $(S_0, S_1, \cdots, S_n)$ is a \emph{1-dimensional random walk}.
  If $p = q = \frac{1}{2}$, we say it is a \emph{symmetric random walk}.

Q: Gambler's ruin
A: Let $(S_n)$ be a random walk with $S_0=z>0$. Define
  \[
    p_z = \P(\text{rw hits $a$ before } 0 \mid \text{starts at } z)
  \]
  and
  \[
    q_z = \P(\text{rw hits 0 before }a \mid \text{starts at }z).
  \]
Then
  \[
    p_z = qp_{z - 1} + pp_{z + 1},
  \]
  for $0 < z < a$, and $p_0 = 0, p_a = 1$.
Then
  \[
    pt^2 - t + q = (pt - q)(t - 1) = 0
  \]
which has solution
  \begin{align*}
    p_z =\begin{cases} A + B\left(\frac{q}{p}\right)^z = \frac{1 - (p/q)^z}{1 - (p/q)^a} &p\neq q \\  A + Bz = z/a &p=q. \end{cases}
  \end{align*}
Letting $p_z\mapsto q_z,p\mapsto q$, $q\mapsto p$ and $z \mapsto a - z$ or arguing that $p_z + q_z = 1$ gives
  \[
    q_z = \begin{cases} \frac{(p/q)^z - (q/p)^a}{1 - (p/q)^a} &p\not = q \\ \frac{a - z}{a} &p=q.\end{cases}
  \]
  \begin{align*}
    \P(\text{rw hits 0 ever}) &= \P\left(\bigcup_{a = z+1}^\infty [\text{rw hits 0 before }a]\right)\\
    &= \lim_{a\to \infty}\P(\text{rw hits 0 before }a)\\
    &= \lim_{a\to \infty}q_z\\
    &= \begin{cases}
      (p/q)^z & p > q\\
      1 & p \leq q.
    \end{cases}
  \end{align*}

Q: Duration of gambler's ruin problem
A: Let $D_z =$ expected time until rw hits $0$ or $a$, starting from $z$. Comparing to a geometric distribution gives that $D_z \leq \frac{a}{p^a + q^a}<\infty$. Therefore
\begin{align*}
  D_z &= p\E[\text{duration}\mid X_1 = 1] + q\E[\text{duration}\mid X_1 = -1]\\
  &= p(1 + D_{z + 1}) + q(1 - D_{z - 1})
\end{align*}
So
\[
  D_z = 1 + pD_{z + 1} + qD_{z - 1},
\]
subject to $D_0 = D_a = 0$.
Now \[
  pt^2 - t + q = 0
\]
has roots $1$ and $q/p$. Therefore
\begin{align*}
D_z=\begin{cases} A + B\left(\frac{q}{p}\right)^z  + Cz=\frac{z}{q - p} - \frac{a}{q - p} \cdot \frac{1 - (q/p)^z}{1 - (q/p)^a} &p=q\\  A + Bz+Cz^2=z(a - z) &p\neq q. \end{cases}
\end{align*}

Q: Gambler's ruin by pgfs
A: Let $U_{z,n} = \P(\text{random walk absorbed at 0 at }n\mid \text{start at }z)$.
Then $U_{0, 0} = 1$; $U_{z, 0} = 0$ for $0 < z \leq a$; $U_{0, n} = U_{a, n} = 0$ for $n > 0$.
Define
\[
  U_z(s) = \sum_{n = 0 }^\infty U_{z, n}s^n.
\]
We know that
\[
  U_{z, n + 1} = p U_{z + 1, n} + qU_{z - 1, n}.
\]
Multiplying by $s^{n + 1}$ and summing gives
\[
  U_z(s) = psU_{z + 1}(s) + qsU_{z - 1}(s).
\]
We try $U_z(s) = [\lambda(s)]^z$. Then
\[
  \lambda(s) = ps\lambda(s)^2 + qs.
\]
Then
\[
  \lambda_1(s), \lambda_2(s) = \frac{1 \pm \sqrt{1 - 4pqs^2}}{2ps}.
\]
So
\[
  U_z(s) = A(s) \lambda_1(s)^z + B(s)\lambda_2(s)^z.
\]
Since $U_0(s) = 1$ and $U_a(s) = 0$, we know that
\[
  A(s) + B(s) = 1
\]
and
\[
  A(s)\lambda_1(s)^a + B(s)\lambda_2(s)^a = 0.
\]
Then we find that
\[
  U_z(s) = \frac{\lambda_1(s)^a\lambda_2(s)^z - \lambda_2(s)^a\lambda_1(s)^z}{\lambda_1(s)^a - \lambda_2(s)^a}.
\]
Since $\lambda_1(s)\lambda_2(s) = \frac{q}{p}$, we can write
\[
  U_z(s) = \left(\frac{q}{p}\right)^z \cdot \frac{\lambda_1(s)^{a - z} - \lambda_2(s)^{a - z}}{\lambda_1(s)^a - \lambda_2(s)^a}.
\]
We see that $U_z(1) = q_z$. We can similarly find the pgf for absorption at $a$, say $V_z(s)$. Then the pgf for the duration is $U_z + V_z$. Hence the expected duration is $D_z = U'_z(1) + V'_z(1).$

Q: Exponential random variable
A: The \emph{exponential random variable with parameter $\lambda$} has pdf
  \[
    f(x) = \lambda e^{-\lambda x}
  \]
  and
  \[
    F(x) = 1 - e^{-\lambda x}
  \]
  for $x \geq 0$, where $\lambda$ is known as the hazard rate.
  We write $X \sim \mathcal{E}(\lambda)$.

Q: Alternate definition of expectation
A: If $X$ is discrete, then
\begin{align*}
  \E[X]&=\sum_{x = 0}^\infty x \P(X = x) \\
&= \sum_{x = 0}^\infty \sum_{y = x + 1}^\infty \P(X = y) \\
&= \sum_{x = 0}^\infty \P(X > x)
\end{align*}
as we have $x$ copies of $\P(X = x)$ in the sum. \\
  If $X$ is continuous, then
  \[
    \E[X] = \int_0^\infty \P(X \geq x)\;\d x - \int_0^\infty \P(X \leq -x)\;\d x.
  \]
\begin{proof}
  \begin{align*}
    \int_0^\infty \P(X \geq x)\;\d x &= \int_0^\infty \int_x^\infty f(y)\;\d y\;\d x\\
    &= \int_0^\infty \int_0^\infty I[y\geq x]f(y)\;\d y\;\d x\\
    &= \int_0^\infty \left(\int_0^\infty I[x\leq y]\;\d x\right) f(y)\;\d y\\
    &= \int_0^\infty \left(\int_0^y \d x\right) f(y)\;\d y\\
    &= \int_0^\infty yf(y)\;\d y.
  \end{align*}
  We can similarly show that $\int_0^\infty \P(X \leq -x)\;\d x = -\int_{-\infty}^0 yf(y)\;\d y$.
\end{proof}

Q: Stochastic order
A: $X \geq_{\mathrm{st}} Y$ if $\P(X > t) \geq \P(Y > t)$ for all $t$.

Q: Joint distribution of continuous rvs
A: Two random variables $X, Y$ have \emph{joint distribution} $F: \R^2 \mapsto [0, 1]$ defined by
  \[
    F(x, y) = \P(X \leq x, Y \leq y).
  \]
  The \emph{marginal distribution} of $X$ is
  \[
    F_X(x) = \P(X \leq x) = \P(X \leq x, Y < \infty) = F(x, \infty) = \lim_{y \to \infty}F(x, y).
\]
  We say $X_1, \cdots, X_n$ are \emph{jointly distributed continuous random variables} and have \emph{joint pdf} $f$ if for any set $A\subseteq \R^n$
  \[
    \P((X_1, \cdots, X_n)\in A) = \int_{(x_1, \cdots x_n)\in A} f(x_1, \cdots, x_n)\;\d x_1\cdots \d x_n.
  \]
  where
  \[
    f(x_1, \cdots, x_n) \geq 0
  \]
  and
  \[
    \int_{\R^n} f(x_1, \cdots, x_n)\;\d x_1 \cdots \d x_n = 1.
  \]

Q: Independence for continuous rvs
A: Continuous random variables $X_1, \cdots, X_n$ are independent if
  \[
    \P(X_1\in A_1, X_2 \in A_2, \cdots, X_n\in A_n) = \P(X_1 \in A_1)\P(X_2 \in A_2) \cdots \P(X_n \in A_n)
  \]
  for all $A_i\subseteq \Omega_{X_i}$.
  If we let $F_{X_i}$ and $f_{X_i}$ be the cdf, pdf of $X$, then
  \[
    F(x_1, \cdots, x_n) = F_{X_1}(x_1)\cdots F_{X_n}(x_n)
  \]
  and
  \[
    f(x_1, \cdots, x_n) = f_{X_1}(x_1) \cdots f_{X_n}(x_n)
  \]
  are each individually equivalent to the definition above.

Q: Normal distribution
A: $X\sim N(\mu, \sigma^2)$ has pdf
  \[
    f(x) = \frac{1}{\sqrt{2 \pi}\sigma}\exp\left(-\frac{(x - \mu)^2}{2\sigma^2}\right)
  \]
  for $x\in\R$. The \emph{standard normal} is $Z\sim N(0, 1)$ where $Z = \frac{X - \mu}{\sigma}$, with pdf $\phi(z)$ and cdf $\Phi(z)$.
  \begin{align*}
    F(1)&=\int_{-\infty}^\infty \frac{1}{\sqrt{2\pi \sigma^2}} e^{-\frac{1}{2\sigma^2}(x - \mu)^2}\;\d x \\
&= \int_{-\infty}^\infty \frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}z^2}\;\d z \\
&= \sqrt{\int_{-\infty}^\infty \frac{1}{\sqrt{2\pi}} e^{-x^2/2}\;\d x\int_{\infty}^\infty \frac{1}{\sqrt{2\pi}} e^{-y^2/2}\;\d y}\\
    &= \sqrt{\int_0^\infty \int_0^{2\pi}\frac{1}{2\pi}e^{-r^2/2}r\;\d r\;\d \theta }\\
    &= 1.
  \end{align*}
\begin{align*}
  \E[X] &= \frac{1}{\sqrt{2\pi}\sigma} \int_{-\infty}^\infty x e^{-(x - \mu)^2/2\sigma^2}\;\d x\\
  &= \frac{1}{\sqrt{2\pi} \sigma}\int_{-\infty}^\infty \underbrace{(x - \mu)e^{-(x - \mu)^2/2\sigma^2}}_{\textrm{antisymm about }\mu}\;\d x + \frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^\infty \underbrace{\mu e^{-(x - \mu)^2/2\sigma^2}}_{\mu F(1)}\;\d x \\
&=\mu \\
\E[Z] &= 0 \\
\E[Z^2]&=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^\infty z^2 e^{-z^2/2} \ \d z  \\
&= \left[-\frac{1}{\sqrt{2\pi}}ze^{-z^2/2}\right]_{-\infty}^\infty + \frac{1}{\sqrt{2\pi}}\int_{-\infty}^\infty e^{-z^2/2}\;\d z \\
&=0+1 \\
&=1 \\
\var Z&=1  \\
\therefore \var X &= \sigma^2 .
\end{align*}
Also, by symmetry, the mode and median of $X$ are also both $\mu$.

Q: Transformation of a single rv
A: If $X$ is a continuous random variable with a pdf $f(x)$, and $h(x)$ is a continuous, strictly increasing function with $h^{-1}(x)$ differentiable, then $Y = h(X)$ is a random variable with cdf  $F_Y(y)=F(h^{-1}(y))$ and pdf
  \[
    f_Y(y) = f_X(h^{-1}(y))\frac{\d }{\d y}h^{-1}(y).
  \]
\begin{proof}
  \begin{align*}
    F_Y(y) &= \P(Y \leq y)\\
    &= \P(h(X) \leq y)\\
    &= \P(X \leq h^{-1}(y))\\
    &= F(h^{-1}(y))
  \end{align*}
\end{proof}
In particular, if $X=U\sim U[0, 1]$, $F\mapsto x$, $h\mapsto F^{-1}$, then for any strictly increasing distribution function $F$, the random variable $Y = F^{-1}U$ has distribution function $F$.
The condition ``strictly increasing'' can be removed if we define
\[
  F^{-1}(u) = \inf\{x: F(x)\geq u, 0 < u < 1\}.
\]
This can also be done for discrete random variables $\P(X = x_i) = p_i$ by letting
\[
  X = x_j\text{ if }\sum_{i = 0}^{j - 1}p_i \leq U < \sum_{i = 0}^j p_i,
\]
for $U\sim U[0, 1]$.

Q: Transformation of multiple rvs
A: Suppose $X_1, X_2, \cdots, X_n$ are random variables with joint pdf $f$. Let
\begin{align*}
  Y_1 &= r_1(X_1, \cdots, X_n)\\
  Y_2 &= r_2(X_1, \cdots, X_n)\\
  &\vdots \\
  Y_n &= r_n(X_1, \cdots, X_n).
\end{align*}
Let $R\subseteq \R^n$ s.t. $\P((X_1, \cdots, X_n)\in R) = 1$. Suppose the map is a bijection $R\to S$. Then
\begin{align*}
  X_1 &= s_1(Y_1, \cdots, Y_n)\\
  X_2 &= s_2(Y_1, \cdots, Y_n)\\
  &\vdots\\
  X_n &= s_n(Y_1, \cdots, Y_n).
\end{align*}
  Suppose $\frac{\partial s_i}{\partial y_j}$ exists and is continuous at every point $(y_1, \cdots, y_n)\in S$. Then the Jacobian is
  \[
    J = \frac{\partial (s_1, \cdots, s_n)}{\partial (y_1, \cdots, y_n)} =
    \det
    \begin{pmatrix}
      \frac{\partial s_1}{\partial y_1} & \cdots & \frac{\partial s_1}{\partial y_n}\\
      \vdots & \ddots & \vdots\\
      \frac{\partial s_n}{\partial y_1} & \cdots & \frac{\partial s_n}{\partial y_n}\\
    \end{pmatrix}
  \]
Take $A\subseteq \R$ and $B = r(A)$. Then
\begin{align*}
  \P((X_1, \cdots, X_n)\in A) &= \int_A f(x_1, \cdots, x_n) \;\d x_1\cdots \d x_n\\
  &= \int_B f(s_1(y_1, \cdots y_n), s_2, \cdots, s_n) |J|\;\d y_1\cdots \;\d y_n\\
  &= \P((Y_1, \cdots Y_n)\in B).
\end{align*}
So the pdf of $(Y_1, \cdots, Y_n)$ is $g(y_1, \cdots, y_n)$
  \[
    = \begin{cases} f(s_1(y_1, \cdots, y_n), \cdots s_n(y_1, \cdots, y_n))|J| &(y_1, \cdots, y_n)\in S \\ 0 &\textrm{otherwise.}\end{cases}
  \]
In particular, suppose
\[
  \mathbf{Y} = \begin{pmatrix}
    Y_1\\
    \vdots\\
    Y_n
  \end{pmatrix} = A
  \begin{pmatrix}
    X_1\\
    \vdots\\
    X_n
  \end{pmatrix} = A\mathbf{X}.
\]
Then $\mathbf{X} = A^{-1}\mathbf{Y}$. Then $\frac{\partial x_i}{\partial y_j} = (A^{-1})_{ij}$. So $|J| = |\det(A^{-1})| = |\det A|^{-1}$. So
\[
  g(y_1, \cdots, y_n) = \frac{1}{|\det A|}f(A^{-1}\mathbf{y}).
\]
If the transformation collapses dimensions, then let $Y_i=X_i$ as needed. If it expands the dimensions, then ignore the extra dependent outputs.

Q: Order statistics
A: Suppose that $X_1, \cdots, X_n$ are some random variables. Then the order statistics $Y_1, \cdots, Y_n$ are $X_1, \cdots, X_n$ arranged in increasing order, ie. $Y_1 \leq Y_2 \leq \cdots \leq Y_n$.
  We sometimes write $Y_i = X_{(i)}$.
If $(X_i)$ are iid, then the joint distribution of the order statistics is
\[
  g(y_1, \cdots y_n) = \begin{cases}n! f(y_1)\cdots f(y_n) &y_1 \leq y_2\leq \cdots \leq y_n \\ 0 &\textrm{otherwise.}
\end{cases}
\]
We have this formula because there are $n!$ combinations of $x_1, \cdots, x_n$ that produces a given order statistics $y_1, \cdots, y_n$, and the pdf of each combination is $f(y_1)\cdots f(y_n)$.

Q: Moment generating function
A: The \emph{moment generating function} of a random variable $X$ is
  \[
    m(\theta) = \E[e^{\theta X}].
  \]
  For those $\theta$ in which $m(\theta)$ is finite, we have
  \[
    m(\theta) = \int_{-\infty}^\infty e^{\theta x}f(x)\;\d x.
  \]
We assume that the mgf determines the distribution of $X$ provided $m(\theta)$ is finite for all $\theta$ in some interval containing the origin.
\begin{thm}
  The $r$th moment $X$ (i.e. $\E[X^r]$) is the coefficient of $\frac{\theta^r}{r!}$ in the power series expansion of $m(\theta)$, and is
  \[
    \E[X^r] = \left.\frac{\d ^n}{\d \theta^n}m(\theta)\right|_{\theta = 0} = m^{(n)}(0).
  \]
\end{thm}
\begin{proof}
  Recall the definition
  \[
    e^{\theta X} = 1 + \theta X + \frac{\theta^2}{2!}X^2 + \cdots.
  \]
  So
  \[
    m(\theta) = \E[e^{\theta X}] = 1 + \theta \E[X] + \frac{\theta^2}{2!}\E [X^2] + \cdots
  \]
\end{proof}

Q: MGF of a sum
A: If $X$ and $Y$ are independent random variables with mgfs $m_X(\theta), m_Y(\theta)$, then $X + Y$ has mgf $m_{X + Y}(\theta) = m_X(\theta)m_Y(\theta)$.
\begin{proof}
  \[
    \E[e^{\theta(X + Y)}] = \E[e^{\theta X}e^{\theta Y}] = \E[e^{\theta X}]\E[e^{\theta Y}] = m_X(\theta)m_Y(\theta).
  \]
\end{proof}

Q: Cauchy distribution
A: The \emph{Cauchy distribution} has pdf
  \[
    f(x) = \frac{1}{\pi(1 + x^2)}
  \]
  for $-\infty < x < \infty$.
We can check
\[
  \int_{-\infty}^\infty \frac{1}{\pi(1 + x^2)}\;\d x = \int_{-\pi/2}^{\pi/2}\frac{1}{\pi}\;\d \theta = 1
\]
with the substitution $x = \tan \theta$. The distribution is a bell-shaped curve.
  \[
    \E[X] = \int_0^\infty \frac{x}{\pi(1 + x^2)}\;\d x + \int_{-\infty}^0 \frac{x}{\pi(1 + x^2)}\;\d x = \infty - \infty
  \]
  which is undefined, but $\E[X^2] = \infty + \infty = \infty$.
Suppose $X, Y$ are independent Cauchy distributions. Let $Z = X + Y$. Then
\begin{align*}
  f(z) &= \int_{-\infty}^\infty f_X(x)f_Y(z - x)\;\d x\\
  &= \int_{-\infty}^\infty \frac{1}{\pi^2} \frac{1}{(1 + x^2)(1 + (z - x)^2)}\;\d x\\
  &= \frac{1/2}{\pi(1 + (z/2)^2)}
\end{align*}
for all $-\infty < z < \infty$ (using partial fractions).
So $\frac{1}{2}Z$ has a Cauchy distribution. By induction, we can show that $\frac{1}{n}(X_1 + \cdots + X_n)$ follows a Cauchy distribution.

Q: Gamma distribution
A: The \emph{gamma distribution} $\Gamma(n, \lambda)$ has pdf
  \[
    f(x) = \frac{\lambda^n x^{n - 1}e^{-\lambda x}}{(n - 1)!}.
  \]
The mgf is
\begin{align*}
  \E[e^{\theta X}] &= \int_0^\infty e^{\theta x} \frac{\lambda^n x^{n - 1}e^{-\lambda x}}{(n - 1)!}\;\d x\\
  &= \left(\frac{\lambda}{\lambda - \theta}\right)^n \underbrace{\int_0^\infty \frac{(\lambda - \theta)^n x^{n - 1}e^{-(\lambda - \theta)}}{(n - 1)!}\;\d x}_{F(\infty)} \\
&= \left(\frac{\lambda}{\lambda - \theta}\right)^n.
\end{align*}
For comparison, suppose $X_1, \cdots, X_n$ are iid $\mathcal{E}(\lambda)$. Let $S_n = X_1 + \cdots + X_n$. Then the mgf of $S_n$ is
\[
  \E\left[e^{\theta(X_1 + \ldots + X_n)}\right] = \E\left[e^{\theta X_1}\right]\cdots \E\left[e^{\theta X_n}\right] = \left(\E\left[e^{\theta X}\right]\right)^n = \left(\frac{\lambda}{\lambda - \theta}\right)^n.
\]
So $\Gamma(n, \lambda)$ is the sum of $n$ iid $\mathcal{E}(\lambda)$ rvs.

Q: Multivariate normal
A: Let $X_1, \cdots, X_n$ be iid $N(0, 1)$. Then their joint density is
\begin{align*}
  g(x_1, \cdots, x_n) &= \prod_{i = 1}^n \phi(x_i) \\
  &= \prod_{1}^n\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x_i^2}\\
  &= \frac{1}{(2\pi)^{n/2}} e^{-\frac{1}{2}\sum_1^n x_i^2}\\
  &= \frac{1}{(2\pi)^{n/2}}e^{-\frac{1}{2}\mathbf{x}^T \mathbf{x}},
\end{align*}
where $\mathbf{x} = (x_1, \cdots, x_n)^T$. Suppose we are interested in
\[
  \mathbf{Z} = \boldsymbol\mu + A\mathbf{X},
\]
where $A$ is an invertible $n\times n$ matrix. Then
\[
  \mathbf{X} = A^{-1}(\mathbf{Z} - \boldsymbol\mu)
\]
and
\[
  |J| = |\det (A^{-1})| = \frac{1}{\det A}
\]
So
\begin{align*}
  f(z_1, \cdots, z_n) &= \frac{1}{(2\pi)^{n/2}}\frac{1}{\det A}\exp\left[-\frac{1}{2}\big((A^{-1}(\mathbf{z} - \boldsymbol\mu))^T(A^{-1}(\mathbf{z} - \boldsymbol\mu))\big)\right]\\
  &= \frac{1}{(2\pi)^{n/2}\det A}\exp\left[-\frac{1}{2}(\mathbf{z} - \mu)^T \Sigma^{-1}(\mathbf{z} - \boldsymbol\mu)\right]\\
  &= \frac{1}{(2\pi)^{n/2}\sqrt{\det \Sigma}}\exp\left[-\frac{1}{2}(\mathbf{z} - \boldsymbol\mu)^T \Sigma^{-1}(\mathbf{z} - \boldsymbol\mu)\right].
\end{align*}
where $\Sigma = AA^T$ is the covariance matrix. We say
\[
  \mathbf{Z} =
  \begin{pmatrix}
    Z_1\\
    \vdots\\
    Z_n
  \end{pmatrix}
  \sim MUN(\boldsymbol\mu, \Sigma)\text{ or }N(\boldsymbol\mu, \Sigma).
\]
We have
\begin{align*}
  \E[(Z - \mu)(Z - \mu)^T] &= \E[AX(AX)^T]\\
  &= \E(AXX^TA^T) = A\E[XX^T]A^T\\
  &= AIA^T\\
  &= AA^T \\
  &= \Sigma,
\end{align*}
so $\cov(Z_i, Z_j)=\Sigma_{ij}$. Now suppose $(Z_i)$ have covariances $0$. Then $\Sigma = \diag(\sigma_1^2, \cdots, \sigma_n^2)$. Then
\[
  f(z_1, \cdots, z_n) = \prod_1^n \frac{1}{\sqrt{2\pi}\sigma_i} e^{-\frac{1}{2\sigma_i^2}(z_i - \mu_i)^2}.
\]
So $(Z_i)$ are independent, with $Z_i\sim N(\mu_i, \sigma_i^2)$.
The multivariate mgf is defined as
\[
  m(\boldsymbol\theta) = \E[e^{\boldsymbol\theta^T \mathbf{X}}] = \E[e^{\theta_1 X_1 + \cdots + \theta_n X_n}].
\]

Q: Central limit theorem
A: \begin{thm}[Continuity theorem]
  If the random variables $X_1, X_2, \cdots$ have mgfs $m_1(\theta), m_2(\theta), \cdots$ and $m_n(\theta) \to m(\theta)$ as $n\to\infty$ for all $\theta$, then $X_n \to_D $ the random variable with mgf $m(\theta)$.
\end{thm}
Let $X_1, X_2, \cdots$ be iid random variables with $\E[X_i] = \mu$, $\var(X_i) = \sigma^2 < \infty$. Define
  \[
    S_n = X_1 + \cdots + X_n.
  \]
  Then for all finite intervals $(a, b)$,
  \[
    \lim_{n \to \infty}\P\left(a \leq \frac{S_{n} - n\mu}{\sigma\sqrt{n}} \leq b\right) = \int_a^b \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}t^2}\;\d t.
  \]
We say it tends to normal in distribution
  \[
    \frac{S_n - n\mu}{\sigma\sqrt{n}} \to_{D} N(0, 1).
  \]
\begin{proof}[Sketch of proof of CLT]
  wlog, assume $\mu = 0, \sigma^2 = 1$ (otherwise replace $X_i$ with $\frac{X_i - \mu}{\sigma}$).
  Then
  \begin{align*}
    m_{X_i}(\theta) &= \E[e^{\theta X_i}] = 1 + \theta \E[X_i] + \frac{\theta^2}{2!} \E[X_i^2] + \cdots\\
    &=1 + \frac{1}{2}\theta^2 + \frac{1}{3!}\theta^3 \E[X_i^3] + \cdots
  \end{align*}
  Now consider $S_n/\sqrt{n}$. Then
  \begin{align*}
    \E[e^{\theta S_n/\sqrt{n}}] &= \E[e^{\theta(X_1 + \ldots + X_n)/\sqrt{n}}]\\
    &= \E[e^{\theta X_1/\sqrt{n}}] \cdots \E[e^{\theta X_n/\sqrt{n}}]\\
    &= \left(\E[e^{\theta X_1/\sqrt{n}}]\right)^n\\
&=m_{X_i}(\theta / \sqrt{n}) \\
    &= \left(1 + \frac{1}{2}\theta^2 \frac{1}{n} + \frac{1}{3!}\theta^3 \E[X^3]\frac{1}{n^{3/2}} + \cdots\right)^{n}\\
    &\to e^{\frac{1}{2}\theta^2}
  \end{align*}
  as $n \to \infty$ since $(1 + a/n)^n \to e^a$. And this is the mgf of the standard normal. So the result follows from the continuity theorem.
\end{proof}
In particular, if $X_i \sim B(1, p)$, then $S_n \sim B(n, p)$. So $\E[S_n] = np$ and $\var (S_n) = p(1 - p)$. So
\[
  \frac{S_n - np}{\sqrt{np(1 - p)}} \to_D N(0, 1).
\]

Q: Useful tools
A: Finding probabilities: Complementary event, partition of disjoint events, union of other events, IE formula.
Finding $\E[N]$: write as the sum of known number of indicators, then take expectations.
Bounds on probability: use inequality.
Sum of indepedent rvs: use gfs.
Finding $\E[X]$: use tower property.
Use special properties of distributions.
Prove indepence of continuous rvs: guess factorisation of joint pdf.
Jacobian: compute $J^{-1}$.