Expected number of cards we end up with in game

Question

Suppose that we have $N$ distinct cards arranged in no particular order. If the first card of the pack is less than the second card of the pack, we keep both cards. Otherwise we discard the second one and keep the first one. We then carry on the process in the same way and we want to determine the expected number of cards we end up with. The base cases can be solved in a straightforward way and give us $e_1=1$, $e_2=\frac{3}{2}$ and $e_3=\frac{11}{6}$, where $e_N$ is the expected value we are looking for if we play with $N$ cards. Looking at these base cases, it would appear that we have the following relation: $$e_N=e_{N-1}+\frac{1}{N}=\frac{1}{N}\sum_{i=1}^{N-1} e_i+1=\sum_{i=1}^N\frac{1}{i}.$$ My question is how can we give a heuristic interpretation to this relation, i.e knowing that the expected value we end up with playing with $N-1$ cards is $e_{N-1}$, why should the expected value we end up with playing with $N$ cards be equal to $e_{N-1}+\frac{1}{N}$ (or $\frac{1}{N}\sum_{i=1}^{N-1} e_i+1$)? I am also very interested in trying to understand if there is any underlying explanation for the logarithmic order which would appear to come into play when we play with a large number of cards. Any comments or ideas would be greatly appreciated.

Answer 1

The following does not directly answer why it should be the case that $e_N=e_{N-1}+1/N$, but rather it proves the assertion that $e_{N}=1+1/2+\cdots+1/N$.

Suppose that $e_{n,N}$ denotes the expectation of number of cards you keep by repeating the procedure for $N$ cards, given that your first draw is $n\le N$ (say we number the cards from $1$ to $N$ for simplicity).

Given $N$ cards, your first draw can be $n$ with probability $1/N$, and since distinct first draws partition the sample space, we have

$$ e_{N}=\frac{1}{N} \left( e_{1,N}+e_{2,N}+\cdots+e_{N,N} \right) $$

Now if your first draw is $n$, then as you repeat the procedure any cards whose number is less than $n$ will surely be discarded at some point. So those cards with numbers less than $n$ are irrelevant to your expectation, and in fact it comes down to question of which of cards with numbers bigger than $n$ you keep at the end. Therefore, in fact for any $n$,

$$ e_{n,N}=e_{1,N-(n-1)} $$

On the other hand, if your first draw is indeed $1$, then whatever number is written on the second card you will always keep it. So in a sense you can regard your second draw as a first draw of a new process containing $m-1$ cards. Therefore, we have

$$ e_{1,m}=1+e_{m-1} $$

for any $m\ge 1$ where $e_{0}:=0$ for convenience. It follows that

$$ e_{N}=\frac{1}{N}\left( e_{1,1}+\cdots+e_{1,N} \right)=\frac{1}{N}\left( N+e_{1}+\cdots+e_{N-1} \right) $$

Now you can use induction on $N$ to show that $e_N=\sum_{i=1}^{N} \frac{1}{i}$.

---

Edit: about your respond to @Ross Millikan's answer:

I think written as it is, it is a not quite logically correct.

You'd rather argue like this:

So you will keep last card if and only if the last card is numbered $N$. You can partition the sample space into events where whether or not you keep the last card. Now if you keep the last card, then it means last card is numbered $N$, and so any card before the last card is numbered from $1$ to $N-1$. You can regard the previous cards as a deck with $N-1$ distinct cards, and expectation of number of cards you get from them by repeating procedure is just $e_{N-1}$. Since you always keep the last card, then the expectation given that you keep the last card is just

$$ 1+e_{N-1} $$

Now suppose that you don't keep the last card. Probability of that happening is just $1-1/N=(N-1)/N$. Then last card is numbered some $m\neq N$. Then previous $N-1$ cards are numbered from $1$ to $N$ with $m$ being 'skipped'. But you can the then renumber them from $1$ to $N-1$ without changing the order, so in that case expectation is just $e_{N-1}$.

So by partition principle it follows that

$$ e_N = \frac{1}{N} (e_{N-1}+1) + \frac{N-1}{N} e_{N-1}=e_{N-1}+1/N $$

Answer 2

You keep the $n^{\text{th}}$ card if it is the highest of the first $n$, which happens with probability $\frac 1n$ This explains your value for $e_N$. The logarithmic order then comes from the fact that the integral of $\frac 1n$ is $\log n$. Your $e_N$ are the harmonic numbers, which are very close to $\log n + \gamma$ with $\gamma \approx 0.577$