Tuan Anh Le

Resampling Algorithms

15 September 2017

Given a set of normalized weights , the goal of a resampling algorithm is to return a set of indices such that for : \begin{align} \E\left[\frac{1}{N} \sum_{n = 1}^N \mathbb 1(i_n = k)\right] = w_k. \end{align}

We consider the multinomial, stratified, and systematic resampling algorithms which can be implemented in Python as follows:

import numpy as np

def resample(weights, algorithm):
    num_weights = len(weights)
    if algorithm == 'multinomial':
        uniforms = np.random.rand(num_weights)
    elif algorithm == 'stratified':
        uniforms = np.random.rand(num_weights) / num_weights + np.arange(num_weights) / num_weights
    elif algorithm == 'systematic':
        uniforms = np.random.rand() / num_weights + np.arange(num_weights) / num_weights
        raise NotImplementedError()

    return np.digitize(uniforms, bins=np.cumsum(weights))

This function returns a set of indices for which the above condition holds. However, the variance can be different. In the figure below, we plot empirical mean and standard deviation of using samples where axis iterates over :

Jupyter notebook for generating this figure.