Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 40 / 4

Assume the draws are independent from $g$, that the target-weighted integrand is covered by its support, and that $\int |\theta (x)|f(x)dx<\infty$. Define the importance weight $w(x)=f(x)/g(x)$. The change-of-density identity isTherefore importance sampling uses the unbiased estimatorThe strong law of large numbers gives consistency. A finite second moment of the weighted integrand additionally gives finite variance and a usual independent-sample central limit theorem. A useful proposal places enough probability where $f|\theta |$ is large and avoids tiny proposal probability density function there; common support alone does not guarantee finite variance.

Write $f=f_0/C_f$ and $g=g_0/C_g$, where $f_0,g_0$ are known nonnegative kernels. If both constants are known, the ordinary weight is $(C_g/C_f)f_0/g_0$. If their ratio is unknown, use self-normalized importance sampling:Indeed, under the normalized proposal law,The strong law of large numbers makes their empirical ratio converge to $\mu$, provided the numerator is absolutely integrable and $0<C_f,C_g<\infty$. Multiplicative constants cancel, whether the unknown one belongs to the target, proposal, or both. Unlike the estimator in part (i), this ratio is generally biased at finite sample size. Exact sampling from $g$ is still presumed; knowing only an unnormalized proposal does not itself supply a sampler.

Set $H_i=f(x_i)\theta (x_i)/g(x_i)$. Independence gives $\mathrm{Var}(n^{-1}{\sum }_i{H}_i)=\mathrm{Var}(H_1)/n$, while part (i) gives ${\mathbb{E}}_g{H}_1=\mu$. Its second moment isConsequentlyThe variance is finite exactly when the displayed second-moment integral is finite, assuming $\mu$ exists. An infinite integral means infinite variance, not failure of the change-of-density identity.

For the standard Cauchy distribution tail, use the indicatorThen $\int \theta (x)f(x)dx$ is the desired probability, and the ordinary importance sampling estimator is $n^{-1}{\sum }_{i}f(x_i)1_{\{x_i\ge k\}}/g(x_i)$. The proposal must cover the nonzero integrand, namely the upper tail. A proposal restricted to $[0,k]$ cannot directly estimate this indicator integral; part (v) instead uses a complementary bounded-interval identity.

Take $k>0$, so the proposal is the uniform distribution on $[0,k]$, with probability density function $g(x)=1/k$. Symmetry of the standard Cauchy distribution givesThus the proposed expression is exactly the unbiased importance sampling estimator of this complementary integral:It has finite variance because $f$ is bounded on $[0,k]$. Explicitly,These follow from the antiderivatives of $(1+x^2{)}^{-1}$ and $(1+x^2{)}^{-2}$. The target itself is $\mu =1/2-\arctan (k)/\pi$. At $k=0$ it is exactly $1/2$ without simulation; for negative $k$ the printed uniform-interval construction must be changed.

Antithetic variates preserve each draw's marginal law but couple two estimates negatively. For an average of identically distributed $H,H^{\prime }$,Negative covariance improves on two independent evaluations at the same computational budget.

Here generate independent $U_1,\dots ,U_r\sim U(0,1)$ and pair $x_j=k{U}_j$ with $x_j^{\prime }=k(1-U_j)$. Both are uniform on $[0,k]$. The antithetic Cauchy-tail integration on a finite interval estimator isIt is unbiased. Put $h(u)=f(ku)$. This decreases, whereas $h(1-u)$ increases. For an independent copy $U^{\prime }$ of $U$, the covariance identity givesEach product is nonpositive, and for $k>0$ it is strictly negative off the diagonal. Thereforewhich is the variance using $2r$ independent evaluations in part (v). Thus the comparison accounts for the doubled number of probability density function evaluations in each pair.