# probability of sum of k discrete uniform random variables smaller than n

Q: $$X_k$$ follows the discrete uniform distribution, and takes integer value from $$0$$ to $$n$$ ($$0,1,2,3,...,n-1,n$$) randomly.

For a given $$k$$ and $$n$$, find the probability when $$X_1+X_2+X_3+...+X_k\leq n$$.

Let's say that the sum of $$k$$ random variables $$X$$ in your question is a random variable $$Z$$. Also, I suppose that the variables in question are mutually independent, otherwise it's impossible to answer your question because of lack of information (and even though, it's generally a really hard work).
In my opinion, the shortest way is to use generating functions. The generating function of these random variables is $$G_{X}(s) = \frac{1}{n}(1 + s + s^2 + ... s^n) = \frac{1-s^{n+1}}{n(1-s)}$$ Then, the generating function of $$Z$$ (of the sum of $$k$$ such variables) is $$G_{Z}(s) = \left(\frac{1-s^{n+1}}{n(1-s)}\right)^k$$ (which is the convolution of $$G_X(s)$$ with itself $$k$$ times) and the probability you seek for is the sum of the coefficients of the terms with $$s^z$$ for $$z=\{0,1,2,...,k\}$$. You can find it using the taylor's formula, so that $$P(Z \leq n) =\sum_{n=0}^{k}\frac{\frac{d^n}{ds^n}G_Z^{}(0)}{n!}$$
• @DanielRicketts, it is the $n$th derivative of the generating function $G_{Z}$. We basically use the standard calculus theory of Taylor's expansion to get back from the closed form to the polynomial as in the formula for $G_{X}$ (but in the direction from right to left). Feel free to ask further questions. May 2, 2021 at 19:27