Inequalities and Limit Theorems

(a) Markov. $X\ge 0$ and $E(X)=10<\infty$, which are the two hypotheses, so with $a=16$

$$P(X\ge 16)\le \frac{E(X)}{16}=\frac{10}{16}=\frac{5}{8}.$$

Only non-negativity and the mean were used; the variance played no part.

(b) Chebyshev. If $X\ge 16$ then $X-10\ge 6$, so $|X-10|\ge 6$: the event $\{X\ge 16\}$ is contained in $\{|X-\mu |\ge 6\}$, and probabilities respect containment. Chebyshev with $k=6$ gives

$$P(X\ge 16)\le P(|X-10|\ge 6)\le \frac{{\sigma }^2}{k^2}=\frac{9}{36}=\frac{1}{4}.$$

This used finite mean and variance, not non-negativity. It is better than Markov because the variance is small relative to the mean; Markov, which cannot see the variance, has to allow for a spike at $16$ carrying $\frac{5}{8}$ of the mass.

(c) Cantelli. With $t=6$,

$$P(X-10\ge 6)\le \frac{{\sigma }^2}{{\sigma }^2+t^2}=\frac{9}{9+36}=\frac{9}{45}=\frac{1}{5}.$$

Halving Chebyshev is not valid: $\frac{1}{8}$ would be a legitimate one-sided bound only if the distribution were known to be symmetric about its mean, and symmetry is not a hypothesis. Part (d) produces a distribution with $P(X\ge 16)=\frac{1}{5}>\frac{1}{8}$, which shows $\frac{1}{8}$ is actually false, not merely unproved.

(d) A distribution attaining $\frac{1}{5}$. Try two atoms: $X=16$ with probability $\frac{1}{5}$ and $X=c$ with probability $\frac{4}{5}$. The mean fixes $c$:

$$\frac{16}{5}+\frac{4c}{5}=10⟹4c=34⟹c=\frac{17}{2}.$$

Check the variance from the deviations $16-10=6$ and $\frac{17}{2}-10=-\frac{3}{2}$:

$$\mathrm{Var}(X)=\frac{1}{5}\cdot 36+\frac{4}{5}\cdot \frac{9}{4}=\frac{36}{5}+\frac{9}{5}=\frac{45}{5}=9.✓$$

Both values are positive, so $X\ge 0$; and $P(X\ge 16)=\frac{1}{5}$ exactly. This is the general extremal shape for Cantelli — one atom at the threshold, the rest of the mass just on the other side of the mean — and it shows that no bound smaller than $\frac{1}{5}$ can hold for every variable with this mean and variance.

(a) Reduce to Markov. The map $y\mapsto y^r$ is strictly increasing on $[0,\infty )$. Because $Y\ge 0$ and $a>0$, both $Y$ and $a$ lie in that domain, so $Y\ge a$ holds if and only if $Y^r\ge a^r$: the events $\{Y\ge a\}$ and $\{Y^r\ge a^r\}$ are the same event and have the same probability. This is where non-negativity is used — for a variable that can be negative and even $r$, $Y^r\ge a^r$ is also produced by $Y\le -a$, and the two events differ.

The variable $Y^r$ is non-negative with finite mean $E(Y^r)$, so Markov's inequality applies to it at threshold $a^r>0$:

$$P(Y\ge a)=P\left(Y^r\ge a^r\right)\le \frac{E(Y^r)}{a^r}.■$$

(b) The uniform on $[0,2]$. The density is $\frac{1}{2}$ on $[0,2]$, so $P(Y\ge \frac{3}{2})=\frac{2-3/2}{2}=\frac{1}{4}$ exactly. The moments are

$$E(Y)=1,E(Y^2)={\int }_0^2\frac{y^2}{2}dy=\frac{1}{2}\cdot \frac{8}{3}=\frac{4}{3},E(Y^4)={\int }_0^2\frac{y^4}{2}dy=\frac{1}{2}\cdot \frac{32}{5}=\frac{16}{5}.$$

With $a=\frac{3}{2}$ the bounds are

$$r=1:\frac{1}{3/2}=\frac{2}{3},r=2:\frac{4/3}{9/4}=\frac{16}{27},r=4:\frac{16/5}{81/16}=\frac{256}{405}.$$

Sanity check: $\frac{2}{3}\approx 0.667$, $\frac{16}{27}\approx 0.593$, $\frac{256}{405}\approx 0.632$, all above the truth $0.25$, as every valid bound must be.

