most recent 30 from http://mathoverflow.net 2013-05-25T14:33:18Z http://mathoverflow.net/feeds/user/8846 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120163/concentration-bounds-for-sums-of-random-variables-of-permutations Joe Bebel 2013-01-29T00:28:51Z 2013-01-29T20:57:02Z

<p>I'm trying to find theorems regarding random variables derived from sampling permutations, specifically concentration bounds.</p> <p>As an example, let $X_i$ be the <code>$\{0,1\}$</code>-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 <code>$\{1, \ldots, m\}$</code> to itself) </p> <p>Note that then the $X_i$ are identically distributed, but not independent, because each $X_i$ essentially 'samples without replacement' from the set <code>$\{1,\ldots,m\}$</code></p> <p>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.</p> <p>More generally, given some set of functions <code>$f_i: S_m \rightarrow \{0,1\}$</code>, let $Y_i$ be a <code>$\{0,1\}$</code>-random variable that represents whether a uniformly random permutation $\sigma \in S_m$ has $f_i(\sigma) = 1$. </p> <p>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] &lt; 1/c$) that we can get some kinds of concentration bound for $Y_1 + \ldots + Y_n$</p> <p>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 Chebychev's inequality. </p> <p>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).</p> <p>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?</p> <p>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.</p>

http://mathoverflow.net/questions/120163/concentration-bounds-for-sums-of-random-variables-of-permutations/120165#120165 Joe Bebel 2013-02-10T11:15:10Z 2013-02-10T11:15:10Z

Thanks, I didn't think about exchangeability when I considered the problem.

http://mathoverflow.net/questions/120163/concentration-bounds-for-sums-of-random-variables-of-permutations/120257#120257 Joe Bebel 2013-02-10T11:14:21Z 2013-02-10T11:14:21Z

Thanks, I think that set of notes is exactly the sort of thing I was looking for.