week 10

Question 1

What is the primary goal of Monte Carlo integration in Bayesian inference?

Answer 1

To estimate posterior expectations of functions, E[h(θ)|x] = ∫ h(θ)π(θ|x)dθ, which are often analytically intractable, especially in high dimensions.

Question 2

Given n independent samples θ₁, ..., θn from the posterior π(θ|x), what is the Monte Carlo estimate h̄n of E[h(θ)|x]?

Answer 2

h̄n = (1/n) Σ<sub>i=1</sub><sup>n</sup> h(θi)

Question 3

According to the Weak Law of Large Numbers (WLLN), how does the Monte Carlo estimator h̄n behave as n → ∞?

Answer 3

h̄n converges in probability to E[h(θ)|x].

Question 4

According to the Strong Law of Large Numbers (SLLN), if Var[h(θ)|x] < ∞, how does the Monte Carlo estimator h̄n behave as n → ∞?

Answer 4

h̄n converges almost surely to E[h(θ)|x].

Question 5

How is the variance of the Monte Carlo estimator h̄n related to the variance of h(θ) under the posterior?

Answer 5

Var[h̄n|x] = (1/n) * Var[h(θ)|x]

Question 6

How can Var[h(θ)|x] be estimated from the posterior samples θ₁, ..., θn?

Answer 6

Using the sample variance: s²n ≈ (1/n) Σ<sub>i=1</sub><sup>n</sup> [h(θi) - h̄n]² (Note: sometimes the 1/(n-1) version is used for unbiasedness, but 1/n is asymptotically equivalent and used in the notes).

Question 7

What is the Monte Carlo error of the estimator h̄n?

Answer 7

It is the estimated standard deviation of h̄n: √(Var[h̄n(θ)|x]) = sn / √n.

Question 8

What does the Central Limit Theorem (CLT) state about the distribution of the Monte Carlo estimator h̄n for large n?

Answer 8

√n * (h̄n - E[h(θ)|x]) / sn converges in distribution to a standard Normal distribution, N(0,1).

Question 9

What is the typical rate of convergence for the Monte Carlo error? How does this compare to methods like Simpson’s rule?

Answer 9

The Monte Carlo error converges at a rate of 1/√n. This is slower than 1D numerical methods (like Simpson’s 1/n⁴ rate) but doesn’t degrade as badly with increasing dimension and requires fewer assumptions (only finite variance).

Question 10

Describe the Inversion Method for generating a sample X from a distribution with CDF F.

Answer 10

1. Generate U ~ U[0,1]. \n2. Compute X = F⁻¹(U), where F⁻¹ is the inverse CDF (quantile function).

Question 11

What is the main requirement for using the Inversion Method?

Answer 11

The inverse CDF F⁻¹ must be known and computable, ideally in closed form.

Question 12

Is the Inversion Method practical for high-dimensional distributions?

Answer 12

Generally no, due to the difficulty of deriving and inverting high-dimensional CDFs.

Question 13

What are the three main requirements for the Accept-Reject Method to sample from a target density f using a proposal density g?

Answer 13

1. The support of f must be contained within the support of g (supp(f) ⊂ supp(g)).\n2. We must be able to generate samples from g.\n3. There must exist a constant M ≥ 1 such that f(x) ≤ M * g(x) for all x.

Question 14

Describe the steps of the standard Accept-Reject Algorithm (Algorithm 2).

Answer 14

1. Generate a candidate Y ~ g.\n2. Generate U ~ U[0,1].\n3. If U ≤ f(Y) / (M * g(Y)), accept X = Y.\n4. Otherwise, reject Y and return to Step 1.

Question 15

Describe the steps of the Alternative Accept-Reject Algorithm (Algorithm 3).

Answer 15

1. Generate a candidate Y ~ g.\n2. Generate U ~ U[0, M * g(Y)].\n3. If U ≤ f(Y), accept X = Y.\n4. Otherwise, reject Y and return to Step 1.

Question 16

What is the probability of accepting a candidate Y in the Accept-Reject method?

Answer 16

The acceptance probability is 1/M.

Question 17

What determines the efficiency of the Accept-Reject method? How can efficiency be improved?

Answer 17

