Visual walkthrough — Law of Large Numbers — weak and strong

4.9.16 · D2 · Maths › Probability Theory & Statistics › Law of Large Numbers — weak and strong

Shuru karne se pehle, teen words plain language mein (har ek ko baad mein picture milegi, lekin abhi naam le lete hain):

---

Step 1 — Ek random variable number line par rakha hua mass hai

KYA. Machine ke possible outputs ko ek horizontal number line par laid out imagine karo. Har output value ke upar ek bar stack karo jiska height us value ki probability hai. Saare bars ki total height $1$ hai — machine hamesha kuch na kuch output karti hai.

KYU. Jo bhi inequality hum banate hain, woh actually ek statement hai ki centre se door kitna probability mass baitha hai. "Centre se door" ke baare mein reason karne ke liye pehle hamein mass ko ek physical cheez ki tarah dekhna hoga jo positions par baitha hai. Yeh picture abstract probability ko real weights ki stack mein badal deti hai.

PICTURE. Figure mein, kale bars probability weights hain. Laal dot $\mu$ mark karta hai — literally woh balance point jahan number line tab level ho jaye jab bars sach mein real weights hote.

$\mu =\mathbb{E}[X]=\underset{\text{add over every possible value}}{\underbrace{\sum _x}}\underset{\text{the position}}{\underbrace{x}}\cdot \underset{\text{the weight there}}{\underbrace{\mathbb{P}(X=x)}}$

Har term hai "position times weight" — bilkul wahi recipe jo centre of mass ke liye hoti hai. Isliye $\mu$ balance point hai, na ki koi abstract symbol.

---

Step 2 — Markov's inequality: dur ka mass mean ko cost karta hai

KYA. Ek aisi machine lo jo sirf $\ge 0$ values output karti hai (uski output $Y$ bolo). Ek threshold $a>0$ chuno. Hum claim karte hain ki $a$ par ya usse aage land karne ki probability zyada nahi ho sakti agar average $\mathbb{E}[Y]$ chhota hai: $\mathbb{P}(Y\ge a)\le \frac{\mathbb{E}[Y]}{a}.$

KYU. Yeh root tool hai — dekho Markov's Inequality. Yahi ek tarika hai jisse hum "average chhota hai" ko "zyada mass door nahi hai" mein convert kar sakte hain. Hum exactly wahi conversion chahte hain, kyunki Weak Law mass ke $\mu$ se door hone ke baare mein hai.

PICTURE. Figure dekho. Poori kali curve weight $y\cdot f(y)$ hai jise hum $\mathbb{E}[Y]$ pane ke liye sum kar rahe hain (yeh Step 1 ka "position times weight" hai, ab ek continuous machine ke liye, smooth density $f$ use karte hue). Hum do shrinking moves karte hain, dono shaded hain:

$\mathbb{E}[Y]=\underset{\text{all the mass, weighted by position}}{\underbrace{{\int }_0^{\infty }yf(y)dy}}\ge \underset{\text{threw away }[0,a):\text{ only removed}\ge 0\text{ stuff}}{\underbrace{{\int }_a^{\infty }yf(y)dy}}\ge \underset{\text{on }[a,\infty ),y\ge a}{\underbrace{{\int }_a^{\infty }af(y)dy}}=a\mathbb{P}(Y\ge a)$

• Pehla $\ge$: humne red-shaded left chunk $[0,a)$ delete kar diya. Kyunki $Y\ge 0$ hai, wahan sab kuch $\ge 0$ tha, toh usse hataane se total sirf kam ho sakta hai. Kaisa dikhta hai: left kaat do, pile aur unchi nahi hogi.
• Doosra $\ge$: right chunk par har $y$ kam se kam $a$ hai, toh har $y$ ko chhote constant $a$ se replace karna phir total ko kam karta hai. Kaisa dikhta hai: right hump ko flatten karke height $a$ ka rectangle bana do.
• Final rectangle ka area $a$ hai times uski total probability $\mathbb{P}(Y\ge a)$.

Dono sides ko $a$ se divide karo aur Markov mil jaata hai. Yahan $\int$ bas "infinitely many thin weights ko add karo" hai — Step 1 ke sum ka continuous version. Isliye integral aata hai, kuch fancy nahi.

---

Step 3 — Chebyshev: Markov ko $\mu$ ke aas paas ek two-sided ruler mein badlo

