Expectation value of a card game (spider solitaire)

Question

The rule is similar to spider solitaire but simpler.

There are n cards, each with a unique number from 1 to n. The cards are drawn one by one, and the first card is placed directly on the table. After the second card is compared with the value of the card on the table, if the value of the card drawn is relatively large, it will cover the card on the table. (Otherwise will be discarded)Find out the expectation value of how many cards are on the table after the above operations are completed.

I think there is a recurrence formula E(n)=1+∑n−1k=0E(k)n$E(n)=1+\frac{\sum _{k=0}^{n-1}E(k)}{n}$ while E(0)=1,E(1)=1$E(0)=1,E(1)=1$ but I stuck here and don't know how to do the next step. Maybe there is another way to solve the problem.

Can anyone help me?

Answer 1

Let's prove by induction that E(n)=E(n−1)+1/n$E(n)=E(n-1)+1/n$, E(1)=1$E(1)=1$.

For n=1$n=1$ and even n=2$n=2$ we have the result, so let's assume we've proved it to n−1$n-1$. The expected number of the cards above the table are exactly E(n−1)$E(n-1)$ when you throw the first n−1$n-1$ cards. The last card has a 1/n$1/n$ chance of being larger than all the previous ones, in which case we would have 1$1$ card added, and (n−1)/n$(n-1)/n$ chance of not being the largest. Multiplying each case with the corresponding probability, we have:

E(n)=E(n−1)⋅n−1n+(E(n−1)+1)1n=E(n−1)+1n.$$E(n)=E(n-1)\cdot \frac{n-1}{n}+(E(n-1)+1)\frac{1}{n}=E(n-1)+\frac{1}{n}.$$

So E(n)=∑ni=11i$E(n)=\sum _{i=1}^n\frac{1}{i}$.