In "[The maximum number of Hamiltonian paths in tournaments](https://doi.org/10.1007/BF02128667)" 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?



Random permutations of Z_n
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](https://en.wikipedia.org/wiki/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](http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=721448) 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](https://doi.org/10.1017/S0963548306008170).


