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.

  • $\begingroup$ Thanks, I think that set of notes is exactly the sort of thing I was looking for. $\endgroup$ – Joe Bebel Feb 10 '13 at 11:14

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.