The Variance and the Asymptotic Distribution of the Length of Longest $k$-alternating Subsequences

Recep Altar \c{C}i\c{c}eksiz; \"Umit I\c{s}lak; Yunus Emre Demirci

arxiv: 2107.12459 · v3 · submitted 2021-07-26 · 🧮 math.PR · math.CO

The Variance and the Asymptotic Distribution of the Length of Longest k-alternating Subsequences

Recep Altar \c{C}i\c{c}eksiz , Yunus Emre Demirci , \"Umit I\c{s}lak This is my paper

Pith reviewed 2026-05-24 13:07 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords variancek-peakslongest k-alternating subsequencerandom permutationscentral limit theoremasymptotic distribution

0 comments

The pith

An explicit variance formula for k-peaks in random permutations yields the asymptotic variance and a central limit theorem for the length of the longest k-alternating subsequence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper first derives a closed-form expression for the variance of the number of k-peaks in a uniformly random permutation. It then applies this expression to obtain an asymptotic formula for the variance of the length of the longest k-alternating subsequence. A central limit theorem is proved for the distribution of this length as the permutation size grows. These results describe the typical fluctuations and limiting behavior of a subsequence statistic in random permutations.

Core claim

An explicit formula is obtained for the variance of the number of k-peaks in a uniformly random permutation. This is then used to obtain an asymptotic formula for the variance of the length of longest k-alternating subsequence in random permutations, and a central limit theorem is proved for the latter statistic.

What carries the argument

The number of k-peaks, which provides the explicit variance that transfers to the asymptotic variance of the longest k-alternating subsequence length.

If this is right

The variance of the number of k-peaks admits an explicit closed-form expression.
The variance of the longest k-alternating subsequence length admits an explicit asymptotic expression.
The length of the longest k-alternating subsequence converges in distribution to a normal law after centering and scaling.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same variance-transfer technique could be tested on other subsequence statistics that admit a peak-count representation.
The explicit variance for k-peaks may allow exact moment calculations for small k without simulation.
The central limit theorem opens the door to concentration bounds or moderate-deviation estimates for the same length statistic.

Load-bearing premise

A specific linking relationship or inequality between the number of k-peaks and the length of the longest k-alternating subsequence allows the variance formula to transfer asymptotically.

What would settle it

Direct Monte Carlo computation of the empirical variance and distribution of the longest k-alternating subsequence length for large n, compared against the claimed asymptotic variance expression and normal limit.

read the original abstract

We obtain an explicit formula for the variance of the number of $k$-peaks in a uniformly random permutation. This is then used to obtain an asymptotic formula for the variance of the length of longest $k$-alternating subsequence in random permutations. Also a central limit is proved for the latter statistic.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives an explicit variance for k-peaks and applies it to get asymptotic variance plus a CLT for longest k-alternating subsequences.

read the letter

The paper's main contribution is an explicit formula for the variance of the number of k-peaks in a uniform random permutation. They then use this to get an asymptotic expression for the variance of the length of the longest k-alternating subsequence and prove a central limit theorem for it. This explicit variance is the new piece. Prior work on alternating subsequences often has asymptotics for the mean but variances are harder, so having a closed form here is useful. The CLT is also a step forward for this statistic. The paper handles the probabilistic calculations in a straightforward way, moving from counting peaks to the target statistic via known relations. No signs of circular reasoning or post-hoc adjustments. One potential soft spot is how precisely the variance of peaks translates to the variance of the longest subsequence. The abstract and stress-test suggest it's a direct application of concentration or monotonicity, which seems reasonable, but the details would need checking to ensure the error terms are controlled properly. It's not a major flaw if the math holds. This kind of result is for researchers in probabilistic combinatorics who work on subsequence lengths in permutations. It adds to the literature on these statistics without claiming to solve a big open problem. I think it deserves a serious referee. The claims are specific and the approach is honest. My recommendation is to send it for peer review.

Referee Report

0 major / 2 minor

Summary. The manuscript obtains an explicit formula for the variance of the number of k-peaks in a uniformly random permutation. This formula is then used to derive an asymptotic formula for the variance of the length of the longest k-alternating subsequence, and a central limit theorem is proved for the latter statistic.

Significance. If the results hold, the work contributes explicit variance expressions and limiting distributions for a natural generalization of alternating subsequences in random permutations. The explicit (parameter-free) variance formula for the number of k-peaks is a strength that directly supports the subsequent asymptotic analysis.

minor comments (2)

[Abstract] The abstract and introduction could include a brief inline definition or example of a k-alternating subsequence and k-peak to aid readers unfamiliar with the extension from the k=1 case.
[Introduction] Notation for the longest k-alternating subsequence length (e.g., L_n^{(k)}) should be introduced once and used consistently; check for any local inconsistencies in later sections.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our manuscript and the recommendation of minor revision. The referee's description accurately reflects the main results: an explicit variance formula for the number of k-peaks, its use in deriving the asymptotic variance of the longest k-alternating subsequence length, and the accompanying central limit theorem.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation begins with an explicit variance formula for the number of k-peaks obtained via direct probabilistic counting on uniform random permutations. This is then linked to the target statistic (length of longest k-alternating subsequence) via standard concentration or monotonicity relations between the two quantities. No step reduces by construction to its own inputs, no fitted parameter is relabeled as a prediction, and no load-bearing premise rests on self-citation chains. The central claims remain independent of the inputs they are derived from.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the work rests on standard domain assumptions about uniform random permutations and basic probability; no free parameters, invented entities, or non-standard axioms are mentioned.

axioms (2)

domain assumption Permutations are drawn uniformly at random
Stated directly in the abstract as the setting for all results.
standard math Linearity of expectation and variance formulas for indicator variables hold
Implicit in deriving an explicit variance formula for the count of k-peaks.

pith-pipeline@v0.9.0 · 5586 in / 1355 out tokens · 34773 ms · 2026-05-24T13:07:16.576254+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Armstrong

D. Armstrong. Enumerative combinatorics problem session. in Oberwolfach Report No, 12 2014

work page 2014
[2]

T. W. Cai. Average length of the longest k-alternating subsequence. Journal of Combinatorial Theory, Series A, 134: 0 51--57, 2015

work page 2015
[3]

Houdr\'e and R

C. Houdr\'e and R. Restrepo. A probabilistic approach to the asymptotics of the length of the longest alternating subsequence. Electronic Journal of Combinatorics, 17, 2010

work page 2010
[4]

U. Islak. Asymptotic results for random sums of dependent random variables. Statistics and Probability Letters, 109: 0 22--29, 2016

work page 2016
[5]

U. Islak. Descent-inversion statistics in riffle shuffles. Turkish Journal of Mathematics, 42 0 (2): 0 502--514, 2018

work page 2018
[6]

Pak and R

I. Pak and R. Pemantle. On the longest k-alternating subsequence. Electronic Journal of Combinatorics, 22 0 (1), 2015

work page 2015
[7]

M. Raic. Normal approximation by stein's method. In Proceedings of the 7th Young Statisticians Meeting, pages 71--97, 2003

work page 2003
[8]

Y. Rinott. On normal approximation rates for certain sums of dependent random variables. Journal of Computational and Applied Mathematics, 55 0 (2): 0 135--143, 1994

work page 1994
[9]

D. Romik. Local extrema in random permutations and the structure of longest alternating subsequences. Discrete Mathematics and Theoretical Computer Science, 2011

work page 2011
[10]

R. Stanley. Longest alternating subsequences of permutations. Michigan Mathematical Journal, 57: 0 675--687, 2008

work page 2008

[1] [1]

Armstrong

D. Armstrong. Enumerative combinatorics problem session. in Oberwolfach Report No, 12 2014

work page 2014

[2] [2]

T. W. Cai. Average length of the longest k-alternating subsequence. Journal of Combinatorial Theory, Series A, 134: 0 51--57, 2015

work page 2015

[3] [3]

Houdr\'e and R

C. Houdr\'e and R. Restrepo. A probabilistic approach to the asymptotics of the length of the longest alternating subsequence. Electronic Journal of Combinatorics, 17, 2010

work page 2010

[4] [4]

U. Islak. Asymptotic results for random sums of dependent random variables. Statistics and Probability Letters, 109: 0 22--29, 2016

work page 2016

[5] [5]

U. Islak. Descent-inversion statistics in riffle shuffles. Turkish Journal of Mathematics, 42 0 (2): 0 502--514, 2018

work page 2018

[6] [6]

Pak and R

I. Pak and R. Pemantle. On the longest k-alternating subsequence. Electronic Journal of Combinatorics, 22 0 (1), 2015

work page 2015

[7] [7]

M. Raic. Normal approximation by stein's method. In Proceedings of the 7th Young Statisticians Meeting, pages 71--97, 2003

work page 2003

[8] [8]

Y. Rinott. On normal approximation rates for certain sums of dependent random variables. Journal of Computational and Applied Mathematics, 55 0 (2): 0 135--143, 1994

work page 1994

[9] [9]

D. Romik. Local extrema in random permutations and the structure of longest alternating subsequences. Discrete Mathematics and Theoretical Computer Science, 2011

work page 2011

[10] [10]

R. Stanley. Longest alternating subsequences of permutations. Michigan Mathematical Journal, 57: 0 675--687, 2008

work page 2008