Monte Carlo Module

The monte_carlo module contains Monte Carlo sampling and resampling functions.

monte_carlo

Copyright 2015 Roger R Labbe Jr.

bayesian_filters library. https://github.com/GeorgePearse/bayesian_filters

Documentation at: https://georgepearse.github.io/bayesian_filters

Supporting book at: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python

This is licensed under an MIT license. See the readme.MD file for more information.

__all__ = ['resampling'] module-attribute

multinomial_resample(weights)

This is the naive form of roulette sampling where we compute the cumulative sum of the weights and then use binary search to select the resampled point based on a uniformly distributed random number. Run time is O(n log n). You do not want to use this algorithm in practice; for some reason it is popular in blogs and online courses so I included it for reference.

residual_resample(weights)

Performs the residual resampling algorithm used by particle filters.

Based on observation that we don't need to use random numbers to select most of the weights. Take int(N*w^i) samples of each particle i, and then resample any remaining using a standard resampling algorithm [1]

Parameters:

Name	Type	Description	Default
weights	list-like of float	list of weights as floats	required

Returns:

Name	Type	Description
indexes	ndarray of ints	array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.

References

.. [1] J. S. Liu and R. Chen. Sequential Monte Carlo methods for dynamic systems. Journal of the American Statistical Association, 93(443):1032–1044, 1998.

stratified_resample(weights)

Performs the stratified resampling algorithm used by particle filters.

This algorithms aims to make selections relatively uniformly across the particles. It divides the cumulative sum of the weights into N equal divisions, and then selects one particle randomly from each division. This guarantees that each sample is between 0 and 2/N apart.

Parameters:

Name	Type	Description	Default
weights	list-like of float	list of weights as floats	required

Returns:

Name	Type	Description
indexes	ndarray of ints	array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.

systematic_resample(weights)

Performs the systemic resampling algorithm used by particle filters.

This algorithm separates the sample space into N divisions. A single random offset is used to to choose where to sample from for all divisions. This guarantees that every sample is exactly 1/N apart.

Parameters:

Name	Type	Description	Default
weights	list-like of float	list of weights as floats	required

Returns:

Name	Type	Description
indexes	ndarray of ints	array of indexes into the weights defining the resample. i.e. the index of the zeroth resample is indexes[0], etc.