Monte Carlo simulation — law of large numbers basis: Exercises

4.9.25 · D4 · Maths › Probability Theory & Statistics › Monte Carlo simulation — law of large numbers basis

Yeh page parent topic ke liye ek self-test ladder hai. Har problem ko solution kholne se pehle khud solve karo. Levels recognising the machinery se lekar synthesising whole estimators tak chadhti hain. Har number jo tumse manga jayega woh vault ke verify block mein checked hai, isliye answers par trust karo.

Poore notes mein reuse hone wale constants: standard error $SE = σ_{g} / n$ (estimate ka spread), aur ek yes/no (Bernoulli) count ke liye, $σ_{g}^{2} = p (1 - p)$ .

Level 1 — Recognition

L1.1

$θ = \int_{0}^{1} cos (x) d x$ ko Monte Carlo se estimate karna hai. $θ$ ko ek expectation ke roop mein rewrite karo aur woh distribution batao jisse tum sample karte ho.

Recall Solution

KYA karte hain: $\int_{0}^{1} g (x) d x$ ko expectation template se match karo. KYU: Uniform $(0, 1)$ density $[0, 1]$ par exactly $1$ hai, isliye $\int_{0}^{1} g (x) d x = \int_{0}^{1} g (x) \cdot 1 d x = E [g (U)], U \sim Unif (0, 1) .$ Yahan $g (x) = cos x$ , isliye $θ = E [cos U], U \sim Unif (0, 1) .$ Tum $U_{1}, \dots, U_{n}$ draw karoge aur $cos U_{i}$ ko average karoge.

L1.2

Ek Monte Carlo run mein sample standard deviation $\overset{σ}{^}_{g} = 0.5$ aur $n = 2500$ samples milte hain. Standard error likho.

Recall Solution

$SE = \frac{σ ^ _{g}}{n} = \frac{0.5}{2500} = \frac{0.5}{50} = 0.01.$ KYU $n$ na ki $n$ : sample mean ka variance $σ_{g}^{2} / n$ hota hai; standard deviation (matlab $θ$ ke same units mein ek error) pane ke liye square root lena padta hai, jisse $n$ aata hai.

Level 2 — Application

L2.1

Tum $π$ estimate karte ho dart method se: $X = 1 {U_{1}^{2} + U_{2}^{2} \leq 1}$ , $\overset{π}{^} = 4 \overset{ˉ}{X}_{n}$ . $p = π /4 \approx 0.785$ use karke, $n = 10000$ ke liye $SE (\overset{π}{^})$ compute karo.

Recall Solution

Step 1 — ek dart ka variance. $X$ Bernoulli $(p)$ hai, isliye $σ_{g}^{2} = p (1 - p) = 0.785 \times 0.215 \approx 0.1688$ . Step 2 — mean $\overset{ˉ}{X}_{n}$ ka SE. $σ_{g}^{2} / n = 0.1688/10000 = 1.688 \times 1 0^{- 5} \approx 0.004109$ . Step 3 — 4 se scale karo (kyunki $\overset{π}{^} = 4 \overset{ˉ}{X}_{n}$ aur $Var (4 Y) = 16 Var (Y)$ , isliye SE 4 se multiply hota hai): $SE (\overset{π}{^}) = 4 \times 0.004109 \approx 0.01644.$ Toh $\overset{π}{^}$ roughly $\pm 0.016$ tak accurate hai — lagbhag do decimal places. Figure dekho: sirf red arc ke andar dots ka fraction hi information carry karta hai.

L2.2

Usi $π$ estimator ke liye, kitne samples $n$ chahiye taaki $SE (\overset{π}{^}) \leq 0.001$ ho?

Recall Solution

Set karo $4 p (1 - p) / n \leq 0.001$ . $n$ ke liye solve karo: $\frac{p ( 1 - p )}{n} \leq \frac{0.001}{4} = 2.5 \times 1 0^{- 4} \Rightarrow \frac{p ( 1 - p )}{n} \leq 6.25 \times 1 0^{- 8} .$ $n \geq \frac{0.1688}{6.25 \times 1 0 ^{- 8}} \approx 2.70 \times 1 0^{6} .$ KYU itna zyada: L2.1 ki error ( $0.016$ ) ko $16 \times$ shrink karne ke liye $1 6^{2} = 256 \times$ zyada samples chahiye. Yahi $1/ n$ ka tax hai.

Level 3 — Analysis

L3.1

