What is the probability that the sum of n numbers between 0 and k is less than k?

Question

I was looking at a very recent question, and I wanted to generalize it as such:

Suppose that $\{x_1, x_2, \cdots x_n\}$ are n independently uniformly distributed real numbers from 0 to k, then what is the probablity that their sum is less k?

I want to check if this type of question is solvable using probability and Bayes Theorem as I have attempted below. Thus we require to find: $$Pr(x_1+x_2+\cdots+x_n\leq k | x_1, x_2, \cdots x_n \in [0, k])$$ $$=\dfrac{Pr(x_1, x_2, \cdots x_n \in [0, k] | x_1+x_2+\cdots+x_n\leq k)Pr(x_1+x_2+\cdots+x_n\leq k)}{Pr(x_1, x_2, \cdots x_n \in [0, k])}$$

Now:

$$Pr(x_1, x_2, \cdots x_n \in [0, k] | x_1+x_2+\cdots+x_n\leq k) = 1$$

and

$$Pr(x_1, x_2, \cdots x_n \in [0, k])$$ $$=Pr(x_1\in [0, k])\cdots Pr(x_n\in [0, k]) $$ $$=\dfrac{x_1\cdots x_n}{k^n}$$ The above is true since the $x_i$'s are independent and uniformly distributed between 0 and k.

Now how do you compute: $Pr(x_1+x_2+\cdots+x_n\leq k)$ to find the last term? Is my use of Bayes Theorem correct?

Answer 1

Discrete Case

The number of ways to sum $n$ integers in $[0,k]$ and get $m$ is $\left[x^m\right]\left(x^0+x^1+x^2+\cdots+x^k\right)^n$. Thus, the number of ways to get $m\in[0,k]$ is $$ \begin{align} &\sum_{m=0}^k\left[x^m\right]\left(x^0+x^1+x^2+\cdots+x^k\right)^n\\ &=\sum_{m=0}^k\left[x^m\right]\left(\frac{1-x^{k+1}}{1-x}\right)^n\\ &=\sum_{m=0}^k\left[x^m\right]\sum_{j=0}^n(-1)^j\binom{n}{j}x^{j(k+1)} \sum_{i=0}^\infty(-1)^i\binom{-n}{i}x^i\\ &=\sum_{m=0}^k\left[x^m\right]\sum_{j=0}^n(-1)^j\binom{n}{j}x^{j(k+1)} \sum_{i=0}^\infty\binom{n+i-1}{i}x^i\\ &=\sum_{m=0}^k\sum_{j=0}^n(-1)^j\binom{n}{j}\binom{n+m-j(k+1)-1}{m-j(k+1)}\\ &=\sum_{m=0}^k\binom{n+m-1}{m}\\ &=\binom{n+k}{k}\\ \end{align} $$ Therefore, the probability is $$ \frac1{(k+1)^n}\binom{n+k}{k} $$

---

Continuous Case

The continuous case is given by the volume of $$ \sum_{j=1}^nx_j\le1 $$ where $x_j\ge0$, which is $\frac1{n!}$. The answer is independent of $k$ since the volumes of both the sample space and the success space are multiplied by $k^n$.

Note that the limit of the discrete case as $k\to\infty$ is $$ \begin{align} \lim_{k\to\infty}\frac1{(k+1)^n}\binom{n+k}{k} &=\lim_{k\to\infty}\frac1{(k+1)^n}\frac{(k+n)(k+n-1)\cdots(k+1)}{n!}\\ &=\frac1{n!} \end{align} $$

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

Suppose that $\ds{\braces{x_{1},x_{2},\ldots,x_{n}}}$ are $\ds{n}$ independently uniformly distributed real numbers from $0$ to $k$, then what is the probablity that their sum is less than $k$ ?.

By definition: \begin{align} &\bbox[10px,#ffd]{\ds{\int_{0}^{k}{\dd x_{1} \over k} \int_{0}^{k}{\dd x_{2} \over k}\cdots \int_{0}^{k}{\dd x_{n} \over k}\bracks{x_{1} + x_{2} + \cdots x_{n} < k}}} \\[5mm] = &\ {1 \over k^{n}} \int_{0}^{\infty}\int_{0}^{\infty}\cdots\int_{0}^{\infty} \bracks{k - x_{1} - x_{2} - \cdots - x_{n} > 0} \dd x_{1}\,\dd x_{2}\ldots\dd x_{n}\ \pars{\begin{array}{l} \mbox{Integrals contribution} \\ \mbox{'beyond'}\ k\ \mbox{vanishes out.} \end{array}} \\[5mm] = &\ {1 \over k^{n}} \int_{0}^{\infty}\int_{0}^{\infty}\cdots\int_{0}^{\infty} \underbrace{\braces{\int_{c - \infty\ic}^{c + \infty\ic}{\exp\pars{\bracks{k - x_{1} - x_{2} - \cdots - x_{n}}s} \over s}\,{\dd s \over 2\pi\ic}}} _{\ds{=\ \bracks{k - x_{1} - x_{2} - \cdots - x_{n} > 0}}}\ \dd x_{1} \,\dd x_{2}\ldots\dd x_{n} \end{align}

where $\ds{c > 0}$.

Then, \begin{align} &\bbox[10px,#ffd]{\ds{\int_{0}^{k}{\dd x_{1} \over k} \int_{0}^{k}{\dd x_{2} \over k}\cdots \int_{0}^{k}{\dd x_{n} \over k}\bracks{x_{1} + x_{2} + \cdots x_{n} < k}}} \\ = &\ {1 \over k ^{n}} \int_{c - \infty\ic}^{c + \infty\ic}{\exp\pars{ks} \over s}\ \underbrace{\pars{\int_{0}^{\infty}\expo{-xs}\dd x}^{n}} _{\ds{=\ {1 \over s^{n}}}}\ \,{\dd s \over 2\pi\ic} = {1 \over k ^{n}}\ \overbrace{\int_{c - \infty\ic}^{c + \infty\ic}{\exp\pars{ks} \over s^{n + 1}} \,{\dd s \over 2\pi\ic}}^{\ds{k^{n} \over n!}}\ =\ \bbx{1 \over n!} \end{align}