Anti-Concentration with respect to Random Permutations

Abstract

Classical anti-concentration results focus on the random sum $S := \sum _{i=1}^n \xi_i v_i$, where $\xi_i$ are independent random variables and $v_i$ are real numbers. In this paper, we prove new concentration results concerning the random sum $S := \sum_{i=1}^n w_{\pi _i } v_i$, where $w_i, v_i$ are real numbers and $\pi$ is a random permutation.