# What is the probability of N integers summing to less than X

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$?

-
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

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.$$

-

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

-