Math Is Fun Forum

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