Exercises — Law of Large Numbers — weak and strong

WLLN (in probability): for every tolerance $\epsilon >0$, ${\lim }_{n\to \infty }\mathbb{P}(|{\bar{X}}_n-\mu |>\epsilon )=0.$ SLLN (almost surely): $\mathbb{P}({\lim }_{n\to \infty }{\bar{X}}_n=\mu )=1.$ WLLN uses convergence in probability (see Modes of Convergence); SLLN uses almost-sure convergence. Almost-sure is the stronger notion: SLLN $\Rightarrow$ WLLN, never the reverse.

$\mathbb{P}(|X-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{{\epsilon }^2}.$ It is Markov's Inequality $(\mathbb{P}(Y\ge a)\le \mathbb{E}[Y]/a)$ applied to the non-negative variable $Y=(X-\mu {)}^2$ with threshold $a={\epsilon }^2$.

$\mu =\frac{1+2+3+4+5+6}{6}=\frac{21}{6}=3.5$. The running average converges to $\boxed{3.5}$. "For almost every infinite sequence" is the Strong Law (almost-sure convergence).

Here ${\sigma }^2=p(1-p)=\frac{1}{4}=0.25$, $\epsilon =0.05$, $n=400$. $\mathbb{P}\le \frac{{\sigma }^2}{n{\epsilon }^2}=\frac{0.25}{400\cdot (0.05{)}^2}=\frac{0.25}{400\cdot 0.0025}=\frac{0.25}{1}=\mathrm{0.25.}$ So at most $0.25$. (Chebyshev is deliberately loose; the true probability is far smaller.)

Set $\frac{0.25}{n(0.05{)}^2}\le 0.01$. Since $(0.05{)}^2=0.0025$: $n\ge \frac{0.25}{0.01\cdot 0.0025}=\frac{0.25}{0.000025}=10,000.$ So $\boxed{n\ge 10,000}$. Why invert this way? We isolate $n$ by multiplying both sides by $n$ and dividing by the target $0.01$ — a monotone rearrangement, so no direction flips.

Markov with $a=12$: $\mathbb{P}(Y\ge 12)\le \frac{\mathbb{E}[Y]}{12}=\frac{3}{12}=\mathrm{0.25.}$ Answer: $\boxed{0.25}$.

Because $\mathbb{E}[g(U)]={\int }_0^1{x}^{2}dx=[\frac{x^3}{3}{]}_0^1=\frac{1}{3}$. The integral is an expectation, so by the SLLN the average converges almost surely to $\boxed{\frac{1}{3}}$. That is exactly why Monte Carlo integration works.

Write ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$. Pulling the constant $\frac{1}{n}$ out squares it: $\mathrm{Var}({\bar{X}}_n)=\frac{1}{n^2}\mathrm{Var}\left({\sum }_{i=1}^n{X}_i\right)=\frac{1}{n^2}({\sum }_i\mathrm{Var}(X_i)+{\sum }_{i\ne j}\mathrm{Cov}(X_i,X_j)).$ Independence makes every $\mathrm{Cov}(X_i,X_j)=0$ for $i\ne j$, so the cross-term double sum vanishes. Identical distribution makes each $\mathrm{Var}(X_i)={\sigma }^2$. Hence $\mathrm{Var}({\bar{X}}_n)=\frac{1}{n^2}\cdot n{\sigma }^2=\frac{{\sigma }^2}{n}.$ The vanishing cross terms are what independence buys you — that is the engine of the whole LLN.

Chebyshev gives $\mathbb{P}(A_n)\le \frac{{\sigma }^2}{n{\epsilon }^2}$. Summing: ${\sum }_{n=1}^{\infty }\mathbb{P}(A_n)\le \frac{{\sigma }^2}{{\epsilon }^2}{\sum }_{n=1}^{\infty }\frac{1}{n}.$ The harmonic series $\sum 1/n$ diverges, so this bound is $+\infty$ — useless. The first Borel–Cantelli Lemma needs a finite sum to conclude "only finitely many $A_n$ occur," and we don't have one. This is precisely why the SLLN is harder: Kolmogorov replaces the term-by-term bound with a maximal inequality controlling ${\max }_{k\le n}|{\bar{X}}_k-\mu |$, yielding a convergent series along a sparse subsequence (like $n=2^k$), after which Borel–Cantelli applies.

Independence means future coins have no memory of the streak; each still has $\mathbb{P}(\text{heads})=\frac{1}{2}$. So nothing "cancels" the 8 heads. Instead the average self-corrects by dilution. Write the deviation of the sum: $S_n-n\mu ={\sum }_{i=1}^n(X_i-\mu ).$ This sum can keep growing — its typical size is of order $\sqrt{n}$ (standard deviation $\sigma \sqrt{n}$). But the average's deviation is ${\bar{X}}_n-\mu =\frac{S_n-n\mu }{n},$ whose standard deviation is $\frac{\sigma \sqrt{n}}{n}=\frac{\sigma }{\sqrt{n}}\to 0$.

Reading the figure (walkthrough):

• The orange path (left axis) is the sum-deviation $S_n-n\mu$. Notice the arrow marking the 8-head streak at the very start: it lifts the orange path up by $8\cdot \frac{1}{2}=4$. From there the orange path keeps drifting — it is never pulled back to zero. That drift is the "$\sqrt{n}$ wandering" made visible; there is no repayment.
• The teal path (right axis) is the average-deviation ${\bar{X}}_n-\mu$. It starts high (the streak dominates a tiny $n$) but is quickly squeezed toward $0$.
• The two dashed plum curves are the funnel $\pm \sigma /\sqrt{n}$. The teal path is trapped inside this narrowing funnel, which visibly clamps to $0$ even while the orange path escapes.

The lesson the picture makes concrete: the streak becomes a vanishing fraction of a huge $n$, not a debt that future tails repay. See Gambler's Fallacy.

• LLN: ${\bar{X}}_n-\mu \to 0$ (the average lands on the constant $\mu$).
• CLT (see Central Limit Theorem): $\sqrt{n}({\bar{X}}_n-\mu )\stackrel{d}{\to }\mathcal{N}(0,{\sigma }^2)$ — after magnifying the shrinking deviation by $\sqrt{n}$, what remains is a fixed-width bell. Reconciliation: ${\bar{X}}_n-\mu$ shrinks at rate $1/\sqrt{n}$. If you zoom by exactly $\sqrt{n}$, you cancel the shrink and see the non-degenerate fluctuation. So LLN tells you where it lands; CLT tells you the shape and scale of the leftover wiggle just before it lands. No contradiction: $\frac{1}{\sqrt{n}}\cdot (\text{bell})\to 0$.

Need $\frac{{\sigma }^2}{n{\epsilon }^2}\le 0.02$ with ${\sigma }^2=4$, $\epsilon =0.2$ so ${\epsilon }^2=0.04$: $n\ge \frac{4}{0.02\cdot 0.04}=\frac{4}{0.0008}=5000.$ Smallest guaranteed $n=\boxed{5000}$.

Fixed-$n$ bound (WLLN machinery): Chebyshev on ${\bar{X}}_n$ gives $\mathbb{P}(|{\bar{X}}_n-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{n{\epsilon }^2}$, which $\to 0$. This controls each $n$ in isolation.

The extra machinery — Kolmogorov's maximal inequality. For independent, mean-zero $Y_1,\dots ,Y_n$ with partial sums $S_k=Y_1+\cdots +Y_k$, it states $\mathbb{P}({\max }_{1\le k\le n}|S_k|\ge t)\le \frac{\mathrm{Var}(S_n)}{t^2}.$ This is strictly stronger than Chebyshev: Chebyshev controls only the endpoint $|S_n|$, whereas this controls the worst partial sum up to $n$ at once — exactly what "stays good for all large $n$" needs.

Upgrade to "forever": apply the maximal inequality on dyadic blocks $2^m\le n<2^{m+1}$. The blockwise bounds now form a convergent series ${\sum }_m(\cdot )<\infty$ (the $\sum 1/n$ divergence of Exercise 3.2 is defeated because each block is summarised by a single $2^{-m}$-type term). The first Borel–Cantelli Lemma then forces only finitely many bad blocks, so after the last one the path is trapped in the good region forever — that is almost-sure convergence, i.e. the SLLN.

The mean would be $\mu ={\int }_{-\infty }^{\infty }xf(x)dx={\int }_{-\infty }^{\infty }\frac{x}{\pi (1+x^2)}dx$. The integrand behaves like $\frac{1}{\pi x}$ for large $|x|$, whose integral diverges (both tails), so $\mu$ is undefined — there is no number for ${\bar{X}}_n$ to converge to. Remarkably, a known fact: the sample mean of $n$ i.i.d. Cauchy variables is itself Cauchy with the same scale — averaging does not narrow it at all. So the LLN's hypothesis $\mathbb{E}|X|<\infty$ is genuinely necessary; the "engine" $\mathrm{Var}({\bar{X}}_n)={\sigma }^2/n$ never even starts because ${\sigma }^2$ (and $\mu$) don't exist.

Yes. The Chebyshev proof needs ${\sigma }^2<\infty$, but that is only the easy route. Khinchin's WLLN requires only $\mathbb{E}|X|<\infty$ (finite mean), and Kolmogorov's SLLN requires the same, $\mathbb{E}|X|<\infty$. So finite variance is a convenience of one proof, not a requirement of the laws. Only when the mean itself fails (Cauchy) does the LLN break.

Setup: draw $U_i,V_i\sim \text{Uniform}(0,1)$ independently and set the indicator $X_i=1\{U_i^2+V_i^2\le 1\}\in \{0,1\}$ ($1$ if the point lands inside the quarter unit-circle). Its expectation is the area of that quarter disc: $\mathbb{E}[X_i]=\mathbb{P}(U^2+V^2\le 1)=\frac{\pi }{4}.$ So ${\bar{X}}_n\to \frac{\pi }{4}$, and the estimator is ${\hat{\pi }}_n=4{\bar{X}}_n$.

Which law guarantees convergence: the SLLN guarantees ${\bar{X}}_n\to \frac{\pi }{4}$ almost surely for a single infinite run, hence ${\hat{\pi }}_n=4{\bar{X}}_n\to \pi$ almost surely.

Finite-$n$ error bound (WLLN with rate): here $\mu =\frac{\pi }{4}$ and the indicator's variance is ${\sigma }^2=\mu (1-\mu )=\frac{\pi }{4}(1-\frac{\pi }{4})\approx \mathrm{0.1685.}$ An error $|{\hat{\pi }}_n-\pi |\le \delta$ means $|{\bar{X}}_n-\frac{\pi }{4}|\le \frac{\delta }{4}$, so set $\epsilon =\frac{\delta }{4}$. Chebyshev gives $\mathbb{P}(|{\hat{\pi }}_n-\pi |\ge \delta )=\mathbb{P}(|{\bar{X}}_n-\frac{\pi }{4}|\ge \frac{\delta }{4})\le \frac{{\sigma }^2}{n(\delta /4{)}^2}=\frac{16{\sigma }^2}{n{\delta }^2}.$ Worked number: to guarantee $\mathbb{P}(|{\hat{\pi }}_n-\pi |\ge 0.1)\le 0.05$, solve $\frac{16(0.1685)}{n(0.1{)}^2}\le 0.05\Rightarrow n\ge \frac{16(0.1685)}{0.05\cdot 0.01}=\frac{2.696}{0.0005}=5392,$ so $n\ge \boxed{5392}$ draws suffice (rounding up). See Monte Carlo Methods.

L1 state the laws & modes ::: WLLN in probability, SLLN almost surely; SLLN⇒WLLN. L2 plug into the bound ::: $\mathbb{P}(|{\bar{X}}_n-\mu |\ge \epsilon )\le {\sigma }^2/(n{\epsilon }^2)$; solve for $n$. L3 why Var shrinks / why naive SLLN fails ::: cross-covariances vanish (independence); $\sum 1/n$ diverges so need a maximal inequality. L4 LLN vs CLT ::: LLN=where it lands ($\mu$); CLT=shape of the $1/\sqrt{n}$ wiggle. L5 hypotheses matter ::: need $\mathbb{E}|X|<\infty$; Cauchy breaks it; Monte Carlo is LLN in action.