# Tag Info

Here is a quick argument showing that $P(\mathbf{md}(\pi)>m)\le Ce^{-cm}$ though I'll not try to make the bounds sharp. Let us consider $n$ independent random variables $X_k$ uniformly distributed on $[0,1]$. The rearrangement $\pi$ will be determined from that model as $\pi(k)=\#\{i\in[n]:X_i\le X_k\}$. Clearly, we have all orderings of $X$ equally ...
It seems that this is a lower bound of $\Omega(n^2)$. Take an $n$ and an $a=\Theta( n)$ coprime with $n$ (with $a<n/2$). Then the permutations $\sigma=(12\dots n)$ and $\tau=(1, a+1)$ generate $S_n$. On the other hand, all residues modulo $n$ form a cycle where the neighbors differ by $a$. The only way to change this cyclic order is to apply $\tau$. ...