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}

, , No Comments
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$.

Asked By : JonyWalk
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). $$

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback