Monte Carlo simulation — law of large numbers basis

4.9.25 · Maths › Probability Theory & Statistics

Monte Carlo kaam karta hi KYUN hai?

KYA chahiye humein: kai quantities secretly expectations hoti hain.

• Ek integral ${\int }_0^{1}g(x)dx=\mathbb{E}[g(U)]$ jahan $U\sim \text{Uniform}(0,1)$.
• Ek probability $P(A)=\mathbb{E}[1_A]$ (ek indicator ki expectation).
• $\pi$, option prices, particle-physics cross-sections — sab randomness par averages hain.

KYUN hum inhe estimate kar sakte hain: agar koi quantity $\mathbb{E}[X]$ ke barabar hai, aur hum $X$ ke independent copies $X_1,\dots ,X_n$ draw karte hain, toh sample mean ${\bar{X}}_n=\frac{1}{n}\sum X_i$ ko $\mathbb{E}[X]$ par "settle" ho jaana chahiye. Yahi "settle down" karna hai Law of Large Numbers.

KAISE use karte hain: random samples generate karo → har ek ko function mein daalo → average karo. Ho gaya.

Law of Large Numbers (derived, not dumped)

Ise first principles se derive karna

Step 1 — Sample mean ka Mean. Kyun? Yeh jaanne ke liye ki yeh kis par centered hai. $\mathbb{E}[{\bar{X}}_n]=\frac{1}{n}{\sum }_{i=1}^n\mathbb{E}[X_i]=\frac{1}{n}\cdot n\mu =\mu .$ Yeh step kyun? Expectation linear hai, isliye yeh sum mein se pass ho jaati hai. Estimator unbiased hai.

Step 2 — Sample mean ka Variance. Kyun? Spread ko shrink hota dekhne ke liye. $\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=1}^n\mathrm{Var}(X_i)=\frac{1}{n^2}\cdot n{\sigma }^2=\frac{{\sigma }^2}{n}.$ Yeh step kyun? Independence ki wajah se sum ka variance, variances ke sum ke barabar hota hai (cross-covariances zero ho jaate hain). $\frac{1}{n^2}$ bahar nikalna $\mathrm{Var}(aY)=a^2\mathrm{Var}(Y)$ use karta hai.

Step 3 — Chebyshev's inequality. Kyun? Yeh "mean se kitni baar door" ko sirf variance use karke bound karta hai. $P(|{\bar{X}}_n-\mu |\ge \epsilon )\le \frac{\mathrm{Var}({\bar{X}}_n)}{{\epsilon }^2}=\frac{{\sigma }^2}{n{\epsilon }^2}.$ Yeh step kyun? Chebyshev kehta hai ki $\epsilon$ se bade deviations rare hote hain jab variance chhota ho.

Step 4 — Limit lo. Jaise $n\to \infty$, $\frac{{\sigma }^2}{n{\epsilon }^2}\to 0$. Squeeze probability ko 0 force karta hai. $■$

Monte Carlo estimator aur uska error

$1/\sqrt{n}$ kyun important hai: ek aur decimal digit ki accuracy paane ke liye (10× chhota error) aapko 100× zyada samples chahiye. Dimension-independence iska faayda hai: yeh $1/\sqrt{n}$ tab bhi hold karta hai chahe $X$ 1-D ho ya 1000-D, isliye Monte Carlo high dimensions mein grid methods ko peeche chhod deta hai.

Worked Example 1 — $\pi$ Estimate karna

KYA: Unit square $[0,1{]}^2$ mein random darts pheenko. Andar girne wale darts ka fraction jo quarter-circle ($x^2+y^2\le 1$) ke andar hai, area $\pi /4$ estimate karta hai.

• Maano $X=1\{U_1^2+U_2^2\le 1\}$ jahan $U_1,U_2\sim \text{Unif}(0,1)$.
• $\mathbb{E}[X]=P(\text{inside})=\frac{\text{area of quarter disk}}{\text{area of square}}=\frac{\pi /4}{1}=\frac{\pi }{4}.$ Kyun? Uniform points → probability = area ratio.

Estimator: $\hat{\pi }=4{\bar{X}}_n$. ×4 kyun? Kyunki ${\bar{X}}_n\to \pi /4$, isliye $\pi$ recover karne ke liye 4 se multiply karo.

Error: $X$ Bernoulli($p=\pi /4\approx 0.785$) hai, isliye ${\sigma }_g^2=p(1-p)\approx 0.169$. Toh $\text{SE}(\hat{\pi })=4\cdot \sqrt{0.169/n}$. $n=10^4$ ke liye, SE $\approx 0.016$ — yani $\hat{\pi }$ ~2 decimals tak sahi. Itna slow kyun? Woh fatal $1/\sqrt{n}$.

Worked Example 2 — Ek 1-D Integral

$\theta ={\int }_0^1{e}^{-x^2}dx$ estimate karo (koi elementary antiderivative nahi hai).

• Likho $\theta =\mathbb{E}[e^{-U^2}]$, $U\sim \text{Unif}(0,1)$. Kyun? ${\int }_0^{1}g(x)dx=\mathbb{E}[g(U)]$ kyunki Uniform density $[0,1]$ par 1 hai.
• $U_1,\dots ,U_n$ draw karo, compute karo ${\hat{\theta }}_n=\frac{1}{n}\sum e^{-U_i^2}$. Kyun? Yeh $g(U)$ ka sample mean hai; LLN ⇒ $\to \theta \approx 0.7468$.
• Standard error: samples se ${\hat{\sigma }}_g$ estimate karo, ${\hat{\theta }}_n\pm 1.96{\hat{\sigma }}_g/\sqrt{n}$ report karo. Kyun? CLT interval deta hai; imaandaari ke liye error bars zaroori hain.

Worked Example 3 — Forecast-then-Verify

Forecast: Main $\pi$ estimate $n=100$ aur phir $n=10000$ ke saath run karta hoon. Error kitna shrink hona chahiye? $n$ ka ratio 100 hai, isliye $\sqrt{100}=10$. Prediction: error ~10× kam hoga.

Verify (typical run): $n=100\Rightarrow$ error $\sim 0.16$; $n=10000\Rightarrow$ error $\sim 0.016$. ✔ $1/\sqrt{n}$ law se match karta hai. Yeh kyun matter karta hai: yeh aapko kuch bhi run karne se pehle compute budget plan karne deta hai.

Common Mistakes (Steel-manned)

Active Recall

Connections

• Central Limit Theorem — confidence interval / error bars deta hai.
• Chebyshev's Inequality — WLLN proof ka engine.
• Strong Law of Large Numbers — almost-sure convergence (WLLN se stronger).
• Variance and Covariance — kyun independence variance ko add karne deti hai.
• Importance Sampling — ${\sigma }_g$ reduce karta hai $1/\sqrt{n}$ wall ko beat karne ke liye.
• Numerical Integration — deterministic alternative jisse Monte Carlo compete karta hai.
• Bernoulli Distribution — indicator-based estimates jaise $\pi$ ke liye model.

Concept Map

Deep Dive

• D1 · Foundations — har symbol zero se
• D2 · Visual walkthrough — derivation pictures mein
• D3 · Worked examples — har scenario
• D4 · Exercises — graded, full solutions
• D5 · Question bank — concept traps