Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 2012-11-23 03:48:23

Naumberg
Guest

### Longest increasing subsequence

Let

be i.i.d random variables uniformly on [0,1]. Let
be the length of the longest increasing subsequence of
. Show that

Hi forum!

Using the Erdos' lemma I can only deduce that

, which is a weaker bound unfortunately.

I would appreciate any further ideas!

Michael

## #2 2012-11-23 08:19:03

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi Naumberg;

Do you mean contiguous?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #3 2012-11-23 08:36:05

Naumberg
Guest

### Re: Longest increasing subsequence

Hi bobby,

what do you mean by "contiguous" here?

## #4 2012-11-23 08:41:22

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

You want a sequence that is next to each other or can we skip?

Example:

{x4,x5,x6,x7,x8} or {x2, x5, x11, x21, xn}

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #5 2012-11-23 08:44:34

Naumberg
Guest

### Re: Longest increasing subsequence

Ah! Yes, we skip!

## #6 2012-11-23 08:47:06

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

As far as I know the Erdos bound is for integers that are permutations it does not apply to continuous data.

May I ask where you got both bounds you mention in post#1 from?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #7 2012-11-23 09:15:49

Naumberg
Guest

### Re: Longest increasing subsequence

Sure. In the lecture we had the following version of Erdos/Szerkeres which applies to continuous data as well:

Let

be a seuqence of n distinct numbers. Then this sequence contains an increasing subsequence or a decreasing subsequence of length
.

Now define another sequence

. If
is the length of the longest increasing subsequence in
, then
are identically distributed and
. So this lower bound is proven. In the lecture we even showed that
and that
.

In our exercise we need to prove that

. Does this help?

## #8 2012-11-23 09:28:01

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi;

I am looking at a paper that discusses this problem but I am not understanding where he is going. Maybe you can follow it better:

http://citeseerx.ist.psu.edu/viewdoc/do … 1&type=pdf

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #9 2012-11-23 09:39:06

Naumberg
Guest

### Re: Longest increasing subsequence

Hi

I cross-checked the paper and this is clearly way to complicated as we usually solve those exercises with one page maximum. One can attend this lecture from the third year or higher.

## #10 2012-11-23 09:42:42

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi;

Is the lecture online?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #11 2012-11-23 10:15:17

Naumberg
Guest

### Re: Longest increasing subsequence

Unfortunately not. But I could scan you the respective page from the notes. Is there a possibility to upload it here?

## #12 2012-11-23 10:21:05

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi;

Yes, just use image upload in Post reply. Do not use quick post.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #13 2012-11-23 10:30:17

Naumberg
Guest

### Re: Longest increasing subsequence

Mmh, I am really a newbie

1. Post a reply - ok
2. upload - how/where? I see no button and cannot use ""

## #14 2012-11-23 10:38:05

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi;

Do you see this?

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #15 2012-11-23 11:12:20

Naumberg
Member
Registered: 2012-11-23
Posts: 3

### Re: Longest increasing subsequence

Logging in is sometimes helpful ...

Offline

## #16 2012-11-23 11:30:38

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi;

I will look at it and post if I solve it. Thanks for the images.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #17 2012-11-23 11:37:20

Naumberg
Member
Registered: 2012-11-23
Posts: 3

Offline

## #18 2012-11-23 17:06:09

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi Naumberg;

I have looked through 3 papers on this exact subject and the original paper by Erdos and Szekeres. In all of them it seems that the bound

was a major achievement. I could not find anyway to tie in what they were doing with the sharper bound you are interested in. I would very much like to see your answer when you find it.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #19 2012-11-26 12:16:29

Naumberg
Member
Registered: 2012-11-23
Posts: 3

### Re: Longest increasing subsequence

Hi bobbym!

I solved the problem. Please find my tex code below (compile yourself for better reading, sry!)

Cheers
Michael

We want to determine a strategy to select an increasing subsequence of $x_1,...,x_n$. Let $Y$ be the length of our increasing subsequence. As $X$ is defined as the longest increasing subsequence we surely have $E[X] \ge E[Y]$. Depending on how good our strategy is we hope to get $E[Y] \ge (1-o(1))(1-\frac{1}{e})\sqrt{n}$ which would complete the proof.

Let us assume that $m:= \sqrt{n}$ is an integer and partition our random sequence in blocks $L_j=(x_{(j-1)m+1},...,x_{jm} )$ for $j=1,...,m$ (we can assume this as we look at asymptotics in $n$ in the end).

The strategy picks the first number $y_1$ out of $x_1,...,x_n$ that is $\le \frac{1}{m}$ and skips to the next block. It then continuous to pick a number $y_i$ in each of the remaining blocks if $y_{i-1} \le y_i \le y_{i-1} + \frac{1}{m}$ and skips this block otherwise. At the end we receive an increasing subsequence $y_1,...,y_Y$ of length $Y$.

input: sequence x(1),...x(n)
output: length Y of an increasing subsequence y(1)<=...<=y(Y)

Y = 0         \\ counting the length of the subsequence
s = zero array     \\ storing the subsequence here

\\ go through intervals elements of L_j
for j = 1 to m
{
\\ boolean helper to implement stopping time, i.e. breaking condition for the loop
success == 0
while (success == 0) do
{
\\ go through elements of L_j
for k = (j-1)*m+1 to j*m
{
\\ find a larger element which is still small enough
if (s(Y) <= x_k <= s(Y)+1/m)
{
Y = Y+1       \\ length of subsequence ++
s(Y) = x_k      \\ store element
success == 1   \\ stop searching in L_j
\\ and go to next interval
}
}
}
}

return(Y)

Now let us estimate the expectation of $Y$,

\begin{alignat*}{1}
E[Y] &= E[\sum_{j=1}^{m} \mathds{1}_{\{ \text{ "found suitable number in }L_j\text{ " }\}}]\\
&= \sum_{j=1}^{m}E[ \mathds{1}_{\{ \text{ "found suitable number in }L_j\text{ " }\}}]
\end{alignat*}

As our "tolerance of increase" $\frac{1}{m}$ stays the same for all numbers we search for, all $x_i$ are independently and uniformly distributed and all parts of the sequence $L_j$ contain the same amount of numbers $m$ we get that

\begin{alignat*}{1}
E[Y] &= m P[ \text{ "found suitable number in }L_1 \text{ " }]\\
&= m (1- P[\forall i=1,...,m : x_i > \frac{1}{m}]) \\
&= m (1- (P[x_1 > \frac{1}{m}])^m) \\
&= m (1- (1- \frac{1}{m})^m) \\
&= \sqrt{n} (1- (1- \frac{1}{\sqrt{n}})^{\sqrt{n}}) \\
&= (1-o(1))(1-\frac{1}{e})\sqrt{n}.
\end{alignat*}

So our strategy gives the lower bound $E[X] \ge E[Y]$.

Offline

## #20 2012-11-26 19:17:56

bobbym
From: Bumpkinland
Registered: 2009-04-12
Posts: 105,319

### Re: Longest increasing subsequence

Hi;

I am sorry but I can not read that very well.

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
No great discovery was ever made without a bold guess.

Offline

## #21 2012-11-27 02:27:21

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,016

### Re: Longest increasing subsequence

Hi naumberg

You can use the math tag {math}{/math} except that the brackets are square and not curly...

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline