Longest increasing subsequence as measure of randomness

Question

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 of permutations and their connection to the Robinson-Schensted algorithm.

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.

Answer 1

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)

and also in this (unpublished?) preprint. I don't know whether they were the first to consider this test statistic.

Answer 2

This is by no means a complete answer, but I think section 7 of the following paper would be a good starting point to learn about the existing literature for this question.

Steele, J. Michael, Variations on the monotone subsequence theme of Erdös and Szekeres, Discrete probability and algorithms. 111-131 (1995). ZBL0832.60012.

The paper can also be found on the author's webpage

However, as I understand it, the short answer to your question is no. In the cited paper, it is shown that there are sequences which closely resemble a random sequence in terms of length of monotone subsequences, but differ with respect to other natural properties.

Answer 3

No test can definitively prove randomness. Particularly a test which assigns a single integer to a sequence. Given the test there will be "pseudo-random" sequences which pass the test but might have a simple rule. To get length $n$ and largest increasing subsequence of $k$ just do $1,2,3,\cdots,k-1,n,n-1,\cdots,k.$ On the other hand they can refute randomness fairly convincingly when they fail.

I've seen claims like this for binary sequences: Ask several people to provide you a binary sequence of length $n$ either by flipping a fair coin or by writing one out that should seem random. Then you need to say which are truly random and which are not. The longest consecutive run of identical bits is a good test. People will tend to avoid long runs. Actually, this is a good test (for a magic trick or classroom demonstration with a perhaps sophisticated but naive audience) because you can quickly scan and separate the random from the faked. Other simple tests might do even better.

By the same token, I'd guess that an intentionally constructed permutation meant to seem random would fall short at least on consecutive increasing subsequences.

Answer 4

This isn't quite what you asked, but if you want to be able to make a precise statement, there is the following beautiful theorem of Kral and Pikhurko:

Theorem A sequence of permutations $\{\pi_i \in S_i\}_{i \in \mathbb{N}}$ is quasi-random if and only if the densities of all length-four permutation patterns converge to $1/24$ as $i \to \infty$.

In particular, if you have too many or too long of increasing subsequences, your density of the pattern $1234$ will be too high. But in order to achieve quasirandomness you also need other pattern densities to converge.

Quasirandom permutations can be defined in lots of equivalent ways, by requiring that your sequence has various properties expected of a random sequence. Remarkably, one of the equivalent conditions is that pattern densities converge to $1/k!$ for all patterns from $S_k$ for all $k$, so the theorem says that checking length-four patterns already guarantees that all patterns (including increasing subsequences $12...k$, converge to the correct density).

Answer 5

You might look at the paper

Samuel Karlin and Stephen F. Altschul, Applications and statistics for multiple high-scoring segments in molecular sequences, Proceedings of the National Academy of Sciences 90, no. 12 (1993), 5873–5877. The authors use the enumeration of permutations by longest increasing subsequence in studying DNA sequencing. See, in particular, their equation [6]. (Altschul took my graduate course in combinatorics at MIT many years ago and went on to do great things in mathematical biology.)

A related paper (somewhat more mathematical) is Craig A. Tracy and Harold Widom, On a distribution function rising in computational biology, https://arxiv.org/abs/math/0011146.