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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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]$.

Cool. Thanks in advance for your help!

Logging in is sometimes helpful ...

Pages: **1**