Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given n numbers (each of which is a random integer, uniformly between 1~n), what is the expected number of increasing subsequences?

share|improve this question
Hint: linearity of expections. –  Boris Bukh Feb 8 '12 at 14:29
This question is much better suited to math.stackexchange.com, where it is likely to receive a warmer welcome and attract a very quick answer. –  cardinal Feb 8 '12 at 14:34
If it is asked at math.stackexchange.com, and it is homework, it should be clearly marked as such –  Yemon Choi Feb 8 '12 at 16:39
add comment

closed as too localized by Bill Johnson, Emil Jeřábek, Did, Yemon Choi, Bruce Westbury Feb 8 '12 at 19:07

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

This is not a research-level question and should be closed, but since someone already gave a wrong answer, I’ll write the correct one.

Given independently uniformly random $x_1,\dots,x_k\in\{1,\dots,n\}$, the probability that the $x_i$’s are pairwise distinct is $n(n-1)\cdots(n-k+1)n^{-k}$, hence the probability that $x_1< x_2<\dots< x_k$ is $\binom nkn^{-k}$. By linearity of expectation, the expected number of increasing subsequences in a randomly chosen sequence $(x_1,\dots,x_n)$ is thus $$\sum_{k=0}^n\binom nk^2n^{-k}.$$ Note that this includes the empty sequence (which is vacuously increasing).

share|improve this answer
Thanks! But any one to judge whether this is correct? –  flyusa2010 Feb 8 '12 at 14:51
But any one to judge whether this is correct? First, this is rude. Second, the answer might be: yourself. –  Did Feb 8 '12 at 15:06
flyusa2010: heaven helps those who help themselves –  Yemon Choi Feb 8 '12 at 16:38
add comment

According to:

MR0626437 (84e:05012) Lifschitz, V.; Pittelʹ, B.

"The number of increasing subsequences of the random permutation. "

The answer for permutations on $n$ elements is:

$\sum_{k = 1}^n C_{n,k}/k!$
where $C_{n,k}$ is the number of subsets with $k$ elements.

The reason is that for each subset $I$ of $k$ indices from $1$ to $n$ there is a $1/k!$ chance that a random permutation will be increasing when restricted to $I$ (for each set of values only $1$ out of the $k!$ yields an increasing sequence).

share|improve this answer
The OP’s experiment does not give permutations. –  Emil Jeřábek Feb 8 '12 at 14:36
Thanks very much! –  flyusa2010 Feb 8 '12 at 14:39
@Emil Your right, I misread the question. –  Pablo Lessa Feb 8 '12 at 15:49
add comment

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