2

This is a question I'm trying to figure out how to solve because my calculator does not allow me to evaluate improper integrals. I am trying to find the z that produces a small enough p to be negligible. In general I think I will need about 5 digits of accuracy maximum but I would also be interested in the general solution for some natural n. The problem boils down to solving this inequality:

Find the least value of $a$ for which: $$\int_a^\infty \frac{\exp(-x^2/2)}{\sqrt{2\pi}} < 10^{-n}$$

Any insights on how I might go about this? This function doesn't even have an elementary antiderivative so this looks like a pretty tricky problem.

O.S.
  • 592
  • 2
    Turn to an ordinary integral using $\displaystyle\int_a^\infty=\displaystyle\int_0^\infty-\displaystyle\int_0^a$. –  Oct 21 '21 at 18:12
  • so then it turns into $1/2 - \int_0^a f(x)$ which actually I can evaluate directly. but for the sake of actually finding the value of a which is less than 10^(-n), how do you proceed? – O.S. Oct 21 '21 at 18:17
  • Use your calculator. Dichotomic search or Newton's iterations... –  Oct 21 '21 at 18:18
  • You can also use the complementary error function which is available in many numerical software packages (see e.g. scipy.special.erfc in scipy). See also numerical approximations in the linked wikipedia article. Finally, it is interesting to note that the task is doable for distributions other than normal using the concentration inequalities. Chernoff's bound is particularly useful since it bounds the tails by an expression exponential in the distance from the mean. – Adam Zalcman Oct 21 '21 at 18:22
  • @AdamZalcman Not really allowed to use a computer though, otherwise this would be a non issue. – O.S. Oct 21 '21 at 18:26
  • @AdamZalcman: preferably the inverse error function. –  Oct 21 '21 at 19:09

1 Answers1

2

Admitting that you know the error function, you are looking for $a$ such that $$\frac{1}{2}-\frac{1}{2} \text{erf}\left(\frac{a}{\sqrt{2}}\right) < 10^{-n}$$that is to say $$\text{erf}\left(\frac{a}{\sqrt{2}}\right)> 1-2\times 10^{-n}$$

When $a$ is large $$\text{erf}\left(\frac{a}{\sqrt{2}}\right)=1-e^{-\frac{a^2}{2}} \left(\frac{\sqrt{\frac{2}{\pi }}}{a}+O\left(\frac{1}{a^3}\right)\right)$$ and then we search for $a$ such that $$e^{-\frac{a^2}{2}} < \sqrt{2\pi}\, 10^{-n}\, a$$ The solution of the equation is given in terms of Lambert function $$a=\sqrt{W\left(\frac{10^{2n}}{2\pi}\right)}$$

Some results $$\left( \begin{array}{ccc} n & \text{estimate} & \text{solution} \\ 1 & 1.43165 & 1.28155 \\ 2 & 2.37533 & 2.32635 \\ 3 & 3.11528 & 3.09023 \\ 4 & 3.73464 & 3.71902 \\ 5 & 4.27575 & 4.26489 \\ 6 & 4.76151 & 4.75342 \\ 7 & 5.20565 & 5.19934 \\ 8 & 5.61710 & 5.61200 \\ 9 & 6.00204 & 5.99781 \\ 10 & 6.36492 & 6.36134 \\ 11 & 6.70910 & 6.70602 \\ 12 & 7.03717 & 7.03449 \\ 13 & 7.35116 & 7.34882 \\ 14 & 7.65274 & 7.65056 \\ 15 & 7.94324 & 7.94324 \end{array} \right)$$

Playing with the inverse error function, we could also have, as an approximation,

$$a=\sqrt{\log \left(\frac{2}{\pi t^2}\right)-\log \left(\log \left(\frac{2}{\pi t^2}\right)\right)}\quad \text{where} \qquad t=2\times 10^{-n}$$ which looks to be slightly better.

$$\left( \begin{array}{ccc} n & \text{estimate} & \text{solution} \\ 1 & 1.32266 & 1.28155 \\ 2 & 2.31834 & 2.32635 \\ 3 & 3.08133 & 3.09023 \\ 4 & 3.71139 & 3.71902 \\ 5 & 4.25847 & 4.26489 \\ 6 & 4.74795 & 4.75342 \\ 7 & 5.19461 & 5.19934 \\ 8 & 5.60785 & 5.61200 \\ 9 & 5.99413 & 5.99781 \\ 10 & 6.35805 & 6.36134 \\ 11 & 6.70305 & 6.70602 \\ 12 & 7.03178 & 7.03449 \\ 13 & 7.34632 & 7.34882 \\ 14 & 7.64835 & 7.65056 \\ 15 & 7.93923 & 7.94324 \end{array} \right)$$

Now, if you need better, I think that the only solution would be given by a couple of iterations of Newton method.

Claude Leibovici
  • 260,315