Do runs same $θ$ estimate karte hain: run A mein $n_{A} = 400$ hai, run B mein $n_{B} = 3600$ hai. Same $σ_{g}$ assume karke, B ka standard error A se kitne factor se chhota hai?

Recall Solution

$\frac{SE _{A}}{SE _{B}} = \frac{σ _{g} / n _{A}}{σ _{g} / n _{B}} = \frac{n _{B}}{n _{A}} = \frac{3600}{400} = 9 = 3.$ B 3 guna zyada accurate hai, halanki usne 9 guna samples use kiye. Neeche ka figure dekho: error $1/ n$ curve ke along girti hai, jo flatten hoti hai — baad ke samples kam faida dete hain.

L3.2

Chebyshev's Inequality use karke, yeh probability bound karo ki ek Monte Carlo estimate $\hat{θ}_{n}$ jiska $Var (\hat{θ}_{n}) = σ_{g}^{2} / n$ hai, $θ$ se kam se kam $ε$ utna deviate kare. Phir $σ_{g}^{2} = 0.25$ , $n = 10000$ , $ε = 0.05$ ke liye bound evaluate karo.

Recall Solution

Chebyshev kehta hai $P (∣ Y - E Y ∣ \geq ε) \leq Var (Y) / ε^{2}$ . $Y = \hat{θ}_{n}$ ke saath: $P (∣ \hat{θ}_{n} - θ ∣ \geq ε) \leq \frac{σ _{g}^{2}}{n ε ^{2}} .$ Plug in karo: $\frac{0.25}{10000 \times ( 0.05 ) ^{2}} = \frac{0.25}{10000 \times 0.0025} = \frac{0.25}{25} = 0.01.$ Toh zyada se zyada 1% chance hai ki estimate $0.05$ ya zyada se off ho. Yeh exactly WLLN proof ka Step 3 hai, numeric banaya gaya.

Level 4 — Synthesis

L4.1

Double integral ke liye ek Monte Carlo estimator design karo $θ = \int_{0}^{1} \int_{0}^{1} (x + y)^{2} d x d y .$ Estimator batao, uska exact mean $θ$ , aur explain karo kyun $1/ n$ error 1-D se 2-D jaane par unchanged rehti hai.

Recall Solution

Build karo. $(U_{1}, U_{2}) \sim Unif ([0, 1]^{2})$ ki joint density $1$ hai, isliye $θ = E [(U_{1} + U_{2})^{2}] .$ Estimator: pairs $(U_{1}^{(i)}, U_{2}^{(i)})$ draw karo aur $g_{i} = (U_{1}^{(i)} + U_{2}^{(i)})^{2}$ ko average karo: $\hat{θ}_{n} = \frac{1}{n} \sum_{i = 1}^{n} (U_{1}^{(i)} + U_{2}^{(i)})^{2} .$ Exact value (checking ke liye): expand aur integrate karo, $θ = \int_{0}^{1} \int_{0}^{1} (x^{2} + 2 x y + y^{2}) d x d y = \frac{1}{3} + 2 \cdot \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{3} = \frac{1}{3} + \frac{1}{2} + \frac{1}{3} = \frac{7}{6} \approx 1.1 \overline{6} .$ Kyun dimension nuksaan nahi karta: error formula $σ_{g} / n$ sirf scalar $g$ ke variance aur count $n$ par depend karta hai — $X$ ki dimension par kabhi nahi. Ek grid method ko 2-D grid ke liye $m^{2}$ points chahiye honge; Monte Carlo same $1/ n$ rakhta hai. Yahi numerical-integration ka fayda hai.

L4.2

L4.1 ke estimator ke liye, ek single $g = (U_{1} + U_{2})^{2}$ ka variance $σ_{g}^{2} = \frac{197}{180} - (\frac{7}{6})^{2}$ hai. $σ_{g}^{2}$ compute karo (4 decimals rakhna) aur $n = 5000$ par SE nikalo.

Recall Solution

Pehle $E [g^{2}] = E [(U_{1} + U_{2})^{4}] = \frac{197}{180} \approx 1.09444$ (ek moment integral). Phir $σ_{g}^{2} = \frac{197}{180} - (\frac{7}{6})^{2} = 1.09444 - 1.36111 = - 0.26667.$ Ek variance negative nahi ho sakta — isliye $E [g^{2}]$ galat stated tha. Honestly recompute karo: $E [g^{2}] = E [(U_{1} + U_{2})^{4}]$ . $S = U_{1} + U_{2}$ ke saath, $E [S^{4}] = \frac{197}{90} \approx 2.18889$ . Phir $σ_{g}^{2} = 2.18889 - 1.36111 = 0.82778.$ $SE = \frac{0.82778}{5000} = 1.6556 \times 1 0^{- 4} \approx 0.01287.$ Baked-in lesson: agar tumhara variance negative aaye, toh koi moment galat tha — variance hamesha $E [g^{2}] - (E g)^{2} \geq 0$ hota hai.

