Relative error in Gaussian distribution.

Question

For discrete Gaussian distribution using cumulative distribution table how is the Relative error calculated? Specifically, In this paper https://eprint.iacr.org/2014/254 on page 7 section 3.4 It says that reversing the table will prevent blowing up of relative errors. I quite did not understand the reason very well.

Answer 1

So I'm not sure exactly what they're doing in this context, but I think I know essentially what is going on. The problem is essentially this: if you sum a rapidly decreasing sequence of positive numbers in floating point arithmetic, eventually the cumulative sum $S_n$ is way bigger than the next term $x_{n+1}$, which causes that term to be swamped, i.e. most or even all of its significant digits are destroyed. The remaining significant digits are all that you get when you attempt to reconstruct $x_{n+1}$ as $S_{n+1}-S_n$. But if instead you sum a rapidly increasing sequence of positive numbers, then the worst thing that could happen is that the cumulative sum itself gets swamped, which is not really a big deal in terms of computing $x_{n+1}$ as $S_{n+1}-S_n$.

One way to play with this (with less technical issues than in the article that you linked) would be to look at the distribution with $P(X=i)=\frac{2^{-i}}{\sum_{j=1}^{100} 2^{-j}}$ for $i=1,2,\dots,100$ and zero otherwise. Try computing the CDF by summing from left to right and then reconstructing the PMF, and then computing it again by summing from right to left and reconstructing the PMF. What you'll find is, if you're using IEEE double precision, the first method will actually just give $P(X=i)=0$ for $i$ larger than about $55$, while the second method will give reasonable results. This would be even worse if it were not for the fact that these numbers are all exactly floating point representable. You could try replacing $2$ with $3$ to see how much worse it can get.