3
$\begingroup$

Assume we draw $n$ numbers uniform i.i.d. from $[0,1]$, and let the least $k$ of them be $x_1,\dots,x_k$. It is well-known that their expectations are $\frac{1}{n+1},\dots,\frac{k}{n+1}$, so the expectation of their sum is $\frac{k(k+1)}{2(n+1)}$. But is there a concentration bound saying that, with high probability as $n\rightarrow\infty$, this sum doesn't exceed $\alpha\cdot\frac{k(k+1)}{2(n+1)}$ for some given parameter $\alpha$?

These $k$ variables are not independent, so we cannot apply Chernoff bound. I found a paper with a related title, but it is not easy to tell if something in there answers this question.

$\endgroup$
5
  • $\begingroup$ Do you view $k$ as fixed? $\endgroup$ Commented Feb 3 at 8:27
  • $\begingroup$ It could be fixed, but could also be a function of $n$. $\endgroup$
    – user139952
    Commented Feb 3 at 12:24
  • $\begingroup$ If $k$ and $\alpha$ are fixed and $n\to\infty$, the statement isn't true in fact. For example, the probability that $x_1$ exceeds $\alpha(k+1)/(2(n+1))$ converges to $e^{-\alpha(k+1)/2}$ -- in that case the sum $x_1+\dots+x_k$ certainly exceeds the given threshold. For $k\to\infty$, a useful approach may be that $x_{k+1}$ concentrates, and then conditional on $x_{k+1}$, the sum $x_1+ \dots+x_k$ has the same distribution as $x_{k+1}(U_1+\dots+U_k)$ where $U_i$ are i.i.d. $U[0,1]$, to which you can indeed apply Chernoff or whatever. $\endgroup$ Commented Feb 3 at 15:06
  • $\begingroup$ Can't you just do this as a calculus problem? The joint density of the order statistics is $n!$ where it is non-zero, so the probability that $x_1+\ldots +x_k\le b$ equals $n!$ times the volume of the region defined by this condition and $0\le x_1\le x_2\le \ldots \le x_n\le 1$. $\endgroup$ Commented Feb 3 at 15:34
  • $\begingroup$ More specifically, this gives $P(x_1+\ldots +x_k\le s)= \binom{n}{k}\int\ldots\int (1-t)^{n-k}\, dt_1\ldots dt_k$, where the integration is over $t_1+\ldots +t_k\le s$, and $t=\max t_j$. $\endgroup$ Commented Feb 3 at 15:44

1 Answer 1

1
$\begingroup$

$\newcommand{\ep}{\varepsilon}\newcommand{\de}{\delta}\newcommand{\D}{\overset{D}=}$Let $X_{n:1},\dots,X_{n:n}$ denote the order statistics in question. Fix any real $t>0$. You wanted to show that for natural $k\le n$ \begin{equation*} p_{n,k}:=P\Big(\sum_{j=1}^k X_{n:j} \ge(1+t)\frac{k(k+1)}{2(n+1)}\Big)\to0 \tag{10}\label{10} \end{equation*} as $n\to\infty$. As noted by James Martin, \eqref{10} will fail to hold unless $k\to\infty$.

So, we henceforth assume that $k\to\infty$ (and hence $n\to\infty$), and then we will show that \eqref{10} holds. Moreover, we will obtain an explicit upper bound on $p_{n,k}$, which goes to $0$ exponentially fast with $k$.

First here, consider the gaps \begin{equation*} G_i:=X_{n:i}-X_{n:i-1} \end{equation*} between the order statistics for $i=1,\dots,n+1$, where $X_{n:0}:=0$ and $X_{n:n+1}:=1$, so that \begin{equation*} X_{n:j}=\sum_{i=1}^j G_i \end{equation*} for $j=1,\dots,n$.

