Let's suppose that I have a sequence of length $L$ of uniformly distributed random numbers on interval $(a,b)$. How can I calculate probability that increasing sub-sequence of length $M,M <L, $ will occur?
5
-
$\begingroup$ Is $(a, b)$ an interval of reals or something else? $\endgroup$– Ben BarberCommented May 8, 2015 at 22:38
-
$\begingroup$ You seem to be asking for the probablity that a continuous random variable takes a particular value. If that is not what you meant, could you please clarify? $\endgroup$– Yemon ChoiCommented May 8, 2015 at 22:51
-
$\begingroup$ Sorry, I forgot to write that it's about increasing sub-sequences. I edited now. Yes, $a,b\in R$. $\endgroup$– user23709Commented May 9, 2015 at 9:42
-
$\begingroup$ Ah, right, now this makes more sense. But presumably you can WLOG take $a=0, b=1$? $\endgroup$– Yemon ChoiCommented May 9, 2015 at 21:11
-
$\begingroup$ @YemonChoi Yes, of course, it can be interval $(0,1)$. $\endgroup$– user23709Commented May 10, 2015 at 11:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Equivalently, you may count the probability of an increasing sub-sequence of length $M$ in a random permutation of $1,2,\dots,L$.
To determine this probability, it is enough to know the number of $L$-permutations avoiding an increasing pattern of length $M+1$. For $M=1$, there is just one such $L$-permutation. For $M=2$, these permutations are counted by Catalan numbers. For $M=3$, see the OEIS sequence A005802.
For general fixed $M$, asymptotic formulas were computed by Regev, see also this paper by Bóna. Very roughly, the number of $L$-permutations with no increasing subsequence of length $M+1$ is $(2M)^L$ up to a polynomial factor in $L$.
