1
$\begingroup$

How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$.

I wish to upperbound it with $1/n$.

$\endgroup$
  • 3
    $\begingroup$ Is there any particular reason you're asking this at CS rather than Mathematics? $\endgroup$ – David Richerby Jan 31 '15 at 21:51
1
$\begingroup$

You can upper bound this probability as follows. The relative order within a consecutive subsequence of a random permutation is just another random permutation, so the probability that a specific consecutive subsequence of length $\log n$ is monotone is exactly $2/(\log n )!$. Since there are at most $n$ of this (actually, exactly $n-\log n+1$), the probability is at most $$ \frac{2n}{(\log n)!} \sim \frac{2n}{\sqrt{2\pi\log n}(\log n/e)^{\log n}} = o\left(\frac{1}{n}\right). $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.