KYA. Markov sirf non-negative $Y$ ki baat karta hai. Lekin hum chahte hain ki $X$ $\mu$ se dono taraf door na ho. Trick: Markov ko machine $Y=(X-\mu {)}^2$ khilao, jo hamesha $\ge 0$ hai, aur threshold $a={\epsilon }^2$ chuno.

KYU. Squaring ek saath do kaam karta hai: quantity ko non-negative banata hai (toh Markov apply hota hai) aur "bahut zyada left" aur "bahut zyada right" ko identically treat karta hai, kyunki $(X-\mu {)}^2$ sign ignore karta hai. Yahi exactly woh two-sided statement hai jo hum chahte hain. Dekho Chebyshev's Inequality.

PICTURE. Figure parabola $y=(x-\mu {)}^2$ dikhata hai. $\mu -\epsilon$ aur $\mu +\epsilon$ par do vertical laal lines hain jahan $(x-\mu {)}^2={\epsilon }^2$ hai. Number line par red band se bahar hona wahi same event hai jab parabola height ${\epsilon }^2$ se upar uthti hai.

$\underset{\text{parabola above the red line}}{\underbrace{(X-\mu {)}^2\ge {\epsilon }^2}}⟺\underset{\text{outside the red band}}{\underbrace{|X-\mu |\ge \epsilon }}$

Ab Markov ko $Y=(X-\mu {)}^2$ par $a={\epsilon }^2$ ke saath apply karo: $\mathbb{P}(|X-\mu |\ge \epsilon )=\mathbb{P}((X-\mu {)}^2\ge {\epsilon }^2)\le \frac{\mathbb{E}[(X-\mu {)}^2]}{{\epsilon }^2}=\frac{{\sigma }^2}{{\epsilon }^2}$

• $\mathbb{E}[(X-\mu {)}^2]$ by definition variance ${\sigma }^2$ hai Step 0 se — average squared spread.
• $\epsilon$ hamaari chosen tolerance hai ("kitna dur hai zyada dur").
• Reading: wide spread $\Rightarrow$ band ke bahar zyada mass allowed; bada tolerance $\Rightarrow$ kam.

---

Step 4 — Averaging machine aur kyun uska spread shrink hota hai