Next, recall that \begin{equation*} (G_1,\dots,G_{n+1})\D\frac{(Y_1,\dots,Y_{n+1})}{Y_1+\dots+Y_{n+1}}, \end{equation*} where $\D$ means the equality in distribution and $Y_1,\dots,Y_{n+1}$ are independent random variables each with the exponential distribution with mean $1$ -- see e.g. Exercise 20, page 103. So, \begin{equation*} \sum_{j=1}^k X_{n:j}=\sum_{j=1}^k \sum_{i=1}^j G_i =\sum_{i=1}^k (k-i+1)G_i\D\sum_{i=1}^k iG_i \\ \D\frac{\sum_{i=1}^k iY_i}{\sum_{i=1}^{n+1}Y_i}. \end{equation*} So, taking some $\ep\in(0,1)$ small enough so that \begin{equation*} \de:=(1+t)(1-\ep)-1>0, \tag{15}\label{15} \end{equation*} we see that \begin{equation*} p_{n,k}=P\Big(\frac{\sum_{i=1}^k iY_i}{\sum_{i=1}^{n+1}Y_i} \ge(1+t)\frac{k(k+1)}{2(n+1)}\Big)\le p_n+q_k, \tag{20}\label{20} \end{equation*} where \begin{equation*} p_n:=P\Big(\sum_{i=1}^{n+1}Y_i<(1-\ep)(n+1)\Big), \end{equation*} \begin{equation*} q_k:=P\Big(\sum_{i=1}^k iY_i\ge(1+\de)\frac{k(k+1)}{2}\Big). \end{equation*} Further, for any real $h>0$, by the Bernstein--Chernoff inequality, \begin{equation*} p_n=P\Big(\sum_{i=1}^{n+1}(1-Y_i)>\ep(n+1)\Big) \\ \le e^{-h\ep(n+1)}E\exp h\sum_{i=1}^{n+1}(1-Y_i) =\Big(\frac{e^{h(1-\ep)}}{1+h}\Big)^{n+1}. \end{equation*} The latter expression is minimized in $h$ when $h=\ep/(1-\ep)$, and then we get \begin{equation*} p_n\le p_{n,\ep}:=\big((1-\ep)e^\ep\big)^{n+1}; \tag{30}\label{30} \end{equation*} note that $p_{n,\ep}\to0$ exponentially fast with $n$, because $(1-\ep)e^\ep<1$.

Further yet, for any real $h\in(0,1/k)$, again by the Bernstein--Chernoff inequality, \begin{equation*} q_k\le\exp\Big\{-h(1+\de)\frac{k(k+1)}{2}\Big\} E\exp h\sum_{i=1}^k iY_i \\ =\exp\Big\{-h(1+\de)\frac{k(k+1)}{2}\Big\}\prod_{i=1}^k\frac1{1-hi}. \end{equation*} Note now that $g(u):=\frac1u\,\ln\frac1{1-u}$ is increasing in $u\in(0,1)$, from $g(0+)=1$. So, \begin{equation*} \frac1{1-u}=e^{g(u)u}\le e^{g(u_0)u} \tag{35}\label{35} \end{equation*} for $u\in(0,u_0]$, and \begin{equation*} g(u_0)<1+\de \end{equation*} if $u_0>0$ is small enough. So, letting now $h=u_0/k$ and using \eqref{35} with $u=hi$, we get \begin{equation*} q_k\le q_{k,\ep,u_0} :=\exp\Big\{-u_0(1+\de-g(u_0))\frac{k+1}{2}\Big\}, \tag{40}\label{40} \end{equation*} and $q_{k,\ep,u_0}\to0$ exponentially fast with $k$.

Collecting \eqref{20}, \eqref{30}, and \eqref{40}, we get \begin{equation*} p_{n,k}\le p_{n,\ep}+q_{k,\ep,u_0}, \end{equation*} and the latter upper bound on $p_{n,k}$ converges to $0$ exponentially fast with $k$. The optimal choice of the parameters $\ep,u_0$ (with $\de$ defined in \eqref{15}) depends on the value of $t>0$ in \eqref{10} and on how fast $k$ grows in relation with $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .