Chapter 2 · Distributions and Limit Theorems

2.2 Characteristic Functions and Probability Inequalities

Two toolkits that make the limit theorems possible: the characteristic function $E[e^{itX}]$, which exists for every random variable, turns independent sums into products and detects convergence in distribution; and the inequalities of Markov, Chebyshev, Cantelli, Jensen, Cauchy–Schwarz and Hölder, which bound probabilities and moments when the law itself is unknown.

The moment generating function of §1.3 is a powerful tool, but it has a serious defect: $E[e^{tX}]$ is often infinite. The Cauchy law, the lognormal law, Student's $t$ and every law with a polynomial tail have no mgf, so the mgf cannot prove anything about them. The remedy is to put an $i$ in the exponent. Since $|e^{itX}|=1$, the characteristic function $\varphi_X(t)=E[e^{itX}]$ exists for every random variable and every real $t$. It keeps all the good properties of the mgf: it determines the law, it turns sums of independent variables into products, its derivatives at $0$ give the moments, and, through Lévy's continuity theorem, its pointwise convergence is exactly convergence in distribution. These are the facts on which the proofs of the weak law of large numbers and the central limit theorem in §2.3 rest.

The second half of the section collects the classical probability inequalities. Markov's and Chebyshev's inequalities bound a tail probability using one or two moments only, so they hold for every law with those moments. Cantelli's inequality is their sharp one-sided form, and the Chernoff bound uses the whole mgf. Jensen's inequality compares $E[g(X)]$ with $g(E[X])$ for convex $g$, and the Cauchy–Schwarz and Hölder inequalities bound expectations of products. CSIR Part B questions ask for the value of a bound or a moment read off a characteristic function. Part C questions ask whether a given function is a characteristic function, whether a bound holds for all laws, or which way an inequality goes, so the sharpness examples and counterexamples matter as much as the inequalities themselves.

Characteristic Functions: Definition and Basic Properties

A complex random variable $W=U+iV$ (with $U,V$ real random variables) has expectation $E[W]=E[U]+iE[V]$ whenever $E|W|\lt\infty$. Expectation is then linear over $\mathbb{C}$, and $|E[W]|\le E|W|$: write $E[W]=re^{i\theta}$ with $r\ge0$; then $r=E[e^{-i\theta}W]=E\left[\operatorname{Re}(e^{-i\theta}W)\right]\le E|W|$.

📘 Definition 2.8 — Characteristic function

The characteristic function (cf) of a random variable $X$ is $$\varphi_X(t)=E\left[e^{itX}\right]=E[\cos tX]+i\,E[\sin tX],\qquad t\in\mathbb{R}.$$ If $X$ has density $f$, then $\varphi_X(t)=\int e^{itx}f(x)\,dx$ (the Fourier transform of $f$); if $X$ has pmf $p$, then $\varphi_X(t)=\sum_xe^{itx}p(x)$. For a random vector $\mathbf{X}=(X_1,\dots,X_d)$ the joint characteristic function is $\varphi_{\mathbf{X}}(\mathbf{t})=E\left[e^{i(t_1X_1+\dots+t_dX_d)}\right]$, $\mathbf{t}\in\mathbb{R}^d$.

When the mgf $M_X$ is finite near $0$, $\varphi_X(t)=M_X(it)$ in the sense of analytic continuation, so cfs can often be read off mgfs by replacing $t$ with $it$. For integer-valued $X$ with pgf $G_X$, $\varphi_X(t)=G_X(e^{it})$.

📐 Theorem 2.17 — Basic properties of a characteristic function

Let $\varphi=\varphi_X$. Then:

  1. $\varphi(t)$ exists for every real $t$, $\varphi(0)=1$ and $|\varphi(t)|\le1$;
  2. $\varphi(-t)=\overline{\varphi(t)}$;
  3. $\varphi$ is uniformly continuous on $\mathbb{R}$;
  4. $\varphi_{aX+b}(t)=e^{ibt}\varphi_X(at)$ for real constants $a,b$;
  5. $\varphi$ is real-valued if and only if $X$ is symmetric about $0$, that is, $X$ and $-X$ have the same law;
  6. $\varphi$ is non-negative definite: for all $n$, real $t_1,\dots,t_n$ and complex $z_1,\dots,z_n$, $\displaystyle\sum_{j=1}^n\sum_{k=1}^n\varphi(t_j-t_k)\,z_j\overline{z_k}\ge0$.

Proof. (1) $|e^{itX}|=1$, so $e^{itX}$ is integrable and $|\varphi(t)|\le E|e^{itX}|=1$. Also $\varphi(0)=E[1]=1$.

(2) $\varphi(-t)=E[\cos(-tX)]+iE[\sin(-tX)]$. Since $\cos$ is even and $\sin$ is odd, this equals $E[\cos tX]-iE[\sin tX]=\overline{\varphi(t)}$.

(3) For all $t$ and $h$, $$|\varphi(t+h)-\varphi(t)|=\left|E\left[e^{itX}\left(e^{ihX}-1\right)\right]\right|\le E\left|e^{ihX}-1\right|.$$ The right side does not depend on $t$. As $h\to0$, $|e^{ihX}-1|\to0$ pointwise and is bounded by $2$, so it tends to $0$ by dominated convergence.

(4) $E\left[e^{it(aX+b)}\right]=e^{ibt}E\left[e^{i(at)X}\right]$.

(5) If $X$ and $-X$ have the same law, then $\varphi(t)=\varphi_{-X}(t)=\varphi(-t)=\overline{\varphi(t)}$, so $\varphi(t)$ is real. Conversely, if $\varphi$ is real, then $\varphi_{-X}(t)=\varphi(-t)=\overline{\varphi(t)}=\varphi(t)$ for all $t$, and the uniqueness theorem (Theorem 2.22 below) gives $-X\overset{d}{=}X$.

(6) Expanding the square of a modulus, $$\sum_{j,k}\varphi(t_j-t_k)z_j\overline{z_k}=E\Big[\sum_{j,k}z_je^{it_jX}\,\overline{z_ke^{it_kX}}\Big]=E\Big|\sum_jz_je^{it_jX}\Big|^2\ge0.$$ ∎

Property (6) is the heart of the matter. Bochner's theorem (statement only) says that a function $\varphi:\mathbb{R}\to\mathbb{C}$ is the cf of some random variable if and only if it is continuous, satisfies $\varphi(0)=1$ and is non-negative definite. Checking (6) directly is rarely practical, so in exercises one uses the necessary conditions (1)–(5), the moment test of Theorem 2.19(3), the inversion formula, or Pólya's sufficient condition (Theorem 2.24).

📐 Theorem 2.18 — Characteristic functions of independent sums
  1. If $X$ and $Y$ are independent, then $\varphi_{X+Y}(t)=\varphi_X(t)\,\varphi_Y(t)$ for all $t$. Hence if $X_1,\dots,X_n$ are independent, $\varphi_{X_1+\dots+X_n}=\prod_j\varphi_{X_j}$, and for iid $X_j$ with common cf $\varphi$, $$\varphi_{S_n}(t)=\varphi(t)^n,\qquad \varphi_{\bar X_n}(t)=\varphi\!\left(\tfrac tn\right)^n.$$
  2. $X_1,\dots,X_d$ are independent if and only if their joint cf factorises: $\varphi_{\mathbf{X}}(t_1,\dots,t_d)=\prod_j\varphi_{X_j}(t_j)$ for all $(t_1,\dots,t_d)$ (the "if" part uses the uniqueness theorem for random vectors, which we state without proof).

Proof. (1) Write $e^{itX}=U_1+iV_1$ and $e^{itY}=U_2+iV_2$, where $U_1=\cos tX$, $V_1=\sin tX$ are functions of $X$ and $U_2,V_2$ are functions of $Y$. They are bounded, and by independence $E[U_1U_2]=E[U_1]E[U_2]$, and similarly for the other three products (Theorem 1.34 of §1.4). Expanding, $$E\left[e^{it(X+Y)}\right]=E[(U_1+iV_1)(U_2+iV_2)]=(E U_1+iE V_1)(E U_2+iE V_2)=\varphi_X(t)\varphi_Y(t).$$ Induction gives the product for $n$ variables, and $\varphi_{\bar X_n}(t)=\varphi_{S_n}(t/n)$ by Theorem 2.17(4).

(2) If the $X_j$ are independent, the same argument applied to $e^{it_1X_1}\cdots e^{it_dX_d}$ gives the factorisation. Conversely, if the joint cf factorises, it equals the joint cf of a vector with the same marginals and independent components; by uniqueness the two vectors have the same joint law, so the $X_j$ are independent. ∎

Note carefully what (1) does not say. The identity $\varphi_{X+Y}=\varphi_X\varphi_Y$ for the cf of the sum alone does not imply independence; only the factorisation of the joint cf in (2) does. The ⚠️ box gives a counterexample with Cauchy variables.

📐 Theorem 2.19 — Moments and the Taylor expansion of a characteristic function
  1. (Expansion inequality) For real $x$ and $n=0,1,2,\dots$, $$\left|e^{ix}-\sum_{k=0}^n\frac{(ix)^k}{k!}\right|\le\min\left(\frac{|x|^{n+1}}{(n+1)!},\ \frac{2|x|^n}{n!}\right).$$
  2. If $E|X|^n\lt\infty$, then $\varphi$ has continuous derivatives up to order $n$, $\varphi^{(k)}(t)=i^kE\left[X^ke^{itX}\right]$, so $\varphi^{(k)}(0)=i^kE[X^k]$ for $k\le n$, and $$\varphi(t)=\sum_{k=0}^n\frac{(it)^k}{k!}E[X^k]+o(|t|^n)\qquad(t\to0).$$ In particular, if $E[X]=0$ and $E[X^2]=\sigma^2$, then $\varphi(t)=1-\tfrac12\sigma^2t^2+o(t^2)$.
  3. (Converse for second moments) If $\varphi$ is twice differentiable at $0$, then $E[X^2]\lt\infty$ and $E[X^2]=-\varphi''(0)$. (More generally, a finite derivative of even order $2m$ at $0$ forces $E[X^{2m}]\lt\infty$.)

Proof. (1) Integration by parts gives, for $n\ge0$, $$\int_0^x(x-s)^ne^{is}ds=\frac{x^{n+1}}{n+1}+\frac{i}{n+1}\int_0^x(x-s)^{n+1}e^{is}ds.$$ Starting from $e^{ix}=1+i\int_0^xe^{is}ds$ and applying this repeatedly, we get by induction $$e^{ix}-\sum_{k=0}^n\frac{(ix)^k}{k!}=\frac{i^{n+1}}{n!}\int_0^x(x-s)^ne^{is}ds.$$ Since $|e^{is}|=1$, the modulus of the right side is at most $\frac{1}{n!}\left|\int_0^x|x-s|^nds\right|=\frac{|x|^{n+1}}{(n+1)!}$. For the second bound (with $n\ge1$), subtract the $n$-th term from the remainder of order $n-1$: since $\frac{i^n}{(n-1)!}\int_0^x(x-s)^{n-1}ds=\frac{(ix)^n}{n!}$, $$e^{ix}-\sum_{k=0}^n\frac{(ix)^k}{k!}=\frac{i^n}{(n-1)!}\int_0^x(x-s)^{n-1}\left(e^{is}-1\right)ds,$$ and $|e^{is}-1|\le2$ gives the bound $\frac{2}{(n-1)!}\cdot\frac{|x|^n}{n}=\frac{2|x|^n}{n!}$. For $n=0$ the second bound reads $|e^{ix}-1|\le2$.

(2) For $n=1$: the difference quotient is $\frac{\varphi(t+h)-\varphi(t)}{h}=E\left[e^{itX}\frac{e^{ihX}-1}{h}\right]$. By (1) with $n=0$, $\left|\frac{e^{ihX}-1}{h}\right|\le|X|$, which is integrable, and the quotient tends to $iX$ pointwise. Dominated convergence gives $\varphi'(t)=E[iXe^{itX}]$, which is continuous in $t$ by dominated convergence again. Induction on $k$ (with the bound $|X|^k$) gives the higher derivatives. For the expansion, (1) gives $$\left|\varphi(t)-\sum_{k=0}^n\frac{(it)^k}{k!}E[X^k]\right|\le E\left[\min\left(\frac{|tX|^{n+1}}{(n+1)!},\frac{2|tX|^n}{n!}\right)\right]=|t|^n\,E\left[\min\left(\frac{|t|\,|X|^{n+1}}{(n+1)!},\frac{2|X|^n}{n!}\right)\right].$$ The last expectation tends to $0$ as $t\to0$, by dominated convergence with the integrable bound $2|X|^n/n!$. So the error is $o(|t|^n)$. Note that this needs only $E|X|^n\lt\infty$, not $E|X|^{n+1}\lt\infty$; this is exactly what the proof of the central limit theorem requires.