KYA. Ab sample mean machine banao. Button $n$ baar dabao, $X_1,\dots ,X_n$ lo, aur unka average output karo: ${\bar{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{X}_i.$ Hum uska mean compute karte hain aur — crucial part — uska variance.

KYU. Chebyshev (Step 3) ko jis bhi machine par point karo uska variance chahiye. Agar hum dikhaa sakein ki ${\bar{X}}_n$ ka variance bahut chhota hai, toh Chebyshev immediately uska mass $\mu$ ke paas force kar dega. Toh yahi step hai jahan actual shrinking hoti hai.

PICTURE. Figure mein ek single $X$ ka spread (wide kali bell) stack hai ${\bar{X}}_n$ ke spread ke saath growing $n$ ke liye (progressively narrower curves, sabse narrow laal mein draw ki gayi). Centre $\mu$ same hai, lekin averaging machine ka spread andar collapse ho jaata hai.

Mean (linearity use karta hai — averages ka average hi average hota hai): $\mathbb{E}[{\bar{X}}_n]=\frac{1}{n}{\sum }_{i=1}^n\underset{=\mu \text{ each}}{\underbrace{\mathbb{E}[X_i]}}=\frac{1}{n}\cdot n\mu =\mu$ Centre kabhi nahi hilta. Accha — machine sahi aim kar rahi hai.

Variance (independence use karta hai — yahan "i.i.d." apni jagah earn karta hai): $\mathrm{Var}({\bar{X}}_n)=\mathrm{Var}(\frac{1}{n}\sum X_i)=\underset{\text{constant }\frac{1}{n}\text{ pulls out squared}}{\underbrace{\frac{1}{n^2}}}\underset{\text{independence: cross terms vanish}}{\underbrace{\sum _{i=1}^n\mathrm{Var}(X_i)}}=\frac{n{\sigma }^2}{n^2}=\frac{{\sigma }^2}{n}$

• $\frac{1}{n}$ ko variance se bahar khaींchne par woh square hokar $\frac{1}{n^2}$ ban jaata hai (variance ek multiplier ke square ke saath scale hota hai).
• Kyunki $X_i$ independent hain, sum ka variance bas variances ka sum hai — koi covariance cross-terms survive nahi karte. Yahi ek jagah hai jahan independence use hoti hai.
• Result: $\mathrm{Var}({\bar{X}}_n)={\sigma }^2/n$. Yeh $1/n$ hi poora engine hai. Har extra draw spread ko aur divide karta hai.

---

Step 5 — Weak Law assemble karo

KYA. Chebyshev (Step 3) ko averaging machine (Step 4) par point karo, jiska mean $\mu$ hai aur variance ${\sigma }^2/n$ hai.

KYU. Ab saare parts click ho jaate hain: Chebyshev ek bound deta hai variance ke terms mein, aur Step 4 ne woh variance chhota kar diya. Substitute karna hi finish line hai.

PICTURE. Figure mein bound $\frac{{\sigma }^2}{n{\epsilon }^2}$ ek kali curve ke roop mein dikhta hai jo $n$ badhne par $0$ ki taraf gir raha hai, aur shaded "probability of being off by more than $\epsilon$" (laal) uske neeche squeeze ho rahi hai — trapped, zero hone par majboor.

$\mathbb{P}(|{\bar{X}}_n-\mu |\ge \epsilon )\le \frac{\mathrm{Var}({\bar{X}}_n)}{{\epsilon }^2}=\frac{{\sigma }^2/n}{{\epsilon }^2}=\underset{\to 0\text{ as }n\to \infty }{\underbrace{\frac{{\sigma }^2}{n{\epsilon }^2}}}$

• Numerator ${\sigma }^2$: ek draw ka fixed spread.
• Denominator $n{\epsilon }^2$: $n\to \infty$ ke saath bina bound ke badhta hai (kisi bhi fixed tolerance $\epsilon$ ke liye).
• Ek fixed number ek exploding number se divide ho $\to 0$.

---

Step 6 — Degenerate & edge cases (koi gap mat chhhodo)

KYA / KYU / PICTURE har us corner ke liye jo reader ko mil sakta hai:

---

Ek picture mein summary

KYA. Ek figure jo poori argument chain karta hai: ek single draw ka wide spread → parabola trick jo "far from $\mu$" ko "square exceeds ${\epsilon }^2$" mein badal deti hai → $1/n$ variance collapse → bound jo tail probability ko zero kar deta hai.

$\underset{\text{Markov}}{\underbrace{Y\ge 0}}\stackrel{Y=(X-\mu {)}^2}{\to }\underset{\text{Chebyshev}}{\underbrace{\mathbb{P}(|X-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{{\epsilon }^2}}}\stackrel{X\to {\bar{X}}_n,\mathrm{Var}=\frac{{\sigma }^2}{n}}{\to }\underset{\text{Weak Law}}{\underbrace{\mathbb{P}(|{\bar{X}}_n-\mu |\ge \epsilon )\le \frac{{\sigma }^2}{n{\epsilon }^2}\to 0}}$

Recall Feynman retelling — poora walkthrough plain words mein

Probability ko chhote weights ki tarah imagine karo jo number line par baithе hain; mean $\mu$ woh point hai jahan woh balance karein. Markov ka idea: agar average position chhota hai, toh bahut zyada weight bahut door park nahi ho sakti — balance tip ho jaata. Usse $\mu$ ke dono sides par use karne ke liye, hum distance ko square karte hain $(X-\mu {)}^2$ (squaring sign bhool jaata hai aur negative nahi ho sakta), usse Markov ko dete hain, aur Chebyshev nikal aata hai: $\mu$ se $\epsilon$ se zyada door hone ka chance zyada se zyada ${\sigma }^2/{\epsilon }^2$ hai. Ab magic move: ek draw ki jagah $n$ independent draws ko average karo. Averaging balance point ko $\mu$ par rakhta hai lekin — kyunki independent wiggles cancel hote hain — spread ${\sigma }^2/n$ tak squeeze ho jaata hai. Woh shrunken spread Chebyshev mein wapas daalo aur bound ban jaata hai ${\sigma }^2/(n{\epsilon }^2)$, jo $n$ badhne par zero ho jaata hai. Toh average probably $\mu$ ke paas hai, aur jitna zyada average karo utne sure ho jaate ho. Sirf do cheezein isse tod sakti hain: balance point exist hi na kare (Cauchy — no mean), ya draws secretly ek doosre par lean karein (dependence wiggles ko cancel karne se rokta hai).

Recall One-line challenge before you leave

Averaging spread ko kyun shrink karta hai lekin centre ko move nahi karta? ::: Linearity $\mathbb{E}[{\bar{X}}_n]=\mu$ rakhti hai (centre fixed); independence variances ko add karta hai, aur $1/n^2$ jo $\frac{1}{n}$ kheench ke aata hai $n$ terms ko beat karta hai, ${\sigma }^2/n$ chodke (spread shrinks).