Given n numbers (each of which is a random integer, uniformly between 1~n), what is the expected number of increasing subsequences?
What is the expected number of increasing subsequence?
-1
$\begingroup$
probability
-
5You should mention that you've already asked this question: http://mathoverflow.net/questions/87890/what-is-the-expected-number-of-increasing-subsequence – 2012-02-08
-
0As currently stated, the questions seems to asks about a random sequence that is allowed to repeat elements (since the default assumption in problems of this kind is that the various numbers in the sequence are independent). However, it looks suspicious that the upper limit for the numbers should be exactly $n$. Could you please state explicitly whether or not the sequence can contain repetitions of the same number? – 2012-02-08