1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ In the numerator of the final line, what is d? $\endgroup$ May 1, 2021 at 16:45
  • $\begingroup$ @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. $\endgroup$
    – mur_tm
    May 2, 2021 at 19:27

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.