2
$\begingroup$

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

  • 0
    Can you explain how?2011-11-13

2 Answers 2

3

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

1

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