On large deviations for combinatorial sums (Q2059423)

Suppose that \(\{(X_{n,i,j})_{1\leq i,j\leq n}\}_{n}\) is a sequence of matrices of independent random variables, and that \((\pi_n(1),\ldots,\pi_n(n))\) is a uniformly chosen permutation of the integers \(1,\ldots,n\). The author considers large deviations for (a suitably normalized version of) the combinatorial sum \(S_n=\sum_{i=1}^nX_{n,i,\pi_n(i)}\) under some Bernstein-type conditions. The main result of the present paper is a regime in which it is shown that the tail probabilities of \(S_n\) are asymptotically (i.e., as \(n\to\infty\)) equal to those of a Gaussian distribution. The range of values for which this holds can be of power order.