REVIEW 3 major objections 4 minor 20 references
Limit Theorems for the Length of the Longest Common Subsequence of Mallows Permutations
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Two independent Mallows permutations have an LCS obeying an L^p law near q=1 and a Gaussian law at fixed q.
desk verdict Proves the natural LCS analogues of the LIS limit theorems for Mallows permutations; the main results look right, but the abstract overclaims and there's a normalization slip to fix. 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 load-bearing object is Lemma 2.12, a domination coupling stated from the earlier paper [12]: for any increasing index set $a$ and any distribution $\nu$ on $S_k$, there are independent $X\sim\mu_{n,q}$, $Y\sim\nu$ and $Z\sim\mu_{n,q}$ with $\mathrm{LIS}(X_a,Y)\le \mathrm{LIS}(Z_a)$. This inequality converts every LIS upper bound for one Mallows permutation into an LCS upper bound for two permutations, yielding the uniform-integrability step and controlling the error sets in the block decomposition. The remaining machinery is the block decomposition into strips of length $\beta/(1-q)$ and, for Theorem 2, the regenerative process generated by two independent infinite Mallows insertion processes whose regeneration times are the first return times of the product chain $M_n=\max\{M_{n-1},Z_n\}-1$.
What would settle it
Search small cases exhaustively, e.g., $n=4$ or $5$, $0<q<1$, all increasing index sets $a$, and all distributions $\nu$ on $S_k$ by linear programming, for a violation of the inequality $\mathrm{LIS}(X_a,Y)\le\mathrm{LIS}(Z_a)$; a single violation would invalidate Lemma 2.12 and the proof of Theorem 1. Alternatively, simulate two independent Mallows permutations with $q_n=1-n^{-\alpha}$ for $\alpha\in(0,1)$, compute $\mathrm{LCS}(\pi_n,\tau_n)/(n\sqrt{1-q_n})$, and check whether the ratio approaches $\sqrt{6}/3$ as $n$ grows; a persistent downward trend would contradict Theorem 1.
Extended reading notes
Core claim
The central discovery is that the LCS of two independent Mallows permutations can be treated as a longest increasing subsequence (LIS) problem on a point set, and that LIS bounds for a single Mallows permutation can be transferred to the two-permutation setting. The key identity is $\mathrm{LCS}(\pi,\tau)=\mathrm{LIS}(\pi^{-1},\tau^{-1})$, after which Theorem 1 partitions $[n]$ into blocks of size $\beta/(1-q)$, proves the blockwise LIS contributions are close to i.i.d., and uses a domination coupling to control error terms; uniform integrability upgrades $L^1$ convergence to $L^p$ with the constant $\sqrt{6}/3$. Theorem 2 builds an infinite Mallows insertion process, defines regeneration times when both permutations have filled $[j]$, bounds the LCS between partial sums of i.i.d. block LCS variables, and derives finiteness of the first two moments of the inter-renewal times through a product Markov chain and Kac's formula; Anscombe's theorem then gives the Gaussian limit.
Load-bearing premise
The block argument of Theorem 1 rests on Lemma 2.12, imported from the earlier paper [12] and not proved here: for every increasing index set $a$ and every distribution $\nu$ on $S_k$, the LIS of a Mallows permutation against $\nu$ is dominated by the LIS of a single Mallows permutation on those indices. If that domination fails for some $\nu$, the uniform-integrability step and the $E_i,F_i$, and residual-block bounds collapse.
Editorial extensions
If this is right
- In the near-uniform regime, the random length $\mathrm{LCS}(\pi_n,\tau_n)$ is concentrated around $0.8165\, n\sqrt{1-q_n}$, with convergence in $L^p$ for every finite $p$, not merely in probability.
- At fixed $q,q'$, the LCS has Gaussian fluctuations with asymptotic mean $a(q,q')\,n$ and standard deviation $\sigma(q,q')\,\sqrt{n}$, where $a=\nu_{0,0}\,\mathbb{E}(Y_1)$ and $\sigma^2=\nu_{0,0}\operatorname{Var}(Y_1-aX_1)$.
- The regenerative representation makes the constants $a$ and $\sigma^2$ computable in principle from the stationary distribution of a simple one-dimensional product Markov chain.
- Sending $\beta\to\infty$ in the finite-$\beta$ weak law of [12] recovers the constant $\sqrt{6}/3$, since $2\bar{J}(\beta)/\sqrt{\beta}\to 1/\sqrt{6}$.
- The block argument implies that the block LCS variables are asymptotically i.i.d., so the LCS inherits the concentration behavior of the LIS rather than the slower fluctuations of i.i.d. random strings.
Reading between the lines
- The paper's abstract advertises two parameters $q,q'$ in the near-uniform regime, but Theorem 1 as stated requires $q_n=q'_n$; a genuine two-parameter $L^p$ law would need a two-parameter analogue of Lemma 2.12, which is not supplied here.
- If Lemma 2.12 were false, Theorem 1 might still be true, but the proof's uniform-integrability step and the $E_i,F_i,E'_i,F'_i$ bounds would need a different mechanism; the theorem and the lemma should not be conflated.
- The regenerative-CLT machinery suggests a testable extension: replacing the geometric insertion variables by other light-tailed discrete distributions should preserve Gaussian LCS fluctuations whenever the product chain has finite second moments.
- The constant $\sqrt{6}/3$ equals $2\bar{J}(\infty)/\sqrt{\infty}$, suggesting that $\bar{J}(\beta)$ may serve as a universal interpolation between the finite-$\beta$ and near-uniform regimes; one could conjecture that finite-$\beta$ corrections to the near-uniform law are governed by derivatives of $\bar{J}$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the longest common subsequence (LCS) of two independent Mallows-distributed random permutations. Theorem 1 states that if q_n in (0,1), q_n -> 1, and n(1-q_n) -> infinity, then for two independent Mallows(n,q_n) permutations, LCS/(n sqrt(1-q_n)) converges to sqrt(6)/3 in L^p for every p>0. Theorem 2 states that for fixed 0<q,q'<1, there exist constants a=a(q,q')>0 and sigma=sigma(q,q')>0 such that (LCS - a n)/(sigma sqrt(n)) converges in distribution to N(0,1). The proof of Theorem 1 reduces LCS to LIS through a coupling lemma (Lemma 2.12) quoted from the authors' earlier paper [12], then uses a block decomposition and a beta-regime weak law for LCS; the proof of Theorem 2 builds a regenerative process from two independent infinite Mallows permutations and applies a renewal central limit theorem.
Significance. If the results hold, they form a substantial advance: they provide the first weak law and CLT for the LCS of two non-uniform random permutations, with an explicit constant sqrt(6)/3 that is consistent with the beta-regime limit in [12] and with the LIS results of [2,3]. The regenerative CLT is conceptually clean and uses only finite second moments, and the constants are defined explicitly from the stationary distribution rather than fitted. The main risks are the heavy reliance on the external coupling lemma and internal normalization errors in the displayed derivation of the weak-law constant; both appear addressable in revision, so the central claims are plausible but not yet fully supported by the manuscript as written.
major comments (3)
- [Section 2.3, Lemma 2.12 and its uses] Lemma 2.12 is load-bearing but is quoted from [12] and not proved in this manuscript. It produces inequality (6), which is the only route transferring uniform integrability of |LIS(Z_n)/(n sqrt(1-q))|^p from [3] to the LCS, and it is invoked again in Lemma 2.13 for the E_i, F_i, and residual-block terms. If Lemma 2.12 fails in any of these applications, the block argument in Section 2.5 collapses. The lemma is stronger than the paper's own needs, since every application here takes nu to be a Mallows distribution; the authors should either reproduce a proof in an appendix or state and prove a Mallows-only version with nu = mu_{k,q}, and verify explicitly that (6), Lemma 2.13, and the uniform-integrability claim (30) are all covered.
- [Theorem 1 versus the abstract] The abstract claims a weak law in the two-parameter regime n(1-q) -> infinity and n(1-q') -> infinity, but Theorem 1 is stated only for a single sequence q_n used for both permutations. The proof in Sections 2.4 and 2.5 uses one parameter q throughout, and no reduction for q_n different from q'_n is supplied. Either Theorem 1 must be extended to independent Mallows(n,q_n) and Mallows(n,q'_n) with n(1-q_n) -> infinity and n(1-q'_n) -> infinity, or the abstract and introduction must be amended to state the single-parameter result that is actually proved.
- [Section 2.5, Eqs. (29)-(36)] As printed, the displayed normalization is internally inconsistent. The beta-regime result Theorem 3 gives X_1 / sqrt(beta(q)/(1-q)) -> 2 Jbar(beta), that is, sqrt((1-q)/beta(q)) X_1 -> 2 Jbar(beta). If Eqs. (29) and (31) are read with sqrt(1-q)/beta as displayed, then Eqs. (34)-(36) do not yield the stated factor 2 Jbar(beta)/sqrt(beta); if they are read with the intended sqrt((1-q)/beta), then Eq. (34) must display the 1/sqrt(beta) factor explicitly. The final constant sqrt(6)/3 is consistent with the intended normalization, but the displayed chain of equations leading to (32) must be corrected before the proof is verifiable.
minor comments (4)
- [Section 2.5, proof of Lemma 2.13] The displayed inequality 1 - 4 floor(a/(1-q)) >= 1 - 5a/(1-q) > q cannot hold as printed for q close to 1, because the right-hand side is negative. It should presumably be 1 - 4/floor(a/(1-q)) > q, which is the type of condition needed to apply Theorem 1.3 of [3]; please correct the expression.
- [Section 2.4, Eqs. (11), (34), (35)] The notation beta is used both for the limiting constant, as in beta(q) -> beta, and for the value in the factor m beta/(n(1-q)) in Eqs. (34) and (35). Since the limit in (35) uses beta(q), the distinction should be made explicit to avoid the appearance of an extra factor.
- [Section 2.6, Lemma 2.14] Lemma 2.14 should state explicitly that all three processes are q-Mallows processes with the same parameter q and should specify the law of p'_n; as written, the lemma only asserts independence of {bar p_i} and {p'_i}, not the marginal distributions.
- [Abstract and introduction] The abstract contains grammatical errors ('The Mallows measure is measure on permutations', 'introduce d') and would benefit from a careful editorial pass before resubmission.
Circularity Check
No significant circularity: the main results are derived from independent coupling lemmas and external LIS limits, and the constants are not fitted.
full rationale
The paper's derivation is self-contained in its main steps and does not reduce to its inputs. Theorem 1 relies on Lemma 2.12, a coupling statement quoted from the authors' earlier paper [12], but that lemma is a parameter-free result with clearly stated assumptions; it does not contain the target limits sqrt(6)/3 or the CLT constants. The constant sqrt(6)/3 is obtained by taking the explicit beta-to-infinity limit of Jbar(beta) via dominated convergence, not by fitting. Theorem 2 constructs a regenerative process and uses renewal time estimates and Anscombe's theorem; a and sigma are defined from the stationary distribution and return moments, not calibrated to the observed LCS. The only load-bearing self-citation is the unproved Lemma 2.12, which is a technical bridge to known LIS bounds and is explicitly attributed to prior work; this raises the need for verification but does not constitute definitional or fitted circularity. The abstract's two-parameter claim not being fully matched by Theorem 1 is a scope discrepancy, not a circular step.
Assumptions & free parameters
assumptions (7)
- domain assumption Mallows process representation and restriction/independence properties (Lemmas 2.1, 2.6-2.8)
- domain assumption Coupling lemma LIS(X_a, Y) <= LIS(Z_a) for arbitrary Y (Lemma 2.12)
- domain assumption Beta-regime weak law for LCS (Theorem 3, from [12])
- domain assumption LIS moment and uniform-integrability bounds (Lemma 5.1 and Theorem 1.3 of [3])
- domain assumption Infinite Mallows permutation of Gnedin-Olshanski and its regenerative structure
- standard math Kac's formula for return times (equation (2.21) of [1])
- standard math Anscombe's random-index central limit theorem (Theorem 4)
Cite this review
Pith. "Pith review of Limit Theorems for the Length of the Longest Common Subsequence of Mallows Permutations." pith.science (2026). https://pith.science/paper/4WIRNRHI
@misc{pith2026190805246,
author = {Pith},
title = {Pith review of: Limit Theorems for the Length of the Longest Common Subsequence of Mallows Permutations},
year = {2026},
howpublished = {\url{https://pith.science/paper/4WIRNRHI}},
note = {Machine review of arXiv:1908.05246}
}
abstract
The Mallows measure is measure on permutations which was introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation $\pi$ is proportional to $q^{Inv(\pi)}$ where $q$ is a positive parameter and $Inv(\pi)$ is the number of inversions in $\pi$. We consider the length of the longest common subsequence (LCS) of two independently permutations drawn according to $\mu_{n,q}$ and $\mu_{n,q'}$ for some $q,q' >0$. We show that when $0<q,q'<1$, the limiting law of the LCS is Gaussian. In the regime that $n(1-q) \to \infty$ and $n(1-q') \to \infty$ we show a weak law of large numbers for the LCS. These results extend the results of \cite{Basu} and \cite{Naya} showing weak laws and a limiting law for the distribution of the longest increasing subsequence to showing corresponding results for the longest common subsequence.
Reference graph
Works this paper leans on
-
[3]
Nayantara Bhatnagar and Ron Peled, Lengths of monotone subsequences in a mallows permutation , Probability Theory and Related Fields 161 (2015), no. 3-4, 719–780
work page 2015
-
[2]
Riddhipratim Basu, Nayantara Bhatnagar, et al., Limit theorems for longest monotone subsequences in random mallows permutations , Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques 53 (2017), no. 4, 1934–1951
work page 2017
-
[12]
Ke Jin et al., The length of the longest common subsequence of two independ ent mallows permutations , The Annals of Applied Probability 29 (2019), no. 3, 1311–1355
work page 2019
-
[1]
28 NAYA BANERJEE† AND KE JIN ‡
David Aldous and Jim Fill, Reversible markov chains and random walks on graphs , 2002. 28 NAYA BANERJEE† AND KE JIN ‡
work page 2002
-
[4]
Renato M Capocelli, Sequences: combinatorics, compression, security, and tra nsmission, Springer Sci- ence & Business Media, 2012
work page 2012
-
[5]
V´ acl´ av Chvatal and David Sankoff,Longest common subsequences of two random sequences , Journal of Applied Probability (1975), 306–315
work page 1975
-
[6]
thesis, University of Warwick, 1994
Vladim ´ ır Danc ´ ık,Expected length of longest common subsequences , Ph.D. thesis, University of Warwick, 1994
work page 1994
-
[7]
Vlado Danˇ c ´ ık and Mike Paterson,Upper bounds for the expected length of a longest common subs equence of two binary sequences , Random Structures & Algorithms 6 (1995), no. 4, 449–458
work page 1995
Show all 20 references
-
[8]
1, 17–31
Joseph G Deken, Some limit results for longest common subsequences , Discrete Mathematics 26 (1979), no. 1, 17–31
1979
-
[9]
Jean-Dominique Deuschel and Ofer Zeitouni, Limiting curves for iid records , The Annals of Probability (1995), 852–878
1995
-
[10]
5, 615–639
Alexander Gnedin and Grigori Olshanski, The two-sided infinite extension of the mallows model for random permutations, Advances in Applied Mathematics 48 (2012), no. 5, 615–639
2012
-
[11]
Ke Jin, The limit of the empirical measure of the product of two indep endent mallows permutations , arXiv preprint arXiv:1702.00140 (2017)
2017 arXiv
-
[13]
George S Lueker, Improved bounds on the average length of longest common subs equences, Journal of the ACM (JACM) 56 (2009), no. 3, 17
2009
-
[14]
i , Biometrika 44 (1957), no
Colin L Mallows, Non-null ranking models. i , Biometrika 44 (1957), no. 1/2, 114–130
1957
-
[15]
2, 514–540
Carl Mueller and Shannon Starr, The length of the longest increasing subsequence of a random mallows permutation, Journal of Theoretical Probability 26 (2013), no. 2, 514–540
2013
-
[16]
PA Pevzner, Computational molecular biology: An algorithmic approach a bradford book, 2000
2000
-
[17]
Jim Pitman and Wenpin Tang, Regenerative random permutations of integers , to appear in Annals of Probability (2017)
2017
-
[18]
David Sankoff and Joseph B Kruskal, Time warps, string edits, and macromolecules: the theory an d practice of sequence comparison , Reading: Addison-Wesley Publication, 1983, edited by Sankoff, Dav id; Kruskal, Joseph B. (1983)
1983
-
[19]
Shannon Starr, Thermodynamic limit for the mallows model on s n, arXiv preprint arXiv:0904.0696 (2009)
2009 arXiv
-
[20]
Michael S Waterman, Introduction to computational biology: maps, sequences an d genomes , CRC Press, 1995
1995
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.