Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
This is a question I found on internet under DSP section so that's why I am posting it here. Help me understand it please.
A computer adds 1000 random numbers that have each been rounded off to the nearest 10$^{\rm th}$. Find the probability that the total round-off error for the sum is $\ge 1$.
How probability of any system can be greater than 1?
The total roundoff error for the sum of $N$ numbers is:
$$ S = \sum_{i=0}^{N-1} E_i $$
The roundoff error for the $i$-th number is represented by the random variable $E_i$. If we assume that the random number generator used by the computer yields numbers $X_i$ taken from a uniform distribution, then the difference between each $X_i$ and the nearest tenth (which is the roundoff error $E_i$) is uniformly distributed on the interval $(-\frac{0.1}{2}, \frac{0.1}{2}) = (-0.05, 0.05)$.
What we're concerned with, though, is the distribution of $S$. Since $S$ is the sum of $N$ independent, identically distributed (iid) random variables, then via the central limit theorem, as $N \to \infty$, $S$ will tend to a Gaussian distribution. If we assume that your case of $N=1000$ is "large enough" for the Gaussian assumption to hold, we can easily estimate the probability that you seek. It's certainly possible to exactly calculate the distribution of $S$, but the Gaussian assumption is likely close enough for most applications with such large $N$.
A Gaussian distribution is characterized by its first two moments, so if we can find those for $S$, then we have all the information we need. These are easy to calculate for a sum of iid random variables. The mean of $S$ is equal to:
$$ \mathbb{E}(S) = \sum_{i=0}^{N-1} \mathbb{E}(E_i) = 0 $$
The variance of $S$ is equal to:
$$ \mathbb{E}\left((S - \mathbb{E}(S))^2\right) = \sum_{i=0}^{N-1} \mathbb{E}\left((E_i - \mathbb{E}(E_i))^2\right) $$
Recall that the random variables $E_i$ are distributed uniformly. It is well known that the uniform distribution over the interval $(a,b)$ has variance $\frac{1}{12}(b-a)^2$. For this case, that yields a variance $\sigma_{E_i}^2 = \frac{0.01}{12}$. Therefore, the variance of the total roundoff error $S$ is $\sigma_{S}^2 = \frac{0.01N}{12}$.
So in summary, we can approximate $S$'s distribution as Gaussian with mean zero and variance $\sigma_{S}^2 = \frac{0.01N}{12}$. Based on those parameters, you can easily calculate the estimated probability distribution function (pdf), then integrate that result to arrive at whatever probability you seek. The probability that there is a total roundoff error with magnitude greater than one would be:
$$ \begin{align} P(|S| > 1) &= P(S>1 \lor S < -1) \\ &= 1 - P(-1 < S < 1) \\ &= 1 - \int_{-1}^{1}f_S(s)ds \end{align} $$
where $f_S(s)$ is the Gaussian distribution's pdf that we arrived at before.
