wu :: forums
« wu :: forums - Expected length of longest increasing subsequence »

Welcome, Guest. Please Login or Register.
Sep 30th, 2022, 2:29pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: william wu, SMQ, Icarus, towr, Eigenray, Grimbal)
   Expected length of longest increasing subsequence
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Expected length of longest increasing subsequence  (Read 11034 times)
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Expected length of longest increasing subsequence  
« on: Feb 26th, 2009, 2:51am »
Quote Quote Modify Modify

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 < such that for all n,
 
An < E(n) < Bn
« Last Edit: Feb 26th, 2009, 3:13am by Eigenray » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Expected length of longest increasing subseque  
« Reply #1 on: Feb 26th, 2009, 3:10am »
Quote Quote Modify Modify

Would you prefer something more interesting for A than 0?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Expected length of longest increasing subseque  
« Reply #2 on: Feb 26th, 2009, 3:14am »
Quote Quote Modify Modify

...yes.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Expected length of longest increasing subseque  
« Reply #3 on: Mar 14th, 2009, 11:44am »
Quote Quote Modify Modify

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.
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Expected length of longest increasing subseque  
« Reply #4 on: Mar 20th, 2009, 12:35pm »
Quote Quote Modify Modify

For the upper bound, it suffices to bound the probability that there exists an increasing subsequence of length k.
IP Logged
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Expected length of longest increasing subseque  
« Reply #5 on: Mar 20th, 2009, 6:05pm »
Quote Quote Modify Modify

*Spoiler* A discussion I had at another forum sometime back
 
-- AI
« Last Edit: Mar 20th, 2009, 6:06pm by TenaliRaman » IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Expected length of longest increasing subseque  
« Reply #6 on: Mar 20th, 2009, 6:50pm »
Quote Quote Modify Modify

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?
IP Logged
ThudnBlunder
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Expected length of longest increasing subseque  
« Reply #7 on: Mar 20th, 2009, 10:36pm »
Quote Quote Modify Modify

on Mar 20th, 2009, 6:50pm, 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
« Last Edit: Mar 21st, 2009, 6:18am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Expected length of longest increasing subseque  
« Reply #8 on: Mar 21st, 2009, 8:19am »
Quote Quote Modify Modify

Eh?  They're mathematical objects.  What does "possible" have to do with anything?
« Last Edit: Mar 21st, 2009, 8:20am by Eigenray » IP Logged
ThudnBlunder
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Expected length of longest increasing subseque  
« Reply #9 on: Mar 21st, 2009, 2:04pm »
Quote Quote Modify Modify

on Mar 21st, 2009, 8:19am, 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.  
 
 
 
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Expected length of longest increasing subseque  
« Reply #10 on: Mar 21st, 2009, 2:30pm »
Quote Quote Modify Modify

on Mar 21st, 2009, 2:04pm, 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'.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Expected length of longest increasing subseque  
« Reply #11 on: Mar 21st, 2009, 3:15pm »
Quote Quote Modify Modify

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.
IP Logged
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Re: Expected length of longest increasing subseque  
« Reply #12 on: Mar 21st, 2009, 6:27pm »
Quote Quote Modify Modify

on Mar 21st, 2009, 3:15pm, Eigenray wrote:
Instead I will think about plows that move infinitely fast when there's no snow on the ground.

 
Zing!
IP Logged
ThudnBlunder
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Expected length of longest increasing subseque  
« Reply #13 on: Mar 28th, 2009, 11:03am »
Quote Quote Modify Modify

on Mar 21st, 2009, 3:15pm, 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. Tongue
 
If you like your ploughs to have a demonstrable top speed, what model would you use then?
« Last Edit: Jun 30th, 2009, 1:02am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Expected length of longest increasing subseque  
« Reply #14 on: Mar 30th, 2009, 11:15pm »
Quote Quote Modify Modify

on Mar 28th, 2009, 11:03am, ThudanBlunder wrote:

No need to be so touchy. You should know I would never knowingly keep separate you from your mathematical universe. Tongue
 
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.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board