Make_predefined (F) (Sampler) produces implementations of stratified and systematic resampling over a field F and given a uniform sampler Sampler.
A detailed treatment of the following algorithms is given in A Tutorial on Particle Filtering and Smoothing: Fifteen years lated (Doucet & Johansen) section 3.4.
In the following, we consider a family of scored particles (x_k, w_k) for k=1 \ldots K with total score W=\sum_k w_k.
The outcome of the resampling strategies described below is a map from each particle x_k to a replication count r_k, such that \sum_k r_k = N. The resulting population will consist in r_1 copies of x_1, r_2 copies of x_2, etc, all with equal score \frac{1}{W}.
Let U be sampled uniformly in [0,\frac{1}{N}]. Consider the set of points U_i = U + \frac{i-1}{N} for i=1 \ldots N-1. Associate to each particle x_k its cumulative score W_k = w_1 + ... + w_k and us set W_0 = 0. We set r_k to be the cardinal of the set of W \cdot U_i included in [W_{k-1}, W_k).
For each i in 1 \ldots N, let U_i be sampled uniformly in [0, \frac{1}{N}]. Associate to each i the particle x_k with the lowest k such that \frac{i-1}{N} + U_i < W_k/W. The replication count r_k is the number of times x_k was selected in this process.
module F : Intf.Fieldmodule Sampler : sig ... end