For which standard deviation is the normal distribution density $0$ up to a given number of decimal places?

Question

Let $\sigma\in(0,1)$ (a typical choice being $\sigma=0.01$), $$\phi(x):=\frac1{\sqrt{2\pi\sigma^2}}e^{-\frac{x^2}{2\sigma^2}}\;\;\;\text{for }x\in\mathbb R$$ and $$\psi(x):=\sum_{k\in\mathbb Z}\phi(x+k)\;\;\;\text{for }x\in\mathbb R.$$

In a computer program, I need to compute $\psi(x)$ for $x\in(-1,1)$. Obviously, very few summands (somtimes even a single) in the definition of $\psi(x)$ may be sufficient to obtain a sensible approximation.

However, for theoretical purposes, I'd like to determine the interval to which $\sigma$ needs to belong to ensure that $\phi(x\pm k)$ is equal to $0$ up to $n\in\mathbb N$ decimal places. How can we derive these intervals?

Answer 1

(This is a complete rewrite, with some small changes to follow the changes to the problem statement.)

Let $\phi(\sigma; x) = \frac{1}{\sqrt{2 \pi} \sigma} \mathrm{e}^{-x^2/(2 \sigma^2)}$. $\phi$ is even, $\phi(\sigma; x) = \phi(\sigma; -x)$ for all $x \in \Bbb{R}$, increasing on $(-\infty, 0)$, and decreasing on $(0,\infty)$.

For $x \in (-1/2,1/2]$, $\phi(\sigma; x + k) \geq \phi(\sigma; x + \ell)$ for any integers $k$ and $\ell$ satisfying $|\ell| > |k|$. For $x \in (-1,-1/2)$, $x+1 \in (-1/2,1/2]$, so $\phi(\sigma; x + 1+ k) > \phi(\sigma; x + \ell)$ for any integers $k$ and $\ell$ satisfying $|\ell| > |k|$. Symmetrically, for $x \in (1/2,1)$, $x-1 \in (-1/2,1/2]$, so $\phi(\sigma; x - 1+ k) > \phi(\sigma; x + \ell)$ for any integers $k$ and $\ell$ satisfying $|\ell| > |k|$. To summarize, we might as well take $x \in (-1/2,1/2]$, since every other choice is redundant and $\phi(\sigma;x) \geq \phi(\sigma; x+k)$ for all integers $k$.

Choose $x \in (-1/2,1/2]$ and let $k$ range over the nonzero integers. We have shown $\phi(\sigma; x) \geq \phi(\sigma; x+k)$.

If what we wanted was to find is $\sigma$ such that $\phi(\sigma; x+k) \leq 10^{-n} \phi(\sigma; x)$, so that the terms $\phi(\sigma; x+\ell)$ for $|\ell|>|k|$ did not change the first $n$ nonzero decimal digits of $\phi(\sigma; x)$, we could just use

$$ \frac{\phi(\sigma; x+k)}{\phi(\sigma; x)} = \exp\left( \frac{x^2 - (k+x)^2}{2\sigma^2} \right) < 10^{-n} \text{,} $$ and solve for $\sigma$ to obtain $$ 0 < \sigma < \sqrt{\frac{k(k+2x)}{\sqrt{2} \ln(10) n}} \text{.} $$

However, you have not asked for $\sigma$ such that the $n$ leading nonzero decimal digits of $\phi(\sigma; x)$ are unchanged by adding $\phi(\sigma; x+k)$ (for some nonzero integer $k$). You have asked for $\sigma$ such that $\phi(\sigma; x+k) < 10^{-n}$ (for some nonzero integer $k$). That is, $$ \frac{1}{\sqrt{2 \pi}\sigma} \mathrm{e}^{-(x+k)^2 / (2 \sigma^2)} < 10^{-n} $$ and this inequality is hopeless. There is no solving for $\sigma$ here.

So what can we do?

Let $x$ be fixed and see how $\phi$ varies with $\sigma$.

We see that $\phi$ is maximized (with respect to $\sigma$) when $\frac{\mathrm{d}}{\mathrm{d}\sigma} \phi(\sigma; x) = 0$, that is, when $$ \frac{e^{-\frac{x^2}{2 \sigma ^2}} \left(x^2-\sigma ^2\right)}{\sqrt{2 \pi }\sigma ^4} = 0 \text{,} $$ which it is easy enough to see happens when $\sigma = |x|$ (since $\sigma > 0$).

We could choose to binary search for $\sigma \in (0, |x|)$ and then for $\sigma \in (|x|, 1)$ to find one or both $\sigma$ intervals to make $\phi$ small enough for the chosen $x$, $k$, and $n$.

To eliminate half the time, it is worthwhile to ask when (if ever) there is a solution with $\sigma \in (|x|, 1)$, since our plot suggests that $\phi$ is large for $\sigma$ nearer to $1$. Also, $\phi$ is monotonically decreasing for $\sigma > |x|$, so we can study the minimum of $\phi$ at $\sigma = 1$ as $x$ ranges over $(-1/2,1/2]$. The minimum value of $\phi$, $1/(\mathrm{e}^{1/8}\sqrt{2\pi}) = 0.352{\dots}$, occurs at $x = 1/2$. Consequently, no $\sigma > |x|$ can ever give $\phi(\sigma; x) < 10^{-1}$, much less give more zero leading decimal digits.

Therefore, only binary search over the interval $\sigma \in (0,|x|)$ is needed. For instance, for $x \in (-1/2, 1/2]$, $k \in \Bbb{Z} \smallsetminus \{0\}$, and $n \in \Bbb{N} = \Bbb{Z}_{>0}$,

search(float x, k, n){
    // find interval of sigma such that 
    // phi(sigma; x+k) < 10^(-n)
    // the lower bound of sigma is always 0
    // we binary search the upper bound over (0,|x|)
    float epsilon, lowerBound, upperBound
    epsilon = 10^(-10)
    lowerBound, upperBound = 0,|x|
    if phi(upperBound, x+k) > 10^(-n) {
        while upperBound - lowerBound > epsilon 
        // Never pretend to compare floats directly; always compare their difference to "small".
        {
            if phi((1/2)*(upperBound + lowerBound), x+k) > 10^(-n)
            {
                // the midpoint is also an upper bound
                upperBound = (1/2)*(upperBound + lowerBound)
            }
            else
            {
                // the midpoint is also a lower bound
                lowerBound = (1/2)*(upperBound + lowerBound)
            }
            debugPrint lowerBound, upperBound
        }
    }
    return "sigma in [0," + toString((1/2)*(upperBound + lowerBound)) + "] makes phi(sigma; x+k) < 10^(-n)."

When run with search(1/4,1,10), ($x = 1/4$, $k = 1$, comparing with $10^{-10}$), we obtain after 32 bisections, lowerBound, upperBound = $$\frac{777902065}{4294967296},\frac{3111608261}{17179869184}$$ and "sigma in [0,0.18111943...] makes phi(sigma; 1/4 + 1) < 10^(-10)."

Answer 2

Probably the best way to tackle this problem is to use the probability density function of the standard normal distribution $$ \Phi(z) = \frac{1}{\sqrt{2\pi}} \exp(-z^2/2) $$ where $z = \frac{x - \mu}{\sigma}$. Now we are able to solve this for any given value of $\Phi$ and obtain $$ \frac{x - \mu}{\sigma} = z = \sqrt{- 2 \ln(\sqrt{2\pi}\Phi)} $$ Thus we obtain the equation for $\sigma$ for a given mean value $\mu = k$.