Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Longest increasing subsequence

  1. Nov 23, 2012 #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
     
  2. jcsd
  3. Nov 23, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    What does the notation "[itex] o(1) [/itex]" mean in this context?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Longest increasing subsequence
Loading...