```

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 26th, 2009, 2:51am)

```

Title: Expected length of longest increasing subsequence
Post by Eigenray on Feb 26th, 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 26th, 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 26th, 2009, 3:14am
...yes.

Title: Re: Expected length of longest increasing subseque
Post by Aryabhatta on Mar 14th, 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 n2 + 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 20th, 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 20th, 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 20th, 2009, 6:50pm

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 20th, 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 21st, 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 21st, 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 21st, 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 21st, 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]2n.  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 21st, 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 28th, 2009, 11:03am

on 03/21/09 at 15:15:47, Eigenray wrote:
 They're mathematical means to a mathematical end.  A sequence of n rectangles is a point in the probability space [0,1]2n.  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.

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 30th, 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. :PIf 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.