(3) If $\varphi''(0)$ exists, Taylor's formula with Peano remainder gives $\varphi(h)+\varphi(-h)-2=\varphi''(0)h^2+o(h^2)$. On the other hand $\varphi(h)+\varphi(-h)-2=E[2\cos hX-2]$, so $$-\varphi''(0)=\lim_{h\to0}E\left[\frac{2(1-\cos hX)}{h^2}\right]\ge E\left[\liminf_{h\to0}\frac{2(1-\cos hX)}{h^2}\right]=E[X^2]$$ by Fatou's lemma, since $2(1-\cos hx)/h^2\to x^2$. Hence $E[X^2]\lt\infty$, and then (2) gives $E[X^2]=-\varphi''(0)$. ∎

📐 Theorem 2.20 — Characteristic functions of the standard laws
law$\varphi(t)$law$\varphi(t)$
$\operatorname{Ber}(p)$$q+pe^{it}$$U(a,b)$$\dfrac{e^{ibt}-e^{iat}}{it(b-a)}$
$\operatorname{Bin}(n,p)$$(q+pe^{it})^n$$U(-a,a)$$\dfrac{\sin at}{at}$
$\operatorname{Poi}(\lambda)$$\exp\left(\lambda(e^{it}-1)\right)$$\operatorname{Exp}(\lambda)$$\dfrac{\lambda}{\lambda-it}$
$\operatorname{Geo}(p)$ on $\mathbb{N}$$\dfrac{pe^{it}}{1-qe^{it}}$$\operatorname{Gamma}(\alpha,\lambda)$$\left(1-\dfrac{it}{\lambda}\right)^{-\alpha}$
$\operatorname{NB}(r,p)$ failures$\left(\dfrac{p}{1-qe^{it}}\right)^r$$N(\mu,\sigma^2)$$\exp\left(i\mu t-\tfrac12\sigma^2t^2\right)$
$\operatorname{Laplace}(\theta,b)$$\dfrac{e^{i\theta t}}{1+b^2t^2}$$C(\theta,\gamma)$$\exp\left(i\theta t-\gamma|t|\right)$

(For $U(a,b)$ and $U(-a,a)$ the value at $t=0$ is $1$. The gamma power uses the principal branch, which is well defined because $\operatorname{Re}(1-it/\lambda)=1\gt0$.)

Proof. Discrete laws. Put $s=e^{it}$ in the pgfs of §2.1: $|e^{it}|=1$ lies in the disc where every series converges absolutely (for the geometric and negative binomial laws, $|qe^{it}|=q\lt1$). For example $\sum_ke^{-\lambda}\frac{(\lambda e^{it})^k}{k!}=e^{-\lambda}e^{\lambda e^{it}}$.

Uniform. $\frac{1}{b-a}\int_a^be^{itx}dx=\frac{e^{ibt}-e^{iat}}{it(b-a)}$; with $a\to-a$, $b\to a$ this is $\frac{2i\sin at}{2iat}$.

Normal. $Z\sim N(0,1)$ is symmetric, so $\varphi_Z(t)=\int\cos(tz)\varphi(z)\,dz$ is real (here $\varphi$ without subscript is the normal density). Differentiating under the integral (allowed by Theorem 2.19(2), since $E|Z|\lt\infty$) and integrating by parts with $\varphi'(z)=-z\varphi(z)$: $$\varphi_Z'(t)=-\int z\varphi(z)\sin(tz)\,dz=\int\varphi'(z)\sin(tz)\,dz=-t\int\varphi(z)\cos(tz)\,dz=-t\,\varphi_Z(t).$$ So $\frac{d}{dt}\left[e^{t^2/2}\varphi_Z(t)\right]=0$ and $\varphi_Z(t)=e^{-t^2/2}$. Theorem 2.17(4) with $X=\mu+\sigma Z$ gives the general case.

Gamma and exponential. Let $X\sim\operatorname{Gamma}(\alpha,\lambda)$ and $c=\lambda-it$. By Theorem 2.19(2), $\varphi'(t)=iE[Xe^{itX}]=\frac{i\lambda^\alpha}{\Gamma(\alpha)}\int_0^\infty x^\alpha e^{-cx}dx$. Integrating by parts (the boundary terms vanish because $\alpha\gt0$ and $\operatorname{Re}c=\lambda\gt0$), $\int_0^\infty x^\alpha e^{-cx}dx=\frac{\alpha}{c}\int_0^\infty x^{\alpha-1}e^{-cx}dx$. Hence $$\varphi'(t)=\frac{i\alpha}{\lambda-it}\,\varphi(t),\qquad \varphi(0)=1.$$ The function $\psi(t)=(1-it/\lambda)^{-\alpha}$ satisfies the same equation, and $\frac{d}{dt}\left[\varphi(t)/\psi(t)\right]=0$, so $\varphi=\psi$. With $\alpha=1$, $\varphi_{\operatorname{Exp}(\lambda)}(t)=\frac{\lambda}{\lambda-it}$.

Laplace. By Theorem 2.15(3), $X=\theta+b(E_1-E_2)$ with $E_1,E_2$ iid $\operatorname{Exp}(1)$, so $\varphi_X(t)=e^{i\theta t}\cdot\frac{1}{1-ibt}\cdot\frac{1}{1+ibt}=\frac{e^{i\theta t}}{1+b^2t^2}$.

Cauchy. This needs the inversion theorem and is proved in Theorem 2.22(3). ∎

✏️ Example 1 — Reading laws and moments off characteristic functions
Identify the law, and answer the question, for each characteristic function. (a) $\varphi(t)=\left(\dfrac{1+3e^{it}}{4}\right)^5$: find $P(X=5)$ and $\operatorname{Var}(X)$. (b) $\varphi(t)=(1-2it)^{-3}$: find $E[X]$ and $E[X^2]$. (c) $\varphi(t)=\cos(2t)\,e^{-t^2/2}$: find $E[X^2]$ and the density of $X$. (d) $\varphi(t)=e^{it-2|t|}$: find $P(X\le3)$. (e) $\varphi(t)=\dfrac{1}{(1+t^2)^2}$: find $\operatorname{Var}(X)$.
(a) $\left(\frac14+\frac34e^{it}\right)^5$ is the cf of $\operatorname{Bin}(5,\tfrac34)$, by Theorem 2.20 and uniqueness. $P(X=5)=\left(\tfrac34\right)^5=\tfrac{243}{1024}\approx0.2373$ and $\operatorname{Var}(X)=5\cdot\tfrac34\cdot\tfrac14=\tfrac{15}{16}$.
(b) $(1-2it)^{-3}=\left(1-\frac{it}{1/2}\right)^{-3}$ is the cf of $\operatorname{Gamma}(3,\tfrac12)$ (that is, $\chi^2_6$). From the cf directly: $\varphi'(t)=6i(1-2it)^{-4}$ and $\varphi''(t)=-48(1-2it)^{-5}$, so $E[X]=\varphi'(0)/i=6$ and $E[X^2]=-\varphi''(0)=48$. Check: $\operatorname{Var}(X)=48-36=12=\alpha/\lambda^2$.
(c) $\cos 2t=\tfrac12(e^{2it}+e^{-2it})$ is the cf of $V=\pm2$ with probability $\tfrac12$ each, and $e^{-t^2/2}$ is the cf of $Z\sim N(0,1)$. By Theorem 2.18 and uniqueness, $X\overset{d}{=}Z+V$ with $Z,V$ independent. Hence $E[X^2]=1+4=5$; from the cf, $\varphi(t)=(1-2t^2+\dots)(1-\tfrac12t^2+\dots)=1-\tfrac52t^2+\dots$, so $-\varphi''(0)=5$. Conditioning on $V$, the density is the mixture $\tfrac12\phi(x-2)+\tfrac12\phi(x+2)$, where $\phi$ is the $N(0,1)$ density: a bimodal law.
(d) $e^{i\cdot1\cdot t-2|t|}$ is the cf of $C(1,2)$. So $P(X\le3)=\tfrac12+\tfrac1\pi\arctan\frac{3-1}{2}=\tfrac12+\tfrac14=\tfrac34$.
(e) $\frac{1}{(1+t^2)^2}=\frac{1}{1+t^2}\cdot\frac{1}{1+t^2}$ is the cf of $L_1+L_2$ with $L_1,L_2$ iid $\operatorname{Laplace}(0,1)$. So $\operatorname{Var}(X)=2+2=4$. From the cf: $(1+t^2)^{-2}=1-2t^2+\dots$, so $-\varphi''(0)=4$ and $E[X]=0$.

Inversion, Uniqueness and Lévy's Continuity Theorem

The cf would be of little use if different laws could share it. The inversion formula recovers the distribution function from the cf, which proves uniqueness and, as a bonus, the cf of the Cauchy law and the uniqueness of mgfs promised in §1.3. Lévy's continuity theorem then shows that cfs also detect convergence of laws.

📐 Theorem 2.21 — The inversion formula

Let $X$ have cdf $F$ and cf $\varphi$.

  1. For all real $a\lt b$, $$\lim_{T\to\infty}\frac1{2\pi}\int_{-T}^T\frac{e^{-ita}-e^{-itb}}{it}\,\varphi(t)\,dt=P(a\lt X\lt b)+\tfrac12P(X=a)+\tfrac12P(X=b).$$ In particular, if $a$ and $b$ are continuity points of $F$, the limit is $F(b)-F(a)$.
  2. (Density version) If $\int_{-\infty}^\infty|\varphi(t)|\,dt\lt\infty$, then $X$ has a bounded continuous density $$f(x)=\frac1{2\pi}\int_{-\infty}^\infty e^{-itx}\varphi(t)\,dt.$$
  3. (Atoms) For every real $a$, $P(X=a)=\displaystyle\lim_{T\to\infty}\frac{1}{2T}\int_{-T}^Te^{-ita}\varphi(t)\,dt$.

Proof (careful sketch). (1) Step 1: Fubini. The integrand is bounded: $\left|\frac{e^{-ita}-e^{-itb}}{it}\right|=\left|\int_a^be^{-itu}du\right|\le b-a$. So on $[-T,T]\times\mathbb{R}$ we may exchange the $dt$-integral and the expectation: $$I_T=E\left[\frac1{2\pi}\int_{-T}^T\frac{e^{it(X-a)}-e^{it(X-b)}}{it}\,dt\right].$$ Step 2: the inner integral. For real $c$, $\int_{-T}^T\frac{e^{itc}}{it}dt=2\int_0^T\frac{\sin tc}{t}dt$, because the cosine part is odd in $t$ and integrates to $0$. With $S(y)=\int_0^y\frac{\sin u}{u}du$, substituting $u=t|c|$ gives $2\operatorname{sgn}(c)\,S(T|c|)$. Hence $$I_T=E\left[g_T(X)\right],\qquad g_T(x)=\frac1\pi\left[\operatorname{sgn}(x-a)\,S(T|x-a|)-\operatorname{sgn}(x-b)\,S(T|x-b|)\right].$$ Step 3: the Dirichlet integral. $S$ is bounded on $[0,\infty)$ and $S(y)\to\frac\pi2$ as $y\to\infty$. So $g_T$ is bounded uniformly in $T$, and $g_T(x)\to g(x)$, where $g=0$ outside $[a,b]$, $g=\tfrac12$ at $x=a$ and at $x=b$, and $g=1$ on $(a,b)$. Step 4: dominated convergence gives $I_T\to E[g(X)]$, which is the stated right side.

(2) If $\varphi$ is integrable, the limit in (1) is an absolutely convergent integral, and $\left|\frac{e^{-ita}-e^{-itb}}{it}\right|\le b-a$ gives $$P(a\lt X\lt b)+\tfrac12P(X=a)+\tfrac12P(X=b)\le\frac{b-a}{2\pi}\int|\varphi|.$$ Letting $b\downarrow a$ shows that $X$ has no atoms, so $F$ is continuous. Writing $\frac{e^{-ita}-e^{-itb}}{it}=\int_a^be^{-itx}dx$ and using Fubini, $F(b)-F(a)=\int_a^bf(x)\,dx$ with $f$ as stated. Dominated convergence shows that $f$ is continuous, and $|f|\le\frac1{2\pi}\int|\varphi|$. Since $\int_a^bf\ge0$ is real for every interval and $f$ is continuous, $f$ is real and non-negative.

(3) By Fubini, $\frac1{2T}\int_{-T}^Te^{-ita}\varphi(t)\,dt=E\left[\frac{\sin(T(X-a))}{T(X-a)}\right]$ (the value $1$ when $X=a$). The integrand is bounded by $1$ and tends to $\mathbf{1}\{X=a\}$, so dominated convergence gives the limit $P(X=a)$. ∎

