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
New model helps explain how provisions promote or reduce wildlife disease
Stress can make hard-working mongooses less likely to help in the future
Grammatical habits in written English reveal linguistic features of non-native speakers' languages
Stephen Tashi
#2
Nov23-12, 07:25 PM
Sci Advisor
P: 3,245
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