Register to reply 
Longest increasing subsequence 
Share this thread: 
#1
Nov2312, 09:12 AM

P: 1

Problem:
"Let [itex]x_1, ..., x_n[/itex] be i.i.d random variables uniformly on [0,1]. Let [itex]X[/itex] be the length of the longest increasing subsequence of [itex]x_1, ..., x_n[/itex]. Show that [itex]E[X] \ge (1o(1))(1e^{1}) \sqrt{n}[/itex]." Hi forum! Using the Erdos' lemma I can only deduce that [itex]E[X] \ge \frac{1}{2} \sqrt{n}[/itex], which is a weaker bound unfortunately. I would appreciate any further ideas! Thanks for your help, Michael 


#2
Nov2312, 07:25 PM

Sci Advisor
P: 3,300

What does the notation "[itex] o(1) [/itex]" mean in this context?



Register to reply 
Related Discussions  
Increasing Torque, Force, and Work: Increasing crank Length (L)  Introductory Physics Homework  3  
Non Decreasing Subsequence in [0,1]  Calculus  4  
Java recursion longest common subsequence  Programming & Computer Science  2  
Subsequence converging  Calculus & Beyond Homework  3  
This sequence has no convergent subsequence?  Calculus & Beyond Homework  3 