# Convolution of i.i.d. with uniform distribution

I am trying to solve another exercise about convolution of continuous variables. Here is what is asked:

Let $X_1,\cdots,X_n$ be i.i.d. such that $X_1 \sim U(0,1)$. Verify that$$P(X_1+\cdots+X_n\leq x)=\frac{1}{n!}\sum_{k=0}^{n-1}(-1)^k {n\choose k}(x-k)_+^n, \quad \forall 0\leq x \leq n$$ where$$(x-k)_+=\begin{cases} 0; & \text{if } x <k \\ x-k; & \text{otherwise} \end{cases}$$

My first thought would be to find $P(S\leq s)$, where $S=\sum\limits_{i=1}^{n}X_i$. But I am wondering how I can solve such a huge convolution? My integral would look like: $$\int_{-\infty}^{+\infty}\cdots\int_{-\infty}^{+\infty}f_{X_1}(x_1)\cdots f_{X_n}(x_n)\,\mathrm{d}x_1\cdots\mathrm{d}x_n.$$ At first I had just $X_1$ and $X_2$ to add and I could find the CDF of $X_1 +X_2$ through convolution like this: $$\int_0^z f_{X_1}(z-v)f_{X_2}(v)\,\mathrm{d}v.$$ My question would be how can I solve it? Just even a hint in order to get started. My teacher say it is a simple generalization but many people suggest me to use conditional expectation, which I did not study yet.

• Maybe try proving the statement by induction. I think the only conditional expectation you need is in order to rewrite it as. $$P(X_1+\cdots +X_{n+1}\leq x) = E(P(X_1+\cdots +X_{n+1}\leq x | X_n)) = \int P(X_1+\cdots +X_{n+1}\leq x | X_{n+1}=y) dX_{n+1}(y) = \int_0^1 P(X_1+\cdots +X_{n}\leq x -y) dy$$ Otherwise search for the Irwin-Hall distribution, as the sum of independent uniformly distributed random variables has this distribution. – Martin Mar 7 '18 at 13:31
• How to you evalutate your integral with the probability of a sum of random variables ? Because it may no longer be a uniform random variable (and it seems not to be looking at what I have to verify) Thank you for Irwin hall, I didn't know that one – Brocolus Mar 7 '18 at 14:03
• Well if you are proving the formula by induction you know that the integrand in the last integral has the desired form for certain values of $x-y$. – Martin Mar 7 '18 at 14:19
• I think this is the point i'm stuck, if i start the basis of my induction, I'll have : $0 \leq x \leq 2$ with $f_{X_1+X_2}(x)=x$ if $x \leq 1$ or $f_{X_1+X_2}(x)=2-x$ if $1 \leq x \leq 2$ I don't see how I would proceed with a sum with more variables – Brocolus Mar 7 '18 at 16:38

$\def\d{\mathrm{d}}\def\peq{\mathrel{\phantom{=}}{}}$The base case of induction is, in fact, $n = 1$.
Denote $S_n = \sum\limits_{k = 1}^n X_k$ for any $n$. For $n = 1$,$$P(S_1 \leqslant x) = P(X_1 \leqslant x) = x_+. \quad \forall 0 \leqslant x \leqslant 1$$
Suppose the proposition holds for $n$. For any $0 \leqslant x \leqslant n + 1$, because $S_n$ and $X_{n + 1}$ are independent, then\begin{align*} &\peq P(S_{n + 1} \leqslant x) = P(S_n + X_{n + 1} \leqslant x)\\ &= \iint\limits_{y + z \leqslant x} f_{X_{n + 1}}(y) f_{S_n}(z) \,\d y\d z = \int_0^1 f_{X_{n + 1}}(y) \,\d y \int_0^{(x - y)_+} f_{S_n}(z) \,\d z\\ &= \int_0^1 P(S_n \leqslant (x - y)_+) f_{X_{n + 1}}(y) \,\d y = \int_0^1 P(S_n \leqslant (x - y)_+) \,\d y\\ &= \int_0^1 \frac{1}{n!} \sum_{k = 0}^{n - 1} \binom{n}{k} (-1)^k ((x - y)_+ - k)_+^n \,\d y. \tag{1} \end{align*} If $0 \leqslant x < 1$, then\begin{align*} (1) &= \frac{1}{n!} \int_0^1 (x - y)_+^n \,\d y = \frac{1}{n!} \int_0^x (x - y)^n \,\d y\\ &= \frac{1}{(n + 1)!} x^{n + 1} = \frac{1}{(n + 1)!} \sum_{k = 0}^n \binom{n + 1}{k} (-1)^k (x - k)_+^{n + 1}. \end{align*} Otherwise, suppose $m = [x] \geqslant 1$, then\begin{align*} (1) &= \frac{1}{n!} \sum_{k = 0}^{n - 1} \binom{n}{k} (-1)^k \int_0^1 ((x - y)_+ - k)_+^n \,\d y\\ &= \frac{1}{n!} \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k \int_0^1 (x - y - k)^n \,\d y + \frac{1}{n!} \binom{n}{m} (-1)^m \int_0^1 (x - y - m)_+^n \,\d y. \end{align*} Because\begin{align*} &\peq \frac{1}{n!} \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k \int_0^1 (x - y - k)^n \,\d y\\ &= \frac{1}{n!} \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k · \frac{1}{n + 1} ((x - k)^{n + 1} - (x - k - 1)^{n + 1})\\ &= \frac{1}{(n + 1)!} \left( \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k (x - k)^{n + 1} - \sum_{k = 1}^m \binom{n}{k - 1} (-1)^{k - 1} (x - k)^{n + 1} \right)\\ &= \frac{1}{(n + 1)!} x^{n + 1} + \frac{1}{(n + 1)!} \sum_{k = 1}^{m - 1} \left( \binom{n}{k} + \binom{n}{k - 1} \right) (-1)^k (x - k)^{n + 1}\\ &\peq - \frac{1}{(n + 1)!} \binom{n}{m - 1} (-1)^{m - 1} (x - m)^{n + 1}\\ &= \frac{1}{(n + 1)!} \sum_{k = 0}^{m - 1} \binom{n + 1}{k} (-1)^k (x - k)^{n + 1} + \frac{1}{(n + 1)!} \binom{n}{m - 1} (-1)^m (x - m)^{n + 1}, \end{align*} and\begin{align*} &\peq \frac{1}{n!} \binom{n}{m} (-1)^m \int_0^1 (x - y - m)_+^n \,\d y = \frac{1}{n!} \binom{n}{m} (-1)^m \int_0^{x - m} (x - y - m)^n \,\d y\\ &= \frac{1}{n!} \binom{n}{m} (-1)^m · \frac{1}{n + 1} (x - m)^{n + 1} = \frac{1}{(n + 1)!} \binom{n}{m} (-1)^m (x - m)^{n + 1}, \end{align*} then\begin{align*} (1) &= \frac{1}{(n + 1)!} \left( \sum_{k = 0}^{m - 1} \binom{n + 1}{k} (-1)^k (x - k)^{n + 1} + \left( \binom{n}{m} + \binom{n}{m - 1} \right) (-1)^m (x - m)^{n + 1} \right)\\ &= \frac{1}{(n + 1)!} \sum_{k = 0}^m \binom{n + 1}{k} (-1)^k (x - k)^{n + 1} = \frac{1}{(n + 1)!} \sum_{k = 0}^{n + 1} \binom{n + 1}{k} (-1)^k (x - k)_+^{n + 1}\\ &= \frac{1}{(n + 1)!} \sum_{k = 0}^n \binom{n + 1}{k} (-1)^k (x - k)_+^{n + 1}. \end{align*} End of induction.
$\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}$ \begin{align} &\bbox[10px,#ffd]{\ds{\int_{0}^{1}\int_{0}^{1}\cdots\int_{0}^{1} \bracks{x_{1} + x_{2} + \cdots + x_{n} < x}\dd x_{1} \,\dd x_{2}\ldots\dd x_{n}}} \\[5mm] = &\ \int_{0}^{1}\int_{0}^{1}\cdots\int_{0}^{1}\ \underbrace{\int_{c - \infty\ic}^{c + \infty\ic} {\expo{\pars{x - x_{1} - x_{2} - \cdots - x_{n}}s} \over s}\,{\dd s \over 2\pi\ic}}_{\ds{\bracks{x - x_{1} - x_{2} - \cdots - x_{n} > 0}}}\ \dd x_{1}\,\dd x_{2}\ldots\dd x_{n} \end{align}
where $\ds{c >0}$.