Expectation

Expectation is the Lebesgue integral against $P$, and every property of it is a property of the integral proved in lebesgue-integral.md. What this page adds is the probabilistic layer: the change-of-variables formula that lets one compute with laws instead of sample spaces, the standard inequalities, the transform methods (moment- and characteristic functions) that drive the central limit theorem, and the concentration bounds that make randomized algorithms work (complexity-theory.md §7).

References: Williams, Probability with Martingales, ch. 5–6; Durrett, Probability, §1.6, 3.3; Boucheron–Lugosi–Massart, Concentration Inequalities.

1. Definition

Definition. For a random variable $X$ on $(\Omega ,\mathcal{F},P)$,

$$E[X]:={\int }_{\Omega }XdP,$$

defined whenever the Lebesgue integral is: always for $X\ge 0$ (value in $[0,\infty ]$), and for general $X$ when $E|X|<\infty$, i.e. $X\in L^1(P)$.

The convergence theorems transfer verbatim and are used under their probabilistic names:

• Monotone convergence. $0\le X_k\uparrow X⟹E[X_k]\uparrow E[X]$.
• Fatou. $E[\mathrm{liminf}{X}_k]\le \mathrm{liminf}E[X_k]$ for $X_k\ge 0$.
• Dominated convergence. $X_k\to X$ a.s., $|X_k|\le Y$ with $E[Y]<\infty$ $⟹E[X_k]\to E[X]$.
• Bounded convergence. The special case $|X_k|\le c$ — available here but not in general measure theory, because $P(\Omega )=1$ makes constants integrable.

That last item is the one genuine simplification probability enjoys: on a probability space, $L^{\infty }\subseteq L^p\subseteq L^1$ for all $p$, and $\Vert X{\Vert }_p$ is non-decreasing in $p$ (Jensen). Nothing of the sort holds on $\mathbb{R}$ with ${\lambda }^1$.

2. Computing with the Law

Theorem (change of variables). For Borel $g:\mathbb{R}\to \mathbb{R}$ with $g\ge 0$ or $g(X)\in L^1$,

$$E[g(X)]={\int }_{\Omega }g(X(\omega ))dP(\omega )={\int }_{\mathbb{R}}g(x)d{P}_X(x).$$

Proof. True for $g=1_B$ by the definition of the pushforward $P_X(B)=P(X\in B)$; extend by linearity to simple $g$, by monotone convergence to $g\ge 0$, and by decomposition to general $g$. $\square$

This is why the sample space disappears (random-variables.md §5). In the two standard cases:

$$E[g(X)]=\sum _{k}g(x_k)P(X=x_k)\text{(discrete)},E[g(X)]={\int }_{\mathbb{R}}g(x)p(x)dx\text{(density }p).$$

Both are instances of one theorem, which is the practical dividend of the measure-theoretic definition: elementary treatments need two separate theories.

Tail formula (layer cake). For $X\ge 0$, $$E[X]={\int }_0^{\infty }P(X>t)dt,$$ from Tonelli applied to $1_{\{t<X(\omega )\}}$ on $\Omega \times >(0,\infty )$ (product-measures.md §3). For integer-valued $X\ge 0$ this reads $E[X]={\sum }_{k\ge 1}P(X\ge k)$.

3. Moments and Variance

Definitions. The $k$-th moment is $E[X^k]$; the variance is $\mathrm{Var}(X)=E[(X-EX{)}^2]=E[X^2]-(EX{)}^2$; the covariance is $\mathrm{Cov}(X,Y)=E[XY]-E[X]E[Y]$.

$L^2$ is a Hilbert space (hilbert-spaces.md), and covariance is its inner product on centred variables. This is not an analogy: uncorrelated means orthogonal, $\mathrm{Var}$ is the squared norm, and bilinearity plus Pythagoras gives

$$\mathrm{Var}\left(\sum _{i=1}^n{X}_i\right)=\sum _{i=1}^n\mathrm{Var}(X_i)\text{for uncorrelated }{X}_i.$$

The geometric reading pays off again in conditional-expectation.md, where conditioning is literally orthogonal projection.

Moments need not exist. The Cauchy law has no mean; the $t$-distribution with 2 degrees of freedom has a mean but no variance. Finiteness of moments is a real hypothesis, and the limit theorems say exactly which ones they need.

4. Inequalities

Markov. For $X\ge 0$ and $t>0$: $P(X\ge t)\le \frac{E[X]}{t}$.

Proof. $t{1}_{\{X\ge t\}}\le X$; take expectations. $\square$

Everything else in this section is Markov applied to a cleverly chosen function.

Chebyshev. $P(|X-EX|\ge t)\le \frac{\mathrm{Var}(X)}{t^2}$ — Markov applied to $(X-EX{)}^2$.

Jensen. For convex $\phi$ with $X,\phi (X)\in L^1$: $\phi (E[X])\le E[\phi (X)]$.

Proof. A convex function has a supporting line at $E[X]$: $\phi (x)\ge \phi (EX)+c(x-EX)$; take expectations. $\square$

Jensen gives $|EX|\le E|X|$, the monotonicity of $L^p$ norms, and the arithmetic–geometric mean inequality as special cases.

