\documentclass{beamer}
\usetheme{default}

\usepackage{amsmath,amssymb}

\title{Probability Review}

\begin{document}

\maketitle

\begin{frame}
  \frametitle{Basics}
  \textcolor{red}{Probabilisty space \(\Omega\)} \pause
  \begin{itemize}
    \item \textcolor{red}{finite set} (Or at most \textcolor{red}{countable} for us.) \pause
    \item with a \textcolor{red}{measure~\(\Pr\colon \Omega \to \mathbb{R}^+\)} satisfying: \pause
    \begin{itemize}
      \item \(\forall \omega \in \Omega \colon \Pr[\omega] \ge 0\) \pause
      \item \(\sum_{\omega \in \Omega} \Pr[\omega] = 1\). \pause
    \end{itemize}
  \end{itemize}

  \textcolor{red}{Event \(A \subseteq \Omega\)} has~\(\Pr[A] = \sum_{\omega \in A} \Pr[\omega]\). \pause

  \textcolor{red}{Union bound.} Let~\(A_1, \ldots,A_m\) be events. Then
  \[
    \Pr[\bigcup_{i = 1}^m A_i] \le \sum_{i = 1}^m \Pr[A_i].
  \] \pause
\end{frame}

\begin{frame}
  \frametitle{Exercise}
  Let~\(\mathcal{S} \subseteq 2^{\{1, 2, \ldots, n\}}\) (i.e.~subsets of~\(\{1, 2, \ldots, n\}\)).
  A \textcolor{red}{2-coloring} of~\(\{1, 2, \ldots, n\}\) is any function~\(f \colon \{1, 2, \ldots, n\} \to \{\mathrm{red}, \mathrm{blue}\}\).
  Show that if~\(\forall S \in \mathcal{S}\):
  \begin{itemize}
    \item \(\forall S \in \mathcal{S}\colon |S| = k\) (assume~\(n > k\)), and
    \item \(|\mathcal{S}| < 2^{k - 1}\),
  \end{itemize}
  then there exists a 2-coloring of~\(\{1, 2, \ldots, n\}\) such that no~\(S \in \mathcal{S}\) is monochromatic.
\end{frame}
    
\begin{frame}
  \frametitle{Conditional probability}

  The probability of event~\(A\) \textcolor{red}{conditioned on event~\(B\)}, denoted~\(\Pr[A | B]\) is
  \[
    \Pr[A | B] = \frac{\Pr[A \cap B]}{\Pr[B]}.
  \]
  \pause

  Event~\(A\) is \textcolor{red}{independent} from event~\(B\) if~\(\Pr[A | B] = \Pr[A]\). \pause
  \begin{itemize}
    \item This implies~\(\Pr[A \cap B] = \Pr[A]\Pr[B]\). \pause
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Exercise}
  Alice and Bob are throwing darts at a target.
  Alice has a chance~\(1/3\) of hitting the target, and Bob has chance~\(1/4\) of doing the same.
  What is the chance Alice hits the target \textcolor{red}{given that at least one of them hit it}?
\end{frame}

\begin{frame}

  Events~\(A_1, \ldots, A_m\) are \textcolor{red}{mutually independent} if for all~\(I \subseteq \{1, 2, \ldots, m\}\):
  \[
    \Pr[\cap_{i \in I} A_i] = \Pi_{i \in I} \Pr[A_i].
  \] \pause

  \textcolor{red}{Chain rule}
  \[
    \Pr[\cap_{i = 1}^m A_i] = \Pi_{i = 1}^m \Pr[A_i | A_{i - 1} \cap A_{i - 2} \cap \cdots \cap A_1].
  \]
\end{frame}