(c) The bound is not monotone in $r$: going from $r=1$ to $r=2$ improved it, and going on to $r=4$ made it worse again. Raising $r$ weights the far tail more heavily in $E(Y^r)$, but the denominator $a^r$ grows too, and which effect wins depends on the distribution and on $a$. So $r$ is a free parameter to be chosen, exactly like the shift $u$ in Cantelli's proof or the exponent $s$ in a Chernoff bound — and the sharpest of these bounds is the infimum over $r$. (For this $Y$, $r=3$ gives $E(Y^3)=2$ and the bound $\frac{2}{27/8}=\frac{16}{27}$ again, a tie with $r=2$.)

(a) The MGF. By the definition and the series for the exponential,

$$M_X(s)=E\left(e^{sX}\right)=\sum _{k=0}^{\infty }{e}^{sk}\frac{e^{-\lambda }{\lambda }^k}{k!}=e^{-\lambda }\sum _{k=0}^{\infty }\frac{{\left(\lambda e^s\right)}^k}{k!}=e^{-\lambda }{e}^{\lambda e^s}=\exp \left(\lambda \left(e^s-1\right)\right).$$

The series converges for every real $s$, so the MGF exists everywhere; in particular it is finite for some $s>0$, which is the hypothesis the generic Chernoff bound needs.

(b) Optimise over $s$. For any $s>0$, Markov applied to $e^{sX}$ gives $P(X\ge a)\le e^{-sa}{M}_X(s)=\exp \left(f(s)\right)$ with

$$f(s)=-sa+\lambda \left(e^s-1\right),f^{\prime }(s)=-a+\lambda e^s,f^{\prime \prime }(s)=\lambda e^s>0.$$

So $f$ is convex and its minimum is at $f^{\prime }(s^{\ast })=0$, that is $e^{s^{\ast }}=a/\lambda$, or $s^{\ast }=\log (a/\lambda )$. Because $a>\lambda$ this is strictly positive, so it is an admissible choice. Substituting,

$$f(s^{\ast })=-a\log \frac{a}{\lambda }+\lambda \left(\frac{a}{\lambda }-1\right)=-a\log \frac{a}{\lambda }+a-\lambda ,$$

and exponentiating,

$$P(X\ge a)\le e^{-\lambda }{e}^a{\left(\frac{\lambda }{a}\right)}^a=e^{-\lambda }{\left(\frac{e\lambda }{a}\right)}^a.$$

When $a\le \lambda$, $f^{\prime }(s)=\lambda e^s-a>0$ for every $s>0$, so $f$ is increasing on $(0,\infty )$ and the infimum is approached as $s\to 0^{+}$, where $e^{-sa}{M}_X(s)\to 1$. The bound degenerates to $P(X\ge a)\le 1$: a Chernoff bound has nothing to say about thresholds at or below the mean.

(c) Four numbers for $\lambda =1$, $a=4$.

Chernoff: $e^{-1}{\left(\frac{e}{4}\right)}^4=\frac{e^3}{256}$.

Markov ($X\ge 0$, mean $1$): $\frac{1}{4}$.

Chebyshev: $\{X\ge 4\}\subseteq \{|X-1|\ge 3\}$ and ${\sigma }^2=1$, so the bound is $\frac{1}{9}$.

Exact: $P(X\ge 4)=1-e^{-1}\left(1+1+\frac{1}{2}+\frac{1}{6}\right)=1-\frac{8}{3}{e}^{-1}$.

Sanity check on the order: $e^3\approx 20.09$ gives Chernoff $\approx 0.078$; Chebyshev $\approx 0.111$; Markov $0.25$; and $\frac{8}{3}{e}^{-1}\approx 0.981$ gives the exact value $\approx 0.019$. So

$$\text{exact}<\text{Chernoff}<\text{Chebyshev}<\text{Markov},$$

every bound exceeding the truth, and tightening in the order of how much of the distribution each one sees: one moment, two moments, the whole MGF. Even Chernoff is loose by a factor of about four here — it is a bound on a worst case, not an estimate.

Convexity first. $\sqrt{x}$ has second derivative $-\frac{1}{4}{x}^{-3/2}<0$, so it is concave; $\frac{1}{x}$ has second derivative $\frac{2}{x^3}>0$, convex; $x^2$ has second derivative $2>0$, convex. Jensen reads $E(g(X))\ge g(E(X))$ for convex $g$ and $E(g(X))\le g(E(X))$ for concave $g$.

(a) $E(X)=\frac{1+4}{2}=\frac{5}{2}$.

