the sense discussed in (Doucet et al., 2000b), is chosen as qι = p( xι | xι - ιι δι ) with the associating wt = p(ot|Xt-1, Ot-1).

The general SIS approximation scheme is thus as follows. At time t - 1, we maintain N
sample sequences { x { } and the N corresponding weight values { w(i) } . When the current observation o t arrives, each sequence x [ 1 is lengthened by a new value x [ i ] sampled from the distribution q ( x t | x t | x t ). The weight value for x ( i ) is then updated using (2). Once the new samples and the new weights are obtained, the expectation of any functional f can be estimated using (1). This procedure can be furthered enhanced with a re-sampling step and a Markov-chain sampling step (see Doucet et al. (2000b), Doucet, de Freitas, Murphy, and Russell (2000a)). We do not describe these important improvements of the SIS here. 3

## 2.4 Rao-Blackwellisation

Rao-Blawellisation is a general technique for improving the accuracy of sampling methods by analytically marginalising some variables and only sampling the remainder (Casella &
Robert, 1996). In its simplest form, consider the problem of estimating the expectation E f(x), where x is a joint product of two variables r,z. Using direct Monte-Carlo sampling, we obtain the estimator: f = f E f f(r(f), z(f). Alternatively, a Rao-Blackwellised estimator can be derived by sampling only the variable r, with the other variable z being integrated out analytically:

$$\mathrm{\boldmath~E~}f(r,z)=\mathrm{\boldmath~E~}h(r)\approx\dot{f}_{R B}=\frac{1}{N}\sum_{1}^{N}h(r^{(i)})$$

where h(r) = E z [f(r, z)|r]. For our convenience, r will be referred to as the Rao-Blackwellising variable.

The Rao-Blackwellised estimator frb is generally more accurate than f for the same number of samples N . This is a direct consequence of the Rao-Blackwell theorem which gives the relationship between unconditional and conditional variance:

$$\operatorname{VAR}X=\operatorname{VAR}[\operatorname{E}[X|Y]]+\operatorname{E}[\operatorname{VAR}[X|Y]]$$

When applying to the problem of estimating E f(r,z), we have:

$$\operatorname{VAR}f(r,z)=\operatorname{VAR}[\operatorname{E}[f(r,z)|r]]+\operatorname{E}[\operatorname{VAR}[f(r,z)|r]]$$

and thus VAR f(r,z) ≥ VAR[E[f(r,z)[r]] = VAR h(r). This suggests that for direct Monte¬
Carlo sampling, the error of RB-sampling (sample only r and marginalise z ) is always smaller than the error of sampling both r and z for the same number of samples, except in the degenerated case. For Bayesian Importance Sampling, using the variance convergence result from (Geweke, 1989), one can also easily prove that as the number of samples tend to infinity, the RB-BIS would generally do better than BIS for the same number of samples.