Although I am by no means an applied mathematician, I like to occasionally explain applications of the math I teach to real world problems. Right now I am teaching some students about [longest increasing subsequences](https://en.wikipedia.org/wiki/Longest_increasing_subsequence) of permutations and their connection to the [Robinson-Schensted algorithm](https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_correspondence).


Suppose you have some discrete time series data $x\_1,x\_2,\ldots$. This determines a permutation $\sigma = \sigma\_1, \sigma\_2,\ldots$ just by relative order of the data (if the data is continuous, or at least drawn from a wide range, it is very likely there will be no "ties" so we have an honest permutation). I remember once hearing (but don't remember where...) that checking the length of the longest increasing subsequence of $\sigma$ could be a way to detect if the data was observed in a random order or not.


But a cursory Googling (which gives a lot of info about longest increasing subsequences, connections to RS, "Ulam's problem" of computing the expected length, dynamic programming for finding a l.i.s., etc.) does not yield much about this application...


**Question**: Is comparing the length of the longest increasing subsequence of $\sigma$ to that of a random permutation a reasonable statistical test for randomness? Is there some literature about this?


Of course, for a more sophisticated test we could look at the shape of $\sigma$ under RS and compare it to the known Vershik–Kerov/Logan–Shepp limit shape.



Longest increasing subsequence as measure of randomness
The Longest Increasing Subsequence has been used as a test statistic for non-parametric tests by García and González-López in


Independence tests for continuous random variables based on the longest increasing subsequence, Journal of Multivariate Analysis, 2014 ([link](https://www.sciencedirect.com/science/article/pii/S0047259X14000335))


and also in [this (unpublished?) preprint](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.714.2983&rep=rep1&type=pdf). I don't know whether they were the first to consider this test statistic.


