# Concentration bounds for sums of random variables of permutations

I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds.

As an example, let $$X_i$$ be the $$\{0,1\}$$-random variable that represents whether a uniformly random permutation $$\sigma \in S_m$$, has that $$\sigma(i)$$ is even (assuming permutations in $$S_m$$ are taken as bijections from $$\{1, \ldots, m\}$$ to itself)

Note that then the $$X_i$$ are identically distributed, but not independent, because each $$X_i$$ essentially 'samples without replacement' from the set $$\{1,\ldots,m\}$$

Then it's easy to see that (say) for $$n = \frac{m}{2}$$, $$Pr[X_1 + X_2 + \ldots + X_n = n] = \frac{n!}{m!}$$ which is asymptotically small.

More generally, given some set of functions $$f_i: S_m \rightarrow \{0,1\}$$, let $$Y_i$$ be a $$\{0,1\}$$-random variable that represents whether a uniformly random permutation $$\sigma \in S_m$$ has $$f_i(\sigma) = 1$$.

Then it seems plausible, given some reasonable conditions on the $$f_i$$ (for example, maybe $$Pr[Y_i = 1] = 1/c$$ for some constant $$c$$, or $$Pr[Y_i + Y_j = 2] < 1/c$$) that we can get some kinds of concentration bound for $$Y_1 + \ldots + Y_n$$

The best I can think of is to use the above two conditions on the $$f_i$$'s to calculate the expected value and variance of $$Y_1 + \ldots + Y_n$$ then invoke Chebyshev's inequality.

However, I can't believe that there's not some additional conditions that would lead to a better bound. Considering the "$$\sigma(i)$$ is even" example above, even though the variables are not mutually independent (or even pairwise independent) we still have that $$X_1 + \ldots X_n$$ is strongly concentrated around its expectation (in some vague sense).

Is there some way to interpret random variables like $$X_1, \ldots, X_n, Y_1, \ldots, Y_n$$, as 'nice' samples of a permutation distribution, as retaining some of the properties of independence that might lead to concentration?

This isn't my area so I might not be asking in the best way, so part of my question is also "what's the right way to ask this question?" :) Thanks a lot.

One useful trick that comes in handy sometimes (I originally saw it in this paper of Talagrand, though it may go further back): We can view a random permutation in $S_n$ as being generated as follows: Start with the identity permutation, and successively perform transpositions of the form $(n, a_n)$, then $(n-1, a_{n-1})$, and so on down to $(2, a_2)$, where each $a_j$ is uniformly chosen from the numbers between $1$ and $j$ (with no transposition if $a_j=j$).
The point is that the $a_j$ are now independent. So if we have a situation where each individual $a_j$ has little impact on the sum of the $X_i$ or $Y_i$, then we can apply concentration bounds for independent variables. For example, changing an individual $a_j$ only impacts at most $3$ positions in the final permutation (whereever $j$, the old $a_j$, and the new $a_j$ end up), changing an individual $a_j$ can only change $X_1+\dots+X_n$ by $3$ (or at most $1$, if you're more careful), so McDiarmid's inequality immediately gives exponential concentration on the sum.
Note that the variables $X_i$ can be permuted without changing their statistics. There is a paper by Persi Diaconis that discusses this situation. Essentially one has bounds on the distance from the distribution of IID variables: what that means for concentrations specifically I do not know.