Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 28K (Principles of Statistics)

Assume that $f(x)=0$ wherever $h(x)=0$ on the part of the space relevant to $g$. The importance sampling algorithm draws independent and identically distributed random variables $Y_1,\dots ,Y_m$ from $h$, forms the weightsand returnsA change of measure givesHence the estimator is unbiased whenever the expectation exists, and, if ${\mathbb{E}}_h|g(Y)w(Y)|<\infty$, the strong law of large numbers gives ${\hat{\mu }}_m\to {\mathbb{E}}_f[g(X)]$ almost surely.

Conditionally on $Y_1,\dots ,Y_m$, the cumulative distribution function of $X^{\ast }$ is the weighted empirical distributionFor fixed $t$, the strong law of large numbers gives, almost surely,whileThe ratio therefore converges almost surely to $F(t)$. This is precisely the claimed convergence in distribution of the self-normalized importance sampling resample.

Apply part (b) simultaneously at every rational $t$; the intersection of these probability-one events still has probability one. On that event, monotonicity and continuity extend the convergence from the rationals to every real $t$.

More directly, fix $\epsilon >0$. Since $F$ is a continuous cumulative distribution function, choose rational pointsso that the two tails have $F(t_0)<\epsilon$ and $1-F(t_k)<\epsilon$, while every increment $F(t_i)-F(t_{i-1})<\epsilon$. Part (b) makes $|F_m^{\ast }(t_i)-F(t_i)|<\epsilon$ at all these finitely many points for all sufficiently large $m$. If $t_{i-1}\le t\le t_i$, monotonicity givesso $|F_m^{\ast }(t)-F(t)|<2\epsilon$; the same estimate follows in the tails. This proves the uniform convergence of distribution functions to a continuous limit:almost surely.