7
$\begingroup$

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?

  • 0
    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$.2012-05-01

3 Answers 3

2

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.

  • 0
    @Joe: In my first draft of the answer I only called it "the first card"; then I noticed that that could be misunderstood to refer to the dummy card, so I added "$v_0$" to clarify that. I usually stick to the notation used in the question to keep things clear; if there had been some cogent reason to deviate from your notation, I would have explicitly announced that I was deviating from it.2012-05-06
1
  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)$
  • 0
    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.2012-05-01
1

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

  • 1
    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$.2012-05-04