Clément Canonne @ccanonne.github.io · Mar 16 Random fact of the day: imagine you have weights a₁,...,aₙ≥0 and want to sample according to these weights. What's an efficient way to do so? You may say Huffman coding, etc. Yes, but... there's a way that's more fun: the Gumbel trick!
35 likes 2 replies
Replies
Is this really efficient? Computing a log is very costly (100 to 200 times a product or a sum of I remember correctly). If you use a high quality random numbers generator, n calls will also cost a lot. This is really elegant though.
Why? Well, it is "well-known" (as usual, these words mean nothing, except that people who already know it believe they don't have to tell you more about it (†).) Alternatively, you can find a proof here: stats.stackexchange.com/a/359443/70569 (and in many other places, I know. Cf. (†) above)