(Accept-reject algorithm). We wish to sample the target density π (with respect to a dominating measure λ), which is known up to a multiplicative constant. Let q be a proposal density (assumed to be...

(Accept-reject algorithm). We wish to sample the target density π (with respect to a dominating measure λ), which is known up to a multiplicative constant. Let q be a proposal density (assumed to be easier to sample.) We assume that there exists a constant M <>∈ X. The Accept-Reject goes as follows: first, we generate Y ∼ g and, independently, we generate U ∼ U([0,1]). If Mq(Y)U ≤ π(Y), then we set X =Y. If the inequality is not satisfied, we then discard Y and U and start again.

(a) Show that X is distributed according to π.

(b) What is the distribution of the number of trials required per sample?

(c) What is the average number of samples needed for one simulation?

(d) Propose a method to estimate the normalizing constant of π.

(e) Compare with the Metropolis-Hastings algorithm with Independent proposal.