# Bound on probabilities of the sum of uniform order statistics

Let $X_1,...,X_n$ be i.i.d. random variable with a uniform distribution on [0,1]. Denote by $X_{(1)}\leq X_{(2)} \leq \ldots \leq X_{(n)}$ their order statistics.

Given $k\geq 1$ and $u\in[0,k]$, I want a simple formula for $$p_k(u):=\mathbb{P}[X_{(1)}+\ldots + X_{(k)}\leq u],$$ or at least a simple lower bound on $p_k(u)$. (By simple, I mean that I don't want a k-dimensional integral...)

Note: Of course, the case $k=1$ is easy: $$p_1(u) = 1-(1-u)^n.$$ And, by using the representation $$U_{(1)},U_{(2)} = 1-Y^{1/n},1-Y^{1/n}Z^{1/(n-1)},$$ where $X,Y$ are iid $\sim U([0,1])$, I was able to compute $p_2(u)$ (with the help of Maple): $$p_2(u) = 1-2(1-\frac{u}{2})^n+ \big(\max(1-u,0)\big)^n$$

• First, no motivation of the problem is done, Second, your $p_2(u)$ seems to be wrong: both Mathematica dropbox.com/s/1q4ls7jrngmlwqu/OrderStatistic.pdf?dl=0 and Maple dropbox.com/s/5q0inmikpqh40cv/CDF.pdf?dl=0 produce $\frac {17267}{32256}$ for $n=5,u=\frac 1 2$, whereas your formula performs $\frac {285}{512}$. – user64494 Oct 28 '17 at 19:10
• @user64494 I haven't looked at your Maple work, but your Mathematica working is incorrect: this is because it is incorrect to treat your $x$ as the 1st order statistic and your $y$ as the second order statistic ... you need the JOINT pdf of the 1st and 2nd order statistics. The OP's result seems correct to me, and very neatly stated too. – wolfies Oct 29 '17 at 5:06
• @wolfes: Can you base your "this is because it is incorrect to treat your xx as the 1st order statistic and your yy as the second order statistic ... you need the JOINT pdf of the 1st and 2nd order statistics"? TIA. – user64494 Oct 29 '17 at 6:39
• @user64494 We are interested in the joint pdf of $(X_{(1)}, X_{(2)})$ -- not just the isolated pdf of say $X_{(1)}$ on its own, and $X_{(2)}$ on its own. This is because there is dependency between $X_{(1)}$ and $X_{(2)}$ which your model is not capturing. – wolfies Oct 29 '17 at 6:43
• @wolfes: Thank you. I got it, looking in en.wikipedia.org/wiki/Order_statistic . – user64494 Oct 29 '17 at 7:01

As pointed out by user63957, the conditional distribution of $T_k:=X_{(1)}+\ldots + X_{(k)}$ given $X_{(k+1)}=x$ is that of $xS_k$, where $S_k:=U_1+\dots+U_k$ and the $U_i$'s are iid random variables (r.v.'s) uniformly distributed on $[0,1]$. So, we have the key relation $$T_k\overset D=X_{(k+1)}S_k,$$ assuming that the $U_i$'s and hence $S_k$ are independent of $X_{(k+1)}$, where $\overset D=$ denotes the equality in distribution. So, the distribution of $T_k$ is the product-convolution of the distributions of $X_{(k+1)}$ and $S_k$. The cdf of $S_k$ is given by the Irwin--Hall formula: $$P(S_k\le x)=\frac1{k!}\sum_{j=0}^k(-1)^j\binom kj(x-j)_+^k$$ for real $x$, where $z_+:=0\vee z$ and $z_+^k:=(z_+)^k$. The distribution of $X_{(k+1)}$ is the beta one with parameters $k+1,n-k$. So, for $t>0$ we have \begin{align*} P(T_k\le t)&=\int_0^1 P(S_k\le t/y)P(X_{(k+1)}\in dy) \\ &=\frac1{k!}\sum_{j=0}^k(-1)^j\binom kj \int_0^1 (t/y-j)_+^k\frac{n!}{k!(n-k-1)!}y^k(1-y)^{n-k-1}dy \\ &=\frac{n!}{(k!)^2(n-k-1)!}\sum_{j=0}^k(-1)^j\binom kj J_{n,k,j}\big(t,(1-t/j)_+\big), \tag{1} \end{align*} where $(1-t/0)_+:=0$ and (using the substitution $y=1-x$) \begin{align*} J_{n,k,j}(t,u)&:=\int_u^1 (t-j+jx)^k x^{n-k-1}dx =\sum_{r=0}^k\binom kr(t-j)^{k-r}j^r \int_u^1 x^{r+n-k-1}dx \\ &=\sum_{r=0}^k\binom kr(t-j)^{k-r}j^r \frac{1-u^{r+n-k}}{r+n-k}.\tag{2} \end{align*} Thus, by formulas (1)--(2), the cdf of $T_k$ is expressed as a double sum of products of powers and binomial coefficients. In particular, for $k=1,2$ this yields the expressions obtained by the OP.

One can also obtain some asymptotics, as follows. Suppose that $k\wedge(n-k)\to\infty$. Then both $X_{(k+1)}$ and $S_k$ are asymptotically normal, and we have \begin{align*} T_k\overset D=X_{(k+1)}S_k&=\Big(\frac kn+(Z_1+o_P(1))\sqrt{\frac{k(n-k)}{n^3}}\Big) \Big(\frac k2+(Z_2+o_P(1))\sqrt{\frac{k}{12}}\Big) \\ &=\frac{k^2}{2n}+(Z_1+o_P(1))\frac k2\sqrt{\frac{k(n-k)}{n^3}} +(Z_2+o_P(1))\frac kn\sqrt{\frac{k}{12}} \\ &+(Z_1+o_P(1))(Z_2+o_P(1))O\Big(\frac kn\Big) \\ &\overset D=\frac{k^2}{2n}+(Z+o_P(1))\frac{k\sqrt k}{2n}\sqrt{\frac13+\frac{n-k}n}, \end{align*} where $Z_1,Z_2,Z$ are iid standard normal r.v.'s, and $o_P(1)$ denotes any r.v.'s $Y_{n,k}$ that go to $0$ in probability as $k\wedge(n-k)\to\infty$. We see that the distribution of $T_k=X_{(1)}+\ldots + X_{(k)}$ is concentrated near $\frac{k^2}{2n}$, which was easy to predict.

One can refine this asymptotics by using bounds on the errors of the normal approximations for $X_{(k+1)}$ and $S_k$.

If you condition on the value of X(k+1), then X(1)...X(k) with the labels "removed" or randomized are IID Uniform(0,X(k+1)). So you can use IID methods to bound the conditional probability, then integrate over the Beta distribution of X(k+1).

(More a comment that is too long for the comment box) ... Given a sample of size $n$ from a standard Uniform parent, one can show, by induction or otherwise, that the joint pdf of the first $k$ order statistics, is:

$$f(x_{(1)}, x_{(2)}, \dots, x_{(k)}) = \frac{n!}{(n-k)!}\left(1-x_{(k)}\right)^{n-k} \quad \quad \text{for }\quad 0 < x_{(1)} < x_{(2)} < \dots <x_{(k)} < 1$$

... which has a neat functional form.

Given joint pdf $f(x_{(1)}, x_{(2)}, \dots, x_{(k)})$, find the cdf of the sum $X_{(1)} + X_{(2)} + \dots + X_{(k)}$

... which unfortunately will result in a $k$-part piecewise solution with kinks at $(1, 2, \dots, k)$.

Using the mathStatica package for Mathematica, I obtained the same solution the OP provided for $k=2$, and was also able to derive a general exact solution for the sum in the $k = 3$ case (in 3 parts). However, an exact general solution seems to get messy quite rapidly.

To illustrate the behaviour of the cdf, here is a plot of the cdf of the sum in the $k =2$ case (as $n$ increases from 2 to 10, and then with $n =30$):

The intuition, of course, is that when $n$ becomes large, the first two order statistics become very small, and so the cdf of their sum shifts to the left.

Here is the $k=3$ case:

• Can you support your claims by Mathematica code? – user64494 Oct 29 '17 at 6:45
• Using the mathStatica package for Mma, define the parent pdf as say: f = 1; domain[f] = {x, 0, 1}; . Then, in the $k = 2$ case, the joint pdf of the first 2 order statistics is given by: g = OrderStat[{1, 2}, f], and the desired cdf is simply: Prob[$x_1 + x_2 < z, g$]. For the first 3 order statistics, it is: g = OrderStat[{1, 2, 3}, f] etc – wolfies Oct 29 '17 at 6:49
• Sorry, but the above is not any executed Mathematica code. You can present it through Dropbox, for example, as an exported PDF file.. – user64494 Oct 29 '17 at 7:04
• The above is all that is needed, other than the requisite software. – wolfies Oct 29 '17 at 7:07
• Thanks for this answer. I did not know that the joint distribution of the $k$ first order statistics had such a simple formula, that really helps. – guigux Nov 2 '17 at 22:00