# On the sum of uniform independent random variables

Let $X_1,...,X_n$ be independent uniform random variables in [0,1] and assume $c>1/2$. Is it true that $$\mathbb{P}\left[\sum_{i=1}^n X_i \leq n \cdot c\right]$$ is increasing with respect to $n$?

I know that the sum of uniform independent random follows Irwin–Hall distribution, but it seems hard to work with the pdf. Maybe a coupling argument? I want to stress that we want to show the result for all $n$, not only for $n$ sufficiently large.

• Based om simulation, I think the result is true, presuming "increasing" is interpreted as meaning "non-decreasing" (in order to cover $c \ge 1$). I leave the proof to you. Jun 18 '16 at 19:16
• I did simulations too. That is why I asked the question. The proof is all that matters...
– user31317
Jun 18 '16 at 20:02
• I have a feeling this might be rather subtle, at least for $c$ close to $1/2$. I just posted and deleted an incorrect answer, and the summary of that is that there are competing effects. Jun 18 '16 at 20:16
• I saw the post, where was the mistake?
– user31317
Jun 18 '16 at 20:18
• The fact that $p_n''<0$ actually works against me, and I need the asymmetry of the interval I'm averaging over to at least compensate for this. Jun 18 '16 at 20:20

The answer is yes. Let $S_n:=\sum_{i=1}^n X_i$, $x\in\mathbb R$, $n=2,3,\dots$, and \begin{equation} G_n(x):=P(S_n/n\le x)=\frac1{n!}\,\sum_j(-1)^j\binom nj (nx-j)_+^n, \end{equation} where $u_+:=0\vee u$; cf. [Irwin--Hall distribution]. The summation here is over all integers $j$, with the usual convention that $\binom nj=0$ if $j\notin\{0,\dots,n\}$. Let \begin{equation} D_n(x):=G_{n+1}(x)-G_n(x). \end{equation} We have to show that $D_n(x)\ge0$ for $x\ge1/2$.

Clearly, $D_n$ is $n-1$ times continuously differentiable, $D_n=0$ outside $(0,1)$, and $D_n(1-x)=-D_n(x)$ (symmetry). For small $x>0$, one has $G_n(x)=\frac1{n!}\,n^nx^n>\frac1{(n+1)!}\,(n+1)^{n+1}x^{n+1}=G_{n+1}(x)$, whence $D_n(x)<0$, whence $D_n>0$ in a left neighborhood of $1$, with $D_n(1)=0$. Also, $D_n(1/2)=0$. So, it suffices to show that $D_n$ has no roots in $(1/2,1)$.

Suppose the contrary. Then, by the symmetry, $D_n$ has at least $3$ roots in $(0,1)$. Then, by the Rolle theorem, the derivative $G_n^{(n-1)}$ of $G_n$ of order $n-1$ has at least $3+n-1=n+2$ roots in $(0,1)$. This contradicts the fact (proved below) that, for each integer $j$ such that $n-1\ge j\ge\frac{n-1}2$, $D_n$ has exactly one root in interval $$h_{n,j}:=[\tfrac jn,\tfrac{j+1}n).$$

Indeed, take any $x\in[1/2,1]$. It is not hard to see that, for $j_x:=j_{n,x}:=\lfloor nx\rfloor$, \begin{equation} G_n^{(n-1)}(x)=n^{n-1}\sum_{j=0}^{j_x}(-1)^j\binom nj (nx-j) \end{equation}
\begin{equation} =\frac{n^{n-1}}{n-1}(-1)^{j_x}\binom n{j_x+1}({j_x}+1) ((n-1)x-{j_x}). \end{equation} Similarly, for $k_x:=j_{n+1,x}$, \begin{equation} G_{n+1}^{(n-1)}(x)=\frac{(n+1)^{n-1}}{2n(n-1)} (-1)^{k_x}\binom{n+1}{k_x+1}(k_x+1)P(n,k_x,x), \end{equation} where \begin{equation} P(n,k,x):=-2 k \left(n^2-1\right) x+k (k n-1)+n \left(n^2-1\right) x^2. \end{equation} Note that $k_x\in\{j_x,j_x+1\}$. Now we have to consider the following two cases.

Case 1: $k_x=j_x=j\in[\frac{n-1}2,n-1]$, which is equivalent to $x\in h'_{n,j}:=[\frac jn,\frac{j+1}{n+1})$. It also follows that in this case $j\ge n/2$. In this case, it is not hard to check that $D_n(x)$ equals $(-1)^j P_{n,j,1}(x)$ in sign, where \begin{equation} P_{n,j,1}(x):=2 j n^n (n-j)+x \left(-2 (n-1) n^n (n-j)-2 j (n+1)^n \left(n^2-1\right)\right)+j (n+1)^n (j n-1)+(n+1)^n \left(n^2-1\right) n x^2, \end{equation} which is convex in $x$. Moreover, $P_{n,j,1}(\frac jn)$ and $P_{n,j,1}(\frac{j+1}{n+1})$ each equals $2 n^n - (1 + n)^n<0$ in sign. So, $P_{n,j,1}<0$ and hence $D_n$ has no roots in $h''_{n,j}=[\frac jn,\frac{j+1}{n+1})$.

Case 2: $k_x=j+1$ and $j_x=j\in[\frac{n-1}2,n-1]$, which is equivalent to $x\in h''_{n,j}:=[\frac{j+1}{n+1},\frac{j+1}n)$. In this case, it is not hard to check that $D_n(x)$ equals $(-1)^{j+1} P_{n,j,2}(x)$ in sign, where \begin{equation} P_{n,j,2}(x):=(j+1) \left((n+1)^n (j n+n-1)-2 j n^n\right)+2 (j+1) \left((n-1) n^n-(n+1)^n \left(n^2-1\right)\right) x+n \left(n^2-1\right) (n+1)^n x^2, \end{equation} which is convex in $x$. Moreover, $P_{n,j,1}(\frac{j+1}n)$ and $-P_{n,j,1}(\frac{j+1}{n+1})$ each equals $2 n^n - (1 + n)^n<0$ in sign. So, $P_{n,j,2}$ has exactly one root in $h''_{n,j}$ and hence so does $D_n$.

Since the interval $h_{n,j}$ is the disjoint union of $h'_{n,j}$ and $h''_{n,j}$, $D_n$ has exactly one root in $h_{n,j}=[\tfrac jn,\tfrac{j+1}n)$, and the proof is complete.

• Hi Iosif,can you explain this: "Then, by the Rolle theorem, the derivative $G^{(n−1)}_n$ of $G_n$ of order $n−1$ has at least $n+2$ roots"
– user31317
Jul 3 '16 at 5:45
• There are two typos here -- sorry. Of course, I meant to say "the derivative $D_n^{(n-1)}$ of $D_n$ of order $n-1$ has at least $3+n-1=n+2$ roots in $(0,1)$". Jul 3 '16 at 12:50
• Here are details on the previous comment. On supposing that your conjecture is false, we saw that $D_n$ must have at least $3$ roots in $(0,1)$. Plus, $0$ and $1$ are roots of $D_n$ (and of its derivatives of orders up to $n-1$). So, $D_n$ must have at least $5$ roots in $[0,1]$. By Rolle's theorem, strictly between any two roots of a differentiable function there is at least one root of its derivative. Jul 3 '16 at 12:50
• [Continuation of the previous comment:] So, $D'_n$ must have at least $5-1=4=3+1$ roots in $(0,1)$. Continuing thus and using the fact that $D_n$ is $n-1$ times continuously differentiable, we see that $D_n^{(n-1)}$ must have at least $3+n-1=n+2$ roots in $(0,1)$. Please let me know if you have more questions about this answer. Jul 3 '16 at 12:51

Let's write $p_n(x)=P(S_n\le nx)$; we want to show that this increases in $n$ for fixed $x>1/2$. By conditioning on $X_{n+1}$, we obtain that $$p_{n+1}(x) = \int_0^1 p_n\left( x+ \frac{x-y}{n} \right) \, dy = n\int_{x-(1-x)/n}^{x+x/n} p_n(t)\, dt .$$ So we're asking if $$p_n(x) \le n \int_{x-(1-x)/n}^{x+x/n} p_n(t)\, dt \quad\quad\quad\quad (1)$$ By a Taylor expansion, the RHS of (1) equals $$p_n(x) + p_n'(x) \frac{2x-1}{2n} + O(p_n''/n^2) ,$$ so we'd be done if we could establish that $|p_n''(t)|\lesssim n p_n'(x)$ near $t=x$ with a sufficiently small implied constant. If we go back to the Irwin Hall distribution $F_n(a)=P(S_n\le a)$, then this becomes $|F_n''(t)|\lesssim F_n'(nx)$ near $t=nx$, and at least for large $n$, this is true since $F''_n$ doesn't vary much on an interval of length $L$, so it can't be much larger than $F'_n(x)/L$.

Comment: If we go back to (1), we see that there are competing effects. On the one hand, we're averaging over an asymmetric interval, giving preference to points $t>x$ where $p_n(t)>p_n(x)$, which is good. On the other hand, $p_n''<0$, which is bad, because this means that $p_n$ decreases more rapidly going to the left of $x$ than it increases going to the right.

• Why don't you go with first order approximation?
– user31317
Jun 18 '16 at 21:01
• Also, can you explain how did you use taylor for (1)?
– user31317
Jun 18 '16 at 21:03
• This can't work because it doesn't address the key issue mentioned in my final paragraph. On a more technical level, we'd be dealing with $n\int p_n'(\xi_t)(t-x)\, dt$, and I can't tell what the sign of this is. Jun 18 '16 at 21:04
• We use mean value theorem for the first order, RHS becomes $p_n(x)+p_{n}'(\xi) \frac{2x-1}{n}$ for some $\xi \in (x-x/n,x+x/n)$. We know that $p_n'(\xi)>0$.
– user31317
Jun 18 '16 at 21:13
• @user31317: I don't know how you want to argue, but you're missing something because I can easily cook up function with positive derivative for which the RHS is $<p_n(x)$ (see my comment again). Jun 18 '16 at 21:20

Let me write $$c=1/2+\delta$$ and define $$P_n(\delta)\equiv \mathbb{P}\left[\sum_{i=1}^n X_i \leq n \cdot c\right].$$ Note that $$P_n(0)=1/2$$ and $$P_n(1/2)=1$$, irrespective of $$n$$.

It is convenient to work with the characteristic function of the Irwin-Hall distribution. I find the principal value integral $$\mathbb{P}\left[\sum_{i=1}^n X_i \leq n \cdot c\right]=\frac{1}{2}-\frac{1}{2\pi}\int_{-\infty}^\infty dt\,\frac{1}{(it)^{n+1}}\left(e^{it(1-c)}-e^{-ict}\right)^n,$$ which can be rewritten as $$P_n(\delta)=\frac{1}{2}+\frac{1}{\pi}\int_{0}^\infty dt\,\sin(2nt\delta)\,\frac{\sin^n t}{t^{n+1}}.$$ The plot shows $$P_n(\delta)$$ for $$n=1,2,3,4$$, from bottom curve to top curve. We need to demonstrate that this ordering of $$P_n(\delta)$$ with increasing $$n$$ holds for all $$n$$, so $$P_n(\delta)$$ increases with $$n$$ for all $$\delta\in(0,1/2)$$. I will attempt to prove this in several steps.

(I) $$P_n(\delta)$$ increases with $$n$$ near $$\delta=0$$.

For small $$\delta$$ the integral evaluates to

$$P_n(\delta)=\tfrac{1}{2}+2nC_n\delta+{\cal O}(\delta^3),$$

with the coefficient

$$C_n=\frac{1}{\pi}\int_0^\infty dt\,\frac{\sin^n t}{t^n}.$$

This integral over the $$n$$-th power of the sinc function is well-studied, we need to show that it decreases more slowly than $$1/n$$. For small $$n$$ this can be checked by explicit calculation, for large $$n$$ it follows from the asymptotic decay $$C_n\propto 1/\sqrt n$$. So the slope $$P'_n(0)=2nC_n\propto \sqrt n$$ is indeed an increasing function of $$n$$.

(II) $$P_n(\delta)$$ increases with $$n$$ near $$\delta=1/2$$.

This follows from a similar expansion around $$\delta=1/2$$, which shows that the first nonzero $$p$$-th order derivative $$P_n^{(p)}(1/2)$$ occurs for $$p=n$$. So near $$\delta=1/2$$ the function expands as

$$P_n(\delta)=1-(-1)^n A_n(\delta-1/2)^n+{\cal O}(\delta-1/2)^{n+1},\;\;A_n>0,$$

hence $$P_n(\delta)$$ increases with $$n$$ for $$\delta$$ just below $$1/2$$.

(III) Large-$$n$$ asymptotics

For $$n\gg 1$$ the sinc integral can be evaluated in closed form by means of the limit $$\lim_{n\rightarrow\infty}\left(\frac{\sin(t/\sqrt n)}{t/\sqrt n}\right)^n=\exp(-t^2/6)$$ so that $$P_n(\delta)$$ becomes asymptotically $$P_n(\delta)\rightarrow\frac{1}{2}+\frac{1}{\pi}\int_0^\infty dt\,\sin(2t\delta\sqrt n)\frac{1}{t}\exp(-t^2/6)=\frac{1}{2}+\frac{1}{2}\,{\rm Erf}\,(\delta\sqrt{6n}),$$ which has indeed a monotonically increasing $$n$$-dependence for each $$\delta\in(0,1/2)$$.

Note that we recover the $$\sqrt n$$ slope at $$\delta=0$$, $$P'_n(0)\rightarrow \sqrt{6n/\pi}\;\;\text{for}\;\;n\rightarrow\infty.$$ At $$\delta=1$$ the deviation from the exact limit $$P_n(1/2)=1$$ is exponentially small, $$\propto\exp(-3n/2)/\sqrt n$$.

The error function asymptotics is remarkably accurate already for small $$n$$, see the plot below for $$n=3$$ and $$n=4$$. For larger $$n$$ the exact and asymptotic curves are indistinguishable on the scale the figure. Bottom line.

I would think that the finite-$$n$$ analytics near $$\delta=0$$ and $$\delta=1/2$$, together with the large-$$n$$ asymptotics for the whole interval $$\delta\in(0,1/2)$$, goes a long way towards a proof of the monotonic increase with $$n$$ of $$P_n(\delta)$$, although some further estimation of the error in the asymptotics is needed to complete the proof. I am surprised by the fact that the large-$$n$$ asymptotics is so accurate already for $$n=4$$.

• You claim this is increasing in n?
– user31317
Jun 18 '16 at 20:28
• This isn't working because you don't control the error uniformly in $n$ (if it were, it would imply that $P\to\infty$ as $n\to\infty$). Jun 18 '16 at 20:40
• Still there is a problem
– user31317
Jun 18 '16 at 21:39
• So if $n \to \infty$, $P_n(\delta)$ goes to $\infty$ for any $\delta$ close to zero unless $\delta$ depends on $n$. Also can you show $C_n>0$ for all $n,\delta$?
– user31317
Jun 19 '16 at 22:32
• for $n\rightarrow\infty$ the function $P_n(\delta)\rightarrow 1$ for all $\delta\in(1/2,1)$. Since this has to happen for $\delta$ arbitrarily close to $0$, the slope $P'_n(0)\rightarrow\infty$ for $n\rightarrow\infty$, and the sinc integral shows that in fact it goes to infinity as $\sqrt n$. Jun 20 '16 at 6:19