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

@inproceedings{cCicceksiz2021TheVA, title={The Variance and the Asymptotic Distribution of the Length of Longest \$k\$-alternating Subsequences}, author={Altar cCicceksiz and Yunus Emre Demirci and Um.it Icslak}, year={2021} }

We obtain an explicit formula for the variance of the length of longest k-alternating subsequence in a uniformly random permutation. Also a central limit is proved for the same statistic.

#### References

SHOWING 1-10 OF 12 REFERENCES

On the Longest $k$-Alternating Subsequence

- Mathematics, Computer ScienceElectron. J. Comb.
- 2015

We show that the longest $k$-alternating substring of a random permutation has length asymptotic to $2(n-k)/3$.

Average length of the longest k-alternating subsequence

- Computer Science, MathematicsJ. Comb. Theory, Ser. A
- 2015

It is shown that the k = 1 case is a well-known result of Richard Stanley and the conjecture on the average maximal length of k-alternating subsequence of permutations is true.

A Probabilistic Approach to the Asymptotics of the Length of the Longest Alternating Subsequence

- Mathematics, Computer ScienceElectron. J. Comb.
- 2010

The methodology is robust enough to tackle similar problems for finite alphabet random words or even Markovian sequences, and a sketch of how some cases of pattern restricted permutations can also be tackled with probabilistic methods is presented.

Longest alternating subsequences of permutations

- Mathematics
- 2005

The length is(w) of the longest increasing subsequence of a permutation w in the symmetric group Sn has been the object of much investigation. We develop comparable results for the length as(w) of…

Local extrema in random permutations and the structure of longest alternating subsequences

- Mathematics
- 2011

Let asn denote the length of a longest alternating subsequence in a uniformly random permutation of order n. Stanley studied the distribution of asn using algebraic methods, and showed in particular…

Asymptotic results for random sums of dependent random variables

- Mathematics
- 2016

Our main result is a central limit theorem for random sums of the form ∑i=1NnXi, where {Xi}i≥1 is a stationary m-dependent process and Nn is a random index independent of {Xi}i≥1. This extends the…

Normal Approximation by Stein ’ s Method

- 2003

The aim of this paper is to give an overview of Stein’s method, which has turned out to be a powerful tool for estimating the error in normal, Poisson and other approximations, especially for sums of…

Descent-inversion statistics in riffle shuffles

- Mathematics
- 2013

This paper studies statistics of riffle shuffles by relating them to random word statistics with the use of inverse shuffles. Asymptotic normality of the number of descents and inversions in riffle…

On normal approximation rates for certain sums of dependent random variables

- Mathematics
- 1994

Abstract Let X1, …, Xn be dependent random variables, and set λ = E∑ni=1Xi, and σ2 = Var∑ni=1Xi. In most of the applications of Stein's method for normal approximations, the error rate |P((∑ni=1Xi −…

Enumerative Combinatorics Problem Session

- 2014