Random permutations of Z_n In "The maximum number of Hamiltonian paths in tournaments" by Noga Alon, 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?
 A: 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$.
A: 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,\dotsc,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 arborescences, 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.

The paper by Bill Cuckler is Hamiltonian Cycles in Regular Tournaments.