For $\sqrt{x}$ (concave): $E(\sqrt{X})=\frac{1+2}{2}=\frac{3}{2}$, while $\sqrt{E(X)}=\sqrt{5/2}$. Since ${\left(\frac{3}{2}\right)}^2=\frac{9}{4}<\frac{5}{2}$, indeed $\frac{3}{2}<\sqrt{5/2}$: the mean of the root is below the root of the mean. $✓$

For $\frac{1}{x}$ (convex): $E(1/X)=\frac{1+1/4}{2}=\frac{5}{8}$, while $1/E(X)=\frac{2}{5}$. And $\frac{5}{8}=0.625>0.4=\frac{2}{5}$. $✓$

For $x^2$ (convex): $E(X^2)=\frac{1+16}{2}=\frac{17}{2}=\frac{34}{4}$, while $E(X{)}^2=\frac{25}{4}$. $✓$ (The gap $\frac{9}{4}$ is the variance, which is the same statement.)

(b) Jensen turns each question into a one-line verdict.

$E(\sqrt{X})=3$ is impossible: $\sqrt{x}$ is concave, so $E(\sqrt{X})\le \sqrt{E(X)}=\sqrt{4}=2<3$ for every positive $X$ with mean $4$.

$E(1/X)=\frac{1}{5}$ is impossible: $\frac{1}{x}$ is convex, so $E(1/X)\ge \frac{1}{E(X)}=\frac{1}{4}>\frac{1}{5}$.

$E(X^2)=20$ is possible: convexity only requires $E(X^2)\ge 16$, and $20$ clears it. Take $X=2$ or $6$ with probability $\frac{1}{2}$ each: $E(X)=4$ and $E(X^2)=\frac{4+36}{2}=20$, and $X>0$. $✓$

(c) Here $E(X^2)=16=E(X{)}^2$, so Jensen's inequality for the strictly convex $g(x)=x^2$ holds with equality. The equality case says this happens only when $X$ is almost surely constant, and the constant must be its mean: $P(X=4)=1$. (Equivalently, $\mathrm{Var}(X)=E(X^2)-E(X{)}^2=0$, and a variable with zero variance is almost surely its mean.)

(a) The three errors.

Step 1 quotes the wrong special case. The bound $e^{-2n{\epsilon }^2}$ is Hoeffding's inequality for summands in $[0,1]$. The general statement is

$$P\left(S_n-E(S_n)\ge t\right)\le \exp \left(-\frac{2t^2}{{\sum }_i(b_i-a_i{)}^2}\right),$$

and here every $b_i-a_i=4$, not $1$. The width of the range enters squared, so this is not a small correction — it is a factor of $16$ in the exponent. Independence, which Step 1 does state, is genuinely needed and is fine.

Step 3 forgets the union. The one-sided bound controls $\{{\bar{X}}_n-\mu \ge \epsilon \}$; the two-sided event is the union of that with $\{{\bar{X}}_n-\mu \le -\epsilon \}$, which is bounded by applying the one-sided result to $-X_i$. Boole's inequality then gives twice the one-sided bound, so the two-sided guarantee carries a factor $2$.

Step 4 reads a bound as an estimate. Hoeffding gives an upper bound valid for every distribution on $[0,4]$; it is not the probability, and for the particular distribution in the laboratory the truth may be far smaller. "At most" is all that has been shown.

Step 2 is arithmetic on the wrong formula and is not itself an error.

(b) The correct guarantee. With $t=n\epsilon$ and ${\sum }_i(b_i-a_i{)}^2=16n$,

$$P\left({\bar{X}}_n-\mu \ge \epsilon \right)=P\left(S_n-E(S_n)\ge n\epsilon \right)\le \exp \left(-\frac{2n^2{\epsilon }^2}{16n}\right)=\exp \left(-\frac{n{\epsilon }^2}{8}\right).$$

At $n=800$, $\epsilon =0.2$: the exponent is $\frac{800\times 0.04}{8}=4$, so the one-sided bound is $e^{-4}$ and the two-sided bound is

$$P\left(|{\bar{X}}_n-\mu |\ge 0.2\right)\le 2e^{-4}.$$

Sanity check by rescaling: $X_i/4\in [0,1]$ and the event is $|\overline{X/4}-\mu /4|\ge 0.05$, so the $[0,1]$ form gives $2e^{-2\cdot 800\cdot 0.0025}=2e^{-4}$, the same. Numerically $2e^{-4}\approx 0.037$ — a real guarantee, and twenty-six orders of magnitude away from the student's $e^{-64}$.

