1
$\begingroup$

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.

Thank you for your help.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Martin Mar 7 '18 at 13:31
  • $\begingroup$ 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 $\endgroup$ – Brocolus Mar 7 '18 at 14:03
  • $\begingroup$ 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$. $\endgroup$ – Martin Mar 7 '18 at 14:19
  • $\begingroup$ 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 $\endgroup$ – Brocolus Mar 7 '18 at 16:38
1
+50
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

Then, \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_{c - \infty\ic}^{c + \infty\ic}{\expo{xs} \over s} \pars{\int_{0}^{1}\expo{-s\xi}\dd\xi}^{n}{\dd s \over 2\pi\ic} = \int_{c - \infty\ic}^{c + \infty\ic}{\expo{xs} \over s} \pars{\expo{-s} - 1 \over -s}^{n}{\dd s \over 2\pi\ic} \\[5mm] = &\ \int_{c - \infty\ic}^{c + \infty\ic} {\expo{xs} \over s^{n + 1}}\pars{1 - \expo{-s}}^{n}{\dd s \over 2\pi\ic} = \int_{c - \infty\ic}^{c + \infty\ic} {\expo{xs} \over s^{n + 1}}\sum_{k = 0}^{n}{n \choose k} \pars{-\expo{-s}}^{k}{\dd s \over 2\pi\ic}\label{1}\tag{1} \\[5mm] = &\ \sum_{k = 0}^{n}{n \choose k}\pars{-1}^{k}\ \underbrace{\int_{c - \infty\ic}^{c + \infty\ic} {\expo{\pars{x - k}s} \over s^{n + 1}}{\dd s \over 2\pi\ic}} _{\ds{\bracks{x - k > 0}\,{\pars{x - k}^{n} \over n!}}}\ =\ \left.{1 \over n!}\sum_{k = 0}^{n}\pars{-1}^{k}{n \choose k} \pars{x - k}^{n}\,\right\vert_{\ k\ <\ x} \\[5mm] = &\ \bbx{{1 \over n!}\sum_{k = 0}^{N}\pars{-1}^{k}{n \choose k} \pars{x - k}^{n}\quad\mbox{where}\quad N \equiv \min\braces{n,\left\lfloor x\right\rfloor}} \end{align}

$\endgroup$

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.