Unimodality conjecture for pattern occurrences in Mallows permutations

Full proof, with strict log-parameter concavity and an exact characterization of the maximum.

Let $\pi\in S_k$, put $s=\operatorname{inv}(\pi)$, and write

$$Z_k(p)=\sum_{\tau\in S_k}p^{\operatorname{inv}(\tau)} =\prod_{j=1}^k(1+p+\cdots+p^{j-1}).$$

The consecutive-homogeneity property of the Mallows distribution gives, at every position $i$,

$$\mathbb P_p\!\left( \operatorname{pat}(\sigma(i),\ldots,\sigma(i+k-1))=\pi \right)=\frac{p^s}{Z_k(p)}.$$

Indeed, condition on the set of values occupying this consecutive block and on the entire outside configuration. Every outside position lies wholly to the left or right of the block, so the cross-block inversion count depends only on its set of values, not on their internal ordering. The conditional weight of each internal relative ordering $\tau$ is therefore proportional to $p^{\operatorname{inv}(\tau)}$.

Summing over the $n-k+1$ possible positions yields

$$\mathbb E_{n,p}(\pi) =(n-k+1)\frac{p^s}{Z_k(p)}. \tag{1}$$

This exact expectation is already contained in Crane, DeSalvo, and Elizalde, The probability of avoiding consecutive patterns in the Mallows distribution, Theorem 8.1, equation (33). The remaining issue in the present conjecture is unimodality as the parameter varies.

For $p>0$, set $\theta=\log p$, and let $I$ be the inversion count of a Mallows permutation of length $k$ at parameter $e^\theta$. Differentiating (1) gives

$$\frac{d}{d\theta} \log\mathbb E_{n,e^\theta}(\pi) =s-\mathbb E_\theta[I],$$

and, more strongly,

$$\frac{d^2}{d\theta^2} \log\mathbb E_{n,e^\theta}(\pi) =-\operatorname{Var}_\theta(I)<0 \qquad(k\ge2). \tag{2}$$

The variance is strictly positive because both the identity and a permutation with one inversion have positive probability at every finite $\theta$. Thus the expectation is strictly log-concave as a function of $\log p$.

Writing $K=\binom{k}{2}$, the mean $\mathbb E_\theta[I]$ increases continuously and strictly from $0$ to $K$. Therefore:

• If $0<s<K$, there is a unique maximizer $p_s>0$, characterized by $\mathbb E_{p_s}[I]=s$; the expectation strictly increases before $p_s$ and strictly decreases afterwards.
• If $s=0$, the expectation strictly decreases and attains its maximum at $p=0$.
• If $s=K$, it strictly increases and tends to $n-k+1$ as $p\to\infty$.
• For $k=1$ the expectation is constant; if $n<k$, it is identically zero.

This proves the conjecture for every consecutive pattern, every $n$, and the entire parameter range $p\in[0,\infty)$.

Source: Bevan and Threlfall, Thresholds for Patterns in Random Permutations with a Given Number of Inversions, Electronic Journal of Combinatorics 31(4) (2024), Conjecture 28.