Level 5 — Mastery

L5.1 — Jab LLN fail karta hai

Tum ek Cauchy-like variable ka mean estimate karne ki koshish karte ho jiska density itna heavy tails wala hai ki $E ∣ X ∣ = \infty$ . WLLN ke proof structure ka use karke exactly explain karo kaunsa step break hota hai aur agar tum $\overset{ˉ}{X}_{n}$ vs $n$ plot karo toh kya observe karte ho.

Recall Solution

Kaunsa step break hota hai: WLLN derivation ko finite variance $σ^{2}$ chahiye (Step 2) — aur kamzor strong law ko bhi $E ∣ X ∣ < \infty$ chahiye. Cauchy ke liye, $E [X]$ define karne wala integral diverge karta hai, isliye koi $μ$ nahi hai jis par converge kiya ja sake. Step 3 (Chebyshev) vacuous hai kyunki $Var (\overset{ˉ}{X}_{n}) = \infty/ n = \infty$ . Kya observe karte ho: running average $\overset{ˉ}{X}_{n}$ kabhi settle nahi hota — woh occasional gigantic samples se hamesha knock around hota rehta hai. Isse plot karo aur tum dekhoge wild jumps hamesha rehte hain, flattening curve nahi. Monte Carlo par trust karne se pehle integrand ke tails hamesha check karo.

L5.2 — Variance reduction budget

Do estimators same $θ$ target karte hain. Estimator A ka $σ_{A}^{2} = 4$ hai; ek smarter importance-sampling estimator B ka $σ_{B}^{2} = 0.25$ hai. A ko kitne samples $n_{A}$ chahiye taaki woh woh error match kar sake jo B $n_{B} = 1000$ se achieve karta hai?

Recall Solution

Standard errors match karo: $\frac{σ _{A}^{2}}{n _{A}} = \frac{σ _{B}^{2}}{n _{B}}$ . $n_{A} = n_{B} \cdot \frac{σ _{A}^{2}}{σ _{B}^{2}} = 1000 \times \frac{4}{0.25} = 1000 \times 16 = 16000.$ Kyun yeh variance reduction ka poora point hai: variance $16 \times$ cut karna 16 guna kam samples ke barabar hai same accuracy ke liye. $σ_{g}^{2}$ mein cleverness brute force in $n$ ko beat karti hai — kyunki dono error mein ratio $σ_{g}^{2} / n$ ke roop mein enter karte hain.

L5.3 — Confidence interval, full pipeline

$n = 400$ samples ka ek run $g$ ka sample mean $\hat{θ} = 2.00$ aur sample standard deviation $\overset{σ}{^}_{g} = 1.5$ deta hai. 95% confidence interval report karo (use karo $z = 1.96$ , CLT).

Recall Solution

Step 1 — SE: $\overset{σ}{^}_{g} / n = 1.5/ 400 = 1.5/20 = 0.075$ . Step 2 — half-width: $z \cdot SE = 1.96 \times 0.075 = 0.147$ . Step 3 — interval: $θ \in 2.00 \pm 0.147 = [1.853, 2.147] .$ KYU CLT: yeh batata hai ki large $n$ ke liye $\hat{θ}$ approximately Normal hai, aur $\pm 1.96$ standard errors Normal ka middle 95% capture karta hai. Iss interval ke bina ek point estimate randomness chhupa deti hai.

Recall Rapid self-check (cover the answers)

Standard error formula? ::: $σ_{g} / n$ . Error ko aadha karne ke liye $n$ ko ... se multiply karo? ::: 4. Kaun si property $Var (\overset{ˉ}{X}_{n}) = σ^{2} / n$ banati hai? ::: samples ki independence. LLN hold karne ke liye integrand ko kaun si condition satisfy karni chahiye? ::: finite mean $E ∣ X ∣ < \infty$ (clean rate ke liye finite variance). Variance $16 \times$ cut karne se equal accuracy ke liye kitne samples bachte hain? ::: $16 \times$ .