A Problem About Increasing Sequences

The original problem (post) is from Clément Canonne on Bluesky:

It’s the end of the semester! To celebrate that, one last* puzzle 🧩 for 2024: pick a permutation π of {1,2,…,n} uniformly at random, and let L(π) be the length of its longest increasing sub-sequence. What is the expectation of L(π)? Is it O(1), Θ(log n), Θ(√n), Θ(n)—something else?

We can treat $\pi$ as a permutation of $n$ uniformly spaced values on $(0, 1]$. If we require that the $k^{th}$ item in a sequence must be greater than $1 - 1/k$, the waiting time between observing items $k-1$ and $k$ is exponentially distributed with $\lambda=1/k$. Summing the first $k$ expected waiting times yields $\mu_k = \sum_{n=1}^k n \sim k^2/2$. This is sufficient to see that $E[L\big(\pi)] = \mathcal{O}\big(n^{1/2})$.

$\textbf{N.B}$ — I later learned that Erdos proved (folklore? Proofs From The Book?) that an increasing or decreasing sequence of $\lfloor n^{1/2} \rfloor$ items must exist.