Exercises — Law of large numbers

(b). The Weak Law talks about a probability shrinking to zero as $n$ grows: for any tolerance $ϵ$, the chance of missing $\mu$ by that much fades away. Option (a) is the Strong Law (a statement about a single infinite run settling forever). Option (c) is simply false — the average never equals $\mu$ exactly, it only concentrates near it. Answer ::: (b)

$\mathrm{Var}({\bar{X}}_n)=\frac{{\sigma }^2}{n}=\frac{9}{100}=0.09$. The standard error is its square root: $\mathrm{SE}=\sqrt{0.09}=0.3$. Equivalently $\sigma /\sqrt{n}=3/10=0.3$. The average is $10\times$ tighter than a single draw ($\sigma =3$). Var ::: 0.09 SE ::: 0.3

False. $E[{\bar{X}}_n]=\mu$ for every $n$ — averaging never shifts the centre, it only shrinks the spread. This is exactly why the average is an unbiased estimate of $\mu$ (see Expected Value and Bias-Variance Tradeoff). Answer ::: False

Plug into $\frac{{\sigma }^2}{n{ϵ}^2}$ with ${\sigma }^2=35/12$, $n=600$, $ϵ=0.2$: $P(|{\bar{X}}_n-3.5|\ge 0.2)\le \frac{35/12}{600\cdot (0.2{)}^2}=\frac{2.91667}{600\cdot 0.04}=\frac{2.91667}{24}\approx \mathrm{0.1215.}$ So at most about a 12.2% chance the average roll is off by $0.2$ or more. Bound ::: ≈ 0.1215

Set the Chebyshev bound to the target: $\frac{0.25}{n(0.05{)}^2}\le 0.05$. Compute $(0.05{)}^2=0.0025$, so the left side is $\frac{0.25}{0.0025n}$. Now $\frac{0.25}{0.0025}=100$ (because $0.25=100\times 0.0025$), leaving $\frac{100}{n}\le 0.05$. Solve: $n\ge \frac{100}{0.05}=2000$. You need $n\ge 2000$ flips (Chebyshev is conservative; the tighter Central Limit Theorem needs far fewer). n ::: 2000

Chebyshev: $\frac{{\sigma }^2}{n{ϵ}^2}\le 0.10$ with ${\sigma }^2=16$, $ϵ=0.5$, ${ϵ}^2=0.25$. The left side is $\frac{16}{0.25n}$. Since $\frac{16}{0.25}=64$ (because dividing by $0.25$ is the same as multiplying by $4$, and $16\times 4=64$), this becomes $\frac{64}{n}\le 0.10$. $\frac{64}{n}\le 0.10\Rightarrow n\ge \frac{64}{0.10}=640.$ Minimum $n=640$ readings. n ::: 640

$\mathrm{SE}=\sigma /\sqrt{n}$. To make $\mathrm{SE}$ half as large you need $\sqrt{n_2}=2\sqrt{n_1}$, i.e. $n_2=4n_1$. So multiply $n$ by 4 (from $1000$ to $4000$).

The figure below plots the standard error $\mathrm{SE}=\sigma /\sqrt{n}$ against sample size $n$ (with $\sigma =1$). Follow the magenta curve: doubling $n$ barely dents the height, and the two marked points show that dropping from $n=1000$ to the same error halved requires jumping all the way to $n=4000$ (the violet and orange dots). The curve flattens brutally to the right — that flatness is the "precision costs quadratically" lesson, because the last slice of accuracy demands the most data.

${\mathrm{SE}}_A=\frac{2}{\sqrt{100}}=\frac{2}{10}=0.2$. ${\mathrm{SE}}_B=\frac{5}{\sqrt{400}}=\frac{5}{20}=0.25$. A is tighter ($0.2<0.25$), even though B has $4\times$ the samples — because B's per-draw noise $\sigma$ is $2.5\times$ larger. Sample size and variance both matter; more data cannot always outrun a noisier source. Smaller SE ::: Estimator A (0.2 vs 0.25)

First reproduce the loose bound so it is self-contained: with ${\sigma }^2=0.25$, $n=10,000$, $ϵ=0.01$, $P(|{\bar{X}}_n-0.5|\ge 0.01)\le \frac{{\sigma }^2}{n{ϵ}^2}=\frac{0.25}{10000\cdot (0.01{)}^2}=\frac{0.25}{10000\cdot 0.0001}=\frac{0.25}{1}=\mathrm{0.25.}$ Chebyshev only uses the variance — it makes no assumption about the shape of the distribution, so it must stay safe for the worst-case shape. That safety costs sharpness, giving the loose $0.25$.

