Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

This is the question i found on internet under DSP section so thats 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$^{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?

share|improve this question
    
@DilipSarwate so it means i have two numbers one come up from the summation of 1000 random numbers without rounding off and another number is the summation of those random numbers after rounding off and have to find the probability of Sum2-Sum1 is greater or equal to 1? –  heavenhitman Dec 8 '12 at 20:04
    
@DilipSarwate ok thanks for the help. –  heavenhitman Dec 8 '12 at 21:19
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
thanks for detailed answer sir. @DilipSarwate thanks for the explanation and calculator it really made it easy to calculate :) –  heavenhitman Dec 8 '12 at 22:23
    
@JasonR Very nice answer, however I have a minor quibble. Does the RHS of your variance equation reduce to what is shown for any $\mathbb{E}\{S\}$? In this case it happens to be 0, so it would. –  Mohammad Dec 9 '12 at 0:20
    
@JasonR (contd) However it threw me off because $\mathbb{E}\{(S - \mathbb{E}(S))^2\} = \mathbb{E}\{(\sum E_i - \mathbb{E}\{\sum E_i\})^2\} = \mathbb{E}\{(\sum E_i - \sum\mathbb{E}\{E_i\})^2 \}$. Factoring, this then leads to: $\mathbb{E}\{(\sum(E_i - \mathbb{E}\{E_i\}))^2\}$, which is not the same as shown on RHS. Your RHS is correct for this case of zero-mean and iid, but I am not sure it holds for any arbitrary mean, as the LHS would seem to indicate. –  Mohammad Dec 9 '12 at 0:20
    
The expectation operator and summation operator are linear and therefore the expectation operator can be distributed over the summation. –  Bryan Dec 10 '12 at 14:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.