Exercises — Law of Large Numbers — weak and strong

WLLN (in probability): har tolerance $\epsilon >0$ ke liye, ${\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 convergence in probability use karta hai (dekho Modes of Convergence); SLLN almost-sure convergence use karta hai. Almost-sure zyada strong notion hai: SLLN $\Rightarrow$ WLLN, kabhi ulta nahi.

$\mathbb{P}(|X-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{{\epsilon }^2}.$ Yeh Markov's Inequality hai $(\mathbb{P}(Y\ge a)\le \mathbb{E}[Y]/a)$ jo non-negative variable $Y=(X-\mu {)}^2$ pe threshold $a={\epsilon }^2$ ke saath apply ki gayi hai.

$\mu =\frac{1+2+3+4+5+6}{6}=\frac{21}{6}=3.5$. Running average $\boxed{3.5}$ pe converge hota hai. "Almost every infinite sequence ke liye" Strong Law hai (almost-sure convergence).

Yahan ${\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.}$ Toh at most $0.25$. (Chebyshev deliberately loose hai; actual probability bahut chhoti hai.)

Set karo $\frac{0.25}{n(0.05{)}^2}\le 0.01$. Kyunki $(0.05{)}^2=0.0025$: $n\ge \frac{0.25}{0.01\cdot 0.0025}=\frac{0.25}{0.000025}=10,000.$ Toh $\boxed{n\ge 10,000}$. Iss tarah invert kyun kiya? Hum $n$ ko isolate karte hain dono sides ko $n$ se multiply karke aur target $0.01$ se divide karke — yeh ek monotone rearrangement hai, isliye koi direction flip nahi hota.

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}$.

Kyunki $\mathbb{E}[g(U)]={\int }_0^1{x}^{2}dx=[\frac{x^3}{3}{]}_0^1=\frac{1}{3}$. Integral hi ek expectation hai, isliye SLLN se average almost surely $\boxed{\frac{1}{3}}$ pe converge karta hai. Yahi exactly reason hai ki Monte Carlo integration kaam karta hai.

Likho ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i$. Constant $\frac{1}{n}$ bahar nikalte hain toh yeh square ho jaata hai: $\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 har $\mathrm{Cov}(X_i,X_j)=0$ banaata hai $i\ne j$ ke liye, toh cross-term double sum vanish ho jaata hai. Identical distribution har $\mathrm{Var}(X_i)={\sigma }^2$ banata hai. Isliye $\mathrm{Var}({\bar{X}}_n)=\frac{1}{n^2}\cdot n{\sigma }^2=\frac{{\sigma }^2}{n}.$ Vanishing cross terms wahi hai jo independence tumhe deta hai — yahi poore LLN ka engine hai.

Chebyshev deta hai $\mathbb{P}(A_n)\le \frac{{\sigma }^2}{n{\epsilon }^2}$. Sum karke: ${\sum }_{n=1}^{\infty }\mathbb{P}(A_n)\le \frac{{\sigma }^2}{{\epsilon }^2}{\sum }_{n=1}^{\infty }\frac{1}{n}.$ Harmonic series $\sum 1/n$ diverge karta hai, isliye yeh bound $+\infty$ hai — bekar. Pehla Borel–Cantelli Lemma ek finite sum chahta hai conclude karne ke liye ki "sirf finitely many $A_n$ occur hote hain," aur woh hamare paas nahi hai. Exactly yahi reason hai ki SLLN zyada mushkil hai: Kolmogorov term-by-term bound ko ek maximal inequality se replace karta hai jo ${\max }_{k\le n}|{\bar{X}}_k-\mu |$ control karta hai, ek sparse subsequence (jaise $n=2^k$) ke saath ek convergent series deta hai, phir Borel–Cantelli apply hota hai.

Independence ka matlab hai future coins ko streak ki koi memory nahi; har ek mein abhi bhi $\mathbb{P}(\text{heads})=\frac{1}{2}$ hai. Toh kuch bhi 8 heads ko "cancel" nahi karta. Balki average self-correct karta hai dilution se. Sum ka deviation likho: $S_n-n\mu ={\sum }_{i=1}^n(X_i-\mu ).$ Yeh sum badhta reh sakta hai — iska typical size $\sqrt{n}$ order ka hai (standard deviation $\sigma \sqrt{n}$). Lekin average ka deviation hai ${\bar{X}}_n-\mu =\frac{S_n-n\mu }{n},$ jiska standard deviation hai $\frac{\sigma \sqrt{n}}{n}=\frac{\sigma }{\sqrt{n}}\to 0$.

Figure padhna (walkthrough):

• Orange path (left axis) sum-deviation $S_n-n\mu$ hai. Notice karo arrow jo start mein 8-head streak mark karta hai: yeh orange path ko $8\cdot \frac{1}{2}=4$ upar uthata hai. Wahan se orange path drift karta rehta hai — yeh kabhi zero pe wapas nahi kheencha jaata. Yeh drift woh "$\sqrt{n}$ wandering" hai jo visible hai; koi repayment nahi hai.
• Teal path (right axis) average-deviation ${\bar{X}}_n-\mu$ hai. Yeh upar se shuru hota hai (streak chhote $n$ ko dominate karti hai) lekin jaldi squeeze ho jaata hai $0$ ki taraf.
• Do dashed plum curves funnel $\pm \sigma /\sqrt{n}$ hain. Teal path is narrowing funnel ke andar trapped hai, jo visibly $0$ tak clamp ho jaata hai jabki orange path escape karta hai.

Woh lesson jo picture concrete banati hai: streak ek bade $n$ ka vanishing fraction ban jaata hai, koi debt nahi jo future tails repay kare. Dekho Gambler's Fallacy.

• LLN: ${\bar{X}}_n-\mu \to 0$ (average constant $\mu$ pe land karta hai).
• CLT (dekho Central Limit Theorem): $\sqrt{n}({\bar{X}}_n-\mu )\stackrel{d}{\to }\mathcal{N}(0,{\sigma }^2)$ — shrinking deviation ko $\sqrt{n}$ se magnify karne ke baad, jo bachta hai woh ek fixed-width bell hai. Reconciliation: ${\bar{X}}_n-\mu$ rate $1/\sqrt{n}$ se shrink karta hai. Agar tum exactly $\sqrt{n}$ se zoom karo, tum shrink cancel kar dete ho aur non-degenerate fluctuation dekhte ho. Toh LLN batata hai kahan land karta hai; CLT batata hai land hone se pehle bache hue wiggle ki shape aur scale. Koi contradiction nahi: $\frac{1}{\sqrt{n}}\cdot (\text{bell})\to 0$.

Chahiye $\frac{{\sigma }^2}{n{\epsilon }^2}\le 0.02$ with ${\sigma }^2=4$, $\epsilon =0.2$ toh ${\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): ${\bar{X}}_n$ pe Chebyshev deta hai $\mathbb{P}(|{\bar{X}}_n-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{n{\epsilon }^2}$, jo $\to 0$. Yeh har $n$ ko alag se control karta hai.

Extra machinery — Kolmogorov's maximal inequality. Independent, mean-zero $Y_1,\dots ,Y_n$ ke liye partial sums $S_k=Y_1+\cdots +Y_k$ ke saath, yeh kehta hai $\mathbb{P}({\max }_{1\le k\le n}|S_k|\ge t)\le \frac{\mathrm{Var}(S_n)}{t^2}.$ Yeh Chebyshev se strictly stronger hai: Chebyshev sirf endpoint $|S_n|$ control karta hai, jabki yeh ek saath $n$ tak worst partial sum control karta hai — exactly wahi jo "sab large $n$ ke liye accha rehta hai" ko chahiye.

"Hamesha ke liye" mein upgrade: dyadic blocks $2^m\le n<2^{m+1}$ pe maximal inequality apply karo. Blockwise bounds ab ek convergent series ${\sum }_m(\cdot )<\infty$ banate hain (Exercise 3.2 ka $\sum 1/n$ divergence defeat ho jaata hai kyunki har block ek single $2^{-m}$-type term se summarised hai). Pehla Borel–Cantelli Lemma tab force karta hai ki sirf finitely many bad blocks hain, isliye last ke baad path hamesha ke liye good region mein trapped hai — yahi almost-sure convergence hai, yaani SLLN.

Mean hoga $\mu ={\int }_{-\infty }^{\infty }xf(x)dx={\int }_{-\infty }^{\infty }\frac{x}{\pi (1+x^2)}dx$. Integrand large $|x|$ ke liye $\frac{1}{\pi x}$ ki tarah behave karta hai, jiska integral diverge karta hai (dono tails), isliye $\mu$ undefined hai — koi number nahi hai jiske pe ${\bar{X}}_n$ converge kare. Kisi ek known fact ki baat karein: $n$ i.i.d. Cauchy variables ka sample mean khud Cauchy hai usi scale ke saath — averaging bilkul bhi narrow nahi karta. Toh LLN ki hypothesis $\mathbb{E}|X|<\infty$ genuinely necessary hai; "engine" $\mathrm{Var}({\bar{X}}_n)={\sigma }^2/n$ kabhi start bhi nahi hota kyunki ${\sigma }^2$ (aur $\mu$) exist hi nahi karte.

Haan. Chebyshev proof ko ${\sigma }^2<\infty$ chahiye, lekin woh sirf easy route hai. Khinchin's WLLN ko sirf $\mathbb{E}|X|<\infty$ chahiye (finite mean), aur Kolmogorov's SLLN ko bhi yahi chahiye, $\mathbb{E}|X|<\infty$. Toh finite variance ek proof ki convenience hai, laws ki requirement nahi. Sirf jab mean khud fail ho jaata hai (Cauchy) tabhi LLN break karta hai.

Setup: $U_i,V_i\sim \text{Uniform}(0,1)$ independently draw karo aur indicator set karo $X_i=1\{U_i^2+V_i^2\le 1\}\in \{0,1\}$ ($1$ agar point quarter unit-circle ke andar land kare). Iska expectation us quarter disc ka area hai: $\mathbb{E}[X_i]=\mathbb{P}(U^2+V^2\le 1)=\frac{\pi }{4}.$ Toh ${\bar{X}}_n\to \frac{\pi }{4}$, aur estimator hai ${\hat{\pi }}_n=4{\bar{X}}_n$.

Kaunsa law convergence guarantee karta hai: SLLN guarantee karta hai ${\bar{X}}_n\to \frac{\pi }{4}$ almost surely ek single infinite run ke liye, isliye ${\hat{\pi }}_n=4{\bar{X}}_n\to \pi$ almost surely.

Finite-$n$ error bound (WLLN with rate): yahan $\mu =\frac{\pi }{4}$ aur indicator ka variance hai ${\sigma }^2=\mu (1-\mu )=\frac{\pi }{4}(1-\frac{\pi }{4})\approx \mathrm{0.1685.}$ Error $|{\hat{\pi }}_n-\pi |\le \delta$ ka matlab hai $|{\bar{X}}_n-\frac{\pi }{4}|\le \frac{\delta }{4}$, toh set karo $\epsilon =\frac{\delta }{4}$. Chebyshev deta hai $\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: guarantee karne ke liye $\mathbb{P}(|{\hat{\pi }}_n-\pi |\ge 0.1)\le 0.05$, solve karo $\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,$ toh $n\ge \boxed{5392}$ draws sufficient hain (rounding up). Dekho Monte Carlo Methods.

L1 laws aur modes state karo ::: WLLN in probability, SLLN almost surely; SLLN⇒WLLN. L2 bound mein plug karo ::: $\mathbb{P}(|{\bar{X}}_n-\mu |\ge \epsilon )\le {\sigma }^2/(n{\epsilon }^2)$; $n$ ke liye solve karo. L3 Var kyun shrink hota hai / naive SLLN kyun fail hota hai ::: cross-covariances vanish ho jaate hain (independence); $\sum 1/n$ diverge karta hai isliye maximal inequality chahiye. L4 LLN vs CLT ::: LLN=kahan land karta hai ($\mu$); CLT=shape of the $1/\sqrt{n}$ wiggle. L5 hypotheses matter karte hain ::: $\mathbb{E}|X|<\infty$ chahiye; Cauchy isse break karta hai; Monte Carlo LLN in action hai.