Law of large numbers — Hinglish notes

1.3.14 · AI-ML › Probability & Statistics

What Exactly Is the Law of Large Numbers?

Do versions kyun? WLLN kehta hai "bade $n$ ke liye sample mean probably $μ$ ke kareeb hai." SLLN kuch aur strong kehta hai: "sample mean eventually $μ$ par settle ho jaayega aur wahin rahega, guaranteed." Machine learning ke liye, WLLN usually kaafi hai.

Derivation from First Principles

Chalte hain Weak Law ko Chebyshev's inequality se prove karte hain.

Step 1: What We Know

Hamare paas i.i.d. random variables $X_{1}, \dots, X_{n}$ hain jinke liye:

Mean: $E [X_{i}] = μ$
Variance: $Var (X_{i}) = σ^{2}$ (finite maana gaya hai)

Sample mean: $\overset{ˉ}{X}_{n} = \frac{1}{n} \sum_{i = 1}^{n} X_{i}$

Step 2: Expected Value of Sample Mean

$E [\overset{ˉ}{X}_{n}] = E [\frac{1}{n} \sum_{i = 1}^{n} X_{i}] = \frac{1}{n} \sum_{i = 1}^{n} E [X_{i}] = \frac{1}{n} \cdot n μ = μ$

Yeh step kyun? Expectation linear hoti hai, isliye hum ise sum ke andar le ja sakte hain. Har $X_{i}$ ka same mean $μ$ hota hai.

Step 3: Variance of Sample Mean

$Var (\overset{ˉ}{X}_{n}) = Var (\frac{1}{n} \sum_{i = 1}^{n} X_{i})$

Kyunki $X_{i}$ independent hain, variances add hote hain: $= \frac{1}{n ^{2}} Var (\sum_{i = 1}^{n} X_{i}) = \frac{1}{n ^{2}} \sum_{i = 1}^{n} Var (X_{i})$

Yeh step kyun? Jab tum ek random variable ko constant $c$ se multiply karte ho, variance $c^{2}$ se scale hota hai. Independence ka matlab hai $Var (X + Y) = Var (X) + Var (Y)$ .

$= \frac{1}{n ^{2}} \cdot n σ^{2} = \frac{σ ^{2}}{n}$

Key insight: Sample mean ki variance $n$ badhne ke saath kam hoti jaati hai. Isliye bade samples zyada reliable hote hain.

Step 4: Apply Chebyshev's Inequality

Chebyshev's inequality kehti hai ki kisi bhi random variable $Y$ ke liye jiska mean $μ_{Y}$ aur variance $σ_{Y}^{2}$ ho: $P (∣ Y - μ_{Y} ∣ \geq ϵ) \leq \frac{σ _{Y}^{2}}{ϵ ^{2}}$

$\overset{ˉ}{X}_{n}$ par apply karo: $P (∣ \overset{ˉ}{X}_{n} - μ ∣ \geq ϵ) \leq \frac{Var ( X ˉ _{n} )}{ϵ ^{2}} = \frac{σ ^{2}}{n ϵ ^{2}}$

Step 5: Take the Limit

$lim_{n \to \infty} P (∣ \overset{ˉ}{X}_{n} - μ ∣ \geq ϵ) \leq lim_{n \to \infty} \frac{σ ^{2}}{n ϵ ^{2}} = 0$

Therefore: $lim_{n \to \infty} P (∣ \overset{ˉ}{X}_{n} - μ ∣ \geq ϵ) = 0$

Yeh step kyun? Jab $n \to \infty$ , upper bound zero ho jaata hai, toh probability khud bhi zero ho jaani chahiye. Isse Weak Law prove hota hai.∎

Worked Examples

Worked example Example 1: Fair Coin Flips

Problem: Tum ek fair coin $n$ baar flip karte ho. Maano $X_{i} = 1$ agar heads aaye, $0$ agar tails. Kya probability hai ki $n = 10, 000$ hone par heads ka proportion 0.5 se 0.01 se zyada differ kare?

Solution: Step 1: Parameters identify karo

$E [X_{i}] = 0.5$
$Var (X_{i}) = E [X_{i}^{2}] - (E [X_{i}])^{2} = 0.5 - 0.25 = 0.25$ Kyun? Ek Bernoulli variable ke liye, $X_{i}^{2} = X_{i}$ , isliye $E [X_{i}^{2}] = P (X_{i} = 1) = 0.5$ . Step 2: Chebyshev bound apply karo $P (∣ \overset{ˉ}{X}_{n} - 0.5∣ \geq 0.01) \leq \frac{0.25}{1000 \cdot ( 0.01 ) ^{2}} = \frac{0.25}{1} = 0.25$ Yeh step kyun? Apne formula mein $σ^{2} = 0.25$ , $n = 10000$ , $ϵ = 0.01$ plug karo.