(c) Chebyshev with a known variance. $\mathrm{Var}({\bar{X}}_n)=\frac{1}{800}$, so

$$P\left(|{\bar{X}}_n-\mu |\ge 0.2\right)\le \frac{1/800}{0.04}=\frac{1}{32}.$$

Now $\frac{1}{32}=0.03125<2e^{-4}\approx 0.0366$: here Chebyshev beats Hoeffding. There is no contradiction. Hoeffding uses only the range $[0,4]$ and must cover the worst distribution on it — for instance the two-point distribution at $0$ and $4$, which has variance $4$, four times the variance we were told. For that distribution Chebyshev would give $\frac{4}{32}=\frac{1}{8}$, and Hoeffding would win. Hoeffding's strength is its exponential decay in $n$ and in ${\epsilon }^2$, which will overtake any $\frac{1}{n{\epsilon }^2}$ bound for larger $n$ or larger deviations; at this moderate deviation, knowing the variance is worth more than knowing the range.

(a) Take $g(x)=\frac{1}{x}$ on the open interval $(0,\infty )$; $g^{\prime \prime }(x)=\frac{2}{x^3}>0$, so $g$ is strictly convex. $X$ takes values in $(0,\infty )$, has finite mean, and $E(g(X))=E(1/X)$ is finite by hypothesis. Jensen gives

$$E\left(\frac{1}{X}\right)\ge \frac{1}{E(X)},$$

and multiplying through by $E(X)>0$ (positive because $X>0$) yields $E(X)E(1/X)\ge 1$. $■$

Since $g$ is strictly convex, equality in Jensen holds if and only if $X$ is almost surely constant. So $E(X)E(1/X)=1$ exactly when $P(X=c)=1$ for some $c>0$ — and then both factors are $c$ and $\frac{1}{c}$, which checks.

(b) Let $X$ be a random variable that takes the value $x_i$ with probability $\frac{1}{n}$ for each $i$ (if some $x_i$ coincide, the probabilities simply add). Then $X>0$ and

$$E(X)=\frac{x_1+\cdots +x_n}{n},E(\log X)=\frac{\log x_1+\cdots +\log x_n}{n}=\log {\left(x_1\cdots x_n\right)}^{1/n}.$$

The function $\log$ has second derivative $-\frac{1}{x^2}<0$ on $(0,\infty )$, so it is strictly concave, and both expectations are finite sums. Jensen in its concave form gives $E(\log X)\le \log E(X)$, that is

$$\log {\left(x_1\cdots x_n\right)}^{1/n}\le \log \frac{x_1+\cdots +x_n}{n}.$$

Applying the strictly increasing function $\exp$ to both sides preserves the inequality and gives AM–GM. $■$

For the equality case, strict concavity means equality in Jensen holds only when $X$ is almost surely constant, and a variable taking each of the $x_i$ with positive probability is constant only if all the $x_i$ coincide. Conversely if all $x_i=c$ both sides equal $c$.

(c) Fix $s$ in the interval and take $g(x)=e^{sx}$. Its second derivative is $s^2{e}^{sx}\ge 0$, so $g$ is convex on all of $\mathbb{R}$, whatever the sign of $s$. $X$ has finite mean and $E(g(X))=M_X(s)$ is finite by hypothesis, so Jensen gives

$$M_X(s)=E\left(e^{sX}\right)\ge e^{sE(X)}=e^{s\mu }.■$$

Now let $a\le \mu$ and $s>0$. Then $s(\mu -a)\ge 0$, so

$$e^{-sa}{M}_X(s)\ge e^{-sa}{e}^{s\mu }=e^{s(\mu -a)}\ge 1.$$

This holds for every $s>0$, hence for the infimum: the Chernoff bound is at least $1$ and says nothing at all about $P(X\ge a)$ when $a\le \mu$. That is as it should be — a variable is typically on either side of its mean with substantial probability, and no tail bound can pretend otherwise. It also explains why, for $a>\mu$, the optimising $s$ is bounded away from $0$: near $s=0$ the bound is close to $1$, and all the gain comes from moving $s$ out to where $e^{-sa}$ has bitten.

(a) $X_n=U^n$: all four modes. Fix an outcome $\omega$ and write $u=U(\omega )\in (0,1)$. Then $u^n\to 0$ as a sequence of numbers, since $0<u<1$. So $X_n(\omega )\to 0$ for every $\omega$, and in particular almost surely. Almost sure convergence implies convergence in probability, which implies convergence in distribution.

For $L^2$, compute directly:

