REVIEW 1 major objections 3 minor 8 references
Permutations avoiding a pattern of length three under Mallows distributions
T0 review · 1 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper proves that avoiding 123 under Mallows(q<1) has probability q^{n^2/4+o(n^2)} and that 132 and 213 decay exponentially at rate 1-q.
desk verdict New, correct asymptotics for Mallows pattern avoidance; Theorem 4's explicit bounds need a small proof patch. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the online construction of a Mallows permutation: at step $j$, place $j$ with $X_j$ geometric($1-q$) truncated to $\{0,\dots,j-1\}$ numbers to its right. This converts the inversion weight into an independent product, and pattern avoidance is read off from inequalities among the $X_j$; for $123$, avoidance forces the non-maximal $X_j$ values to form a strictly increasing sequence. For $312$ and $231$, the avoidance probabilities satisfy a convolution recursion that, after multiplying by $w_n=\prod_{l=1}^n(1-q^l)$, gives a generating function $G_q$ obeying the $q$-difference equation $G_q(t)=1/(1-(1-q)tG_q(qt))$; its radius of convergence yields the exponential rate. A subadditivity argument, using that the induced blocks of a Mallows permutation are independent Mallows permutations, guarantees the exponential rate exists for every length-three pattern.
What would settle it
Fix $q=1/2$ and compute the weighted count of $123$-avoiding permutations exactly by dynamic programming over inversion counts for $n$ up to a few hundred; Theorem 1 predicts $(1/n^2)\log P^q_n(S_n(123))\to \frac14\log q\approx -0.1733$. Drift away from that value would falsify the theorem. The companion check for $132$ is $(1/n)\log P^q_n(S_n(132))\to \log(1-q)\approx -0.6931$.
Extended reading notes
Core claim
The central claim is that under Mallows($q$) with $q\in(0,1)$, the asymptotic avoidance probability splits sharply by pattern. Theorem 1 gives $\lim_{n\to\infty}(P^q_n(S_n(123)))^{1/n^2}=q^{1/4}$, so $P^q_n(S_n(123))=q^{n^2/4+o(n^2)}$: a $123$-avoider is super-exponentially rare. Theorem 2 gives $\lim_{n\to\infty}(P^q_n(S_n(132)))^{1/n}=\lim_{n\to\infty}(P^q_n(S_n(213)))^{1/n}=1-q$, the slowest possible exponential decay since the identity permutation alone contributes a $(1-q)^n$ lower bound. For $312$ and $231$, the paper proves the rate is $1/r(q)$, where $r(q)$ is the radius of convergence of the generating function $G_q(t)=\sum_n w_n P^q_n(S_n(312))t^n$ satisfying $G_q(t)=1/(1-(1-q)tG_q(qt))$, and Theorem 4 bounds this rate explicitly. It also proves $P^q_n(S_n(312))=P^q_n(S_n(231))>P^q_n(S_n(213))=P^q_n(S_n(132))$ for all $n\ge3$, and the duality $q\leftrightarrow 1/q$ transfers the results to $q>1$ with $123$ as the exceptional pattern.
Load-bearing premise
The explicit upper and lower bounds for the $312/231$ decay rate are valid only if the threshold coming from inequality (5.6) is the smallest of the three candidate thresholds (5.1), (5.2), and (5.6); the paper states this ordering without proof.
Editorial extensions
If this is right
- For $q<1$, the expected number of $123$-avoiders among $n$ independent Mallows($q$) permutations is asymptotic to $q^{n^2/4}$; one needs roughly $q^{-n^2/4}$ samples to see one.
- For $132$ and $213$, the rate $1-q$ is the minimal possible, so these patterns are only exponentially rare, markedly more common than $123$-avoiders.
- For $312$ and $231$, the rate is computable numerically by iterating the functional equation; the explicit bounds in Theorem 4 differ by less than $0.01$ for $q\le0.5$.
- By parameter duality, for $q>1$ the results carry over to every pattern except $123$.
Reading between the lines
- The $q^{1/4}$ constant for $123$ is probably the first member of a family: avoiding $12\cdots k$ under Mallows($q$) should decay like $q^{c_k n^2}$ with $c_3=1/4$; a transfer-matrix computation for $k=4,5$ could test this.
- Theorem 1 leaves the subexponential prefactor open; extracting it would tie the proof to known large-deviation results for geometric order statistics and the longest increasing subsequence in Mallows permutations.
- The unproved ordering claim behind Theorem 4 can be checked by directly comparing the closed forms in (5.1), (5.2), and (5.6) for all $q$; if it fails, the characterization by $1/r(q)$ would survive but the explicit bounds would need replacement.
- The table's 'true values' are numerical, not proven; a worthwhile target is a proof that the $312/231$ rate is monotone or has a closed form.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the probability that a random permutation of size n drawn from the Mallows(q) distribution avoids a fixed pattern τ ∈ S3, with q ∈ (0,1). Using the online construction of Mallows permutations, subadditivity, and a generating-function analysis, the author proves that the probability of avoiding 123 decays like q^{n^2/4} in the n^2-exponential scale (Theorem 1), that the probabilities for 132 and 213 decay with exponential rate exactly 1−q (Theorem 2), and obtains a functional equation for the generating function relevant to 312/231 (Proposition 5). Theorem 3 translates finite nested inequalities into lower and upper bounds on the exponential rate, and Theorem 4 gives explicit closed-form lower and upper bounds LB(q) and UB(q) for the 312/231 rate. A duality argument extends the results to q>1 for patterns other than 123.
Significance. The results are substantial and novel. The exact n^2-exponential rate for 123-avoidance under Mallows(q) is a striking super-exponential decay, and Theorems 1 and 2 complement the Stanley–Wilf picture for non-uniform random permutations. The derivations are self-contained, rely on standard tools (online construction, subadditivity, generating functions), and involve no fitted parameters; the numerical 'true values' in the table are computed from the derived functional equations. The main gap concerns the proof of Theorem 4's explicit bounds, which is local and fixable.
major comments (1)
- [Section 5, proof of Theorem 4] The upper-bound derivation requires c to be simultaneously smaller than the right-hand sides of (5.1), (5.2), and (5.6), because the case analysis reaches (5.5) only when c < (5.1) and c < (5.2). The paper states without proof that 'One can show that the right hand side of (5.6) is the smallest of the three.' If this ordering fails for some q ∈ (0,1), then choosing c equal to the right-hand side of (5.6) does not satisfy the hypotheses, and the claimed upper bound UB(q) in (1.21) does not follow from the preceding argument. The same section also asserts, without proof, that the right-hand side of (5.4) is the smallest threshold for the lower bound; that particular ordering claim is not needed for the validity of the lower bound (since c satisfying any one of (5.1), (5.2), or (5.4) suffices), but it should be justified or removed. Please supply the missing ordering proof by elementary algebra, or adjust the statement of Theorem 4 to use a c whose validity is demonstrated.
minor comments (3)
- [Section 7, around (7.1)] The assertion that P^q_{n−⌊n^α⌋}(σ'_1=i_1,...,σ'_m=i_m) is maximized over 1≤i_1<...<i_m≤n−⌊n^α⌋ at {i_1,...,i_m}={1,...,m} is stated as 'readily' without proof. A short argument using the inversion count (the set {1,...,m} minimizes the number of inversions with the complement) would make the proof self-contained.
- [Section 7, equation (7.2)] The notation B^c_{n,ε} in (7.2) appears to be a typo for B^c_{n,α}, since the event B_{n,α} was defined just above.
- [Table after Theorem 4] The 'true value' row in the table contains only four entries (presumably for q=0.1, 0.2, 0.3, 0.4), while the table has columns up to q=0.9. Please clarify which values the 'true value' row refers to and why it is omitted for larger q.
Circularity Check
No circularity: all results follow from the definition of the Mallows distribution, the online construction, and self-contained recurrences; no fitted parameters or load-bearing self-citations.
full rationale
The paper is a self-contained mathematical derivation. Theorem 1 is proved by expressing the event of avoiding 123 in terms of the geometric random variables X_j in the online construction, then deriving two-sided bounds via direct estimates of P(X_i1 < ... < X_im); the target limit q^{1/4} is obtained from those bounds, not assumed. Proposition 4 derives exact recurrences for the avoiding probabilities by decomposing according to the position of 1; these recurrences are combinatorial consequences of the online construction and the Mallows definition. Proposition 5 obtains the functional equation G_q(t) = 1/(1 - (1-q)t G_q(qt)) algebraically from that recurrence, and Theorem 3 only translates the functional equation into convergence-radius comparisons. Theorem 4 is an application of Theorem 3 with explicit inequalities. The phrases 'It turns out' and 'One can show' in Section 5 indicate unproved ordering comparisons among candidate bounds; if those comparisons fail, the explicit constants in Theorem 4 would not be justified, but this is a rigor gap, not circularity, because the bounds are not used to define or fit the quantity being estimated. The numerical 'true values' in the table are computed from the paper's own functional equation for large N and are not used as inputs to any theorem. The cited literature includes standard external sources such as Bhatnagar-Peled, Gladkich-Peled, Marcus-Tardos, and Stanley; the only reference to the author's group is [6], which concerns the excluded 321 case and is not load-bearing for any proved result. No parameter is fitted to a subset of data, no known result is merely renamed, and no load-bearing premise is justified only by a self-citation. Accordingly, the derivation is not circular.
Assumptions & free parameters
assumptions (3)
- standard math The number of permutations of length n avoiding any length-three pattern is the Catalan number C_n.
- domain assumption The restrictions of a Mallows(q) permutation to disjoint intervals are independent and each has a Mallows distribution with the same q.
- standard math Fekete's sub-additive lemma: for a sub-additive sequence {a_n}, lim a_n/n exists.
Cite this review
Pith. "Pith review of Permutations avoiding a pattern of length three under Mallows distributions." pith.science (2026). https://pith.science/paper/MHBQPE2Y
@misc{pith2026190801382,
author = {Pith},
title = {Pith review of: Permutations avoiding a pattern of length three under Mallows distributions},
year = {2026},
howpublished = {\url{https://pith.science/paper/MHBQPE2Y}},
note = {Machine review of arXiv:1908.01382}
}
abstract
We consider permutations avoiding a pattern of length three under the family of Mallows distributions. In particular, for any pattern $\tau\in S_3-\{321\}$, we obtain rather precise results on the asymptotic probability as $n\to\infty$ that a permutation $\sigma\in S_n$ under the Mallows distribution with parameter $q\in(0,1)$ avoids the pattern. By a duality between the parameters $q$ and $\frac1q$, we also obtain rather precise results on the above probability for $q>1$ and any pattern $\tau\in S_3-\{123\}$.
Figures
Reference graph
Works this paper leans on
-
[1]
and Peled, R., Lengths of monotone subsequences in a Mallows per- mutation, Probab
Bhatnagar, N. and Peled, R., Lengths of monotone subsequences in a Mallows per- mutation, Probab. Theory Relat. Fields 161 (2015), 719-780
work page 2015
-
[2]
Combinatorics of Permutations , Chapman & Hall/CRC, Boca Raton, FL, (2004)
Bona, M. Combinatorics of Permutations , Chapman & Hall/CRC, Boca Raton, FL, (2004)
work page 2004
-
[3]
Crane, H. and DeSalvo, S., The probability of avoiding consecutive patterns in the Mallows distribution , Random Structures Algorithms 53 (2018), 417-447
work page 2018
-
[4]
and Peled, R., On the cycle structure of Mallows permutations , Ann
Gladkich, A. and Peled, R., On the cycle structure of Mallows permutations , Ann. Probab. 46 (2018), 1114–1169
work page 2018
-
[5]
and Tardos, G., Excluded permutation matrices and the Stanley-Wilf conjecture, J
Marcus, A. and Tardos, G., Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), 153–160
work page 2004
-
[6]
Panzo, H., (private correspondence)
-
[7]
Rabinovitch, P., Uniform and Mallows Random Permutations: Inversions, Leve ls and Sampling , Thesis (Ph.D.) Carleton University (Canada). 2012. 91 pp. , ProQuest LLC
work page 2012
-
[8]
Stanley, R. P., Enumerative Combinatorics. Volume 1 , 2nd ed., Cambridge Studies in Advanced Mathematics 49. Cambridge Univ. Press, Cambridge. Department of Mathematics, Technion—Israel Institute of T echnology, Haifa, 32000, Israel Email address : pinsky@math.technion.ac.il URL: http://www.math.technion.ac.il/~pinsky/
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.