Interpretation: Zyada se zyada 25% chance hai ki 1% se zyada galat ho. Reality mein, Central Limit Theorem use karte hue (tighter bound), probability lagbhag 0.046 (4.6%) hai. LLN hume ek conservative guarantee deta hai.

Worked example Example 2: Estimating Average Height

Problem: Ek population ka mean height $μ = 170$ cm hai, standard deviation $σ = 10$ cm hai. Kitne logon ko sample karna hoga taaki sample mean true mean ke 1 cm andar rahe, kam se kam 95% probability ke saath?

Solution:

Hum chahte hain: $P (∣ \overset{ˉ}{X}_{n} - 170∣ < 1) \geq 0.95$ Equivalently: $P (∣ \overset{ˉ}{X}_{n} - 170∣ \geq 1) \leq 0.05$

Step 1: Chebyshev bound use karo $\frac{σ ^{2}}{n ϵ ^{2}} \leq 0.05$ $\frac{100}{n \cdot 1} \leq 0.05$ Yeh step kyun? Hum right side ko 0.05 (maximum allowed error probability) set karte hain aur $n$ ke liye solve karte hain.

Step 2: $n$ ke liye solve karo $n \geq \frac{100}{0.05} = 2000$

Answer: Kam se kam 2,000 logon ko sample karo.

Reality check: CLT (normal approximation) use karte hue, sirf lagbhag 385 logon ki zaroorat hogi. Chebyshev conservative hai lekin kisi bhi distribution ke liye kaam karta hai.

Worked example Example 3: Monte Carlo Integration

Problem: Uniform random points sample karke aur check karke ki woh curve ke neeche hain ya nahi, $\int_{0}^{1} e^{- x^{2}} d x$ estimate karo.

Solution:

Step 1: Problem set up karo

$X_{i} \sim Uniform (0, 1)$ aur $Y_{i} \sim Uniform (0, 1)$ draw karo
Maano $Z_{i} = 1$ agar $Y_{i} \leq e^{- X_{i}^{2}}$ , warna $0$
Integral equals $E [Z_{i}] = P (Y_{i} \leq e^{- X_{i}^{2}})$

Step 2: LLN apply karo $\overset{ˉ}{Z}_{n} = \frac{1}{n} \sum_{i = 1}^{n} Z_{i} \to E [Z_{i}] = \int_{0}^{1} e^{- x^{2}} d x \approx 0.7468$

Yeh step kyun? LLN se, $Z_{i}$ ka sample mean true integral value par converge karta hai.

Step 3: Error bound

$Var (Z_{i}) \leq 0.25$ (Bernoulli ki variance $p = 0.5$ par maximize hoti hai)
Standard error: $σ / n = 0.5/ n$
Error $< 0.001$ ke liye: $n \geq (0.5/0.001)^{2} = 250, 000$ samples chahiye ML Connection: Yeh reinforcement learning aur Bayesian inference mein high-dimensional integration ke liye Monte Carlo methods ki foundation hai.

Common Mistakes & Steel-Manning

Why This Matters for Machine Learning

Training Convergence: Stochastic gradient descent (SGD) LLN use karta hai—mini-batch ka gradient batch size badhne ke saath true gradient par converge karta hai.
Monte Carlo Methods: Expectations estimate karna (RL mein value functions, Bayesian ML mein posterior means) accuracy guarantee karne ke liye LLN par depend karta hai.
Sample Complexity: LLN humein batata hai ki desired precision tak quantities estimate karne ke liye kitne examples chahiye. $O (1/ n)$ variance decay learning theory ke liye fundamental hai.
Ensemble Methods: Kai models ki predictions ko average karne se error kyun kam hoti hai? LLN! Individual model errors average out ho jaate hain.
A/B Testing: LLN click-through rates, conversion rates, etc. estimate karne ke liye sample proportions use karna justify karta hai.

Recall Ek 12-Saal-Ke-Bacche Ko Explain Karo

Socho tum apne school ke bachon ki average height pata karna chahte ho. Tum ek bachche ko measure karte ho—shayad woh bahut lamba hai, jaise 180 cm. Tum sochte ho, "Wah, sab log lamba honge!" Lekin phir tum doosre bachche ko measure karte ho—150 cm. Ab tum confused ho.

Lekin kya hoga agar tum 10 bachche measure karo? Phir 50? Phir 200? Jaise-jaise tum aur measure karte jaate ho, tumhara average school ke saare bachon ki real average height ke kareeb aata jaata hai.

Law of Large Numbers ek jaadu ka waada hai: "Agar tum data collect karte raho, tumhara average sach ke kareeb aata jaata rahega." Aisa nahi hai ki randomness khatam ho jaati hai—kuch bachche lamba hain, kuch chhote hain—lekin average stable ho jaata hai.

