Prerequisites & Notation

Before You Begin

Probability inequalities convert moment information into tail probability bounds. Before we begin, make sure you are comfortable with the following building blocks from earlier chapters.

Expectation, variance, and the law of the unconscious statistician (LOTUS)(Review FSP Ch. 4)
Self-check: Can you compute $\mathbb{E}[g(X)]$ directly from the PMF or PDF of $X$ without finding the distribution of $g(X)$ ?
Moment generating function $M_X(t) = \mathbb{E}[e^{tX}]$ and its basic properties(Review FSP Ch. 9)
Self-check: Can you write the MGF of $X \sim \mathcal{N}(\mu, \sigma^2)$ from memory?
Indicator functions and the identity $\mathbb{P}(A) = \mathbb{E}[I_A]$ (Review FSP Ch. 4)
Self-check: Can you express the tail probability $\mathbb{P}(X \geq a)$ as the expectation of an indicator?
Convex and concave functions
Self-check: Can you verify that $g(x) = e^x$ is convex and $g(x) = \log x$ is concave using second derivatives?
Independence of random variables and the product rule for expectations(Review FSP Ch. 3)
Self-check: If $X_1, \ldots, X_n$ are independent, what is $\mathbb{E}[\prod_{i=1}^n e^{t X_i}]$ ?

Notation for This Chapter

Symbols introduced or heavily used in this chapter. Where possible, notation tokens $\ntn{key}$ are used so the reader can customize display.

Symbol	Meaning	Introduced
$\mathbb{E}[X]$	Expectation of random variable $X$
$\text{Var}(X)$	Variance of $X$	s02
$M_X(t)$	Moment generating function $\mathbb{E}[e^{tX}]$	s03
$I_A$	Indicator of event $A$	s01
$\sigma^2$	Variance $\text{Var}(X)$
$\mu$	Mean $\mathbb{E}[X]$
$\\bar{X}_n$	Sample mean $\frac{1}{n}\sum_{i=1}^n X_i$	s04
$\\mathcal{N}(\\mu, \\sigma^2)$	Gaussian distribution with mean $\mu$ and variance $\sigma^2$
$D(P \\\| Q)$	Kullback-Leibler divergence	s05

← Ch 9 Markov's Inequality