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

Question

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

Answer 1

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!}$$