What Does o(1) Mean in the Longest Increasing Subsequence Problem?

  • Context: Graduate 
  • Thread starter Thread starter Naumberg
  • Start date Start date
  • Tags Tags
    Increasing Subsequence
Click For Summary
SUMMARY

The discussion centers on the Longest Increasing Subsequence (LIS) problem, specifically addressing the expected length E[X] of the LIS for i.i.d. random variables uniformly distributed on [0,1]. The key conclusion is that E[X] is bounded below by (1-o(1))(1-e^{-1})√n, which is a stronger result than the previously established bound of E[X] ≥ 1/2√n derived from Erdős' lemma. The notation "o(1)" indicates a term that approaches zero as n increases, providing a more precise asymptotic behavior of the expected length.

PREREQUISITES
  • Understanding of the Longest Increasing Subsequence problem
  • Familiarity with Erdős' lemma and its implications
  • Basic knowledge of probability theory and random variables
  • Concept of asymptotic notation, particularly "o(1)"
NEXT STEPS
  • Study the proof of the expected length of the Longest Increasing Subsequence in random sequences
  • Explore advanced probability concepts related to random variables
  • Learn about asymptotic analysis and its applications in algorithm analysis
  • Investigate other results related to Erdős' lemma in combinatorial mathematics
USEFUL FOR

Mathematicians, computer scientists, and algorithm researchers interested in combinatorial optimization and probabilistic analysis of algorithms.

Naumberg
Messages
1
Reaction score
0
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 news on Phys.org
What does the notation "[itex]o(1)[/itex]" mean in this context?
 

Similar threads

Undergrad Computing the expectation of the minimum difference between the 0th i.i.d.r.v. and ith i.i.d.r.v.s where 1 ≤ i ≤ n
  • · Replies 0 ·
Replies
0
Views
2K
Undergrad How are the following three definitions subtly different?
  • · Replies 15 ·
Replies
15
Views
2K
MHB Confidence Interval for Mean $\mu$: Let $X_1, X_2, \dots, X_n$
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How to calculate expectation and variance of kernel density estimator?
  • · Replies 9 ·
Replies
9
Views
3K
Graduate Correlation and mathematical expectation question
  • · Replies 3 ·
Replies
3
Views
2K
Does a Bounded, Divergent Sequence Always Have Multiple Convergent Subsequences?
  • · Replies 8 ·
Replies
8
Views
3K
MHB Probabilities about length of songs
  • · Replies 1 ·
Replies
1
Views
2K
MHB Probability that we get totally at most 30 times "head"
  • · Replies 6 ·
Replies
6
Views
2K
MHB Likelihood Ratio Test for Common Variance from Two Normal Distribution Samples
  • · Replies 1 ·
Replies
1
Views
4K
Subsequences and sequential compactness
  • · Replies 10 ·
Replies
10
Views
3K