$$E\left[(X_n-0{)}^2\right]=E\left(U^{2n}\right)={\int }_0^1{u}^{2n}du=\frac{1}{2n+1}⟶0.$$

So $X_n\to 0$ in every sense.

(b) $Y_n=n{U}^n$: almost surely, in probability, in distribution — but not in $L^2$. Again fix $u=U(\omega )\in (0,1)$. The ratio of consecutive terms is

$$\frac{(n+1)u^{n+1}}{n{u}^n}=u\left(1+\frac{1}{n}\right)⟶u<1,$$

so from some index on the terms shrink by at least a fixed factor $r$ with $u<r<1$, and $n{u}^n\to 0$ (the exponential decay of $u^n$ beats the linear growth of $n$). Hence $Y_n\to 0$ for every $\omega$, so almost surely, and therefore in probability and in distribution by the implications.

In $L^2$ it fails:

$$E\left(Y_n^2\right)=n^2{\int }_0^1{u}^{2n}du=\frac{n^2}{2n+1}⟶\infty .$$

The sequence converges to $0$ at every single outcome and its mean square diverges — because near $u=1$ the convergence is very slow and $n^2$ is very large. (Even the mean does not go to zero: $E(Y_n)=\frac{n}{n+1}\to 1$.) This is a case of almost sure convergence not implying $L^2$ convergence.

(c) $Z_n$: in probability, in $L^2$, in distribution — but not almost surely. For any $\epsilon \in (0,1]$, $P(|Z_n|\ge \epsilon )=P(Z_n=1)=\frac{1}{n}\to 0$, so $Z_n\to 0$ in probability, hence in distribution. And $E(Z_n^2)=E(Z_n)=\frac{1}{n}\to 0$, so also in $L^2$.

For the almost-sure question, note that $Z_n$ takes only the values $0$ and $1$, so the numerical sequence $Z_n(\omega )$ converges to $0$ if and only if it is eventually $0$: there is some $N$ with $Z_n(\omega )=0$ for all $n\ge N$. Fix $N\ge 2$ and $M\ge N$. By independence,

$$P\left(Z_n=0\text{ for }N\le n\le M\right)=\prod _{n=N}^M\left(1-\frac{1}{n}\right)=\prod _{n=N}^M\frac{n-1}{n}=\frac{N-1}{N}\cdot \frac{N}{N+1}\cdots \frac{M-1}{M}=\frac{N-1}{M}.$$

The events $\{Z_n=0\text{ for }N\le n\le M\}$ decrease in $M$ to $\{Z_n=0\text{ for all }n\ge N\}$, so by continuity of probability from above

$$P\left(Z_n=0\text{ for all }n\ge N\right)=\underset{M\to \infty }{\lim }\frac{N-1}{M}=0.$$

(For $N=1$ the event is empty, since $P(Z_1=1)=1$.) The convergence set is the countable union over $N$ of these events, so by countable subadditivity it has probability at most ${\sum }_{N}0=0$. Hence $P(Z_n\to 0)=0$: the sequence converges almost surely to nothing — it is $1$ infinitely often for almost every outcome, even though at each fixed time the chance of a $1$ is only $\frac{1}{n}$.

Summary. $X_n$: all four. $Y_n$: a.s., $P$, $d$, not $L^2$. $Z_n$: $P$, $L^2$, $d$, not a.s. Between them, (b) and (c) show that neither of $\stackrel{a.s.}{\to }$ and $\stackrel{L^2}{\to }$ implies the other.

(a) The graphs. Each $X_n$ is a rectangle standing on the interval $[0,\frac{1}{n}]$ with height $n$, and zero to the right of it. On axes with $\omega$ from $0$ to $1$ horizontally and height up to $4$: $X_1$ is the horizontal line at height $1$ across the whole of $[0,1]$; $X_2$ is height $2$ on $[0,\frac{1}{2}]$ and $0$ on $(\frac{1}{2},1]$; $X_4$ is height $4$ on $[0,\frac{1}{4}]$ and $0$ after. Draw the drops at $\omega =\frac{1}{2}$ and $\frac{1}{4}$ as vertical dashed segments, with a filled dot at the top (the endpoint $\frac{1}{n}$ belongs to the tall part).

The area under each graph is $n\times \frac{1}{n}=1$: the rectangles get taller and narrower at exactly compensating rates. Label each rectangle "area $1$".

(b) One outcome. Draw a vertical dashed line at $\omega =0.3$. It crosses the tall part of $X_1$ (height $1$), of $X_2$ (since $0.3\le \frac{1}{2}$, height $2$) and of $X_3$ (since $0.3\le \frac{1}{3}$, height $3$), but not of $X_4$ (since $0.3>\frac{1}{4}$). So the sequence at $\omega =0.3$ is $1,2,3,0,0,0,\dots$: three spikes and then zero forever.

The same happens at every $\omega >0$. Fix such an $\omega$ and let $N$ be any integer with $N>\frac{1}{\omega }$. For every $n\ge N$ we have $\frac{1}{n}\le \frac{1}{N}<\omega$, so $\omega$ lies in the zero part and $X_n(\omega )=0$. A sequence that is eventually constantly $0$ converges to $0$. The only outcome where this fails is $\omega =0$, which lies in $[0,\frac{1}{n}]$ for every $n$, so $X_n(0)=n\to \infty$. The divergence set is $\{0\}$, a single point, whose uniform probability is $0$. Hence $P(X_n\to 0)=P\left((0,1]\right)=1$: $X_n\stackrel{a.s.}{\to }0$. $■$

The mechanism is visible on the sketch: the rectangles are nested, each inside the last, so once the line at $\omega$ has escaped a rectangle it has escaped all later ones. Contrast a moving bump, which would revisit $\omega$ forever.

(c) Moments. $E(X_n)=n\cdot P\left(\omega \le \frac{1}{n}\right)=n\cdot \frac{1}{n}=1$ for every $n$, and

$$E\left(X_n^2\right)=n^2\cdot \frac{1}{n}=n⟶\infty .$$

So $E[(X_n-0{)}^2]=n$ does not tend to $0$: there is no $L^2$ convergence, and indeed the mean squares diverge. The feature that shows $E(X_n)\nrightarrow 0$ is the constant area: the expectation of a non-negative function on $[0,1]$ under the uniform probability is the area under its graph, and every rectangle has area $1$. A sequence can go to zero at almost every point while its area stays fixed, provided the height escapes to infinity on a vanishing set — and by the implications, $X_n\to 0$ in probability and in distribution as well, since almost sure convergence gives both.

(d) The CDFs. $X_4$ takes the value $0$ with probability $\frac{3}{4}$ and $4$ with probability $\frac{1}{4}$, so

