5.8b Importance-sampling labs

Source: Lab ideas from Computational Physics (Landau, Páez, Bordeianu), §5.8. Rewritten as original drills. Continues 5.8 Importance sampling.

Rejection under $w(x)=2x$ and importance sampling with $w(x)=2(1-x)$ for $\int_0^1 e^{-x}\,dx$. Chapter LCG only.

Fixed LCG

r ← (1103515245 * r + 12345) % 2**31, uniform r / 2**31. Advance before each draw. Seed 1 unless noted.

Formula refresh

Warm up: pick the matching equation among lookalikes (same walk as the theory lesson).

Labs

Activity: Rejection accepted count

On $[0,1]$, take $w(x)=2x$ and box height $w_0=2$. For each of Nthrows trials: draw uniforms $U,V$ from the chapter LCG; set $x=U$, $W=w_0 V$; accept if $W\le w(x)$. Print the accepted count (integer).

Input: Nthrows.

With $N=1000$, seed $1$, the accepted count is fixed by the LCG stream.

Write-ups

0/4 solved

5.8b.W1

Using “ratio”, “weight”, and “average”, explain:

State the importance-sampling estimator ⟨f/w⟩ in words.

Minimum 3 words. Your answer must include: “ratio”, “weight”, “average”.

0 words/ 3 min

Meet the writing requirements, then you can open the model answer.

Explorers

# rejection_importance.py — original sketches
M = 2**31

def reject_w2x(Nthrows, seed=1):
    r, hits = seed, 0
    for _ in range(Nthrows):
        r = (1103515245 * r + 12345) % M
        x = r / M
        r = (1103515245 * r + 12345) % M
        if 2.0 * (r / M) <= 2.0 * x:
            hits += 1
    return hits

def importance_inv(N, seed=1):
    import math
    r, s = seed, 0.0
    for _ in range(N):
        r = (1103515245 * r + 12345) % M
        u = r / M
        x = 1.0 - math.sqrt(1.0 - u)
        s += math.exp(-x) / (2.0 * (1.0 - x))
    return s / N

Next: 5.9 Integration reference sketches.