Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a follow-up to a previous question (which received excellent answers, thanks!):
Expected number of "good" balls drawn from an urn.

Suppose we have a $n$ balls in an urn labeled $1$ through $n$, and we draw balls without replacement. Suppose we draw a first ball, and then draw an additional $k$ balls uniformly at random without replacement. What is the expected number of balls which have a label larger than the label of the first ball?

In this version, we are given an urn containing $n$ balls, and again we are drawing uniformly at random without replacement. Again, we draw a first ball with label $1 \leq x \leq n$, and an additional $k$ balls.

Let $\ell_i$ denote the label of ball $i$, and suppose that $j$-th ball drawn is the first ball such that $\ell_j > x$. A maximal decreasing subsequence is the largest subsequence of balls such that the respective labels of these balls are in decreasing order, and none of these balls have labels less than $x$.

That is, there is a maximal subsequence of size $d$ if:

  • for all balls $i < j$, the labels are $\ell_i < x$, and
  • beginning with ball $j$, there are balls $S_1 = j, S_2, \ldots S_d$ with labels such that $$ \ell_{S_1} > \ell_{S_2} > \cdots > \ell_{S_d} > x $$ and
  • any balls $b$ not in the subsequence either have a label $\ell_b < x$ or come after ball $S_a$ and have a label $\ell_b > \ell_{S_a}$

Note that the subsequence must be in order, but not necessarily contiguous. In particular for any ball in the sequence $S_i < S_{i+1}$, but we don't require that $S_{i+1} = S_i + 1$.

What is the expected length of a maximal decreasing sequence?

share|improve this question
Tons is known on longest increasing subsequence in a permutation. Restricting to balls $ > x$ should just restrict you to the permutation of elts $> x$. Expected length for permutaion of 1,...,N is like $2 \sqrt(N)$. I would think $E ( 2 \sqrt(n-x))$ would be right. See aldous & diaconis, longest increasing subsequences, if interested. –  mike Apr 26 '12 at 21:52
@mike thanks for the reference. If you want to expand your comment into an aswer, I'll probably vote up. –  Joe Apr 26 '12 at 22:52
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.