$$F_{X_4}(x)=\{\begin{array}{ll}0,& x<0,\\ \frac{3}{4},& 0\le x<4,\\ 1,& x\ge 4,\end{array}$$

a staircase with a jump of $\frac{3}{4}$ at $x=0$ and a jump of $\frac{1}{4}$ at $x=4$. The CDF of the constant $0$ is $F(x)=0$ for $x<0$ and $1$ for $x\ge 0$: a single jump of size $1$ at $x=0$. Draw both, with the plateau of $F_{X_4}$ at height $\frac{3}{4}$ sitting just below the limit's plateau at $1$.

For general $n$ the plateau is at $1-\frac{1}{n}$ and the second jump is at $x=n$. As $n$ grows the plateau rises to $1$ and the second jump marches off to the right, so at every fixed $x>0$, $F_{X_n}(x)=1-\frac{1}{n}\to 1=F(x)$ once $n>x$; and for $x<0$ both are $0$. That is convergence at every continuity point of $F$, which is the definition of $X_n\stackrel{d}{\to }0$. At $x=0$, the one discontinuity of the limit, convergence is not required — but here it happens anyway, since $F_{X_n}(0)=1-\frac{1}{n}\to 1=F(0)$.

(a) $\mu =\frac{1+2+\cdots +6}{6}=\frac{21}{6}=\frac{7}{2}$, and

$$E\left(X_i^2\right)=\frac{1+4+9+16+25+36}{6}=\frac{91}{6},{\sigma }^2=\frac{91}{6}-\frac{49}{4}=\frac{182-147}{12}=\frac{35}{12}.$$

(b) Chebyshev. Independence gives $\mathrm{Var}({\bar{X}}_n)=\frac{{\sigma }^2}{n}=\frac{35}{12n}$, so

$$P\left(|{\bar{X}}_n-\mu |\ge \frac{1}{10}\right)\le \frac{35/(12n)}{1/100}=\frac{3500}{12n}=\frac{875}{3n}.$$

Requiring $\frac{875}{3n}\le \frac{1}{20}$ gives $n\ge \frac{875\times 20}{3}=\frac{17500}{3}=5833.\overline{3}$, so the smallest integer is $n=5834$.

Sanity check: at $n=5834$ the bound is $\frac{875}{17502}<0.05$, and at $n=5833$ it is $\frac{875}{17499}>0.05$.

(c) Hoeffding. Each $X_i\in [1,6]$, a range of width $5$, so ${\sum }_i(b_i-a_i{)}^2=25n$. With $t=n\epsilon =\frac{n}{10}$ the two-sided bound is

$$P\left(|{\bar{X}}_n-\mu |\ge \frac{1}{10}\right)\le 2\exp \left(-\frac{2(n/10{)}^2}{25n}\right)=2\exp \left(-\frac{n}{1250}\right).$$

Requiring $2e^{-n/1250}\le \frac{1}{20}$ means $e^{-n/1250}\le \frac{1}{40}$, that is $n\ge 1250\log 40$. Since $\log 40=2\log 2+\log 10\approx 1.3863+2.3026=3.6889$, this is $n\ge 4611.1$, so the smallest integer is $n=4612$.

Sanity check: at $n=4612$, $2e^{-4612/1250}\approx 0.04996<0.05$; at $n=4611$ it is $\approx 0.05000$, just over. Hoeffding needs about $79\%$ of Chebyshev's sample here; the advantage would grow if the tolerance $\frac{1}{20}$ were tightened, because Hoeffding's $n$ grows like $\log (1/\delta )$ and Chebyshev's like $1/\delta$.

(d) What is proved. Both bounds say that for the fixed $\epsilon =\frac{1}{10}$,

$$\underset{n\to \infty }{\lim }P\left(|{\bar{X}}_n-\mu |\ge \epsilon \right)=0,$$

and the same argument works for every $\epsilon >0$. That is the definition of ${\bar{X}}_n\stackrel{P}{\to }\mu$: the weak law of large numbers, convergence in probability.

The strong law asserts ${\bar{X}}_n\stackrel{a.s.}{\to }\mu$, a statement about the whole trajectory of a single sequence of rolls, and no bound on a single $P(|{\bar{X}}_n-\mu |\ge \epsilon )$ is by itself a statement about trajectories — the misbehaving set could in principle move around from $n$ to $n$ forever, as the typewriter-style sequences do, while shrinking at every $n$. What converts a sequence of bounds into an almost-sure statement is summability over $n$ together with the Borel–Cantelli lemma; that is a further step neither part (b) nor (c) has taken. Chebyshev's bound, of order $\frac{1}{n}$, is not summable at all; Hoeffding's, of order $e^{-cn}$, is — so the Hoeffding route can be completed into a strong law, whereas the Chebyshev route cannot.

(a) A summable bound. The $X_i$ are independent and bounded in $[a,b]$, so Hoeffding's two-sided inequality applies with ${\sum }_i(b_i-a_i{)}^2=n(b-a{)}^2$ and $t=n\epsilon$:

$$P(A_n)=P\left(|S_n-n\mu |\ge n\epsilon \right)\le 2\exp \left(-\frac{2n^2{\epsilon }^2}{n(b-a{)}^2}\right)=2q^n,q=\exp \left(-\frac{2{\epsilon }^2}{(b-a{)}^2}\right).$$

Since $\epsilon >0$ and $b>a$, the exponent is strictly negative, so $0<q<1$ and the bounds form a convergent geometric series:

$$\sum _{n=1}^{\infty }P(A_n)\le 2\sum _{n=1}^{\infty }{q}^n=\frac{2q}{1-q}<\infty .$$

(b) Borel–Cantelli. The first Borel–Cantelli lemma says that events whose probabilities have a finite sum occur infinitely often with probability $0$. So $P(A_n\text{ infinitely often})=0$. Let $N_{\epsilon }$ be that null event. For $\omega \notin N_{\epsilon }$ only finitely many $A_n$ contain $\omega$; let $N(\omega )$ be one more than the largest such $n$ (or $1$ if there are none). Then for every $n\ge N(\omega )$, $\omega \notin A_n$, that is $|{\bar{X}}_n(\omega )-\mu |<\epsilon$. This holds for every $\omega$ outside the null set $N_{\epsilon }$, which is what "for almost every $\omega$" means. $■$

(c) From one $\epsilon$ to all. Convergence ${\bar{X}}_n(\omega )\to \mu$ means: for every $\epsilon >0$ there is $N$ with $|{\bar{X}}_n(\omega )-\mu |<\epsilon$ for $n\ge N$. Part (b) delivers this one $\epsilon$ at a time, each with its own exceptional null set, and there are uncountably many $\epsilon$; an uncountable union of null sets need not be null, so we cannot simply take them all. The repair is to use only $\epsilon =\frac{1}{j}$ for $j=1,2,3,\dots$.

Apply (b) with $\epsilon =\frac{1}{j}$ to get null sets $N_{1/j}$, and put $N={\bigcup }_{j\ge 1}{N}_{1/j}$. By countable subadditivity, $P(N)\le {\sum }_{j}P(N_{1/j})=0$. Now take any $\omega \notin N$ and any $\epsilon >0$. Choose $j$ with $\frac{1}{j}<\epsilon$. Since $\omega \notin N_{1/j}$, there is $N_j(\omega )$ with $|{\bar{X}}_n(\omega )-\mu |<\frac{1}{j}<\epsilon$ for all $n\ge N_j(\omega )$. As $\epsilon$ was arbitrary, ${\bar{X}}_n(\omega )\to \mu$. The convergence set therefore contains the complement of $N$, so

$$P\left({\bar{X}}_n\to \mu \right)\ge 1-P(N)=1.■$$

The passage is legitimate because a countable family of tolerances suffices to test convergence — any $\epsilon$ is beaten by some $\frac{1}{j}$ — and countably many null sets union to a null set.

(d) Why Chebyshev cannot do it. Chebyshev gives $P(A_n)\le \frac{{\sigma }^2}{n{\epsilon }^2}$, and ${\sum }_n\frac{1}{n}$ diverges, so Borel–Cantelli has nothing to bite on. The bound tends to $0$, which is the weak law, but a failure budget of $\sum \frac{1}{n}=\infty$ leaves room for the running mean to wander out of $(\mu -\epsilon ,\mu +\epsilon )$ infinitely often, ever more rarely; Chebyshev cannot rule that out, and the mechanism of (b) needs a finite budget.

The finite-fourth-moment route gets its summability from Markov applied to $S_n^4$, which yields $P(A_n)\le \frac{C}{{\epsilon }^4{n}^2}$ and $\sum \frac{1}{n^2}<\infty$. Boundedness is a strictly stronger hypothesis than a finite fourth moment — a variable confined to $[a,b]$ has every moment finite, with $E|X-\mu {|}^4\le (b-a{)}^4$ — so the theorem proved here is a special case of the fourth-moment theorem. What the stronger hypothesis buys is a much better rate: geometric tails $2q^n$ instead of $\frac{C}{n^2}$, which is exactly the difference between Hoeffding and Chebyshev-type bounds seen throughout. In both proofs the structure is identical — a summable bound on the tail probabilities, Borel–Cantelli, then the countable-$\epsilon$ trick — and neither reaches Kolmogorov's theorem, which needs only $E|X|<\infty$ and a genuinely harder argument.

(a) The CLT. The $X_i$ are i.i.d. with $\mu =p$ and ${\sigma }^2=p(1-p)$. Since $0<p<1$, ${\sigma }^2$ is strictly positive and, being at most $\frac{1}{4}$, finite. All hypotheses hold, and

$$\sqrt{n}({\hat{p}}_n-p)\stackrel{d}{\to }N\left(0,p(1-p)\right).$$

(This is the standardised statement $\frac{{\hat{p}}_n-p}{\sqrt{p(1-p)/n}}\stackrel{d}{\to }N(0,1)$ with the constant $\sqrt{p(1-p)}$ multiplied back in.)

(b) The log-odds. $g(p)=\log p-\log (1-p)$, so

$$g^{\prime }(p)=\frac{1}{p}+\frac{1}{1-p}=\frac{1}{p(1-p)},$$

which is finite and non-zero on $(0,1)$. The delta method with $\theta =p$ and ${\tau }^2=p(1-p)$ gives

$$\sqrt{n}\left(g({\hat{p}}_n)-g(p)\right)\stackrel{d}{\to }N\left(0,{\left[g^{\prime }(p)\right]}^{2}p(1-p)\right)=N\left(0,\frac{1}{p(1-p)}\right).$$

At $p=\frac{1}{4}$: $p(1-p)=\frac{3}{16}$, so the asymptotic variance is $\frac{16}{3}$. The estimated log-odds has approximate standard error $\sqrt{16/(3n)}=\frac{4}{\sqrt{3n}}$ — larger than that of ${\hat{p}}_n$ itself by the factor $|g^{\prime }(p)|=\frac{16}{3}$, because the logit is steep near the edges of $(0,1)$.

(c) A function with a stationary point. $h^{\prime }(p)=1-2p$. At $p=\frac{1}{4}$, $h^{\prime }(p)=\frac{1}{2}\ne 0$, so the delta method applies: