Bartholomew's blog

A question about LIS of random permutation
By Bartholomew, history, 5 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

»
5 years ago, # |
  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
»
5 years ago, # |
← 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
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I don't think that's true, one doesn't have to include $$$n$$$ in LIS

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Sorry but I have no idea that how can get the conclusion above？

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You are right! The answer is indeed $$$O(\sqrt{n})$$$ or more precisely $$$\approx 2\sqrt{n}$$$ when $$$n$$$ is large, according to this paper.

    → Reply
»
5 years ago, # |
  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
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't get the point that we can prove it by this theory.

    Can you be more specific please? XD

    → Reply