Random permutations of Z_n - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T21:04:36Z http://mathoverflow.net/feeds/question/54051 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/54051/random-permutations-of-z-n Random permutations of Z_n Jeremy H 2011-02-02T02:15:19Z 2011-02-03T14:45:55Z <p>In <a href="http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf" rel="nofollow">http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf</a>, the author states the following without proof (equation 3.1):</p> <p>"Consider a random permutation $\pi$ of $\mathbb{Z}_n$. What is the probability that $\pi(i+1)−\pi(i) \mod{n} &lt; n/2$ for all $i$?"</p> <p>The claim is that this is $(2+o(1))^{−n}$, which makes sense and seems like it should be a standard argument. However, I have not been able to come up with a short proof, nor have I been able to find a proof in the literature.</p> <p>Does anyone know of a complete proof?</p> http://mathoverflow.net/questions/54051/random-permutations-of-z-n/54103#54103 Answer by Louigi Addario-Berry for Random permutations of Z_n Louigi Addario-Berry 2011-02-02T15:26:32Z 2011-02-03T14:45:55Z <p>I emailed Noga to ask him; here is his response (touched up slightly for MO; any errors in what I post are probably mine rather than Noga's). The only details not present are the required applications of Stirling's formula.</p> <blockquote> <p>As far as I recall the argument I had in mind was as follows (I am not trying to optimize the error term). Let $k$ be an even integer, much smaller than $n$ but much bigger than $\log n$, I guess $k=n^{0.01}$ or so should be ok. Split the set of vertices $[n]$ of the cyclic tournament to $k$ blocks of consecutive vertices, each of size $n/k$. Call the blocks $B_1,..,B_k$. We will count only Hamilton cycles in the tournament in which all edges go between distinct blocks, say from $B_i$ to $B_j$, with $j \lt i+k/2$ for each such edge, and with exactly $n/(k(k-2)/2)$ edges between each such pair of blocks.</p> <p>To count those you use the so called <a href="http://en.wikipedia.org/wiki/BEST_theorem" rel="nofollow">BEST theorem</a> to count the number of Euler circuits in the digraph on the $k$ vertices $B_1,\ldots,B_k$ with $n/(k(k-2)/2)$ directed edges from $B_i$ to $B_j$ for $i \neq j$, $j\lt i+(k-2)/2$ (and divide by $([n/(k(k-2)/2)]!)^{n/(k(k-2)/2)}$ to make sure all edges from B_i to B_j are considered the same.)</p> <p>In the BEST theorem ignore the determinant corresponding to the number of arborecences, which is not needed here (we are anyway only proving a lower bound) and is negligible. This gives $[(n/k-1)!]^{k}$ divided by the term above. Now this has to be multiplied by $[(n/k)!]^k$, because inside each block B_i we can decide on the order in which we take the $n/k$ vertices (we enter the block represented by a vertex $(n/k)$ times, so we can decide which vertex we enter in each such step). Now take the resulting product, use Stirling and choose the optimal $k$: this should give the claim (not sure with which error term). It may well be that some stronger lower bounds are known, and in fact I think that a similar bound holds for any regular tournament (I believe there is a <a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=721448" rel="nofollow">paper by Bill Cuckler about that</a> in CPC 2007). Hope this makes sense, please feel free to mention whatever you see fit in Mathoverflow.</p> </blockquote> http://mathoverflow.net/questions/54051/random-permutations-of-z-n/54178#54178 Answer by GH for Random permutations of Z_n GH 2011-02-03T10:12:15Z 2011-02-03T10:12:15Z <p>For odd $n$ the answer to your question (as stated!) can be found in Noga Alon's paper. Namely, the number of permutations in your question equals the permanent of an $n\times n$ matrix $A$ in which each row and each column has $(n-1)/2$ ones and $(n+1)/2$ zeros. Therefore $2/(n-1)*A$ is doubly stochastic, so by van der Waerden's conjecture (proved by Egorichev and Falikman in 1981) the requested probability is $\geq n!^{-1}((n-1)/2)^n n!/n^n=(1/e+o(1))2^{-n}$.</p> <p>For even $n$ the answer is similar. Then the number of permutations in your question equals the permanent of an $n\times n$ matrix $A$ in which each row and each column has $n/2$ ones and $n/2$ zeros. Therefore $2/n*A$ is doubly stochastic, so similarly as before the requested probability is $\geq n!^{-1}(n/2)^n n!/n^n=2^{-n}$.</p> <p>On the other hand, for all $n$ the considered permanent is $\ll \sqrt{n} n!/2^n$ by Noga Alon's main theorem in the paper, hence the requested probability is $\ll \sqrt{n}2^{-n}$.</p> <p>Of course this does not explain why (3.1) in Noga Alon's paper holds. This is a statement about random <strong><em>cyclic permutations</em></strong> $\pi$ satisfying $\pi(i+1)−\pi(i) \mod{n} &lt; n/2$ for all $i$.</p>