Expected number of cards in the stack?

Question

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?

Answer 1

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.

Answer 2

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)$

Answer 3

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}$$