Let $a$ be an arbitrary sequence and denote by $\mbox{gap}\_k(a) = a\_{(k)} - a\_{(k+1)}$, where $a\_{(k)}$ is the $k$th largest component of $a$. Of course, $k+1$ should be no larger than the length of $a$. Let $b$ be an arbitrary sequence with the same length as $a$. I would like to prove or disprove
$$\mathbb{E} \mbox{gap}\_k(\sigma(a) + b) \geq \mbox{gap}\_k(a),$$
where $\sigma(\cdot)$ is a uniform permutation operator.



Monotonicity of the gap of permutated sequence
It is not necessarily true. Set $a=(0,3,4)\;$ and $b=(0,0,2).$ Then possible sequences of the form $\sigma(a)+b\;$ (reordered) are $(0,3,6),$ $(0,4,5)\;$ and $(2,3,4),\;$ so 
$$
 \mathop{\mathbb E}\mathop{\rm gap}\nolimits\_2(\sigma(a)+b)=\frac83
 <3=\mathop{\rm gap}\nolimits\_2(a).
$$


