Expected number of cards in the stack?

Suppose we have a deck of cards, ordered [1,52] (using e.g. the bridge ordering). Shuffle the cards (uniformly at random). Turn over the top card, it has value $v_0$.

We will turn over cards one by one and place them either on the stack or in the discard.

The stack starts off empty. Let $v_t$ be the value of the top card in the stack (or $\infty$ when the stack is empty).

Now we begin turning over additional cards. For each card $i$ with value $v_i$, if $v_0 < v_i < v_t$ then we place card $i$ on the top of the stack, so that now $v_t = v_i$. Otherwise, we place card $i$ in the discard.

After turning over $k$ cards, what is the expected number of cards in the stack?

• This is related to longest increasing/decreasing subsequence in a permutation, but I don't think it's the same. For example, if the first card in the stack has value $v_0 + 1$, then the size of the stack will be 1, even if the discard pile has a decreasing subsequence of length $k-1$. – Joe May 1 '12 at 18:37

In a circle with $53$ cards, choose one dummy card uniformly at random and number the remaining cards beginning at that position, say, clockwise. Then draw from the numbered cards as you described. The condition for putting the card $v_i$ on the stack is fulfilled if and only if the card is the clockwise neighbour of the first card $v_0$ among all the cards drawn up to that point (including the dummy card), and by symmetry the probability for that is $1/(i+1)$. Thus the expected number of cards on the stack after turning over $k$ cards (in addition to the first card) is

$$\sum_{i=1}^k\frac1{i+1}=\sum_{j=2}^{k+1}\frac1j=H_{k+1}-1\;,$$

where $H_k$ is the $k$-th harmonic number. Note that the probability of each card to be counted as a record low is exactly the same as it is in the standard case without special treatment of the first card; the result in that case would be $H_{k+1}$, and $1$ is subtracted from that because the first card doesn't count as a record low.

• "condition for putting the card vi on the stack is fulfilled if and only if the card is the clockwise neighbour of the first card v0 among all the cards drawn up to that point (including the dummy card)" This seems to ignore the threshold. A card that's just counter-clockwise of the dummy card will be the first clockwise neighbor, however, it shouldn't be put in the stack. – Joe May 4 '12 at 22:02
• @Joe: I don't understand "A card that's just counter-clockwise of the dummy card will be the first clockwise neighbor" -- of what? Do you mean the clockwise neighbour of the first card $v_0$? If so, why would that be? A card that's just counter-clockwise of the dummy card is the highest card; it should be put on the stack if and only if it's the clockwise neighbour of the first card $v_0$, as in any other case; I don't see how the case where it's just counter-clockwise of the dummy card is any different than other cases. – joriki May 5 '12 at 11:07
• Maybe I don't understand your answer. Where are the cards that are less than $v_0$ in the clockwise order? – Joe May 5 '12 at 19:59
• @Joe: I'm not sure I understand that question; I suspect that there's some deeper misunderstanding that we haven't identified yet. The cards are numbered clockwise, beginning at the position of the dummy card, so the cards that are less than $v_0$ are the ones that lie between the dummy card and $v_0$ (going clockwise). – joriki May 5 '12 at 21:19
• I thought you were calling $v_0$ the dummy card. I think I see what you were saying. – Joe May 6 '12 at 1:42
1. I think $v_0$ never changes, so you are sort of restricted to cards bigger that $v_0$ right at the start
2. If $v_0$ is 0 (which I realize it is not) , you put a new card on the stack if it is a record low, and by symmetry the probability that the $j^{th}$ you turn over is a record low is $\frac 1 j$, so the expected number of cards after you've turned over n cards is like $log(n)$.
3. when $v_0$ isn't 0, this argument more or less works, but the card you turn over has to be $> v_0$, and a new low among all other cards $> v_0$. This involves conditioning on the number of such cards , which I think is hypergeometric, and something can be ground out.
4. If you only want to know how many cards after you've gone through the whole deck, then conditional on $v_0$ it's like $log(53 - v_0)$
• (2) is well known. (3) is the crux, but the above is too sketchy. I agree that the number of cards $> v_0$ is hypergeometric. – Joe May 1 '12 at 19:31
• Let $L$ be the number of record lows, and let $D$ be the number of cards $> v_0$. Then $E[L] = E[E[L|D]] = \sum E[L|D]p(D)$, where $p(D)$ is hypergeometric. I was really hoping for something more elegant than that... something that could be given in closed form. – Joe May 1 '12 at 19:39

I use an approach similar to mike one, but obtaining a closed formula.

First solve a simpler problem, you have $v_0=0$ and $n$ cards, the expected number of record low, as stated by mike, is $\sum_{i=1}^{n} 1/i$.

Now increasing $v0$, we can just discard all the cards below $v_0$, so we can solve the subproblem with $v_0=0$ and $n=N-v_0$. Doing the summation for each $v_0$: $$\sum_{j=1}^N \frac{1}{N}\sum_{i=1}^{N-j}\frac{1}{i}=\frac{1}{N}\sum_{i=1}^N\frac{N-i}{i}=\frac{1}{N}\sum_{i=1}^N(\frac{N}{i}-1)=\sum_{i=1}^N\frac{1}{i}-1$$

For $N=52$, the solution is $\simeq3.538$.

EDIT: I've see now that i've forgot that we are interested in the expectation after $k$ cards, we should do the summation only the first $k-1$ terms. $$\mathbb{E}(k,N)=\frac{1}{N}\sum_{i=1}^{k-1}(\frac{N}{i}-1)=\sum_{i=1}^{k-1}\frac{1}{i}-\frac{k-1}{N}$$

• That works if you turn over all the cards in the deck. What if you only turn over $k$? – Joe May 1 '12 at 22:16
• @Joe: I've forgot to consider $k$, I've added this part. – carlop May 2 '12 at 7:45
• For that to work, do you need to assume that the number of record lows and the number $> v_0$ are independent? $E[X,Y] = E[X]\cdot E[Y]$ only when $X$ and $Y$ are independent. – Joe May 2 '12 at 19:24
• I don't see any reason why that sum should give the right result if you truncate it at $k-1$. That would seem to assume that the $i$-th term in the sum is the expected value for the $(i+1)$-th card drawn, but that's clearly not the case, e.g. for $i=2$. – joriki May 4 '12 at 15:51