(adsbygoogle = window.adsbygoogle || []).push({}); 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

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Longest increasing subsequence

Loading...

Similar Threads - Longest increasing subsequence | Date |
---|---|

Increasing sequence of sigma algebras | Oct 30, 2015 |

Enumeration of increasing sequences of 2 dice sums | Feb 20, 2015 |

Convergence of non increasing sequence of random number | Dec 31, 2012 |

Longest streaks of successes | Aug 20, 2012 |

Strictly increasing cdf | Nov 9, 2011 |

**Physics Forums - The Fusion of Science and Community**