wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Expected length of longest increasing subsequence
        
(Message started by: Eigenray on Feb 26^th, 2009, 2:51am)

Title: Expected length of longest increasing subsequence
Post by Eigenray on Feb 26^th, 2009, 2:51am

Let E(n) be the expected value of the length of the longest increasing subsequence of a random permutation of {1,2,3,...,n}. E.g., E(1) = 1, E(2) = 3/2, E(3) = 2.

Show that there exist constants 0 < A < B < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif such that for all n,

Ahttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn < E(n) < Bhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn

Title: Re: Expected length of longest increasing subseque
Post by towr on Feb 26^th, 2009, 3:10am

Would you prefer something more interesting for A than 0?

Title: Re: Expected length of longest increasing subseque
Post by Eigenray on Feb 26^th, 2009, 3:14am

...yes.

Title: Re: Expected length of longest increasing subseque
Post by Aryabhatta on Mar 14^th, 2009, 11:44am

Interesting problem.

An attempt at partial solution (> Asqrt(n) part).

If F(n) is the expected length of the longest decreasing subsequence, then by symmetry E(n) = F(n) (I hope).

Now consider E+F.

We can use the following fact:

If there are n² + 1 distinct integers, then there is a subsequence of n+1 integers which is monotonic. Thus for every permutation, E + F > A sqrt(n) for some A > 0.

This shows that E(n) + F(n) > A sqrt(n) for some A > 0.

Upper bound, will have to think about it.

Title: Re: Expected length of longest increasing subseque
Post by Eigenray on Mar 20^th, 2009, 12:35pm

For the upper bound, it suffices to bound the probability that [hide]there exists an increasing subsequence of length k[/hide].

Title: Re: Expected length of longest increasing subseque
Post by TenaliRaman on Mar 20^th, 2009, 6:05pm

*Spoiler* [hide]A discussion I had at another forum sometime back (https://nrich.maths.org/discus/messages/67613/68689.html?1141499791)[/hide]

-- AI

Title: Re: Expected length of longest increasing subseque
Post by Eigenray on Mar 20^th, 2009, 6:50pm

Here's what got me thinking about this:

Suppose we have n rectangles, each with a width and height chosen uniformly at random between 0 and 1. Now suppose we stack them, without rotation, into as few piles as possible, with the restriction that if (w,h) is above (W,H), then w < W and h < H. Then the expected number of piles we will need is E(n).

Extension 1: What if rotations are allowed?

Extension 2: What if we had boxes (i.e., rectangular parallelepipeds) instead, and we wanted to nest them into as few pieces as possible. Then how many would we need?

Title: Re: Expected length of longest increasing subseque
Post by ThudanBlunder on Mar 20^th, 2009, 10:36pm

on 03/20/09 at 18:50:29, Eigenray wrote:

Suppose we have n rectangles, each with a width and height chosen uniformly at random between 0 and 1. ?

And suppose further that this were possible. LOL

Title: Re: Expected length of longest increasing subseque
Post by Eigenray on Mar 21^st, 2009, 8:19am

Eh? They're mathematical objects. What does "possible" have to do with anything?

Title: Re: Expected length of longest increasing subseque
Post by ThudanBlunder on Mar 21^st, 2009, 2:04pm

on 03/21/09 at 08:19:11, Eigenray wrote:

Eh? They're mathematical objects. What does "possible" have to do with anything?

But impossible mathematical operations should not be a means to an end.

Title: Re: Expected length of longest increasing subseque
Post by towr on Mar 21^st, 2009, 2:30pm

on 03/21/09 at 14:04:39, ThudanBlunder wrote:

But impossible mathematical operations should not be a means to an end.

It's possible up to an arbitrarily close approximation. What's the fuss?
Picking a real number uniformly from a finite interval is well defined mathematically. Besides, I never hear you complain about picking a number from a normal distribution, which is just as 'impossible'.

Title: Re: Expected length of longest increasing subseque
Post by Eigenray on Mar 21^st, 2009, 3:15pm

They're mathematical means to a mathematical end. A sequence of n rectangles is a point in the probability space [0,1]²ⁿ. The number of piles required is a function on this space. I was curious about its expected value. I guess I shouldn't have wasted my time thinking about this impossible problem. Instead I will think about plows that move infinitely fast when there's no snow on the ground.

Title: Re: Expected length of longest increasing subseque
Post by Obob on Mar 21^st, 2009, 6:27pm

on 03/21/09 at 15:15:47, Eigenray wrote:

Instead I will think about plows that move infinitely fast when there's no snow on the ground.

Zing!

Title: Re: Expected length of longest increasing subseque
Post by ThudanBlunder on Mar 28^th, 2009, 11:03am

on 03/21/09 at 15:15:47, Eigenray wrote:

No need to be so touchy. You should know I would never knowingly ~~kee~~ separate you from your mathematical universe. :P

If you like your ploughs to have a demonstrable top speed, what model would you use then?

Title: Re: Expected length of longest increasing subseque
Post by Eigenray on Mar 30^th, 2009, 11:15pm

on 03/28/09 at 11:03:47, ThudanBlunder wrote:

No need to be so touchy. You should know I would never knowingly ~~keep~~ separate you from your mathematical universe. :P

If you like your ploughs to have a demonstrable top speed, what model would you use then?

I don't really care how fast the ploughs move; let them go backwards in time if you want. I just think it's funny that you find a probability question objectionable because it involves, of all things, random numbers.

Suppose instead that we flip a fair coin (not that those exist either) to determine the binary digits of the lengths and widths. With probability one, after a finite number of flips we will have enough information to be able to tell which of any two given numbers is larger.