# Sampling scheme based on newton's method - what is it called?

I recently thought of a crazy sampling scheme, which has almost certainly been thought of by someone else before. I'm interested to find out what it is called, and if it is ever useful.

The idea is as follows: to sample from a smooth 1D probability distribution on interval $$[a,b]$$ with density $$p$$ (and derivative $$p'$$), we pick a uniform random number $$y \in [0,1]$$, then numerically solve for the place where the cumulative distribution function equals $$y$$, using Newton's method and numerical integration.

Ie., given $$f(x) := y - CDF(x) = y - \int_a^x p(s)ds,$$ with derivative $$f'(x) = -p(x) - \int_a^x p'(s) ds,$$ we solve $$f(x)=0$$ by iterating, $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)},$$ and simple halving backtracking to ensure convergence if the initial guess is not in the radius of convergence. The integrals are approximated to the desired accuracy with quadrature that is good for integrating smooth functions (eg., Gaussian quadrature).

What is this called? Are there ever situations where this could be better than other standard sampling methods?

• When I first saw this, I thought it was based on Newton-method derived fractals. I was thinking "fractal sampling sounds cool". Then I saw it was inverse CDF, and I was like "darnit". Commented Feb 19, 2016 at 16:41
• Thank you for your question on MSE.meta. Just to let you know that you are dealing with a notorious ass**** user on that site. I myself was a victim of that ridiculous user before. This is a good tool to keep evidence in case it is needed: archive.ph
– user361106
Commented Jun 19, 2022 at 21:12