# Longest consecutive subsequence bound with limit

Let $S\subseteq \{1,2,\ldots,n\}$ and let $X(S)$ be the length of maximal consecutive subsequence in $S$.

For example: if $S=\{4,5,7,8,9,11,12\}$ then $X(S)=3$ because of the subsequence $\{7,8,9\}$.

Let $S\subseteq \{1,2,\ldots,n\}$ chosen uniformly from $\{1,2,\ldots,n\}$'s subsequences.

I need to find a function $f(n)$, such that for any $\varepsilon>0$ we have:

$$\lim_{n\to \infty}(\Pr((1-\varepsilon)f(n)\le X(S) \le (1+\varepsilon)f(n))) = 1$$

-
Don't you mean $n\to \infty$ rather than $x$? –  Jean-Sébastien Feb 17 '13 at 18:24
you are right, got it corrected. thanks –  user123 Feb 17 '13 at 18:43
It is quite surprising that such a function $f$ should exist. If it exists, I think it must be something like $f(n) = \log_2(n)$. –  azimut Aug 26 '13 at 23:51