prbnmcn-dagger
Legend:
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.

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`
```module Make_float (P : Particle with type field = float) : S with type field = float and type particle = P.t```

`Make_float` instantiates `Make` over the field of floats.