Isliye scientists bahut saare experiments karte hain, isliye polls hazaron logon se puchte hain, aur isliye casinos hamesha paisa kamaate hain (unhone lakho games khele hain, isliye average hamesha unke favor mein kaam karta hai).

Connections

Central Limit Theorem — LLN batata hai sample mean kahan jaata hai; CLT batata hai woh wahan kaise pahunchta hai (normal distribution)
Chebyshev Inequality — Woh tool jo humne LLN prove karne ke liye use kiya; kisi bhi distribution ke liye probability bounds deta hai
Variance and Standard Deviation — Variance $σ^{2} / n$ convergence rate control karta hai
Monte Carlo Methods — Integrals aur expectations estimate karne ke liye LLN ka direct application
Confidence Intervals — LLN population parameters estimate karne ke liye sample statistics use karna justify karta hai
Bias-Variance Tradeoff — LLN ke anusaar estimates ki variance sample size ke saath decrease hoti hai
Stochastic Gradient Descent — Mini-batch gradients LLN se true gradient par converge karte hain
Bootstrap Sampling — Resampling-based inference ke liye LLN par rely karta hai
Expected Value — Woh $μ$ jis par sample means converge karte hain
Independent and Identically Distributed — LLN ke liye required i.i.d. assumption

#flashcards/ai-ml

Law of Large Numbers kya kehta hai? :: Jitna zyada baar tum experiment repeat karte ho, sample mean $\overset{ˉ}{X}_{n}$ expected value $μ$ par converge karta hai. Probability ki $∣ \overset{ˉ}{X}_{n} - μ ∣$ kisi bhi fixed $ϵ$ se zyada ho, zero ho jaati hai jab $n \to \infty$ .

Weak LLN aur Strong LLN mein kya farq hai?

Weak LLN:

P (∣ \overset{ˉ}{X}_{n} - μ ∣ \geq ϵ) \to 0

(convergence in probability). Strong LLN:

P (lim_{n \to \infty} \overset{ˉ}{X}_{n} = μ) = 1

(almost sure convergence). Strong LLN zyada strong hai—eventual settling at

μ

guarantee karta hai.

Sample mean

\overset{ˉ}{X}_{n}

ki variance kya hoti hai agar har

X_{i}

ki variance

σ^{2}

ho?

Var (\overset{ˉ}{X}_{n}) = σ^{2} / n

. Yeh

n

badhne ke saath decrease hoti hai, isliye bade samples zyada precise estimates dete hain.

Sample mean mein error sample size ke saath kitni tezi se decrease hoti hai?

\overset{ˉ}{X}_{n}

ka standard deviation

σ / n

hota hai, isliye error

O (1/ n)

ki tarah decrease hoti hai. Error aadhi karne ke liye, tumhe 4× samples chahiye.

Law of Large Numbers ke liye kya assumptions chahiye?

Random variables (1) independent aur (2) identically distributed (i.i.d.) hone chahiye jinki (3) finite expected value

μ

ho (aur Chebyshev se WLLN ke liye finite variance).

Agar tum ek fair coin

n

baar flip karo, toh LLN heads ke proportion ke baare mein kya kehta hai?

Heads ka proportion

\overset{ˉ}{X}_{n}

n \to \infty

hone par

p = 0.5

par converge karta hai. Probability ki

∣ \overset{ˉ}{X}_{n} - 0.5∣ > ϵ

ho, kisi bhi

ϵ > 0

ke liye zero ho jaati hai.

Monte Carlo integration mein LLN kaise use hota hai?

Random points sample karo; har point par ek function value compute karo. In values ka sample mean LLN se expected value (integral) par converge karta hai. Error

1/ n

ki tarah scale hoti hai.

SGD mein mini-batch gradients true gradient par kyun converge karte hain?

LLN ki wajah se. Har mini-batch ek noisy gradient estimate deta hai. Batch size badhne ke saath, gradients ka sample mean true gradient

\nabla L

par converge karta hai.

LLN ke liye Chebyshev's inequality kya bound deti hai?

P (∣ \overset{ˉ}{X}_{n} - μ ∣ \geq ϵ) \leq σ^{2} / (n ϵ^{2})

. Yeh ek distribution-free guarantee deta hai jo finite variance wale kisi bhi random variable ke liye kaam karta hai.

LLN ka matlab yeh kyun nahi hai ki 1000 fair coin flips mein exactly 500 heads aayenge?

LLN probability mein convergence guarantee karta hai, deterministic convergence nahi. Sample mean 0.5 ke arbitrarily close ho jaata hai, lekin randomness rehti hai—tumhe 498, 501, ya 503 heads mil sakte hain. Absolute fluctuations khatam nahi hote.