I have a probability distribution (PDF) defined by a Fourier series.. actually it's a purely cosine series over a known range. The PDF quite smooth, so most of the power is in the low 5 or so frequencies. The function is (like a PDF must be) always positive. It's well defined everywhere.
I only need a single sample, so tabulation or function fitting is likely too expensive; that'd pay off if I needed thousands of samples, but I need just one, then I'll throw the PDF away and generate a new one. (This is all part of a Markov chain walk, and the transitions are defined by Fourier coefficients).
So, I want to efficiently generate one sample from this PDF. What's the best strategy?
One method that works but is slow is to use a von Neuman rejection method. The PDF is bounded from above by the sum of the absolute values of all the sine coefficients. I can generate a random point x in U(0,1), evaluate the series for that x, then accept the point with a probability based on the ratio of f(x) and the upper bound. This will work but it's super-slow!
The second strategy would be to generate a U(0,1) sample and feed it through the inverse CDF, but that involves solving a nonlinear equation for x, which is iterative and even slower.
Are there any other strategies I can experiment with?