Блог пользователя Bartholomew

A question about LIS of random permutation
Автор Bartholomew, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Can you be more specific please? XD

    → Ответить