Efficiency is determined by the acceptance probability 1/M. Efficiency increases as M gets closer to 1. This is achieved by choosing a proposal density g that closely matches the shape of the target f, minimizing the required envelope constant M.

Question 18

What is the optimal value M* for the constant M for a given proposal g?

Answer 18

M* = sup<sub>x ∈ supp(f)</sub> [f(x) / g(x)].

Question 19

Can Accept-Reject sampling be used if f and g are known only up to their normalizing constants (i.e., using kernels f̃ and g̃)?

Answer 19

Yes. Find M̃ such that f̃(x) ≤ M̃ * g̃(x). Run the algorithm using f̃, g̃, and M̃. The acceptance probability becomes a / (b * M̃), where a and b are the unknown normalizing constants of f and g.

Question 20

Why does the efficiency of Accept-Reject sampling often deteriorate in high dimensions?

Answer 20

It becomes increasingly difficult to find a proposal g that matches f well everywhere, leading to a large required constant M and thus a very low acceptance probability (the ‘curse of dimensionality’).

Question 21

What is the core idea of Importance Sampling for estimating ∫ h(x)f(x)dx?

Answer 21

Introduce an ‘importance density’ g(x) from which we can sample, and rewrite the integral as ∫ [h(x) * f(x) / g(x)] g(x) dx. This expectation is then estimated using samples from g.

Question 22

Given n i.i.d. samples X₁, ..., Xn from the importance density g, what is the basic Importance Sampling estimator for ∫ h(x)f(x)dx?

Answer 22

(1/n) * Σ<sub>i=1</sub><sup>n</sup> [h(X_i) * w(X_i)], where w(X_i) = f(X_i) / g(X_i) are the importance weights.

Question 23

What is the key requirement on the support of the importance density g relative to f and h?

Answer 23

The support of g must cover all points x where |h(x)|f(x) > 0 to avoid division by zero or infinite variance.

Question 24

What is a guideline for choosing a good importance density g to achieve low variance?

Answer 24

Choose g such that the product |h(x)|f(x)/g(x) is as constant as possible. Often, this means g should resemble |h(x)|f(x) and have heavier tails than f.

Question 25

What is **Self-Normalized Importance Sampling** used for?

Answer 25

When the importance weights `w(x) = f(x)/g(x)` can only be calculated up to an unknown normalizing constant (e.g., `f` and/or `g` are unnormalized densities).

Question 26

What is the formula for the Self-Normalized Importance Sampling estimator?

Answer 26

`[Σ<sub>i=1</sub><sup>n</sup> h(X_i) * w(X_i)] / [Σ<sub>i=1</sub><sup>n</sup> w(X_i)]`, where `X_i ~ g` and `w(X_i)` are the (possibly unnormalized) importance weights.

Question 27

What is a key difference between the basic IS estimator and the self-normalized IS estimator regarding bias?

Answer 27

The basic IS estimator is unbiased. The self-normalized IS estimator is biased for finite *n*, but it is asymptotically unbiased (consistent).

Question 28

What stricter condition on supports is required for self-normalized importance sampling compared to basic importance sampling?

Answer 28

`supp(f) ⊂ supp(g)` is required for self-normalized IS.

Question 29

What is the goal of **Sampling Importance Resampling (SIR)**?

Answer 29

To convert weighted samples obtained from importance sampling into an approximately unweighted sample from the target distribution `f`, primarily to reduce variance caused by highly variable weights.

Question 30

Describe the three main steps of the **Sampling Importance Resampling (SIR)** algorithm.

Answer 30

1. **Sample:** Draw `X₁, ..., Xn ~ g` from the proposal distribution.\n2. **Weight:** Calculate importance weights `w(X_i) = f(X_i) / g(X_i)` and normalize them: `w̃(X_i) = w(X_i) / Σ<sub>j=1</sub><sup>n</sup> w(X_j)`.\n3. **Resample:** Draw `Y₁, ..., Yn` by sampling *with replacement* from the set `{X₁, ..., Xn}` according to the normalized weights `w̃(X_i)`.

Question 31

What is the potential problem with SIR, especially when the importance weights are very uneven?

Answer 31

**Sample depletion** (or impoverishment): The resampled set `{Y₁, ..., Yn}` may contain many duplicates of only a few original samples `X_i` that had very high weights, leading to a loss of diversity and potentially poor estimates.