\begin{frame}
  \frametitle{Random variables}

  \begin{itemize}
    \item A \textcolor{red}{random variable~\(X\)} is a measurable function~\(X \colon \Omega \to \mathbb{R}\). \pause
    \item \textcolor{red}{Example.} For a~\(t \in \mathbb{R}\), ``\(X \ge t\)'' is the event~\(\{\omega \in \Omega \colon X(\omega) \ge t\}\). \pause
    \item A random variable~\(X\) is \textcolor{red}{independent of event~\(A\)} if~\(\forall S \subseteq \mathbb{R}: \Pr[X \in S | A] = \Pr[X \in S]\). \pause
    \item Random variables~\(X, Y\) are \textcolor{red}{independent} if~\(\forall S, T \subseteq \mathbb{R}\), ``\(X \in S\)'' and~``\(Y \in T\)'' are independent events.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Expectation}
  \begin{itemize}
    \item \textcolor{red}{Expectation} of a random variable~\(X\) is~\(\mathbb{E}[X] = \sum_{\omega \in \Omega} X(\omega) \Pr[\omega]\). \pause
    \item \textcolor{red}{Linearity of expectation.} For random variables (not necessarily independent!!!!) \(X_1, \ldots, X_m\) and~\(\lambda_1, \ldots, \lambda_m \in \mathbb{R}\) we have
      \[
        \mathbb{E}[\lambda_1 X_1 + \cdots + \lambda_m X_m] = \sum_{i = 1}^m \lambda_i \mathbb{E}[X].
      \] \pause
    \item If~\(X, Y\) are independent random variables then~\(\mathbb[E]{XY} = \mathbb[E]{X} \mathbb[E]{Y}\). \pause
      \begin{itemize}
        \item \textcolor{red}{Homework.} Is the converse true? \pause
      \end{itemize}
    \item For an integer random variable~\(X \colon \Omega \to \mathbb{N}_0\), we have~\(\mathbb{E}[X] = \sum_{k = 0}^\infty \Pr[X \ge k]\).
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Exercise}
  
  \begin{block}{Exercise}
    Suppose we keep tossing a biased coin where a heads lands with probability~\(p\) and tails land with probability~\(1 - p\).
    What is the expected number of tosses until we get the first heads.
  \end{block} \pause

  \begin{block}{Exercise}
  Shuffle a deck of cards and start revealing cards one by one.
  What is the expected number of cards until we reveal the first ace?
  \end{block} \pause

  \begin{block}{Exercise}
    Suppose that we are looking with our perfect vision at the Pentagon at from an angle which is uniformly random.
    What is the expected number of sides of the Pentagon that we see?
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Markov's and Chebyshev's inequality}

  \begin{block}{Markov's inequality}
    Let~\(X\colon \Omega \to \mathbb{R}^+\) be a positive random variable.
    Then for any~\(t > 0\) we have
    \[
      \Pr[X \ge t] \le \mathbb{E}[X] / t.
    \]
  \end{block}
  \pause

  \begin{block}{Variance}
    \textcolor{red}{Variance} of a random variable~\(X\) is~\(\mathsf{Var}[X] = \mathbb{E}[(X - \mathbb{E}[X])^2]\). \pause
    \begin{itemize}
      \item Can be computed as~\(\mathbb{E}[X^2] - \mathbb{E}[X]^2\). \pause
      \item \(c \in \mathbb{R}\), \(\mathsf{Var}[cX] = c^2\mathsf{Var}[X]\). \pause
      \item For mutually independent~\(X_1, \ldots, X_m\), \(\mathsf{Var}[X_1 + \cdots + X_m] = \sum_{k = 1}^m \mathsf{Var}[X_k]\). \pause
    \end{itemize}
  \end{block}

  \begin{block}{Chebyshev's inequality}
    Let~\(X\) be a random variable.
    For any~\(t \in \mathbb{R}^+\)
    \[
      \Pr[|X - \mathbb{E}[X]| \ge t] \le \mathsf{Var}[X] / t^2.
    \]
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Chernoff bounds}

  Let~\(X_1, \ldots, X_n\) be \textcolor{red}{independent 0/1} random variables satisfying~\(\Pr[X_i = 1] = p\) for some~\(p \le 1/2\).
  Let~\(X = \sum_{i = 1}^n X_i\) and~\(\mu = \mathbb{E}[X] = np\). \pause
  \begin{itemize}
    \item \textcolor{red}{Small-deviation bound.} \(\Pr[X \ge \mu + k\sqrt{\mu}] = 2^{-\Theta(k^2)}\) for any~\(k = \mathcal{O}(\sqrt{\mu})\) satisfying~\(k\sqrt{\mu} \le n\). \pause
    \item \textcolor{red}{Large-deviation bound.} \(\Pr[X \ge \mu + r\mu] = \Theta(r)^{-\Theta(r\mu)}\) for any~\(r \ge 1\) satisfying~\(\mu + r\mu \le n\). \pause
  \end{itemize}

  \begin{block}{Proof}
    On the board.
  \end{block}
\end{frame}

\end{document}
