Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 – Mahmoud 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.