Register to reply

Longest increasing subsequence

by Naumberg
Tags: expectation, increasing, sequence
Share this thread:
Nov23-12, 09:12 AM
P: 1

"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,
Phys.Org News Partner Science news on
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
Stephen Tashi
Nov23-12, 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