Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been working on finding the probability for the event, that the sum of $n$ independent random variables are less than $s$, when they are evenly distributed on $[0,1)$.

I've used the law of total probability to derive the formula:

$P(S<s) = \frac{1}{n!}\sum_{k=0}^{\lfloor s\rfloor}(-1)^k\binom{n}{k}(s-k)^n$

$f_S(s) = \frac{1}{(n-1)!}\sum_{k=0}^{\lfloor s\rfloor}(-1)^k\binom{n}{k}(s-k)^{n-1}$

Now I'm not very strong in probability, but I believe you could express the same thing using the normal distribution. Or at least approximate it. Is that so? In that case how would you express it, and how would you normally determine the approximation error?

share|improve this question
    
You can't express the same thing as a normal distribution. One way to see this is to note that it's not a smooth function; another is to note that it takes zero values. What you can do is to find a normal distribution with the same mean and variance, which is easy, since the mean and variance are additive, so are just $n$ times the values for the individual distributions. For large $n$, that normal distribution will become a good approximation of the distribution; see en.wikipedia.org/wiki/Central_limit_theorem. –  joriki Apr 6 '11 at 17:36
    
@joriki: I think the function has derivatives of all orders, doesn't it? n of them being non zero. –  Thomas Ahle Apr 6 '11 at 18:08
    
The normal distribution is about the summing an infinite number of random variables, right? So as you say, you should be able to approximate my problem using it. That's what I want to do. –  Thomas Ahle Apr 6 '11 at 18:09
1  
I don't think it has any name other than "the sum of $n$ independent random variables with uniform distribution on [0,1]". –  joriki Apr 6 '11 at 18:19
1  
For $n=2$, it's called a triangular distribution; see en.wikipedia.org/wiki/Triangular_distribution -- the graph there also shows you that it's not a smooth function. –  joriki Apr 6 '11 at 18:22
show 3 more comments

2 Answers

up vote 4 down vote accepted

The distribution of the sum of $n$ IID random variables uniform on $[0,1]$ is also known as the Irwin-Hall distribution or the uniform sum distribution.

The normal approximation is to approximate a distribution with a normal distribution which has the same mean $(\frac{n}{2})$ and standard deviation $(\sqrt{\frac{n}{12}})$.

One way to bound the error in a normal approximation is to use the Berry-Esséen theorem which gives effective bounds on the errors in a normal approximation in terms of the third central moment of a distribution.

$$|P(S<\frac{n}{2}+\sigma \sqrt{n} x) - \Phi(x)| \le \frac {C \rho}{\sigma^3\sqrt{n}}$$

where $\Phi$ is the cumulative distribution function for a standard normal distribution, $C$ can be taken to be $1/2$, $\sigma = \sqrt{\frac{1}{12}}$, and $\rho$ is the $3$rd central moment of $U(0,1)$, $1/32$.

I think the extreme cases for the Berry-Esseen estimate do not look much like the uniform distribution, so it could be that you can get better estimates for the accuracy of a normal approximation.

share|improve this answer
    
Very interesting. I think the formula on wikipedia to evaluate fX is less efficient than mine? –  Thomas Ahle Apr 7 '11 at 9:01
add comment

For an explicit expression for the denisty function see MathWorld: Uniform Sum Distribution, for example.

EDIT:

The density function $f_n$ of the sum $U_1 + \cdots + U_n$, where $U_i$ are independent uniform$(0,1)$ variables, is given, according to the MathWorld link above, by $$ f_n (x) = \frac{1}{{2(n - 1)!}}\sum\limits_{k = 0}^n {( - 1)^k {n \choose k}(x - k)^{n - 1} {\mathop{\rm sgn}} (x - k)},\;\; 0 < x < n. $$

Normal approximation (general setting). Suppose that $X_1,X_2,\ldots$ is a sequence of independent and identically distributed random variables with mean $\mu$ and variance $\sigma^2$. Define $S_n = \sum\nolimits_{i = 1}^n {X_i }$. Then, by the central limit theorem, $$ \frac{{S_n - n\mu }}{{\sigma \sqrt n }} \to {\rm N}(0,1), $$ as $n \to \infty$. This means that, for any $x \in \mathbb{R}$, $$ {\rm P}\bigg(\frac{{S_n - n\mu }}{{\sigma \sqrt n }} \le x \bigg) \to \Phi (x), $$ where $\Phi$ denotes the distribution function of the ${\rm N}(0,1)$ distribution. Thus, $$ {\rm P}(S_n \le n\mu + \sigma \sqrt n x) \to \Phi (x). $$ Note that the first convergence above gives rise to the approximation $$ S_n \approx n \mu + \sigma \sqrt{n} Z, $$ where $Z \sim {\rm N}(0,1)$.

Back to your specific question, you just need to substitute the expectation and variance of a uniform$(0,1)$ random variable. In the context of normal approximation, consider also the four plots given in the MathWorld link above.

share|improve this answer
    
Thank you for the link and the general usage of the Normal distribution. –  Thomas Ahle Apr 7 '11 at 9:08
    
Are there any advantages on the MathWorld pdf compared to mine? It seams slightly more complex and a bit less efficient. –  Thomas Ahle Apr 7 '11 at 9:09
    
@Thomas Ahle: Indeed, your formula looks more elegant. –  Shai Covo Apr 7 '11 at 10:18
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.