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
Flapping baby birds give clues to origin of flight
Prions can trigger 'stuck' wine fermentations, researchers find
Socially-assistive robots help kids with autism learn by providing personalized prompts
Stephen Tashi
#2
Nov23-12, 07:25 PM
Sci Advisor
P: 3,296
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