Let $f(x)$ be a density function on $\mathbb R$; I want to find numerically the $\alpha$ quantile of the associated distribution, i.e. I want to find $c$ such that

$$\int_{-\infty}^c f(x)dx = \alpha$$

$f(x)$ is reasonably fast to compute, but if I apply the usual root-finding algorithms (say, newton-raphson) I would need to compute the integral of $f(x)$ at every iteration, which is impractical.

Do you have any references as of how solve the problem numerically? Is there a root-finding algorithm that doesn't need the evaluation of the function, but only of its derivative (in this case $f(x)$) ?

  • $\begingroup$ You should be able to compute the integral to machine precision in 30 function evaluations using exp-sinh quadrature, then use bisection->Newton to find the root. I don't see why this is impractical. $\endgroup$ – user14717 Apr 5 '17 at 0:56
  • $\begingroup$ An additional idea is to use exp-sinh to evaluate $F(0)$, then $F(c)$ can be evaluated via tanh-sinh quadrature in ~10 function evaluations. Start creating a lookup table for $F(c_{i})$ as the iterations proceed. If need be, build a barycentric rational approximation to $F$. $\endgroup$ – user14717 Apr 5 '17 at 1:08
  • $\begingroup$ @user14717 Hi! What is a barycentirc rational approximation? Anyhow, if I use the tanh-sinh quadrature to compute $F(c)$, I still need to call the density ~11 times per iteration. It could work though. $\endgroup$ – Ant Apr 5 '17 at 7:24
  • $\begingroup$ pdfs.semanticscholar.org/c6d7/… $\endgroup$ – user14717 Apr 5 '17 at 15:19
  • $\begingroup$ An implementation of barycentric rational interpolation: github.com/boostorg/math/pull/58 $\endgroup$ – user14717 Apr 5 '17 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.