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.

Lets say I have $N$ integers $X_i$, each one a random number such that $1 \leq X_i \leq M$. What is the probability that $\sum X_i \leq M$? What is the probability that $\sum X_i = M$?

share|improve this question
1  
Use $\backslash$leq. –  Did Nov 13 '11 at 1:01
    
Depending on how large $N$ is, the central limit theorem could be used to get a reasonably accurate estimate of these probabilities. –  Dilip Sarwate Nov 13 '11 at 1:02
    
Can you explain how? –  Robert Martin Nov 13 '11 at 2:14

2 Answers 2

up vote 2 down vote accepted

Assuming that the $X_i$ are independent and each of the values $\{1,2,\dots,M\}$ is equally likely, the probability that the sum is exactly $k$ is given by $$\mathbb{P}\left(\sum X_i=k\right)={1\over M^N}\sum_j (-1)^j{N\choose j}{k-jM-1\choose k-jM-N}.$$

This isn't as bad as it looks, since the sum is actually finite. Let's try it with $k=27$, $N=10$, and $M=6$. The probability of getting a sum of 27 when you throw 10 fair, six-sided dice is $${1\over 6^{10}}\left[{10\choose 0}{26\choose 17}-{10\choose 1}{20\choose 11}+{10\choose 2}{14\choose 5}\right] ={2665\over 104976}\approx 0.0254.$$

share|improve this answer

Following Dilip Sarwate comment, a simple approximation comes from applying the central limit theorem (on the favorable side, we have a uniform distribution, and we know that the sum of uniforms converges quickly to a normal; on the unfavorable side, we have a discrete variable). Let's try. $$E(X_i)= \frac{M+1}{2}$$

$$E(X_i^2)=\frac{1}{M}\sum_{k=1}^M k^2 = \frac{(M+1)(2M+1)}{6} \Rightarrow Var(X_i)=\frac{M^2-1}{12}$$

We assume then than $Z = \sum_{i=1}^N X_i$ can be approximated by a gaussian with $\mu = N \frac{M+1}{2}$ and $\sigma^2 = N \frac{M^2-1}{12} $ and evaluate the probabilities accordingly. For example, for the case computed by Byron Schmuland:

define(mu(M,N) , N*(M+1)/2);
define(var(M,N) , N*(M^2-1)/12);
define( prob(M,N,k) , exp(- (k-mu(M,N))^2/(2*var(M,N)))/sqrt(2*%pi*var(M,N)));
float(prob(6,10,27));
0.024659460902552

Or, a little more precise (integrating the cdf) :

define( zcdf(M,N,k), cdf_normal(k,mu(M,N),sqrt(var(M,N))));
define( prob1(M,N,k), zcdf(M,N,k+1/2) - zcdf(M,N,k-1/2));
float(prob1(6,10,27));
0.024701452245632
share|improve this answer

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.