Non-enumerative proof that there are many simple permutations?

Question

Terence Tao asked for a non-enumerative proof that a positive proportion of permutations are derangements and got a great answer. Inspired by this, I'd like to ask about another family of permutations.

An interval in the permutation $\pi$ (thought of in one-line notation) is a contiguous sequence of entries which is also contiguous in value. For example, the entries $43$ form an interval in the permutation $514362$. Every permutation of length $n$ has trivial intervals of lengths $0$, $1$, and $n$, and permutations with only these trivial intervals are (sometimes) called simple.

Like fixed points, it can be shown that the number of nontrivial intervals in a random permutation is Poisson distributed (see this paper by Corteel, Louchard, and Pemantle), although unlike fixed points, the expected number of nontrivial intervals in a random permutation is $2$. It follows that (in the limit) the proportion of simple permutations is $1/e^2$.

Is there a "non-enumerative" proof that a positive proportion of permutations are simple?

Answer 1

I think the main idea of Brendan McKay's answer to Terence Tao's question still works. It's a bit more complicated (and less non-enumerative), but still "robust" in the sense of Tao's question.

First one should somehow "estimate away" those permutations that have an interval of length 3 or more. The proportion of such permutations is only $O(1/n)$.

Then, since the average number of intervals of length 2 is 2, it suffices to show that (i) there can't be many more permutations with 1 interval than with none, and (ii) there can't be many more permutations with 2 intervals than with 1.

There is a variety of ways to define a "switching operation" that provides (up to a $O(1/n)$ error) the necessary comparisons. For instance, consider the operation of taking a symbol that belongs to an interval of length 2 and switching it with the first symbol. The inverse operation is to look at the first symbol (say $i$), and switch it with a neighbor of $i-1$ or $i+1$.

For a permutation with $k$ intervals (of length 2 and disjoint), there are (in general) $2k$ ways of performing the "interval destroying" operation, and, regardless of $k$, 4 ways of performing the "interval creating" inverse. Taking $k=1$ this shows that asymptotically there are only twice as many permutations with one interval as with none, and with $k=2$ it shows that there are roughly as many permutations with two intervals as with one.