## Return to Answer

2 alternate interpretation

Assuming the interpretation that I gave in a comment above, it suffices to find the length of the longest consecutive subsequence in a sequence of $n$ random variables $(X_1, \ldots, X_n)$, each of which is uniform on $[0,1]$. Such an $n$-tuple determines a permutation as long as we never have $X_i = X_j$; this occurs with probability zero.

The probability that $X_{i+1} < \cdots < X_{i+r}$ is just $1/r!$. So the expected number of increasing consecutive subsequences of length $r$ in a sequence of length $n$ is $n/r!$.

Therefore the length of the longest increasing consecutive subsequence should be near $r_0(n)$, where $r_0 := r_0(n)$ satisfies $r_0! = n$. This is not a constant times $\log n$. However, if we solve $(r/e)^r = n$ for $r$ (this is roughly Stirling's approximation), we get $r = \log(n)/W(\log(n)/e)$, where W is the Lambert W function. As $z \to \infty$, $W(z)$ grows slower than $\log z$, so it seems like $r_0(n)$ grows a bit faster than $\log n/\log \log n$. It wouldn't be hard to confuse this with a constant times $\log n$ if you were working off of numerical data.

Another interpretation of this problem is, given a permutation $a_1 a_2 \ldots a_n$, to find the longest sequence $i_1, i_2, \ldots, i_r$ such that $a_{i_1}, a_{i_2}, \ldots, a_{i_r}$ are consecutive integers. (For example, in 691528347, the numbers 1, 2, 3, 4 appear in that order.) The longest subsequence of $\sigma$ in this sense has the same length as the longest subsequence of $\sigma^{-1}$ in the sense previously in this answer; for example, the inverse of 691528347 is 357841962, which has the consecutive increasing sequence 3578. So the lengths of the longest increasing sequences in these two interpretations have the same distribution.

1

Assuming the interpretation that I gave in a comment above, it suffices to find the length of the longest consecutive subsequence in a sequence of $n$ random variables $(X_1, \ldots, X_n)$, each of which is uniform on $[0,1]$. Such an $n$-tuple determines a permutation as long as we never have $X_i = X_j$; this occurs with probability zero.

The probability that $X_{i+1} < \cdots < X_{i+r}$ is just $1/r!$. So the expected number of increasing consecutive subsequences of length $r$ in a sequence of length $n$ is $n/r!$.

Therefore the length of the longest increasing consecutive subsequence should be near $r_0(n)$, where $r_0 := r_0(n)$ satisfies $r_0! = n$. This is not a constant times $\log n$. However, if we solve $(r/e)^r = n$ for $r$ (this is roughly Stirling's approximation), we get $r = \log(n)/W(\log(n)/e)$, where W is the Lambert W function. As $z \to \infty$, $W(z)$ grows slower than $\log z$, so it seems like $r_0(n)$ grows a bit faster than $\log n/\log \log n$. It wouldn't be hard to confuse this with a constant times $\log n$ if you were working off of numerical data.