

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^{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. 

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:
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:
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:
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]^{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 21^{st}, 2009, 6:27pm on 03/21/09 at 15:15:47, Eigenray wrote:
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 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:
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. 

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