World's most popular travel blog for travel bloggers.

# Probability of having a log(n) length monotone subsequence in a random permutation of {1,...,n}

, ,
Problem Detail:

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

###### Answered By : Yuval Filmus

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

Question Source : http://cs.stackexchange.com/questions/37813

3200 people like this