3 ms·

Somewhat OT, but: I've always felt there's some sort of connection between Metropolis and the alias method [1] Can someone more knowledgeable perhaps shed some

Somewhat OT, but: I've always felt there's some sort of connection between Metropolis and the alias method [1] Can someone more knowledgeable perhaps shed some light on this idea? [1] https://en.wikipedia.org/wiki/Alias_method https://en.wikipedia.org/wiki/Alias_method

dahart 7y ago
I don't pretend to be all that knowledgeable, but I've implemented & used both methods... There is a similarity in the sense that both are trying to generate samples with a density that is proportional to a given distribution. Metropolis generally in the continuous case, and the alias method is for discrete distribution sampling. Apart from that, I don't see a very strong connection between the techniques. Metropolis is for random walks, while the alias method is for direct sampling. The very brilliantly clever observation of the alias method is that when you have N items in your discrete distribution, you can sample from a uniformly discretized set of buckets that have a width that is the average size of your discrete weights, and then split up and distribute any of the weights that are of larger than average size into other buckets that have less than average size. It possible to always have no more than 2 items in a bucket, so it allows storing the data structure in an array of size 2N, and allows O(1) sampling from your discrete weights. Metropolis is more about taking a walk through a probability field, so each sample is in some sense a result of the history of the previous samples, and it spends more time in local areas where probabilities are high. With Metropolis, you have to make sure you don't get stuck in local maxima, that your sampler can break through low-probability regions in your distribution. With the alias method, you get independent samples, there's no risk of missing some of the space. Both methods can accept quasi-random or low-discrepancy inputs, but both of them will have limited benefit, unlike inverse transform sampling.

dahart 7y ago

I don't pretend to be all that knowledgeable, but I've implemented & used both methods... There is a similarity in the sense that both are trying to generate samples with a density that is proportional to a given distribution. Metropolis generally in the continuous case, and the alias method is for discrete distribution sampling. Apart from that, I don't see a very strong connection between the techniques. Metropolis is for random walks, while the alias method is for direct sampling. The very brilliantly clever observation of the alias method is that when you have N items in your discrete distribution, you can sample from a uniformly discretized set of buckets that have a width that is the average size of your discrete weights, and then split up and distribute any of the weights that are of larger than average size into other buckets that have less than average size. It possible to always have no more than 2 items in a bucket, so it allows storing the data structure in an array of size 2N, and allows O(1) sampling from your discrete weights. Metropolis is more about taking a walk through a probability field, so each sample is in some sense a result of the history of the previous samples, and it spends more time in local areas where probabilities are high. With Metropolis, you have to make sure you don't get stuck in local maxima, that your sampler can break through low-probability regions in your distribution. With the alias method, you get independent samples, there's no risk of missing some of the space. Both methods can accept quasi-random or low-discrepancy inputs, but both of them will have limited benefit, unlike inverse transform sampling.