# Longest increasing subsequence

by Naumberg
Tags: expectation, increasing, sequence
 P: 1 Problem: "Let $x_1, ..., x_n$ be i.i.d random variables uniformly on [0,1]. Let $X$ be the length of the longest increasing subsequence of $x_1, ..., x_n$. Show that $E[X] \ge (1-o(1))(1-e^{-1}) \sqrt{n}$." Hi forum! Using the Erdos' lemma I can only deduce that $E[X] \ge \frac{1}{2} \sqrt{n}$, which is a weaker bound unfortunately. I would appreciate any further ideas! Thanks for your help, Michael
 Sci Advisor P: 3,296 What does the notation "$o(1)$" mean in this context?