Author |
Topic: Expected length of longest increasing subsequence (Read 11391 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Expected length of longest increasing subsequence
« on: Feb 26th, 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,
A n < 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:
Posts: 13730
|
|
Re: Expected length of longest increasing subseque
« Reply #1 on: Feb 26th, 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 26th, 2009, 3:14am » |
Quote Modify
|
...yes.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Expected length of longest increasing subseque
« Reply #3 on: Mar 14th, 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 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:
Posts: 1948
|
|
Re: Expected length of longest increasing subseque
« Reply #4 on: Mar 20th, 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 20th, 2009, 6:05pm » |
Quote 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:
Posts: 1948
|
|
Re: Expected length of longest increasing subseque
« Reply #6 on: Mar 20th, 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 20th, 2009, 10:36pm » |
Quote 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:
Posts: 1948
|
|
Re: Expected length of longest increasing subseque
« Reply #8 on: Mar 21st, 2009, 8:19am » |
Quote 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:
Posts: 4489
|
|
Re: Expected length of longest increasing subseque
« Reply #9 on: Mar 21st, 2009, 2:04pm » |
Quote 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:
Posts: 13730
|
|
Re: Expected length of longest increasing subseque
« Reply #10 on: Mar 21st, 2009, 2:30pm » |
Quote 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:
Posts: 1948
|
|
Re: Expected length of longest increasing subseque
« Reply #11 on: Mar 21st, 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 21st, 2009, 6:27pm » |
Quote 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:
Posts: 4489
|
|
Re: Expected length of longest increasing subseque
« Reply #13 on: Mar 28th, 2009, 11:03am » |
Quote 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. 
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:
Posts: 1948
|
|
Re: Expected length of longest increasing subseque
« Reply #14 on: Mar 30th, 2009, 11:15pm » |
Quote 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.
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print