What is the expected length of the longest consecutive subsequence of a random permutation of the integers 1 to N? To be more precise we are looking for the longest string of consecutive integers in the permutation (disregarding where this string occurs). I believe the answer should be ~ c ln(n), but I have been unable to prove this.


Update: We are looking for the longest increasing subsequence. This is to say 9,1,5,2,7,3 has an increasing subsequence 1,2,3.



longest consecutive subsequence of a random permutation
The purpose of this answer is to use the [second moment method](http://en.wikipedia.org/wiki/Second_moment_method) to make rigorous the heuristic argument of Michael Lugo. (Here is why his argument is only heuristic: If $N$ is a nonnegative integer random variable, such as the number of length-$r$ increasing consecutive sequences in a random permutation of $\{1,2,\ldots,n\}$, knowing that $E[N] \gg 1$ does not imply that $N$ is positive with high probability, because the large expectation could be caused by a rare event in which $N$ is very large.)


**Theorem:** The expected length of the longest increasing block in a random permutation of $\{1,2,\ldots,n\}$ is $r\_0(n) + O(1)$ as $n \to \infty$, where $r\_0(n)$ is the smallest positive integer such that $r\_0(n)!>n$. ("Block" means consecutive subsequence $a\_{i+1},a\_{i+2},\ldots,a\_{i+r}$ for some $i$ and $r$, with no conditions on the relative sizes of the $a\_i$.)


**Note:** As Michael pointed out, $r\_0(n)$ is of order $(\log n)/(\log \log n)$.


**Proof of theorem:** Let $P\_r$ be the probability that there exists an increasing block of length at least $r$. The expected length of the longest increasing block is then $\sum\_{r \ge 0} r(P\_r-P\_{r+1}) = \sum\_{r \ge 1} P\_r$. We will bound the latter sum from above and below.


*Upper bound:* The probability $P\_r$ is at most the expected *number* of increasing blocks of length $r$, which is exactly $(n-r+1)/r!$, since for each of the $n-r+1$ values of $i$ in $\{0,\ldots,n-r\}$ the probability that $a\_{i+1},\ldots,a\_{i+r}$ are in increasing order is $1/r!$. Thus $P\_r \le n/r!$. By comparison with a geometric series with ratio $2$, we have $\sum\_{r > r\_0(n)} P\_r \le P\_{r\_0(n)} \le 1$. On the other hand $\sum\_{1 \le r \le r\_0(n)} P\_r \le \sum\_{1 \le r \le r\_0(n)} 1 \le r\_0(n)$, so $\sum\_{r \ge 1} P\_r \le r\_0(n) + 1$.


*Lower bound:* Here we need the second moment method. For $i \in \{1,\ldots,n-r\}$, let $Z\_i$ be $1$ if $a\_{i+1}<a\_{i+2}<\ldots<a\_{i+r}$ and $a\_i>a\_{i+1}$, and $0$ otherwise. (The added condition $a\_i>a\_{i+1}$ is a trick to reduce the positive correlation between nearby $Z\_i$.) The probability that $a\_{i+1}<a\_{i+2}<\ldots<a\_{i+r}$ is $1/r!$, and the probability that this holds while $a\_i>a\_{i+1}$ fails is $1/(r+1)!$, so $E[Z\_i]=1/r! - 1/(r+1)!$. Let $Z=\sum\_{i=1}^{n-r} Z\_i$, so 
$$E[Z]=(n-r)(1/r! - 1/(r+1)!).$$
Next we compute the second moment $E[Z^2]$ by expanding $Z^2$. If $i=j$, then $E[Z\_i Z\_j] = E[Z\_i] = 1/r! - 1/(r+1)!$; summing this over $i$ gives less than or equal to $n/r!$. If $0<|i-j|<r$, then $E[Z\_i Z\_j]=0$ since the inequalities are incompatible. If $|i-j|=r$, then $E[Z\_i Z\_j] \le 1/r!^2$ (the latter is the probability if we drop the added condition in the definition of $Z\_i$ and $Z\_j$). If $|i-j|>r$, then $Z\_i$ and $Z\_j$ are independent, so $E[Z\_i Z\_j] = (1/r! - 1/(r+1)!)^2$. Summing over all $i$ and $j$ shows that
$$E[Z^2] \le \frac{n}{r!} + E[Z]^2 \le \left(1 + O(r!/n) \right) E[Z]^2.$$
The second moment method gives the second inequality in
$$P\_r \ge \operatorname{Prob}(Z \ge 1) \ge \frac{E[Z]^2}{E[Z^2]} \ge 1 - O(r!/n).$$
If $r \le r\_0(n)-2$, then $r! \le (r\_0(n)-1)!/(r\_0(n)-1)$, so $r!/n \le 1/(r\_0(n)-1)$, so $P\_r \ge 1 - O(1/r\_0(n))$. Thus
$$\sum\_{r \ge 1} P\_r \ge \sum\_{r=1}^{r\_0(n)-2} \left( 1 - O(1/r\_0(n)) \right) = r\_0(n) - O(1).$$


