flâneur

Efficient Weighted Sampling // A Random Walk Through Geek-Space

sebastiansylvan.com · 1,260 words · saved by 1 readers

Here’s a really simple and cheap way to do importance sampling that I came across a few months ago (while learning about particle filters, incicentally). It’s simple enough that I have no idea how I went so long without ever knowing about it! In case anyone else is in the same boat - let me walk you through it. Let’s say you have an array of N values, and an associated array of N weights and you want to randomly sample your input values such that the probability of each value being chosen is proportional to its weight. There are many ways of doing that, but I’d like to focus on a particularly efficient approach (it’s O(N) with a relatively small constant factor). Imagine laying out 8 input values in a row like this, where their weights correspond to their width in the diagram. Now, to select 8 weighted samples we could line up another row of evenly spaced “cells” below the first one, corresponding to our chosen samples (modulo my poor mspaint skills). To pick our samples, we could just

Efficient Weighted Sampling // A Random Walk Through Geek-Space A Random Walk Through Geek-Space Brain dumps and other ramblings from Sebastian Sylvan Efficient Weighted Sampling 28 / Jan 2017 Here's a really simple and cheap way to do importance sampling that I came across a few months ago (while learning about particle filters , incicentally). It's simple enough that I have no idea how I went so long without ever knowing about it! In case anyone else is in the same boat - let me walk you through it. Let's say you have an array of N values, and an associated array of N weights and you want to

saved by

related reading