Author 
Topic: Expected length of longest increasing subsequence (Read 11034 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Expected length of longest increasing subsequence
« on: Feb 26^{th}, 2009, 2:51am » 
Quote 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 26^{th}, 2009, 3:13am by Eigenray » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Expected length of longest increasing subseque
« Reply #1 on: Feb 26^{th}, 2009, 3:10am » 
Quote 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:
Posts: 1948


Re: Expected length of longest increasing subseque
« Reply #2 on: Feb 26^{th}, 2009, 3:14am » 
Quote Modify

...yes.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Expected length of longest increasing subseque
« Reply #3 on: Mar 14^{th}, 2009, 11:44am » 
Quote 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 n^{2} + 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:
Posts: 1948


Re: Expected length of longest increasing subseque
« Reply #4 on: Mar 20^{th}, 2009, 12:35pm » 
Quote 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:
Posts: 1001


Re: Expected length of longest increasing subseque
« Reply #5 on: Mar 20^{th}, 2009, 6:05pm » 
Quote Modify

*Spoiler* A discussion I had at another forum sometime back  AI

« Last Edit: Mar 20^{th}, 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:
Posts: 1948


Re: Expected length of longest increasing subseque
« Reply #6 on: Mar 20^{th}, 2009, 6:50pm » 
Quote 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:
Posts: 4489


Re: Expected length of longest increasing subseque
« Reply #7 on: Mar 20^{th}, 2009, 10:36pm » 
Quote Modify

on Mar 20^{th}, 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 21^{st}, 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:
Posts: 1948


Re: Expected length of longest increasing subseque
« Reply #8 on: Mar 21^{st}, 2009, 8:19am » 
Quote Modify

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

« Last Edit: Mar 21^{st}, 2009, 8:20am by Eigenray » 
IP Logged 



ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Expected length of longest increasing subseque
« Reply #9 on: Mar 21^{st}, 2009, 2:04pm » 
Quote Modify

on Mar 21^{st}, 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:
Posts: 13730


Re: Expected length of longest increasing subseque
« Reply #10 on: Mar 21^{st}, 2009, 2:30pm » 
Quote Modify

on Mar 21^{st}, 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:
Posts: 1948


Re: Expected length of longest increasing subseque
« Reply #11 on: Mar 21^{st}, 2009, 3:15pm » 
Quote 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:
Posts: 489


Re: Expected length of longest increasing subseque
« Reply #12 on: Mar 21^{st}, 2009, 6:27pm » 
Quote Modify

on Mar 21^{st}, 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:
Posts: 4489


Re: Expected length of longest increasing subseque
« Reply #13 on: Mar 28^{th}, 2009, 11:03am » 
Quote Modify

on Mar 21^{st}, 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. If you like your ploughs to have a demonstrable top speed, what model would you use then?

« Last Edit: Jun 30^{th}, 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:
Posts: 1948


Re: Expected length of longest increasing subseque
« Reply #14 on: Mar 30^{th}, 2009, 11:15pm » 
Quote Modify

on Mar 28^{th}, 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. 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 



