Longest increasing subsequence


by Naumberg
Tags: expectation, increasing, sequence
Naumberg
Naumberg is offline
#1
Nov23-12, 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 (1-o(1))(1-e^{-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
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
Stephen Tashi
Stephen Tashi is offline
#2
Nov23-12, 07:25 PM
Sci Advisor
P: 3,175
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
Subsequence Calculus & Beyond Homework 3