The Central Limit Theorem adds a real assumption: for large $n$, ${\bar{X}}_n$ is approximately normal with SE $=\sigma /\sqrt{n}=0.5/\sqrt{10000}=0.005$. Then $ϵ=0.01$ is $2$ standard errors out, and the two-tailed normal tail beyond $2$ SE is $\approx 0.0455$. Because CLT knows the bell shape, it can commit to a much smaller number. Tighter theorem ::: Central Limit Theorem (uses the normal shape, not just variance)

Use the worst-case variance ${\sigma }^2=0.25$ so the guarantee holds no matter what $g$ is. $\frac{0.25}{n(0.002{)}^2}\le \mathrm{0.05.}$ $(0.002{)}^2=4\times 10^{-6}$, so the left side is $\frac{0.25}{4\times 10^{-6}n}$. Now $\frac{0.25}{4\times 10^{-6}}=62500$ (because $0.25÷0.000004=62500$), giving $\frac{62500}{n}\le 0.05$. $n\ge \frac{62500}{0.05}=1,250,000$. Need 1,250,000 samples. This is the pessimistic Chebyshev count behind Monte Carlo Methods; CLT-based error bars are much smaller in practice. n ::: 1,250,000

The averaged-gradient noise scales as ${\sigma }_g/\sqrt{b}$, so noise $\propto 1/\sqrt{b}$. To divide noise by $4$ we need $\sqrt{b_2}=4\sqrt{b_1}$, i.e. $b_2=16b_1=16\times 16=256$. Batch size 256. Notice $16\times$ more compute buys only $4\times$ less noise — the same $1/\sqrt{n}$ tax that governs all LLN estimates, and why huge batches show diminishing returns. Batch size ::: 256

The bootstrap's own Monte-Carlo error also obeys $\propto 1/\sqrt{B}$. To cut $0.02$ to $0.005$ is a factor of $4$, needing $\sqrt{B_2}=4\sqrt{B_1}$, so $B_2=16B_1=16\times 100=1600$. About 1600 resamples. B ::: 1600

No — it does not converge. Every version of the Law we built assumes a finite $\mu$ (and Chebyshev also needs finite ${\sigma }^2$). The Cauchy distribution violates the very first hypothesis, so the Law does not apply, and in fact ${\bar{X}}_n$ keeps wandering forever — a single extreme draw can dominate the whole average no matter how large $n$ is. Lesson: the guarantee is conditional. Heavy tails (infinite variance, or worse, infinite mean) break LLN. Always check the hypotheses before trusting an average. Converges? ::: No — mean is undefined, LLN's assumptions fail

Let $S_n=\sum X_i$ = total heads, ${\bar{X}}_n=S_n/n$ = fraction. Recall SD = standard deviation = square root of variance.

• Fraction: $\mathrm{SE}({\bar{X}}_n)=\sigma /\sqrt{n}=0.5/\sqrt{n}$. This shrinks like $1/\sqrt{n}$ — multiply $n$ by $4$ and it halves — so the fraction concentrates at $0.5$. ✓
• Count: $\mathrm{SD}(S_n)=\sigma \sqrt{n}=0.5\sqrt{n}$. This grows like $\sqrt{n}$ — multiply $n$ by $4$ and it doubles — so it heads to infinity.

So the typical gap between heads-count and $n/2$ grows like $\sqrt{n}$, even while the fraction's gap from $0.5$ shrinks like $1/\sqrt{n}$. Both are true at once — this is exactly why "I'll get exactly $n/2$ heads" is wrong. Fraction error growth ::: shrinks like 1/√n Count error growth ::: grows like √n

Under a fair coin, ${\bar{X}}_n$ has $\mu =0.5$ and $\mathrm{SE}=0.5/\sqrt{100}=0.05$. The observed fraction $0.6$ sits at $\frac{0.6-0.5}{0.05}=\frac{0.1}{0.05}=2\text{standard errors above the mean.}$ A deviation of $2$ SE or more happens roughly $5\%$ of the time for a fair coin (normal approximation). That is not strong evidence of bias — it is a mildly unusual but perfectly ordinary result. Concluding "biased!" here is the gambler's-fallacy reflex; you should build a proper confidence interval and demand a much larger deviation (say $3$ SE or more) before doubting the coin. Conclusion: $z=2$ → not strong evidence; a fair coin produces results this far out about $5\%$ of the time. z ::: 2 standard errors → not strong evidence

• Can you restate WLLN vs SLLN in words? ::: WLLN: probability of missing $\mu$ by $ϵ$ → 0. SLLN: a single run settles at $\mu$ with probability 1.
• What must you multiply $n$ by to halve the error? ::: 4.
• What breaks the Law entirely? ::: Infinite mean or infinite variance (heavy tails, e.g. Cauchy).