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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.