Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Bartholomew's blog

A question about LIS of random permutation
By Bartholomew, history, 7 years ago, In English

What's the expected length of LIS of a random n-permutation.

According to my test, it approximates $$$O(\sqrt n)$$$.

But how to prove it?

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
7 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Ah, I want to know the proof, too. I just met it today.

→ Reply
»
7 years ago, hide # |
← Rev. 3  
Vote: I like it -16 Vote: I do not like it

Let $$$E_n$$$ be the expected value.

Based on the position of $$$n$$$ in a $$$n$$$-permutation, we have the formula: $$$E_n = \dfrac{E_0+E_1+...+E_{n-1}}{n} + 1$$$, which leads to $$$E_n = E_{n-1} + \dfrac{1}{n}$$$.

So $$$E_n = 1 + \dfrac{1}{2} + ... \dfrac{1}{n} \approx \log{n}$$$.

Edit: Wrong solution

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In this problem that observation is needed: 1017C - The Phone Number.

The tutorial says the formal proof, by Dilworth's theorem.

→ Reply