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
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
#2
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