Random permutations of Z_n - MathOverflow

Random permutations of Z_n

2011-02-02T02:15:19Z

In http://www.springerlink.com/content/y19u81675243r237/fulltext.pdf, the author states the following without proof (equation 3.1):

"Consider a random permutation $\pi$ of $\mathbb{Z}_n$. What is the probability that $\pi(i+1)−\pi(i) \mod{n} < n/2$ for all $i$?"

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.

Does anyone know of a complete proof?

Answer by Louigi Addario-Berry for Random permutations of Z_n

2011-02-02T15:26:32Z

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.

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.

To count those you use the so called BEST theorem 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.)

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 paper by Bill Cuckler about that in CPC 2007). Hope this makes sense, please feel free to mention whatever you see fit in Mathoverflow.

Answer by GH for Random permutations of Z_n

2011-02-03T10:12:15Z

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}$.

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}$.

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}$.

Of course this does not explain why (3.1) in Noga Alon's paper holds. This is a statement about random cyclic permutations $\pi$ satisfying $\pi(i+1)−\pi(i) \mod{n} < n/2$ for all $i$.