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.



Concentration bounds for sums of random variables of permutations
One useful trick that comes in handy sometimes (I originally saw it in [this paper](http://arxiv.org/pdf/math/9406212.pdf) 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](http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/#more-3243) immediately gives exponential concentration on the sum. 


