6 ms·
The general version of this is called inverse transform sampling [0], which uses the fact that for the cdf F of any random variable X the random variable Y = F(
by pash 2y ago
The general version of this is called inverse transform sampling [0], which uses the fact that for the cdf F of any random variable X the random variable Y = F(X) has a standard uniform distribution [1]. Since every cdf increases monotonically on the unit interval, every cdf is invertible [2]. So apply the inverse cdf to both sides of the previous equation and you get F^-1(Y) = X is distributed like X.
Sampling from a standard uniform distribution and then using the inverse transform is the commonest way of generating random numbers from an arbitrary distribution.
0. https://en.m.wikipedia.org/wiki/Inverse_transform_sampling https://en.m.wikipedia.org/wiki/Inverse_transform_sampling
1. https://en.m.wikipedia.org/wiki/Probability_integral_transform https://en.m.wikipedia.org/wiki/Probability_integral_transfo...
2. Not every cdf is one-to-one, however, so you may need a generalized inverse.
- tmoertel 2y agoFor the particular case of the exponential distribution we can go further. By taking advantage of the theory of Poisson processes, we can take samples using a parallel algorithm. It even has a surprisingly succinct SQL translation: SELECT * FROM Population WHERE weight > 0 ORDER BY -LN(1.0 - RANDOM()) / weight LIMIT 100 -- Sample size. Notice our exponentially distributed random variable on prominent display in the ORDER BY clause. If you're curious, I explore this algorithm and the theory behind it in https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
- lkuty 2y agoQuite off-topic, but do you know when you'll write the article about CPS, if ever?
- tmoertel 2y agoOops. I had quite forgotten that I need to write about that. I said I would over a decade ago, so that's a long time for you to wait. Sorry about that. I mainly write for myself, so I need the time and the motivation. Until recently, my job at G took up my time and also provided an internal community where I could scratch the writing itch, which reduced the motivation for public writing on my blog. But now that I'm semi-retired, I'll try to write more frequently. Thanks for the accountability!
- evanb 2y agoInverse transform sampling is a special case of normalizing flow where we don't need to learn anythin.g https://en.wikipedia.org/wiki/Flow-based_generative_model https://en.wikipedia.org/wiki/Flow-based_generative_model