Pattern Recognition and Machine Learning

11.1. Basic Sampling Algorithms 535

value forkin that any value that is sufficiently large to guarantee a bound on the
desired distribution will lead to impractically small acceptance rates.
As in the case of rejection sampling, thesampling-importance-resampling(SIR)
approach also makes use of a sampling distributionq(z)but avoids having to de-
termine the constantk. There are two stages to the scheme. In the first stage,
Lsamplesz(1),...,z(L)are drawn fromq(z). Then in the second stage, weights
w 1 ,...,wLare constructed using (11.23). Finally, a second set ofLsamples is
drawn from the discrete distribution(z(1),...,z(L))with probabilities given by the
weights(w 1 ,...,wL).
The resultingLsamples are only approximately distributed according top(z),
but the distribution becomes correct in the limitL→∞. To see this, consider the
univariate case, and note that the cumulative distribution of the resampled values is
given by

p(z
a)=

∑

l:z(l)
a

wl

=

∑

lI(z

(l)
a) ̃p(z(l))/q(z(l))

∑

l ̃p(z

(l))/q(z(l)) (11.25)

whereI(.)is the indicator function (which equals 1 if its argument is true and 0
otherwise). Taking the limitL→∞, and assuming suitable regularity of the dis-
tributions, we can replace the sums by integrals weighted according to the original
sampling distributionq(z)

p(z
a)=

∫

I(z
a){ ̃p(z)/q(z)}q(z)dz

∫

{ ̃p(z)/q(z)}q(z)dz

=

∫

I(z
a) ̃p(z)dz

∫

̃p(z)dz

=

∫

I(z
a)p(z)dz (11.26)

which is the cumulative distribution function ofp(z). Again, we see that the normal-
ization ofp(z)is not required.
For a finite value ofL, and a given initial sample set, the resampled values will
only approximately be drawn from the desired distribution. As with rejection sam-
pling, the approximation improves as the sampling distributionq(z)gets closer to
the desired distributionp(z). Whenq(z)=p(z), the initial samples(z(1),...,z(L))
have the desired distribution, and the weightswn=1/Lso that the resampled values
also have the desired distribution.
If moments with respect to the distributionp(z)are required, then they can be