Cauchy–Schwarz. $|E[XY]|\le \Vert X{\Vert }_2\Vert Y{\Vert }_2$, with equality iff $X,Y$ are a.s. proportional — the $L^2$ inner-product inequality (lebesgue-integral.md §8), whence $|\mathrm{Cov}(X,Y)|\le {\sigma }_X{\sigma }_Y$ and the correlation coefficient lies in $[-1,1]$.

5. Generating Functions and Characteristic Functions

Definitions. The moment generating function is $M_X(t)=E[e^{tX}]$ (possibly $+\infty$), and the characteristic function is

$${\phi }_X(t)=E\left[e^{itX}\right]={\int }_{\mathbb{R}}{e}^{itx}d{P}_X(x),$$

i.e. the Fourier transform of the law.

${\phi }_X$ is defined for every law and every $t$ — $|e^{itX}|=1$, so the integral converges absolutely — which is exactly why it, and not $M_X$, is the right tool. It is uniformly continuous, ${\phi }_X(0)=1$, $|{\phi }_X|\le 1$, and ${\phi }_{aX+b}(t)=e^{itb}{\phi }_X(at)$.

Uniqueness / inversion (Lévy). ${\phi }_X$ determines $P_X$. If ${\phi }_X\in L^1$, the law has a bounded continuous density $p(x)=\frac{1}{2\pi }\int e^{-itx}{\phi }_X(t)dt$.

Independence. $X\perp Y⟹{\phi }_{X+Y}={\phi }_X{\phi }_Y$ (independence.md §4). Convolution of laws becomes multiplication of transforms.

Moments. If $E|X{|}^n<\infty$ then ${\phi }_X$ is $n$ times differentiable and ${\phi }_X^{(k)}(0)=i^{k}E[X^k]$ — so a Taylor expansion of ${\phi }_X$ near $0$ encodes the low-order moments, which is precisely how the CLT proof extracts a Gaussian.

Lévy continuity theorem. $X_k\Rightarrow X$ (in distribution) $⟺$ ${\phi }_{X_k}(t)\to {\phi }_X(t)$ pointwise, provided the limit is continuous at $0$. This converts a statement about measures into a statement about ordinary functions and is the engine of the CLT.

The moment problem is the caveat on the parallel theory of moments: a law is not in general determined by its moments (the lognormal has moment-identical companions). Determinacy needs a growth condition — e.g. Carleman's, or finiteness of $M_X$ near $0$. Characteristic functions have no such defect.

6. Concentration

Chebyshev gives decay $t^{-2}$; for sums of bounded independent variables the truth is exponential, and the improvement is what makes randomized computation practical.

Chernoff method. For any $\lambda >0$, $$P(S\ge t)=P(e^{\lambda S}\ge e^{\lambda t})\le e^{-\lambda t}E\left[e^{\lambda S}\right],$$ then optimize over $\lambda$. Markov plus the MGF.

Hoeffding's inequality. Let $X_1,\dots ,X_n$ be independent with $a_i\le X_i\le b_i$ a.s., and $S={\sum }_i{X}_i$. Then for $t>0$

$$P(|S-E[S]|\ge t)\le 2\exp \left(\frac{-2t^2}{{\sum }_i(b_i-a_i{)}^2}\right).$$

Proof sketch. Hoeffding's lemma bounds $E[e^{\lambda (X_i-E{X}_i)}]\le e^{{\lambda }^2(b_i-a_i{)}^2/8}$ by convexity; independence multiplies the MGFs (§5); optimize $\lambda$ in the Chernoff bound. $\square$

Chernoff bound for Bernoulli sums. If $S\sim \mathrm{Bin}(n,p)$ with $\mu =np$, then $P(S\ge (1+\delta )\mu )\le e^{-{\delta }^2\mu /(2+\delta )}$ and $P(S\le (1-\delta )\mu )\le e^{-{\delta }^2\mu /2}$.

Amplification — the complexity-theory use. A $\mathsf{BPP}$ machine accepts with probability $\ge 2/3$ on yes-instances and $\le 1/3$ on no-instances (complexity-theory.md §7). Run it $n$ times independently and take the majority: the number of correct runs is a sum of i.i.d. Bernoulli$(2/3)$ variables, and Hoeffding with $t=n/6$ bounds the probability of a wrong majority by $2e^{-n/18}$. So $\mathrm{poly}(n)$ repetitions drive the error to $2^{-\mathrm{poly}(n)}$, which is why the constant $2/3$ in the definition of $\mathsf{BPP}$ is arbitrary. That is the whole content of "the error can be amplified".

The distinction to keep: Chebyshev needs only a variance and is tight for heavy-tailed variables; exponential bounds need boundedness (or a sub-Gaussian / sub-exponential tail hypothesis) and are what fail for the Cauchy law.

7. Where This Is Used

• Modes of convergence and laws of large numbers — Chebyshev gives the weak law in three lines.
• The central limit theorem — §5's characteristic functions and the continuity theorem.
• Conditional expectation — the $L^2$ geometry of §3.
• Computational complexity theory — §6's amplification.