Text: Computational Statistics by Givens and Hoeting

Section 6.3.1: Sampling Importance Resampling Algorithm

The authors provide a proof that random variable $\bf X$ drawn with the SIR algorithm has a distribution that converges to $f$ (the target distribution) as $m \rightarrow \infty$.

Let ${\bf{X}} = (X_1, \ldots, X_p)$ be a random vector from $f$ and let $g$ be an envelope for $f$.

Define the standardize importance weights as $$w({\bf y}_i) = \frac{w^*({\bf y}_i)}{\sum_{i = 1}^m w^*({\bf y}_i)}$$

The algorithm is below: enter image description here

I am able to follow the proof after equation 6.13. I cannot work my mind around how to obtain the equality there. Any hints would be appreciated.

Also, I'm not sure of any other proper tags to use, so please add them as you see fit.


The $X_i$ are drawn iid with support $\{y_1,\dots,y_m\}$ and with probabilities $$ P(X = y | Y_1,\dots,Y_n) := w(y) = \frac{w^*(y)}{\sum_{i=1}^m w^*(y_i)} $$ for $w^*(y) = \frac{f(y)}{g(y)} > 0$.

Then $P(X \in A | Y_1,\dots,Y_m) = E(1_{X\in A} | Y_1, \dots, Y_m)$ so $$ P(X \in A | Y_1,\dots,Y_m) = \sum_{x \in \{y_1,\dots,y_m\}} 1_{x \in A} P(X = x | Y_1,\dots,Y_n) $$ $$ = \sum_{i=1}^m 1_{y_i \in A} w(y_i) = \sum_{i=1}^m 1_{y_i \in A} \frac{w^*(y)}{\sum_{i=1}^m w^*(y_i)} $$

$$ = \frac{\sum_{i=1}^m 1_{y_i \in A} w^*(y_i) }{\sum_{i=1}^m w^*(y_i)} $$ as desired.

  • 1
    $\begingroup$ Would it be correct to think of the mass function for $X$ as a conditional mass function? $P(X = y) := P(X = y | Y_1, \ldots, Y_m)$ $\endgroup$ Jun 29 '18 at 16:50
  • 1
    $\begingroup$ @SOULed_Outt yeah good point, it is conditioned on $Y_1,\dots,Y_n$. I just updated to reflect this $\endgroup$
    – jld
    Jun 29 '18 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.