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|$.
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})$.
Let $\varphi=\varphi_X$. Then:
- $\varphi(t)$ exists for every real $t$, $\varphi(0)=1$ and $|\varphi(t)|\le1$;
- $\varphi(-t)=\overline{\varphi(t)}$;
- $\varphi$ is uniformly continuous on $\mathbb{R}$;
- $\varphi_{aX+b}(t)=e^{ibt}\varphi_X(at)$ for real constants $a,b$;
- $\varphi$ is real-valued if and only if $X$ is symmetric about $0$, that is, $X$ and $-X$ have the same law;
- $\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).
- 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.$$
- $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.
- (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).$$
- 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)$.
- (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)$. ∎
| 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). ∎
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.
Let $X$ have cdf $F$ and cf $\varphi$.
- 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)$.
- (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.$$
- (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)$. ∎
- (Uniqueness) If $\varphi_X(t)=\varphi_Y(t)$ for all $t$, then $X$ and $Y$ have the same distribution.
- (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$.
- (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.
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.
Let $X_n$ have cf $\varphi_n$.
- If $X_n\xrightarrow{d}X$, then $\varphi_n(t)\to\varphi_X(t)$ for every real $t$.
- 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$.
- (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.
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$.
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.
- (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$.
- (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$.
- (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$. ∎
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.
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$.
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.
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$.
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:
- $(E[X])^2\le E[X^2]$, $|E[X]|\le E|X|$ and $e^{E[X]}\le E[e^X]$;
- for $X\gt0$: $E[\log X]\le\log E[X]$, $E[1/X]\ge1/E[X]$ and $E[\sqrt X]\le\sqrt{E[X]}$;
- (Lyapunov's inequality) for $0\lt r\lt s$, $\left(E|X|^r\right)^{1/r}\le\left(E|X|^s\right)^{1/s}$;
- (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. ∎
For $p\ge1$ write $\|X\|_p=\left(E|X|^p\right)^{1/p}$.
- (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$.
- (Hölder) If $p,q\gt1$ with $\frac1p+\frac1q=1$, then $E|XY|\le\|X\|_p\,\|Y\|_q$.
- (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$. ∎
- 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.
- $\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)).
- 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$.
- $\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).
- 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$.
- 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).
- 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$.
- 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).
- 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.
- 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.
- 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
- 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 (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 $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 $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.
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$.
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$.
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$.
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)$.
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$.
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$.
Suggested plan: 3 lectures × 60 min.
- 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.
- 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).
- 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 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.
- 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$.
- 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?
- 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.
- 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.
🧪 Self-check quiz
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