wu :: forums « wu :: forums - Expected length of longest increasing subsequence » Welcome, Guest. Please Login or Register. Feb 26th, 2024, 6:25pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Eigenray, Grimbal, towr, SMQ, Icarus, william wu)    Expected length of longest increasing subsequence « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Expected length of longest increasing subsequence  (Read 11354 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,

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:
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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »