0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ When you draw the third card, which do you compare it to? The higher of the two (if you have kept both) or the first one? $\endgroup$ Feb 29, 2016 at 17:42
  • $\begingroup$ @RossMillikan the third card is compared to the second card if it has been kept (i.e higher than first) $\endgroup$
    – user223935
    Feb 29, 2016 at 17:46

2 Answers 2

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thanks for your very clear explanation, this gives a great intuition about the whole problem. Do you believe that my comment above which justifies the relation $e_N=e_{N-1}+\frac{1}{N}$ is also correct? $\endgroup$
    – user223935
    Feb 29, 2016 at 19:20
  • 1
    $\begingroup$ @user223935 I've edited last section of the answer to show how Ross Millikan's answer can be used to deduce correct conclusion. $\endgroup$
    – user160738
    Feb 29, 2016 at 19:49
  • $\begingroup$ Ok thanks man, just one last thing. Do you think there is a possible intuitive interpretation of the logarithmic order which appears when the number of cards becomes large? $\endgroup$
    – user223935
    Feb 29, 2016 at 20:38
  • $\begingroup$ @user223935 As in Ross Millikan's answer, it is a known fact that harmonic numbers more or less behave logarithmically when $N$ is large. You can interpret the result as $e_N/\log N \to 1 $ as $N\to \infty$. You can say a bit more about it, using E-M constant as $e_N\approx \log N + \gamma$. I think the wikipedia page on the topic (which is linked in his answer) does a good intuitive explanation of the phenomena at some point, where it shows how area under the graph $1/x$ can be interpreted as the harmonic sum. Then you can relate it to the integral of the function, which is evidently $\log x$ $\endgroup$
    – user160738
    Mar 1, 2016 at 4:04
1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Thanks for your input. So I guess the problem can be solved directly (by immediate induction) in the following way. Suppose that playing with $N-1$ cards we end up on average with $e_{N-1}$ cards. With $N$ cards, we end up with one extra card if and only if the $N$-th card is higher in value than all the other cards, which happens with probability $\frac{1}{N}$. $\endgroup$
    – user223935
    Feb 29, 2016 at 18:30
  • $\begingroup$ Can we also find an interpretation for the $e_N=\frac{1}{N}\sum_{i=1}^{N-1} e_i+1$ relation? $\endgroup$
    – user223935
    Feb 29, 2016 at 18:33
  • $\begingroup$ For the logarithmic order I was aware of Euler's constant, but I am trying to understand it from a heuristic viewpoint. A bit like with binary search, the complexity is logarithmic because we half the search interval at each iteration, something along those lines. $\endgroup$
    – user223935
    Feb 29, 2016 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .