Probability – Sum of Uniform Independent Random Variables

pr.probabilityprobability distributions

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.

Best Answer

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.

Related Question