Library

Module

Module type

Parameter

Class

Class type

Resampling functions.

Resampling is used to improve the statistical quality of a population of weighted particles.

Informally, resampling consists in sampling `N`

new particles (each with weight `1/N`

) from a given population such that the resulting population is distributed identically to the target one (ie is unbiased).

An straightforward to proceed would be to sample from a multinomial distribution with parameters `N`

and the normalized weights of the given population. Other schemes are used in practice.

We consider the following schemes:

- systematic resampling
- stratified resampling

In the following, we consider an (ordered, even if arbitrarily) family of particles `(x_k, w_k)`

for `k=1...K`

.

The outcome of resampling is a map from each particle `x_k`

to a replication count `r_k`

.

### Systematic resampling

Let `U`

be sampled uniformly in `[0,1/N]`

. Consider the partition of the `[0,1)`

interval in `N`

sub-intervals given by the points `U_i = U + (i-1)/N`

for `i=1...N-1`

.

Associate to each particle `x_k`

its cumulative weight `W_k = w_1 + ... + w_k`

and let us set `W_0 = 0`

.

We set `r_k`

to be the cardinal of the set of `U_i`

included in `[W_{k-1}, W_k]`

.

### Stratified resampling

For each `i`

in `1...N`

, let `U_i`

be sampled uniformly in `[0, 1/N]`

and consider the family of intervals `(i-1)/N, (i-1)/N + U_i`

for `i=1...N`

. We associate to each `i`

the particle `x_k`

with the lowest `k`

such that `W_k`

verifies `(i-1)/N + U_i < W_k`

.

The replication count `r_k`

is the number of times `x_k`

was selected in this process.

### References

A Tutorial on Particle Filtering and Smoothing: Fifteen years lated (Doucet & Johansen)

`module type Particle = sig ... end`

A `Particle`

is any abstract type from which a `weight`

can be computed.

`module type S = sig ... end`

The module type exposing resampling functions.

```
module Make
(F : Intf.Field)
(P : Particle with type field = F.t)
(Sampler : sig ... end) :
S with type field = F.t and type particle = P.t
```

The `Make`

functor is generic over a field `F`

and a uniform sampler. Genericity over the underlying field is especially useful for testing, using arbitrary-precision rationals.

`module Float_field : Intf.Field with type t = float`