Register to reply

Longest increasing subsequence

by Naumberg
Tags: expectation, increasing, sequence
Share this thread:
Naumberg
#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
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
Stephen Tashi
#2
Nov23-12, 07:25 PM
Sci Advisor
P: 3,252
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