Deviation of sum of highest values Suppose that $n$ random variables are drawn uniformly and independently from $[0,1]$. We know from Chernoff that the probability that their sum is greater than $\frac12n(1+\varepsilon)$ is exponentially small in $n$.
What about the sum of the highest $n/2$ values from among these $n$ values? The expected value is close to $\frac38n$ (when $n$ is large). Is the probability that this sum is greater than $\frac38n(1+\varepsilon)$ also exponentially small in $n$?
 A: This is true, and all you need is Cramer's large deviation principle. Let your iid uniform variables be $\mathbb X = \{X_k,k= 1,\dots,n\}$, First note for any $\delta>0$, the probability that less than $n/2$ numbers from $\mathbb X$ are greater than $(1-\delta)/2$ is exponentially small. Therefore, the probability that the sum of $n/2$ largest numbers from $\mathbb{X}$ exceeds $3(1+\varepsilon)n/8$ is at most the probability that the sum of all numbers from $\mathbb{X}$ larger than $(1-\delta)/2$ exceeds $3(1+\varepsilon)n/8$, plus some exponentially small term. 
The last one you can rewrite as
$$
\frac1n\sum_{k=1}^n X_k \mathbf{1}_{X_{k}>(1-\delta)/2}>\frac{3}8(1+\varepsilon).\tag{1}
$$
Note that
$$
\mathsf{E} [X_1 \mathbf{1}_{X_{1}>(1-\delta)/2}] = \frac12\left(1-\Big(\frac{1-\delta}2\Big)^2\right)<\frac{3}{8}(1+\varepsilon)
$$
for small enough $\delta$. Therefore, $(1)$  has exponentially small probability for small $\delta$ due to Cramer's LDP (applied to $\{X_k\mathbf{1}_{X_{k}>(1-\delta)/2},k=1,\dots,n \}$). 
A: There's an alternative version of Chernoff's inequality known as McDiarmid's inequality (based off of Azuma's martingale inequality) that is applicable here.  Basically the inequality says that if you have a function of $n$ independent variables which is "bounded in single coordinate differences" (changing one variable while leaving the others fixed can only change the function by a constant), then you have similar guarantees to the Chernoff bounds.  
Since changing a single term can affect the sum of the largest $n/2$ variables by at most $1$, this immediately gives an exponential bound.  