📐 Theorem 2.22 — Uniqueness and its first consequences
  1. (Uniqueness) If $\varphi_X(t)=\varphi_Y(t)$ for all $t$, then $X$ and $Y$ have the same distribution.
  2. (Uniqueness of mgfs, completing Theorem 1.32(5) of §1.3) If $M_X(t)=M_Y(t)\lt\infty$ for all $|t|\lt h$, where $h\gt0$, then $X\overset{d}{=}Y$.
  3. (The Cauchy law) The cf of $C(\theta,\gamma)$ is $e^{i\theta t-\gamma|t|}$. Consequently, if $X_j\sim C(\theta_j,\gamma_j)$ are independent, then $\sum_jX_j\sim C\left(\sum\theta_j,\sum\gamma_j\right)$, and if $X_1,\dots,X_n$ are iid $C(\theta,\gamma)$, then $\bar X_n\sim C(\theta,\gamma)$ for every $n$.

Proof. (1) By Theorem 2.21(1), $F_X(b)-F_X(a)=F_Y(b)-F_Y(a)$ whenever $a$ and $b$ are continuity points of both cdfs. All but countably many points are such points. Let $a\to-\infty$ through them: $F_X(b)=F_Y(b)$ for all $b$ in a dense set, and right-continuity gives $F_X=F_Y$ everywhere.

(2) Sketch. Fix $0\lt h'\lt h$. For complex $z$ with $|\operatorname{Re}z|\le h'$, $|e^{zX}|=e^{(\operatorname{Re}z)X}\le e^{h'X}+e^{-h'X}$, which is integrable, so $g_X(z)=E[e^{zX}]$ is finite there. Differentiation under $E$, justified by dominated convergence as in Theorem 1.32, shows that $g_X$ is analytic in the strip $\{|\operatorname{Re}z|\lt h\}$, and likewise $g_Y$. They agree on the real segment $(-h,h)$, so by the identity theorem for analytic functions they agree on the whole strip, in particular on the imaginary axis: $\varphi_X(t)=g_X(it)=g_Y(it)=\varphi_Y(t)$. Now apply (1).

(3) The $\operatorname{Laplace}(0,1)$ law has density $\frac12e^{-|x|}$ and the integrable cf $\frac{1}{1+t^2}$ (Theorem 2.20). Theorem 2.21(2) gives $\frac12e^{-|x|}=\frac1{2\pi}\int e^{-itx}\frac{dt}{1+t^2}$. Multiply by $2$ and replace $x$ by $-s$: $$e^{-|s|}=\int_{-\infty}^\infty e^{ist}\,\frac{1}{\pi(1+t^2)}\,dt,$$ which says exactly that the $C(0,1)$ density has cf $e^{-|s|}$. By Theorem 2.17(4), $\theta+\gamma X$ has cf $e^{i\theta t}e^{-\gamma|t|}$. For independent Cauchy variables the cfs multiply to $\exp\left(i(\sum\theta_j)t-(\sum\gamma_j)|t|\right)$, and for iid ones $\varphi_{\bar X_n}(t)=\left(e^{i\theta t/n-\gamma|t|/n}\right)^n=e^{i\theta t-\gamma|t|}$. Uniqueness finishes the proof. ∎

Part (3) is the proof promised in Theorems 2.15(2) and 2.16(6) of §2.1. Note also the duality used in it: if a density $f$ has a non-negative integrable cf $\varphi$, then $\varphi/(2\pi f(0))$ is itself a density whose cf is $f(-t)/f(0)$. The pairs Laplace–Cauchy and triangle–Fejér (Exercise II.1) are the standard examples.

📘 Definition 2.9 — Convergence in distribution
Random variables $X_n$ with cdfs $F_n$ converge in distribution (or weakly, or in law) to $X$ with cdf $F$, written $X_n\xrightarrow{d}X$ or $F_n\Rightarrow F$, if $$F_n(x)\to F(x)\quad\text{at every point }x\text{ where }F\text{ is continuous.}$$ Only the laws matter: the $X_n$ and $X$ may even be defined on different probability spaces.

The exception at discontinuity points is essential. If $X_n\equiv\frac1n$ and $X\equiv0$, we certainly want $X_n\xrightarrow{d}X$, yet $F_n(0)=0$ for all $n$ while $F(0)=1$; the point $0$ is a jump of $F$ and is excluded. Section 2.3 compares this mode with the other modes of convergence.

📐 Theorem 2.23 — Lévy's continuity theorem

Let $X_n$ have cf $\varphi_n$.

  1. If $X_n\xrightarrow{d}X$, then $\varphi_n(t)\to\varphi_X(t)$ for every real $t$.
  2. Conversely, if $\varphi_n(t)\to\psi(t)$ for every real $t$, and the limit $\psi$ is continuous at $t=0$, then $\psi$ is the cf of some random variable $X$, and $X_n\xrightarrow{d}X$.
  3. (Truncation inequality) For every random variable $X$ and every $u\gt0$, $$P\left(|X|\ge\tfrac2u\right)\le\frac1u\int_{-u}^u\left(1-\varphi_X(t)\right)dt.$$

Proof. (3) For real $x\ne0$, $\frac1{2u}\int_{-u}^u(1-e^{itx})\,dt=1-\frac{\sin ux}{ux}$ (the imaginary part is odd and vanishes); the value is $0$ at $x=0$. By Fubini, $$\frac1u\int_{-u}^u(1-\varphi_X(t))\,dt=2E\left[1-\frac{\sin uX}{uX}\right].$$ The function $1-\frac{\sin y}{y}$ is non-negative, and for $|y|\ge2$ it is at least $1-\frac{1}{|y|}\ge\frac12$. Hence the right side is at least $2\cdot\frac12P(|uX|\ge2)=P(|X|\ge2/u)$.

(1) Sketch. Convergence in distribution is equivalent to $E[g(X_n)]\to E[g(X)]$ for every bounded continuous $g$ (the Helly–Bray characterisation, proved in §2.3). Apply this to $g(x)=\cos tx$ and $g(x)=\sin tx$.

(2) Sketch, naming each step. Step 1 (Helly's selection theorem). Every sequence of cdfs has a subsequence $F_{n_k}$ that converges at all continuity points of some non-decreasing right-continuous $G$ with $0\le G\le1$; $G$ may be defective, i.e. mass may escape to $\pm\infty$. Step 2 (tightness). By (3), $P(|X_n|\ge2/u)\le\frac1u\int_{-u}^u(1-\varphi_n(t))dt$. As $n\to\infty$ the right side tends to $\frac1u\int_{-u}^u(1-\psi(t))dt$ (dominated convergence, $|1-\varphi_n|\le2$), and since $\psi$ is continuous at $0$ with $\psi(0)=\lim\varphi_n(0)=1$, this is small when $u$ is small. So for every $\varepsilon\gt0$ there is $K$ with $P(|X_n|\ge K)\lt\varepsilon$ for all large $n$: no mass escapes, and $G$ is a proper cdf. Step 3 (identify the limit). By (1), the cf of $G$ is $\lim\varphi_{n_k}=\psi$. Step 4 (the whole sequence). Every subsequence of $(F_n)$ has a further subsequence converging to a cdf with cf $\psi$, which by uniqueness is the same $G$ every time. A sequence all of whose subsequences have sub-subsequences converging to $G$ converges to $G$. ∎

The continuity condition in (2) cannot be dropped. For $X_n\sim N(0,n)$, $\varphi_n(t)=e^{-nt^2/2}\to\psi(t)$, where $\psi(0)=1$ and $\psi(t)=0$ for $t\ne0$. This $\psi$ is not continuous at $0$, and indeed $F_n(x)=\Phi(x/\sqrt n)\to\frac12$ for every $x$: the mass spreads out to $\pm\infty$ and there is no limit law.

📐 Theorem 2.24 — Pólya's criterion (statement)
Let $\varphi:\mathbb{R}\to[0,1]$ be even and continuous, with $\varphi(0)=1$, convex on $(0,\infty)$ and $\varphi(t)\to0$ as $t\to\infty$. Then $\varphi$ is the characteristic function of an absolutely continuous symmetric law.

Examples: $e^{-|t|}$ (Cauchy), $(1-|t|)^+=\max(1-|t|,0)$ (Exercise II.1), and $e^{-|t|^\alpha}$ for $0\lt\alpha\le1$. The functions $e^{-|t|^\alpha}$ are also cfs for $1\lt\alpha\le2$ (the symmetric stable laws; $\alpha=2$ is normal), although Pólya's criterion does not cover them, but for $\alpha\gt2$ they are not cfs (Example 2(b)). Pólya's criterion is only sufficient: $e^{-t^2/2}$ is a cf but is concave near $0$.

✏️ Example 2 — Is it a characteristic function?
Decide, with proof, which of the following are characteristic functions: (a) $\cos^2t$; (b) $e^{-t^4}$; (c) $(1-|t|)^+$; (d) $|\cos t|$; (e) $e^{-\sqrt{|t|}}$; (f) $\dfrac{1}{1+t^4}$.
(a) Yes $\cos t$ is the cf of $V=\pm1$ (probability $\tfrac12$ each), so $\cos^2t$ is the cf of $V_1+V_2$ with $V_1,V_2$ iid, which takes the values $-2,0,2$ with probabilities $\tfrac14,\tfrac12,\tfrac14$. Directly: $\cos^2t=\tfrac12+\tfrac14e^{2it}+\tfrac14e^{-2it}$.
(b) No $e^{-t^4}=1-t^4+\dots$ is twice differentiable at $0$ with $\varphi''(0)=0$. By Theorem 2.19(3), $E[X^2]=0$, so $X=0$ a.s. and its cf would be $\equiv1$, a contradiction. The same argument rules out $e^{-|t|^\alpha}$ for every $\alpha\gt2$.
(c) Yes It is even, continuous, equal to $1$ at $0$, convex (linear) on $(0,1]$, constant $0$ on $[1,\infty)$, hence convex on $(0,\infty)$, and it tends to $0$: Pólya's criterion applies. Exercise II.1 identifies the density $\frac{1-\cos x}{\pi x^2}$.
(d) No Suppose $\varphi(t)=|\cos t|$ were a cf. Then $\varphi(\pi)=1$, so $E[1-\cos\pi X]=0$, and $\cos\pi X=1$ a.s.: $X$ takes only even integer values (Exercise II.8). Then $\varphi(t)=\sum_kp_{2k}e^{2ikt}$ is a Fourier series in $e^{2it}$ with non-negative coefficients $p_{2k}$. But the Fourier series of $|\cos t|$ is $$|\cos t|=\frac2\pi+\frac4\pi\sum_{k\ge1}\frac{(-1)^{k+1}}{4k^2-1}\cos 2kt,$$ whose coefficient of $e^{4it}$ is $-\frac{2}{15\pi}\lt0$. By uniqueness of Fourier coefficients this is a contradiction.
(e) Yes $g(t)=e^{-\sqrt t}$ on $t\gt0$ has $g'(t)=-\frac{e^{-\sqrt t}}{2\sqrt t}\lt0$ and $g''(t)=e^{-\sqrt t}\left(\frac{1}{4t}+\frac{1}{4t^{3/2}}\right)\gt0$, so it is decreasing and convex with limit $0$. Pólya's criterion applies (this is a symmetric stable law with $\alpha=\tfrac12$).
(f) No $\frac{1}{1+t^4}=1-t^4+\dots$ again has $\varphi''(0)=0$, which by Theorem 2.19(3) would force $X\equiv0$. Note that (f) passes the tests of Theorem 2.17(1)–(5): it is real, even, continuous and bounded by $1$. Those conditions are necessary but far from sufficient.
✏️ Example 3 — Limit laws through characteristic functions
(a) Let $X_n\sim\operatorname{Bin}(n,p_n)$ with $np_n\to\lambda\gt0$. Show that $X_n\xrightarrow{d}\operatorname{Poi}(\lambda)$. (b) Let $X_\lambda\sim\operatorname{Poi}(\lambda)$. Show that $\dfrac{X_\lambda-\lambda}{\sqrt\lambda}\xrightarrow{d}N(0,1)$ as $\lambda\to\infty$. (c) Let $U_n$ be uniform on $\{1,2,\dots,n\}$. Show that $U_n/n\xrightarrow{d}U(0,1)$.
(a) $\varphi_n(t)=\left(1+p_n(e^{it}-1)\right)^n$. With $x_n=np_n(e^{it}-1)\to\lambda(e^{it}-1)$, the limit $(1+x_n/n)^n\to e^{x}$ (valid for complex $x_n\to x$) gives $\varphi_n(t)\to e^{\lambda(e^{it}-1)}$, the $\operatorname{Poi}(\lambda)$ cf. It is continuous, so Lévy's theorem gives the claim. This re-proves Theorem 2.6 of §2.1.
(b) By Theorem 2.17(4) the standardised variable has cf $$\psi_\lambda(t)=e^{-it\sqrt\lambda}\exp\left(\lambda\left(e^{it/\sqrt\lambda}-1\right)\right).$$ Expand $e^{iu}=1+iu-\frac{u^2}{2}+r(u)$ with $|r(u)|\le\frac{|u|^3}{6}$ (Theorem 2.19(1)), $u=t/\sqrt\lambda$: $$\log\psi_\lambda(t)=-it\sqrt\lambda+\lambda\left(\frac{it}{\sqrt\lambda}-\frac{t^2}{2\lambda}+r\right)=-\frac{t^2}{2}+\lambda r,\qquad|\lambda r|\le\frac{|t|^3}{6\sqrt\lambda}\to0.$$ So $\psi_\lambda(t)\to e^{-t^2/2}$, and Lévy's theorem gives $N(0,1)$. In practice $\operatorname{Poi}(\lambda)\approx N(\lambda,\lambda)$ for large $\lambda$ (with a continuity correction, §2.3).
(c) For $t\ne0$, summing the geometric series, $$\varphi_{U_n/n}(t)=\frac1n\sum_{k=1}^ne^{itk/n}=\frac{e^{it/n}\left(e^{it}-1\right)}{n\left(e^{it/n}-1\right)}\to\frac{e^{it}-1}{it},$$ because $n(e^{it/n}-1)\to it$ and $e^{it/n}\to1$. The limit is the $U(0,1)$ cf, which is continuous. (Here a direct proof is also easy: $P(U_n/n\le x)=\lfloor nx\rfloor/n\to x$.)
Interactive 1 — Characteristic Functions of Standardised Sums

Choose a law and the number $n$ of iid copies added (or press Play). The plot shows the cf of the standardised sum $S_n^*=(S_n-n\mu)/(\sigma\sqrt n)$, namely $\left[e^{-i\mu s}\varphi(s)\right]^n$ with $s=t/(\sigma\sqrt n)$: real part in blue, imaginary part dashed red, modulus in thin green. The dashed purple curve is $e^{-t^2/2}$, the cf of $N(0,1)$. With $n=1$ you see the cf of the law itself: lattice laws have $|\varphi(2\pi)|=1$, and the Cauchy cf has a corner at $0$ (no mean). For the Cauchy law the plot shows the cf of $\bar X_n$ instead, which never changes.

1
mean, variance read off φ at 0—
value at t = 1 (normal: 0.6065)—
max |cf − e^(−t²/2)| on [−8, 8]—
|φ(2π)| of one summand—

Markov, Chebyshev and Cantelli Inequalities

Often we know a mean and a variance but not the law. The next inequalities give tail bounds that hold for every law with the given moments. They are weak for any particular law, but they are sharp over the whole class, and they are exactly what the weak law of large numbers needs.

📐 Theorem 2.25 — Markov's inequality and the Chernoff bound
  1. (Markov) If $X\ge0$ and $a\gt0$, then $$P(X\ge a)\le\frac{E[X]}{a}.$$ When $E[X]\lt\infty$, equality holds if and only if $P(X\in\{0,a\})=1$.
  2. (General form) If $g:[0,\infty)\to[0,\infty)$ is non-decreasing and $g(a)\gt0$, then $P(|X|\ge a)\le\dfrac{E[g(|X|)]}{g(a)}$. In particular $P(|X|\ge a)\le\dfrac{E|X|^r}{a^r}$ for every $r\gt0$.
  3. (Chernoff bound) For every real $a$, $$P(X\ge a)\le\inf_{t\ge0}e^{-ta}M_X(t).$$

Proof. (1) Pointwise, $a\,\mathbf{1}\{X\ge a\}\le X$: if $X\ge a$ the left side is $a\le X$, and otherwise it is $0\le X$. Taking expectations (Theorem 1.28(3)) gives $aP(X\ge a)\le E[X]$. Equality means $E\left[X-a\mathbf{1}\{X\ge a\}\right]=0$ for a non-negative integrand, so $X=a\mathbf{1}\{X\ge a\}$ a.s. (Theorem 1.28(4)), i.e. $X\in\{0,a\}$ a.s.; conversely such an $X$ gives equality.

(2) Since $g$ is non-decreasing, $g(a)\mathbf{1}\{|X|\ge a\}\le g(|X|)$; take expectations.

(3) For $t\ge0$, $x\mapsto e^{tx}$ is non-decreasing, so $\mathbf{1}\{X\ge a\}\le e^{t(X-a)}$ and $P(X\ge a)\le e^{-ta}M_X(t)$ (trivially true if $M_X(t)=\infty$). Take the infimum over $t$. ∎

📐 Theorem 2.26 — Chebyshev's inequality

Let $X$ have mean $\mu$ and finite variance $\sigma^2\gt0$. For every $k\gt0$ and $\varepsilon\gt0$, $$P(|X-\mu|\ge k\sigma)\le\frac{1}{k^2},\qquad P(|X-\mu|\ge\varepsilon)\le\frac{\sigma^2}{\varepsilon^2}.$$ The bound is sharp: for $k\ge1$ the law $P(X=\mu\pm k\sigma)=\frac{1}{2k^2}$, $P(X=\mu)=1-\frac1{k^2}$ has variance $\sigma^2$ and attains equality. If $X_1,\dots,X_n$ are uncorrelated with common mean $\mu$ and variance $\sigma^2$, then $P(|\bar X_n-\mu|\ge\varepsilon)\le\dfrac{\sigma^2}{n\varepsilon^2}$.

Proof. Apply Markov's inequality to $(X-\mu)^2\ge0$ with $a=\varepsilon^2$: $P(|X-\mu|\ge\varepsilon)=P((X-\mu)^2\ge\varepsilon^2)\le\frac{\sigma^2}{\varepsilon^2}$. Put $\varepsilon=k\sigma$ for the first form. For the three-point law, $E[X]=\mu$, $\operatorname{Var}(X)=2\cdot\frac{1}{2k^2}\cdot k^2\sigma^2=\sigma^2$ and $P(|X-\mu|\ge k\sigma)=\frac1{k^2}$. For the sample mean, $\operatorname{Var}(\bar X_n)=\frac{1}{n^2}\sum\operatorname{Var}(X_j)=\frac{\sigma^2}{n}$ because the covariances vanish; apply the second form to $\bar X_n$. ∎

The last statement already contains a weak law of large numbers: $P(|\bar X_n-\mu|\ge\varepsilon)\to0$ for every $\varepsilon\gt0$. Section 2.3 develops this. For $k\le1$ Chebyshev's bound is at least $1$ and says nothing.

📐 Theorem 2.27 — Cantelli's inequality (one-sided Chebyshev)

Let $X$ have mean $\mu$ and finite variance $\sigma^2$. For every $\lambda\gt0$, $$P(X-\mu\ge\lambda)\le\frac{\sigma^2}{\sigma^2+\lambda^2},\qquad P(X-\mu\le-\lambda)\le\frac{\sigma^2}{\sigma^2+\lambda^2}.$$ With $\lambda=k\sigma$ the bound is $\frac{1}{1+k^2}$. It is sharp: the two-point law with $X-\mu=\lambda$ with probability $\frac{\sigma^2}{\sigma^2+\lambda^2}$ and $X-\mu=-\frac{\sigma^2}{\lambda}$ with probability $\frac{\lambda^2}{\sigma^2+\lambda^2}$ attains equality.

Proof. Let $Y=X-\mu$, so $E[Y]=0$ and $E[Y^2]=\sigma^2$. For every $u\ge0$, the event $\{Y\ge\lambda\}$ implies $Y+u\ge\lambda+u\gt0$, hence $(Y+u)^2\ge(\lambda+u)^2$. By Markov's inequality, $$P(Y\ge\lambda)\le\frac{E[(Y+u)^2]}{(\lambda+u)^2}=\frac{\sigma^2+u^2}{(\lambda+u)^2}.$$ The right side is minimised at $u=\sigma^2/\lambda$ (set its derivative to zero), where it equals $$\frac{\sigma^2+\sigma^4/\lambda^2}{(\lambda+\sigma^2/\lambda)^2}=\frac{\sigma^2(\lambda^2+\sigma^2)/\lambda^2}{(\lambda^2+\sigma^2)^2/\lambda^2}=\frac{\sigma^2}{\sigma^2+\lambda^2}.$$ The lower tail follows by applying this to $-X$. For the two-point law, $E[Y]=\frac{\lambda\sigma^2-\sigma^2\lambda}{\sigma^2+\lambda^2}=0$ and $E[Y^2]=\frac{\lambda^2\sigma^2+\sigma^4}{\sigma^2+\lambda^2}=\sigma^2$, and $P(Y\ge\lambda)$ is the stated bound. ∎

Cantelli's bound $\frac{1}{1+k^2}$ is smaller than Chebyshev's $\frac1{k^2}$ for every $k$, and it is informative even for $k\lt1$. Adding the two one-sided bounds gives $\frac{2}{1+k^2}$, which beats $\frac1{k^2}$ only when $k\lt1$. A useful consequence (Exercise III.7): the median $m$ of a law with finite variance satisfies $|m-\mu|\le\sigma$.

✏️ Example 4 — How good are the bounds?
(a) $X\sim\operatorname{Bin}(100,\tfrac12)$. Bound $P(X\ge70)$ by Markov's, Chebyshev's and Cantelli's inequalities and by the Chernoff bound, and compare with the exact value. (b) Do the same for $P(X\ge3)$ when $X\sim\operatorname{Exp}(1)$.
(a) Moments $\mu=50$, $\sigma^2=25$. Markov: $P(X\ge70)\le\frac{50}{70}\approx0.714$. Chebyshev: $P(X\ge70)\le P(|X-50|\ge20)\le\frac{25}{400}=0.0625$. Cantelli: $\frac{25}{25+400}=\frac1{17}\approx0.0588$.
(a) Chernoff $M(t)=\left(\frac{1+e^t}{2}\right)^{100}$. Minimising $h(t)=-70t+100\log\frac{1+e^t}{2}$: $h'(t)=0$ gives $\frac{e^t}{1+e^t}=0.7$, i.e. $e^t=\frac73$. The bound is $$e^{-100D},\qquad D=0.7\log\frac{0.7}{0.5}+0.3\log\frac{0.3}{0.5}\approx0.08228,$$ so $P(X\ge70)\le e^{-8.228}\approx2.67\times10^{-4}$. The exact value is $\sum_{k\ge70}\binom{100}{k}2^{-100}\approx3.93\times10^{-5}$. Chebyshev is off by a factor of about $1600$, Chernoff by a factor of about $7$: the mgf "knows" the exponential decay of binomial tails, two moments cannot.
(b) $\mu=\sigma=1$, exact $P(X\ge3)=e^{-3}\approx0.0498$. Markov: $\frac13$. Chebyshev: $P(X-1\ge2)\le P(|X-1|\ge2)\le\frac14$. Cantelli: $\frac{1}{1+4}=0.2$. Chernoff: $e^{-3t}\frac{1}{1-t}$ for $0\le t\lt1$ is minimised at $t=\frac23$, giving $3e^{-2}\approx0.406$, worse than Cantelli here. Chernoff bounds win only far in the tail; for exponential tails they lose a factor proportional to the distance.
Lesson A bound valid for all laws with given moments is necessarily weak for a particular law. Use the exact law when it is known; use Chebyshev or Cantelli when only moments are known, as in the law of large numbers.
✏️ Example 5 — Sample sizes and guaranteed proportions
(a) A coin with unknown probability $p$ of heads is tossed $n$ times and $\hat p$ is the proportion of heads. How large must $n$ be to guarantee $P(|\hat p-p|\ge0.05)\le0.05$ for every $p$? (b) In a large examination the marks have mean $62$ and standard deviation $8$; nothing else is known. At most what proportion of candidates can have scored $78$ or more, and at least what proportion scored strictly between $46$ and $78$? Are the bounds attained? (c) Compare with the answers if the marks are known to be normal.
(a) $\hat p$ has mean $p$ and variance $\frac{p(1-p)}{n}\le\frac1{4n}$. By Chebyshev, $P(|\hat p-p|\ge0.05)\le\frac{1}{4n(0.05)^2}=\frac{100}{n}$, which is at most $0.05$ when $n\ge2000$. The normal approximation of §2.3 gives $n\ge\left(\frac{1.96}{2\times0.05}\right)^2\approx385$: Chebyshev is safe but wasteful.
(b) $78=62+2\times8$. Cantelli with $k=2$: the proportion with marks $\ge78$ is at most $\frac{1}{1+4}=0.2$. Chebyshev with $k=2$: the proportion with $|X-62|\ge16$ is at most $\frac14$, so at least $0.75$ scored strictly between $46$ and $78$. Both bounds are attained: the first by marks equal to $78$ for $20\%$ and to $58$ for $80\%$ of the candidates (the two-point law of Theorem 2.27, with $\sigma^2/\lambda=4$), the second by marks $46$ and $78$ for $12.5\%$ each and $62$ for the remaining $75\%$.
(c) For $N(62,64)$: $P(X\ge78)=1-\Phi(2)\approx0.0228$ and $P(46\lt X\lt78)=2\Phi(2)-1\approx0.9545$. Knowing the shape of the law sharpens the bounds tenfold.
Interactive 2 — Exact Tails Against Markov, Chebyshev and Cantelli

For the chosen law, the solid blue curve is the exact two-sided tail $P(|X-\mu|\ge k\sigma)$ and the dashed red curve is Chebyshev's bound $\min(1,1/k^2)$; the solid green curve is the one-sided tail $P(X-\mu\ge k\sigma)$ and the dashed amber curve is Cantelli's bound $1/(1+k^2)$. For non-negative laws the dotted purple curve is Markov's bound $\mu/(\mu+k\sigma)$ for the same one-sided tail. Move $k$ (or press Play), and switch to the log scale to see how many orders of magnitude separate a bound from the truth. The two extremal laws show that each bound can be attained.

2.00
P(|X − μ| ≥ kσ) exact—
Chebyshev 1/k²—
P(X − μ ≥ kσ) exact—
Cantelli 1/(1 + k²) · Markov—

Convexity and Moments: Jensen, Cauchy–Schwarz and Hölder

The second family of inequalities compares expectations of functions. Jensen's inequality explains why $E[X^2]\ge(E[X])^2$, why $E[1/X]\ge1/E[X]$ for positive $X$, why the geometric mean is below the arithmetic mean and why higher moments grow; the Cauchy–Schwarz and Hölder inequalities bound $E[XY]$ by moments of $X$ and $Y$ separately.

📘 Definition 2.10 — Convex and concave functions

A function $g$ on an interval $I$ is convex if $g(\lambda x+(1-\lambda)y)\le\lambda g(x)+(1-\lambda)g(y)$ for all $x,y\in I$ and $\lambda\in[0,1]$, and strictly convex if the inequality is strict whenever $x\ne y$ and $0\lt\lambda\lt1$. It is (strictly) concave if $-g$ is (strictly) convex.

Two facts are used constantly. If $g$ is twice differentiable on an open interval with $g''\ge0$ ($g''\gt0$), it is convex (strictly convex). And a convex $g$ on an open interval has a supporting line at every point $m$: there is a constant $c$ (any number between the left and right derivatives at $m$) with $$g(x)\ge g(m)+c(x-m)\qquad\text{for all }x\in I.$$ (Chord slopes of a convex function increase, so the one-sided derivatives exist and the line through $(m,g(m))$ with slope $c$ lies below the graph.) For strictly convex $g$ the inequality is strict for $x\ne m$.

📐 Theorem 2.28 — Jensen's inequality and its consequences

Let $X$ take values in an open interval $I$ with $E|X|\lt\infty$, and let $g$ be convex on $I$. Then $E[g(X)]$ is well defined (possibly $+\infty$) and $$g\left(E[X]\right)\le E\left[g(X)\right].$$ If $g$ is strictly convex, equality holds if and only if $X$ is a.s. constant. For concave $g$ the inequality is reversed. Consequences:

  1. $(E[X])^2\le E[X^2]$, $|E[X]|\le E|X|$ and $e^{E[X]}\le E[e^X]$;
  2. for $X\gt0$: $E[\log X]\le\log E[X]$, $E[1/X]\ge1/E[X]$ and $E[\sqrt X]\le\sqrt{E[X]}$;
  3. (Lyapunov's inequality) for $0\lt r\lt s$, $\left(E|X|^r\right)^{1/r}\le\left(E|X|^s\right)^{1/s}$;
  4. (AM–GM–HM) for positive numbers $a_1,\dots,a_n$, $\dfrac{n}{\sum1/a_j}\le\left(\prod a_j\right)^{1/n}\le\dfrac1n\sum a_j$.

Proof. Let $m=E[X]$. First, $m\in I$: if $I=(\alpha,\beta)$ and $\alpha\lt X\lt\beta$, then $\alpha\le m\le\beta$, and $m=\alpha$ would make $X-\alpha\gt0$ a variable with mean $0$, impossible by Theorem 1.28(4); likewise $m\ne\beta$. Take a supporting line at $m$: $g(X)\ge g(m)+c(X-m)$. The right side is integrable, so the negative part of $g(X)$ is integrable and $E[g(X)]$ is well defined. Taking expectations, $E[g(X)]\ge g(m)+c\cdot0=g(m)$.

If equality holds, $W=g(X)-g(m)-c(X-m)$ is non-negative with $E[W]=0$, so $W=0$ a.s. For strictly convex $g$ the supporting line touches the graph only at $m$, so $X=m$ a.s. For concave $g$ apply the result to $-g$.

(1) Use $g(x)=x^2$, $|x|$ and $e^x$. (2) $\log$ and $\sqrt{\cdot}$ are concave and $1/x$ is convex on $(0,\infty)$. (3) Let $Y=|X|^r$. If $E|X|^s=\infty$ there is nothing to prove; otherwise $E[Y]\lt\infty$ (§1.3). The function $g(y)=y^{s/r}$ is convex on $[0,\infty)$ since $s/r\gt1$. If $E[Y]=0$ the inequality is trivial; otherwise the supporting-line argument at $m=E[Y]\gt0$ works on the closed half-line, and $(E[Y])^{s/r}\le E[Y^{s/r}]=E|X|^s$. Take the $s$-th root. (4) Let $X$ be uniform on $\{a_1,\dots,a_n\}$ (counting repeated values with multiplicity). Then (2) with $\log$ gives $\frac1n\sum\log a_j\le\log\left(\frac1n\sum a_j\right)$, which is AM–GM; apply AM–GM to the numbers $1/a_j$ for GM–HM. ∎

📐 Theorem 2.29 — Cauchy–Schwarz, Hölder and Minkowski inequalities

For $p\ge1$ write $\|X\|_p=\left(E|X|^p\right)^{1/p}$.

  1. (Cauchy–Schwarz) If $E[X^2]$ and $E[Y^2]$ are finite, then $E|XY|\lt\infty$ and $$\left(E[XY]\right)^2\le E[X^2]\,E[Y^2],$$ with equality if and only if $aX=bY$ a.s. for some constants $(a,b)\ne(0,0)$. Applied to $X-E[X]$ and $Y-E[Y]$ it gives $|\operatorname{Cov}(X,Y)|\le\sigma_X\sigma_Y$, i.e. $|\rho|\le1$.
  2. (Hölder) If $p,q\gt1$ with $\frac1p+\frac1q=1$, then $E|XY|\le\|X\|_p\,\|Y\|_q$.
  3. (Minkowski) If $p\ge1$, then $\|X+Y\|_p\le\|X\|_p+\|Y\|_p$.

Proof. (1) $|XY|\le\frac12(X^2+Y^2)$ gives $E|XY|\lt\infty$. If $E[X^2]=0$, then $X=0$ a.s. and both sides vanish (and $1\cdot X=0\cdot Y$). Otherwise, for every real $s$, $$0\le E[(Y-sX)^2]=E[Y^2]-2sE[XY]+s^2E[X^2].$$ A quadratic in $s$ that is never negative has non-positive discriminant: $4(E[XY])^2-4E[X^2]E[Y^2]\le0$. Equality means the discriminant is $0$, so the quadratic has a real root $s_0$, i.e. $E[(Y-s_0X)^2]=0$ and $Y=s_0X$ a.s. Conversely, a linear relation gives equality by direct substitution. This is the inequality behind $|\rho|\le1$ in §1.4.

(2) Young's inequality: for $a,b\ge0$, $ab\le\frac{a^p}{p}+\frac{b^q}{q}$. For $a,b\gt0$ it follows from the concavity of $\log$: $\log\left(\frac{a^p}{p}+\frac{b^q}{q}\right)\ge\frac1p\log a^p+\frac1q\log b^q=\log(ab)$. If $\|X\|_p=0$ or $\|Y\|_q=0$, then $XY=0$ a.s.; if one of them is infinite there is nothing to prove. Otherwise apply Young's inequality to $a=|X|/\|X\|_p$ and $b=|Y|/\|Y\|_q$ and take expectations: $$\frac{E|XY|}{\|X\|_p\|Y\|_q}\le\frac{E|X|^p}{p\|X\|_p^p}+\frac{E|Y|^q}{q\|Y\|_q^q}=\frac1p+\frac1q=1.$$

(3) For $p=1$ this is the triangle inequality. For $p\gt1$, let $q=\frac{p}{p-1}$; we may assume $\|X\|_p,\|Y\|_p\lt\infty$, and then $E|X+Y|^p\le2^{p-1}(E|X|^p+E|Y|^p)\lt\infty$ by convexity of $|x|^p$. Now $$|X+Y|^p\le|X|\,|X+Y|^{p-1}+|Y|\,|X+Y|^{p-1},$$ and Hölder applied to each term (note $(p-1)q=p$) gives $$E|X+Y|^p\le\left(\|X\|_p+\|Y\|_p\right)\left(E|X+Y|^p\right)^{1/q}.$$ Divide by $(E|X+Y|^p)^{1/q}$ (if it is $0$ there is nothing to prove) and use $1-\frac1q=\frac1p$. ∎

✏️ Example 6 — Prove or disprove
(a) If $X\gt0$, then $E[X]\,E[1/X]\ge1$. (b) If $X\ge0$, then $E[\sqrt X]\ge\sqrt{E[X]}$. (c) If $X\ge0$ and $0\lt E[X^2]\lt\infty$, then $P(X\gt0)\ge\dfrac{(E[X])^2}{E[X^2]}$. (d) If $E[X]=0$ and $E[X^2]=1$, then $E|X|^3\ge1$. (e) If $X\gt0$ and $E[\log X]=\log E[X]$ (both finite), then $X$ is a.s. constant. (f) If $E[XY]=E[X]\,E[Y]$ and $X,Y$ have finite variances, then $\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y)$, and $X,Y$ are independent.
(a) True If $E[X]=\infty$ there is nothing to prove. Otherwise $g(x)=1/x$ is convex on $(0,\infty)$, so $E[1/X]\ge1/E[X]$. Alternatively, Cauchy–Schwarz with $\sqrt X$ and $1/\sqrt X$: $1=\left(E[\sqrt X\cdot\tfrac1{\sqrt X}]\right)^2\le E[X]E[1/X]$. Equality holds only for constant $X$.
(b) False $\sqrt{\cdot}$ is concave, so the inequality goes the other way. For $X=0$ or $4$ with probability $\tfrac12$ each: $E[\sqrt X]=1\lt\sqrt2=\sqrt{E[X]}$.
(c) True (second-moment method) $E[X]=E[X\mathbf{1}\{X\gt0\}]\le\sqrt{E[X^2]\,E[\mathbf{1}\{X\gt0\}]}=\sqrt{E[X^2]P(X\gt0)}$ by Cauchy–Schwarz. Square and divide by $E[X^2]$. This lower bound on a probability is used to show that random structures exist (Exercise IV.6 refines it).
(d) True Lyapunov with $r=2$, $s=3$: $\left(E|X|^3\right)^{1/3}\ge\left(E[X^2]\right)^{1/2}=1$. Equality holds for $X=\pm1$ with probability $\tfrac12$ each, so $1$ is the best constant.
(e) True $\log$ is strictly concave on $(0,\infty)$, and equality in Jensen's inequality for a strictly concave function forces $X$ to be a.s. constant.
(f) First part true, second false $E[XY]=E[X]E[Y]$ means $\operatorname{Cov}(X,Y)=0$, so the variances add. But uncorrelated is not independent: $X\sim N(0,1)$ and $Y=X^2$ have $E[XY]=E[X^3]=0=E[X]E[Y]$, yet $Y$ is a function of $X$.
⚠️ Counterexamples and pitfalls
  1. A cf always exists; an mgf need not. The Cauchy law has cf $e^{-|t|}$ but $E[e^{tX}]=\infty$ for all $t\ne0$; the lognormal law has all moments but no mgf. Proofs that use mgfs (for example of the central limit theorem) silently assume that the mgf exists; proofs with cfs do not.
  2. $\varphi_{X+Y}=\varphi_X\varphi_Y$ does not imply independence. Take $X=Y\sim C(0,1)$. Then $\varphi_{X+Y}(t)=\varphi_{2X}(t)=e^{-2|t|}=\varphi_X(t)\varphi_Y(t)$, but $X$ and $Y$ are as dependent as possible. Independence is equivalent to factorisation of the joint cf (Theorem 2.18(2)).
  3. Real and even does not make a cf. $\frac{1}{1+t^4}$ and $e^{-t^4}$ are real, even, continuous and bounded by $1$, but are not cfs (Example 2). Conversely a cf can be negative: $\cos t$ is the cf of $\pm1$.
  4. $\varphi(t)\to0$ is not automatic. The Riemann–Lebesgue lemma says $\varphi(t)\to0$ as $|t|\to\infty$ for laws with a density, but a lattice law has a periodic cf with $|\varphi(2\pi/h)|=1$ (span $h$), and the Cantor law has no atoms and no density and its cf does not tend to $0$ (Exercise II.2).
  5. A pointwise limit of cfs need not be a cf. $N(0,n)$ has cf $e^{-nt^2/2}\to\mathbf{1}\{t=0\}$, which is discontinuous at $0$; there is no limit law. Lévy's theorem needs continuity of the limit at $0$.
  6. Odd derivatives do not force moments. Only even-order derivatives at $0$ guarantee moments (Theorem 2.19(3)). There are symmetric laws with $E|X|=\infty$ whose cf is differentiable at $0$ with $\varphi'(0)=0$ (for example $P(X=\pm k)=\frac{c}{k^2\log k}$, $k\ge2$, which matters for the weak law in §2.3).
  7. Markov's inequality needs $X\ge0$. For $X=-10$ or $1$ with probability $\tfrac12$ each, $P(X\ge1)=\tfrac12$ while $E[X]/1=-4.5$.
  8. Chebyshev is useless for $k\le1$ and crude for known laws. For the normal law $P(|Z|\ge2)=0.0455$ against the bound $0.25$. The bound is attained only by three-point laws (Theorem 2.26).
  9. Two one-sided Cantelli bounds do not add up to Chebyshev. $\frac{2}{1+k^2}\gt\frac1{k^2}$ for $k\gt1$. Use Cantelli for one tail, Chebyshev for both.
  10. Jensen's direction. $E[1/X]\ne1/E[X]$ and $E[\log X]\ne\log E[X]$ in general; for convex $g$ the inequality is $g(E X)\le E g(X)$, reversed for concave $g$. A common error is to apply it to a function that is convex on only part of the range of $X$, such as $x^3$ for a variable taking negative values.
  11. Uncorrelated is not independent. $X\sim N(0,1)$, $Y=X^2$ (Example 6(f)). Chebyshev's bound for $\bar X_n$ needs only uncorrelatedness; the product formula for cfs needs independence.

Exercises

I
Computing and using characteristic functions.
  • 1 For $X\sim U(a,b)$ derive $\varphi_X(t)$, and deduce that $U(-a,a)$ has cf $\frac{\sin at}{at}$. Use the cf to find $E[X^2]$ for $U(-a,a)$.
  • 2 For the geometric law on $\{0,1,2,\dots\}$, $P(X=k)=q^kp$, find $\varphi_X$ and use it to find $E[X]$.
  • 3 $X$ takes the values $-1,0,1$ with probabilities $\tfrac14,\tfrac12,\tfrac14$. Show that $\varphi_X(t)=\cos^2(t/2)$.
  • 4 Identify the laws with characteristic functions $\cos t\cos2t$ and $\cos^3t$.
  • 5 $X$ and $Y$ are iid with cf $\varphi$. Show that $X-Y$ has cf $|\varphi(t)|^2$, a real non-negative function. Use this to find the law of $X-Y$ when $X,Y$ are iid $\operatorname{Exp}(1)$.
  • 6 Expand the cf of $N(0,\sigma^2)$ in powers of $t$ and read off $E[X^4]$ and $E[X^6]$.
  • 7 Prove that every cf satisfies $\operatorname{Re}\left(1-\varphi(2t)\right)\le4\operatorname{Re}\left(1-\varphi(t)\right)$.
  • 8 (Insurance: compound Poisson) The number of claims in a month is $N\sim\operatorname{Poi}(\lambda)$, and the claim sizes $Y_1,Y_2,\dots$ are iid with cf $\psi$, independent of $N$. Show that the total $S=\sum_{j=1}^NY_j$ has cf $\exp\left(\lambda(\psi(t)-1)\right)$, and deduce $E[S]=\lambda E[Y]$ and $\operatorname{Var}(S)=\lambda E[Y^2]$. Evaluate them for $\lambda=4$ claims per month and exponential claims with mean $2$ (thousand rupees).
1 $\frac1{b-a}\int_a^be^{itx}dx=\frac{e^{itb}-e^{ita}}{it(b-a)}$ for $t\ne0$. For $(-a,a)$: $\frac{e^{iat}-e^{-iat}}{2iat}=\frac{\sin at}{at}$. Expanding, $\frac{\sin at}{at}=1-\frac{a^2t^2}{6}+\dots$, so $E[X^2]=-\varphi''(0)=\frac{a^2}{3}$, which is $\frac{(2a)^2}{12}$.
2 $\varphi(t)=\sum_kq^kpe^{itk}=\frac{p}{1-qe^{it}}$. Then $\varphi'(t)=\frac{ipqe^{it}}{(1-qe^{it})^2}$, so $\varphi'(0)=\frac{ipq}{p^2}$ and $E[X]=\varphi'(0)/i=\frac qp$.
3 $\varphi(t)=\tfrac12+\tfrac14(e^{it}+e^{-it})=\tfrac12(1+\cos t)=\cos^2(t/2)$. (It is the law of $V_1+V_2$ with $V_j=\pm\tfrac12$ iid; compare Example 2(a).)
4 $\cos t\cos2t$ is the cf of $V_1+2V_2$ with $V_1,V_2$ iid $\pm1$: the values $\pm1,\pm3$, each with probability $\tfrac14$. And $\cos^3t=\frac18\left(e^{3it}+3e^{it}+3e^{-it}+e^{-3it}\right)$: the values $\pm3$ with probability $\tfrac18$ each and $\pm1$ with probability $\tfrac38$ each (the law of $V_1+V_2+V_3$).
5 $\varphi_{X-Y}(t)=\varphi_X(t)\varphi_{-Y}(t)=\varphi(t)\overline{\varphi(t)}=|\varphi(t)|^2$. For $\operatorname{Exp}(1)$: $\left|\frac1{1-it}\right|^2=\frac1{1+t^2}$, the $\operatorname{Laplace}(0,1)$ cf, in agreement with Theorem 2.15(3).
6 $e^{-\sigma^2t^2/2}=\sum_k\frac{(-1)^k\sigma^{2k}t^{2k}}{2^kk!}$. Comparing with $\sum_r\frac{(it)^r}{r!}E[X^r]$: $\frac{E[X^4]}{24}=\frac{\sigma^4}{8}$, so $E[X^4]=3\sigma^4$; $\frac{E[X^6]}{720}=\frac{\sigma^6}{48}$, so $E[X^6]=15\sigma^6$.
7 For real $u$: $1-\cos2u=2\sin^2u=8\sin^2\frac u2\cos^2\frac u2\le8\sin^2\frac u2=4(1-\cos u)$. Put $u=tX$ and take expectations: $E[1-\cos2tX]\le4E[1-\cos tX]$, which is the claim because $\operatorname{Re}\varphi(t)=E[\cos tX]$.
8 Condition on $N$: given $N=n$, $\varphi_S=\psi^n$ by independence, so $\varphi_S(t)=\sum_ne^{-\lambda}\frac{\lambda^n}{n!}\psi(t)^n=e^{\lambda(\psi(t)-1)}$. With $K(t)=\lambda(\psi(t)-1)$, $\varphi_S'=K'\varphi_S$ and $\varphi_S''=(K''+K'^2)\varphi_S$; at $0$, $K'(0)=i\lambda E[Y]$ and $K''(0)=-\lambda E[Y^2]$. So $E[S]=\lambda E[Y]$ and $E[S^2]=\lambda E[Y^2]+\lambda^2(E[Y])^2$, giving $\operatorname{Var}(S)=\lambda E[Y^2]$. For exponential claims with mean $2$: $E[Y^2]=2\cdot2^2=8$, so $E[S]=8$ and $\operatorname{Var}(S)=32$ (thousand rupees and thousand rupees squared).
II
Inversion, uniqueness and Lévy's continuity theorem.
  • 1 (Triangle and Fejér) The triangular density $g(x)=(1-|x|)^+$ is the density of $U_1+U_2$ with $U_1,U_2$ iid $U(-\tfrac12,\tfrac12)$. Find its cf, and use the inversion formula to show that $f(x)=\frac{1-\cos x}{\pi x^2}$ is a probability density with cf $(1-|t|)^+$.
  • 2 Use Theorem 2.21(3) to show that if $\varphi_X(t)\to0$ as $|t|\to\infty$, then $X$ has no atoms. Show that the converse fails, using the Cantor variable $X=\sum_{k\ge1}2\varepsilon_k3^{-k}$ with $\varepsilon_k$ iid $\operatorname{Ber}(\tfrac12)$: find $\varphi_X$ and show that $|\varphi_X(2\pi\cdot3^m)|$ does not depend on $m\ge0$ and is not $0$.
  • 3 Show that $e^{-|t|^3}$ is not a characteristic function.
  • 4 $X_n$ is geometric on $\mathbb{N}$ with $p=\lambda/n$. Show that $X_n/n\xrightarrow{d}\operatorname{Exp}(\lambda)$ using characteristic functions.
  • 5 $X_n\sim\operatorname{Gamma}(n,1)$. Show that $\dfrac{X_n-n}{\sqrt n}\xrightarrow{d}N(0,1)$ using characteristic functions.
  • 6 Let $\varphi$ be a cf. Show that $\varphi^n$ ($n\in\mathbb{N}$), $|\varphi|^2$, $\operatorname{Re}\varphi$ and $\sum_{k\ge0}p_k\varphi^k$ (for a pmf $(p_k)$ on $\{0,1,\dots\}$) are cfs.
  • 7 $X$ and $Y$ are independent, $X\sim N(0,1)$ and $X+Y\sim N(1,3)$. Find the law of $Y$, justifying each step.
  • 8 (a) Show that if $|\varphi_X(t_0)|=1$ for some $t_0\ne0$, then $X$ takes values in a lattice $a+\frac{2\pi}{t_0}\mathbb{Z}$ a.s. (b) (Cancellation can fail.) Let $\varphi_1(t)=(1-|t|)^+$ and let $\varphi_2$ be the $2$-periodic function equal to $1-|t|$ on $[-1,1]$. Using $\varphi_2(t)=\frac12+\sum_{k\text{ odd}}\frac{4}{\pi^2k^2}\cos k\pi t$, show that $\varphi_2$ is a cf, and find independent $X,Y,Y'$ with $X+Y\overset{d}{=}X+Y'$ but $Y\not\overset{d}{=}Y'$.
1 $U(-\tfrac12,\tfrac12)$ has cf $\frac{\sin(t/2)}{t/2}$, so $g$ has cf $\frac{\sin^2(t/2)}{t^2/4}=\frac{2(1-\cos t)}{t^2}$, which is integrable. By Theorem 2.21(2), $(1-|x|)^+=\frac1{2\pi}\int e^{-itx}\frac{2(1-\cos t)}{t^2}dt=\int e^{-itx}f(t)\,dt$. At $x=0$ this gives $\int f=1$, and $f\ge0$, so $f$ is a density; replacing $x$ by $-x$ (everything is even) shows that its cf is $(1-|x|)^+$. This is the duality remark after Theorem 2.22.
2 $\left|\frac1{2T}\int_{-T}^Te^{-ita}\varphi(t)dt\right|\le\frac1{2T}\int_{-T}^T|\varphi(t)|dt\to0$ when $|\varphi(t)|\to0$ (a Cesàro mean of a function tending to $0$), so every atom has probability $0$. For the Cantor variable, independence gives $\varphi_X(t)=\prod_k\frac{1+e^{2it/3^k}}{2}=e^{it/2}\prod_{k\ge1}\cos\frac{t}{3^k}$ (using $\sum3^{-k}=\tfrac12$). At $t=2\pi3^m$ the factors with $k\le m$ are $\cos(2\pi3^{m-k})=1$, and the rest give $\prod_{j\ge1}\cos\frac{2\pi}{3^j}$, independent of $m$ and $\approx-0.371$ (all factors are non-zero and the product converges since $\sum(1-\cos(2\pi/3^j))\lt\infty$). $X$ is continuous (it has no atoms: every value has probability $\lim2^{-k}=0$) but $\varphi_X(t)\not\to0$; of course $X$ has no density.
3 $e^{-|t|^3}=1-|t|^3+O(t^6)$, so $\frac{\varphi(h)+\varphi(-h)-2}{h^2}=-2|h|+O(h^4)\to0$ and $\varphi''(0)=0$ exists ($\varphi'(t)=-3t|t|e^{-|t|^3}$ is differentiable at $0$ with derivative $0$). By Theorem 2.19(3), $E[X^2]=0$, so $X=0$ a.s., whose cf is $1\ne e^{-|t|^3}$.
4 $\varphi_{X_n/n}(t)=\frac{pe^{it/n}}{1-qe^{it/n}}$ with $p=\lambda/n$. Now $n\left(1-(1-\tfrac\lambda n)e^{it/n}\right)=n(1-e^{it/n})+\lambda e^{it/n}\to-it+\lambda$, and $np\,e^{it/n}\to\lambda$, so the cf tends to $\frac{\lambda}{\lambda-it}$, the continuous $\operatorname{Exp}(\lambda)$ cf. Lévy's theorem gives the claim (the discrete twin of the exponential, §2.1).
5 The cf is $\psi_n(t)=e^{-it\sqrt n}\left(1-\frac{it}{\sqrt n}\right)^{-n}$, so $\log\psi_n(t)=-it\sqrt n-n\log\left(1-\frac{it}{\sqrt n}\right)$. With the principal logarithm, $-\log(1-z)=z+\frac{z^2}2+O(|z|^3)$ for small $|z|$: $\log\psi_n(t)=-it\sqrt n+n\left(\frac{it}{\sqrt n}-\frac{t^2}{2n}+O(n^{-3/2})\right)=-\frac{t^2}{2}+O(n^{-1/2})$. Hence $\psi_n(t)\to e^{-t^2/2}$. (This is the CLT of §2.3 for sums of $n$ iid $\operatorname{Exp}(1)$ variables.)
6 $\varphi^n$ is the cf of a sum of $n$ iid copies; $|\varphi|^2$ is the cf of $X-Y$ (Exercise I.5); $\operatorname{Re}\varphi=\frac12(\varphi+\overline\varphi)$ is the cf of the mixture "$X$ or $-X$ with probability $\tfrac12$ each" ($\overline{\varphi(t)}=\varphi_{-X}(t)$); and $\sum p_k\varphi^k$ is the cf of $X_1+\dots+X_N$ with $N\sim(p_k)$ independent of the iid $X_j$ (condition on $N$, as in Exercise I.8). Each is a cf by construction.
7 By Theorem 2.18, $e^{it-3t^2/2}=\varphi_{X+Y}(t)=e^{-t^2/2}\varphi_Y(t)$. Since $e^{-t^2/2}$ never vanishes we may divide: $\varphi_Y(t)=e^{it-t^2}$, the cf of $N(1,2)$. By uniqueness $Y\sim N(1,2)$. (The division step is where non-vanishing of the cf matters; see part 8(b).)
8 (a) Write $\varphi(t_0)=e^{i\theta}$. Then $E\left[1-\cos(t_0X-\theta)\right]=1-\operatorname{Re}\left(e^{-i\theta}\varphi(t_0)\right)=0$ with a non-negative integrand, so $\cos(t_0X-\theta)=1$ a.s., i.e. $t_0X-\theta\in2\pi\mathbb{Z}$ a.s., and $X\in\frac{\theta}{t_0}+\frac{2\pi}{t_0}\mathbb{Z}$. (b) The series has non-negative coefficients $\frac12$ and $\frac{2}{\pi^2k^2}$ for each of $e^{\pm ik\pi t}$, summing to $\varphi_2(0)=1$; so $\varphi_2$ is the cf of $Y'$ with $P(Y'=0)=\frac12$ and $P(Y'=\pm k\pi)=\frac{2}{\pi^2k^2}$ for odd $k$. Let $Y$ have cf $\varphi_1$ (density $\frac{1-\cos x}{\pi x^2}$, part 1) and $X$ also have cf $\varphi_1$, all independent. Then $\varphi_{X+Y}=\varphi_1^2=\varphi_1\varphi_2=\varphi_{X+Y'}$, because $\varphi_1=\varphi_2$ on $[-1,1]$ and $\varphi_1=0$ outside it. So $X+Y\overset{d}{=}X+Y'$ although $Y$ is continuous and $Y'$ is discrete.
III
Markov, Chebyshev, Cantelli and Chernoff.
  • 1 $X\ge0$ has mean $3$. Bound $P(X\ge12)$. If also $\operatorname{Var}(X)=4$, give the Chebyshev and Cantelli bounds for $P(X\ge12)$.
  • 2 Show that Markov's inequality is sharp: for $0\lt m\le a$ find $X\ge0$ with $E[X]=m$ and $P(X\ge a)=m/a$.
  • 3 $X\sim U(0,1)$. Compute $P(|X-\tfrac12|\ge k\sigma)$ exactly for $k=1.5$ and compare with Chebyshev's bound. For which $k$ is the exact probability $0$?
  • 4 (Manufacturing) Rods have mean length $50$ mm and standard deviation $0.2$ mm; nothing else is known. Give a lower bound for the proportion of rods with length strictly between $49.5$ and $50.5$ mm. What is the proportion if the lengths are normal?
  • 5 (Opinion poll) How many people must be sampled so that Chebyshev's inequality guarantees $P(|\hat p-p|\ge0.02)\le0.1$ for every $p$?
  • 6 For $X\sim\operatorname{Poi}(\lambda)$ and $a\gt\lambda$, show that the Chernoff bound is $P(X\ge a)\le e^{-\lambda}\left(\frac{e\lambda}{a}\right)^a$. Evaluate it for $\lambda=4$, $a=12$ and compare with the exact value.
  • 7 Prove that a median $m$ of a law with mean $\mu$ and finite variance $\sigma^2$ satisfies $|m-\mu|\le\sigma$, (a) using Cantelli's inequality, (b) using Jensen's inequality and the fact that a median minimises $E|X-c|$.
  • 8 $X\ge0$ has mean $\mu\gt0$ and variance $\sigma^2$. Show that $P(X=0)\le\frac{\sigma^2}{\sigma^2+\mu^2}$ and compare with Example 6(c).
1 Markov: $P(X\ge12)\le\frac3{12}=\frac14$. Chebyshev: $P(X-3\ge9)\le P(|X-3|\ge9)\le\frac4{81}\approx0.0494$. Cantelli: $\frac{4}{4+81}=\frac4{85}\approx0.0471$.
2 $X=a$ with probability $\frac ma$ and $X=0$ otherwise: $E[X]=m$ and $P(X\ge a)=\frac ma$. By Theorem 2.25(1) such two-point laws are the only ones attaining equality.
3 $\sigma=\frac1{\sqrt{12}}\approx0.2887$, so $k\sigma=0.4330$ for $k=1.5$, and $P(|X-\tfrac12|\ge0.4330)=1-2(0.4330)\approx0.1340$, against Chebyshev's $\frac1{2.25}\approx0.4444$. The exact probability is $\max(0,1-2k\sigma)$, which is $0$ for $k\ge\sqrt3$: a bounded law has no tail beyond its range, while Chebyshev's bound is still $\frac13$ at $k=\sqrt3$.
4 $P(|L-50|\ge0.5)\le\frac{0.04}{0.25}=0.16$, so at least $84\%$ of the rods are within the limits. If the lengths are normal, the proportion is $P(|Z|\lt2.5)\approx0.9876$.
5 $P(|\hat p-p|\ge0.02)\le\frac{p(1-p)}{n(0.02)^2}\le\frac{1}{4n(0.0004)}=\frac{625}{n}$, which is at most $0.1$ when $n\ge6250$.
6 $e^{-ta}M(t)=\exp\left(-ta+\lambda(e^t-1)\right)$; the exponent is minimised at $e^t=a/\lambda$ (positive $t$ since $a\gt\lambda$), giving $\exp\left(-a\log\frac a\lambda+a-\lambda\right)=e^{-\lambda}\left(\frac{e\lambda}{a}\right)^a$. For $\lambda=4$, $a=12$: $e^{-4}\left(\frac{e}{3}\right)^{12}\approx0.00561$, while $P(X\ge12)\approx0.000915$. Chebyshev would give $\frac{4}{64}=0.0625$.
7 (a) If $m\gt\mu+\sigma$, then $P(X\ge m)\ge\frac12$, but Cantelli gives $P(X-\mu\ge m-\mu)\le\frac{\sigma^2}{\sigma^2+(m-\mu)^2}\lt\frac12$, a contradiction; similarly $m\lt\mu-\sigma$ is impossible. (b) $|\mu-m|=|E[X-m]|\le E|X-m|\le E|X-\mu|\le\sqrt{E(X-\mu)^2}=\sigma$, using Jensen twice ($|\cdot|$ and $x^2$) and the minimising property of the median (Theorem 1.29 of §1.3).
8 $\{X=0\}\subseteq\{X-\mu\le-\mu\}$, so Cantelli's lower-tail bound gives $P(X=0)\le\frac{\sigma^2}{\sigma^2+\mu^2}$. Equivalently $P(X\gt0)\ge\frac{\mu^2}{\sigma^2+\mu^2}=\frac{(E X)^2}{E[X^2]}$, which is exactly the second-moment bound of Example 6(c): two proofs of the same inequality.
IV
Jensen, Cauchy–Schwarz and Hölder.
  • 1 $X\gt0$ has $E[X]=2$. What can be said, for every such $X$, about $E[1/X]$, $E[\log X]$, $E[X^2]$ and $E[\sqrt X]$? Are the bounds attained?
  • 2 Prove the AM–GM inequality with weights: for positive $a_j$ and weights $w_j\ge0$ with $\sum w_j=1$, $\prod a_j^{w_j}\le\sum w_ja_j$.
  • 3 For $X\sim\operatorname{Exp}(1)$ compute $\|X\|_r=\left(E[X^r]\right)^{1/r}$ for $r=1,2,3$ and check Lyapunov's inequality.
  • 4 (Gibbs' inequality) For pmfs $p=(p_i)$ and $q=(q_i)$ on a finite set with all $q_i\gt0$, prove that $D(p\|q)=\sum_ip_i\log\frac{p_i}{q_i}\ge0$, with equality iff $p=q$ (terms with $p_i=0$ are $0$). Deduce that the entropy $-\sum p_i\log p_i$ of a law on $n$ points is at most $\log n$.
  • 5 Show that if $a\le X\le b$, then $\operatorname{Var}(X)\le\frac{(b-a)^2}{4}$, and find when equality holds.
  • 6 (Paley–Zygmund) For $X\ge0$ with $0\lt E[X^2]\lt\infty$ and $0\le\theta\le1$, prove $P(X\gt\theta E[X])\ge(1-\theta)^2\frac{(E[X])^2}{E[X^2]}$. Evaluate the bound for $X\sim\operatorname{Poi}(1)$, $\theta=\tfrac12$, and compare with the exact probability.
  • 7 Use Hölder's inequality to show that $r\mapsto\log E|X|^r$ is convex on any interval of $r\ge0$ where it is finite, and deduce Lyapunov's inequality from this.
  • 8 (Finance: volatility drag) Each year an investment is multiplied by $R=1.5$ or $R=0.6$ with probability $\tfrac12$ each, independently. Compute $E[R]$ and $E[\log R]$. Show that the expected wealth grows while, by Jensen's inequality and the strong law of §2.3, the wealth itself tends to $0$ almost surely.
1 By Theorem 2.28: $E[1/X]\ge\frac12$, $E[\log X]\le\log2$, $E[X^2]\ge4$, $E[\sqrt X]\le\sqrt2$. All four are attained by $X\equiv2$, and (by the equality case for strictly convex or concave functions) only by it. Nothing more can be said: $E[1/X]$ and $E[X^2]$ can be arbitrarily large.
2 Let $X=a_j$ with probability $w_j$. Concavity of $\log$: $\sum w_j\log a_j=E[\log X]\le\log E[X]=\log\sum w_ja_j$. Exponentiate.
3 $E[X^r]=\Gamma(1+r)$: $\|X\|_1=1$, $\|X\|_2=\sqrt2\approx1.414$, $\|X\|_3=6^{1/3}\approx1.817$, increasing in $r$ as Lyapunov's inequality requires.
4 Let $I$ have pmf $p$ and $W=q_I/p_I$ on $\{p_I\gt0\}$. By Jensen for the concave $\log$, $-D(p\|q)=E[\log W]\le\log E[W]=\log\sum_{p_i\gt0}q_i\le\log1=0$. Equality needs $W$ constant and $\sum_{p_i\gt0}q_i=1$, which forces $p=q$. With $q_i=\frac1n$: $D(p\|q)=\log n-H(p)\ge0$.
5 With $c=\frac{a+b}{2}$, $\operatorname{Var}(X)=\min_tE(X-t)^2\le E(X-c)^2\le\left(\frac{b-a}{2}\right)^2$ since $|X-c|\le\frac{b-a}2$. Equality needs $|X-c|=\frac{b-a}{2}$ a.s. and $E[X]=c$: $X=a$ or $b$ with probability $\frac12$ each.
6 Split $E[X]=E[X\mathbf{1}\{X\le\theta EX\}]+E[X\mathbf{1}\{X\gt\theta EX\}]\le\theta E[X]+\sqrt{E[X^2]\,P(X\gt\theta EX)}$ (Cauchy–Schwarz on the second term). Rearrange: $(1-\theta)E[X]\le\sqrt{E[X^2]P(X\gt\theta EX)}$, and square. For $\operatorname{Poi}(1)$: $E[X^2]=2$, so the bound is $\frac14\cdot\frac12=\frac18$, while $P(X\gt\tfrac12)=P(X\ge1)=1-e^{-1}\approx0.632$.
7 Let $r=\lambda r_1+(1-\lambda)r_2$ with $0\lt\lambda\lt1$. Hölder with $p=\frac1\lambda$, $q=\frac1{1-\lambda}$: $E|X|^r=E\left[|X|^{\lambda r_1}|X|^{(1-\lambda)r_2}\right]\le\left(E|X|^{r_1}\right)^\lambda\left(E|X|^{r_2}\right)^{1-\lambda}$. Taking logs gives convexity of $L(r)=\log E|X|^r$. Since $L(0)=0$, the chord slope $L(r)/r$ is non-decreasing in $r\gt0$, i.e. $\left(E|X|^r\right)^{1/r}=e^{L(r)/r}$ increases with $r$.
8 $E[R]=1.05$, so the expected wealth after $n$ years is $1.05^n\to\infty$. But $E[\log R]=\frac12\log(1.5\times0.6)=\frac12\log0.9\approx-0.0527\lt0=\log1$; Jensen explains why $E[\log R]\lt\log E[R]$. Wealth after $n$ years is $W_n=\exp\left(\sum_{j\le n}\log R_j\right)$, and by the strong law $\frac1n\sum\log R_j\to-0.0527$ a.s., so $W_n\approx e^{-0.0527n}\to0$ a.s. The mean is carried by rare lucky paths.
🎯 Exam corner CSIR Part BCSIR Part CGATE ST

E1. CSIR Part B A random variable $X$ has characteristic function $\varphi(t)=\cos(t)\,e^{2it-3t^2}$. Then $E[X^2]$ equals (A) $7$; (B) $10$; (C) $11$; (D) $13$.

Idea $e^{2it-3t^2}$ is the cf of $N(2,6)$ and $\cos t$ that of $V=\pm1$. By Theorem 2.18 and uniqueness, $X\overset{d}{=}Y+V$ with $Y\sim N(2,6)$ independent of $V$.
Compute $E[X]=2$, $\operatorname{Var}(X)=6+1=7$, so $E[X^2]=7+4=11$. Option (A) is the variance and (B) forgets $V$ ($6+4$).
Answer (C).

E2. CSIR Part B GATE ST Among all random variables with mean $10$ and variance $4$, the largest possible value of $P(X\ge16)$ is (A) $\tfrac19$; (B) $\tfrac1{10}$; (C) $\tfrac49$; (D) $\tfrac58$.

Idea A one-sided tail with given mean and variance: Cantelli's inequality, which is sharp.
Compute $\lambda=6$, $\sigma^2=4$: $P(X\ge16)\le\frac{4}{4+36}=\frac1{10}$. It is attained by $X=16$ with probability $\frac1{10}$ and $X=10-\frac46=\frac{28}{3}$ with probability $\frac9{10}$ (mean $1.6+8.4=10$, variance $\frac{1}{10}\cdot36+\frac9{10}\cdot\frac49=4$). Option (A) is Chebyshev's two-sided bound, valid but not the maximum; (D) is Markov's bound, which does not even apply without $X\ge0$.
Answer (B).

E3. CSIR Part B $X$ is a positive random variable with $E[X]=4$ and all the expectations below finite. Which statement is necessarily true? (A) $E[\sqrt X]\ge2$; (B) $E[\log X]\le\log4$; (C) $E[1/X]\le\tfrac14$; (D) $E[X^2]\le16$.

Idea Jensen: concave functions ($\sqrt{\cdot}$, $\log$) give "$\le$", convex ones ($1/x$, $x^2$) give "$\ge$".
Check (B) is Jensen for $\log$. The other three hold in the opposite direction, and each fails for $X=2$ or $6$ with probability $\tfrac12$ each: $E[\sqrt X]\approx1.932\lt2$, $E[1/X]=\frac13\gt\frac14$, $E[X^2]=20\gt16$.
Answer (B).

E4. CSIR Part C Which of the following functions are characteristic functions of some random variable? (One or more options may be correct.) (A) $\cos(t^2)$; (B) $e^{-|t|}\cos t$; (C) $\dfrac{1}{2-e^{it}}$; (D) $\max(1-t^2,\,0)$.

(A) No $\cos(t^2)=1-\frac{t^4}{2}+\dots$ has $\varphi''(0)=0$, which by Theorem 2.19(3) would force $X\equiv0$ and $\varphi\equiv1$.
(B) Yes It is the product of the $C(0,1)$ cf and the cf of $\pm1$, hence the cf of $X+V$ with $X\sim C(0,1)$ and $V=\pm1$ independent.
(C) Yes $\frac{1}{2-e^{it}}=\frac{1/2}{1-\frac12e^{it}}$ is the cf of the geometric law $P(X=k)=2^{-(k+1)}$ on $\{0,1,\dots\}$.
(D) No It is continuous and integrable, so if it were a cf, Theorem 2.21(2) would give a density $f(x)=\frac1\pi\int_0^1(1-t^2)\cos(tx)\,dt=\frac{2(\sin x-x\cos x)}{\pi x^3}$. At $x=4.5$, $\sin x-x\cos x\approx-0.029\lt0$, so $f$ would be negative somewhere, which is impossible. (Pólya's criterion does not apply either: $1-t^2$ is concave.)
Answer (B) and (C).

E5. CSIR Part C Let $X$ have mean $\mu$ and finite variance $\sigma^2\gt0$. Which of the following are true for every such $X$? (A) $P(|X|\ge1)\le E[X^2]$; (B) $P(|X-\mu|\ge\sigma/2)\le\tfrac14$; (C) $P(X\ge\mu+\sigma)\le\tfrac12$; (D) $E[X^4]\ge\left(E[X^2]\right)^2$.

(A) True Theorem 2.25(2) with $r=2$, $a=1$.
(B) False Chebyshev with $k=\frac12$ gives only the bound $4$. For $X=\pm1$ with probability $\frac12$ each ($\mu=0$, $\sigma=1$), $P(|X|\ge\frac12)=1$.
(C) True Cantelli with $\lambda=\sigma$: $\frac{\sigma^2}{2\sigma^2}=\frac12$.
(D) True Jensen for $x^2$ applied to $X^2$ (or Cauchy–Schwarz); if $E[X^4]=\infty$ it holds trivially.
Answer (A), (C) and (D).

E6. CSIR Part C GATE ST Let $X_1,X_2,\dots$ be iid standard Cauchy and $\bar X_n=\frac1n\sum_{j=1}^nX_j$. Which of the following are true? (A) $\bar X_n$ is standard Cauchy for every $n$. (B) $\frac12(X_1+X_2)$ has the same law as $X_1$. (C) $X_1-X_2$ has the $C(0,2)$ law. (D) $P(|\bar X_n|\gt1)\to0$ as $n\to\infty$.

(A) True $\varphi_{\bar X_n}(t)=\left(e^{-|t|/n}\right)^n=e^{-|t|}$ (Theorem 2.22(3)).
(B) True The case $n=2$ of (A).
(C) True $\varphi_{X_1-X_2}(t)=e^{-|t|}e^{-|-t|}=e^{-2|t|}$, the cf of $C(0,2)$.
(D) False $P(|\bar X_n|\gt1)=P(|X_1|\gt1)=\frac12$ for every $n$: the sample mean does not converge in probability (no weak law without a mean, §2.3).
Answer (A), (B) and (C).
🧑‍🏫 For the teacher

Suggested plan: 3 lectures × 60 min.

  1. Characteristic functions. Motivate with the Cauchy law, which has no mgf. Definition 2.8, Theorem 2.17 (do (3) and (6) on the board), Theorem 2.18 with the warning that only the joint cf characterises independence. Theorem 2.19: prove the expansion inequality for $n=0,1,2$ only and the Fatou argument for (3). Theorem 2.20: derive the normal cf by the differential equation; leave the gamma case for reading. Example 1. Project Interactive 1 with $n=1$ to show lattice periodicity and the Cauchy corner.
  2. Inversion and continuity. Theorem 2.21(1) as a careful sketch (Fubini, Dirichlet integral, dominated convergence), then Theorem 2.22 with the Laplace–Cauchy duality, which students enjoy. Definition 2.9 with the $X_n=\frac1n$ example. Lévy's theorem: prove the truncation inequality, state the rest, and show the $N(0,n)$ counterexample. Example 2 as a class poll, Example 3(b). Play Interactive 1 with the exponential and Bernoulli laws to watch the standardised cfs approach $e^{-t^2/2}$ (a preview of §2.3).
  3. Inequalities. Markov (one-line proof), Chebyshev with its extremal law, Cantelli with the optimisation over $u$. Example 4 with Interactive 2 on the log scale; Example 5. Jensen with the supporting line picture, then Lyapunov, AM–GM, Cauchy–Schwarz and Hölder via Young. Example 6 and E3–E5.

Discussion questions. (1) Why does the Chebyshev bound for $\bar X_n$ need only uncorrelated variables, while the cf of $S_n$ needs independent ones? (2) Chebyshev's bound is attained, yet it is far from the truth for every common law. In what sense is it "best possible", and when is it nevertheless the right tool? (3) In Exercise IV.8 the expected wealth grows while almost every investor is ruined. Which quantity should an investor maximise, and why?

Misconceptions to watch for. Believing that $\varphi_{X+Y}=\varphi_X\varphi_Y$ characterises independence; thinking every real, even function bounded by $1$ is a cf; applying Markov's inequality to variables that take negative values; using Chebyshev with $k\lt1$; mixing up the direction of Jensen's inequality for concave functions; reading $E[X]$ off $\varphi'(0)$ without the factor $i$; dropping the continuity-at-$0$ hypothesis in Lévy's theorem.

Suggested homework. I(1, 4, 5, 8), II(1, 3, 5, 7), III(1, 3, 6, 7), IV(1, 4, 6, 8); Exam corner E1, E4, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. How many participants does an online experiment (an "A/B test") or a clinical survey need, if the guarantee must hold whatever the true response rate is? How much do Chebyshev's inequality, an exponential (Chernoff–Hoeffding) bound and the normal approximation disagree?

Why it matters. Technology companies run thousands of experiments a year, and public-health agencies plan vaccination-coverage surveys, with sample sizes chosen to control the probability that an estimated proportion misses the truth by more than a margin $\varepsilon$. A bound that holds for every law (Chebyshev) is safe but expensive; the normal approximation is cheap but only asymptotic. Hoeffding's inequality, $P(|\hat p-p|\ge\varepsilon)\le2e^{-2n\varepsilon^2}$ for averages of $[0,1]$-valued variables, is a non-asymptotic compromise proved with the Chernoff method of Theorem 2.25(3).

What to do.

  1. For $\varepsilon=0.02$ and confidence levels $1-\delta=0.90,0.95,0.99$, compute the sample sizes required by Chebyshev ($n\ge\frac{1}{4\varepsilon^2\delta}$), by Hoeffding ($n\ge\frac{\log(2/\delta)}{2\varepsilon^2}$) and by the normal approximation ($n\ge\frac{z_{\delta/2}^2}{4\varepsilon^2}$). Tabulate and plot them against $\delta$.
  2. For each $n$ and for $p\in\{0.05,0.2,0.5\}$, compute the exact probability $P(|\hat p-p|\ge\varepsilon)$ from the binomial law (scipy.stats.binom). Which guarantees actually hold, and with how much to spare?
  3. Prove Hoeffding's lemma for a single Bernoulli variable, $E[e^{s(I-p)}]\le e^{s^2/8}$, at least numerically on a grid of $p$ and $s$, and derive the bound above with the Chernoff method.
  4. Write a one-paragraph recommendation: when would you, as a statistician, accept the normal-approximation sample size, and when would you insist on a non-asymptotic bound?

Tools: Python (numpy, scipy.stats) or R; Interactive 2 for the shape of the tails; Example 5 for the Chebyshev calculation.

Hand in: A two-page note with the sample-size table and plot, the exact-coverage table, and the recommendation.

Going further. Read about Bernstein's inequality, which uses the variance as well as the range, and about the Berry–Esseen theorem (§2.3), which bounds the error of the normal approximation itself. Concentration inequalities of this kind are central in machine-learning theory (generalisation bounds) and in sequential testing.

Instructor note: for $\varepsilon=0.02$ and $\delta=0.05$ the three sample sizes are $12500$ (Chebyshev), about $4612$ (Hoeffding) and about $2401$ (normal). The exact binomial error probabilities at the normal-approximation size are close to $0.05$ for $p=0.5$ and much smaller for $p=0.05$, because $p(1-p)$ is then far below $\frac14$; students should notice that the worst case is $p=\frac12$.

🧪 Self-check quiz

0/5 correct

Q1. The characteristic function of the exponential law with rate $\lambda$ is

Q2. A random variable has characteristic function $e^{-3|t|}$. Its law is

Q3. $X$ has mean $0$ and variance $1$; nothing else is known. The best upper bound for $P(X\ge2)$ valid for all such $X$ is

Q4. For every random variable $X$ with $E[e^X]\lt\infty$ and $E|X|\lt\infty$,

Q5. The characteristic function of $X$ is real-valued for all $t$. Then necessarily