Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.