1. ## another probability question

A deck of cards with numbers on: 1,2,...,N. Draw a card randomly from the
deck, keep it at hand, then draw another one; if the new one is larger than
the largest number in the hand, keep it, otherwise, discard it. Stop when
you have the card N. Question: What is the expectation of the numbers of
cards at hand.

2. This is a nice problem! This is from high school???

Let's denote given $\displaystyle N$ cards, let $\displaystyle X$ be the number on the first card you pick, and let $\displaystyle C^N$ be the random variable of the number of cards you pick for $\displaystyle N$ cards. The reason, I have all the different random variables is that we are going to end up with a recurrence relation.

$\displaystyle \mathbf{E}[C^1]=1$

$\displaystyle \mathbf{E}[C^N]=\mathbf{E}[\mathbf{E}[C^N\ |\ X]]$

Since $\displaystyle \mathbf{P}(X=i)=\frac{1}{N}$:

$\displaystyle =\sum_{i=1}^{N}\mathbf{E}[C^N\ |\ X=i]\frac{1}{N}$

Ok, here is the trick. Suppose you pull a 4 (X=4). From the standpoint of $\displaystyle C^N$, you could just throw away the 1, 2, and 3 cards from the deck. They do not impact $\displaystyle C^N$ anymore. So now you have a deck containing 5 to N. The position you are in now is exactly the same as if you had N-5 cards and you hadn't started yet except that you already picked a card. So you get:

$\displaystyle =\frac{1}{N}\sum_{i=1}^{N}\left(\mathbf{E}[C^{N-i}]+1\right)$

A little manipulation and you get:
$\displaystyle \mathbf{E}[C^N]=1+\frac{1}{N}\sum_{i=1}^{N-1}\mathbf{E}[C^{\,i}]\hspace{1cm}(1)$

This is a nasty recurrence relation so let's try to get rid of most of the terms. So then:
$\displaystyle \mathbf{E}[C^{N-1}]=1+\frac{1}{N-1}\sum_{i=1}^{N-2}\mathbf{E}[C^{\,i}]\hspace{1cm}(2)$

Now multiply (2) by $\displaystyle (N-1)/N$ and subtract from (1) (so we can eliminate most of the terms in the sum).

$\displaystyle \mathbf{E}[C^N]-\frac{N-1}{N}\mathbf{E}[C^{N-1}]=1-\frac{N-1}{N}+\frac{1}{N}\mathbf{E}[C^{N-1}]$

More manipulation:

$\displaystyle \mathbf{E}[C^N]=\frac{1}{N}+\mathbf{E}[C^{N-1}]$

Yet more:

$\displaystyle \mathbf{E}[C^N]=\sum_{i=1}^N\frac{1}{i}$

3. Originally Posted by iq987
A deck of cards with numbers on: 1,2,...,N. Draw a card randomly from the
deck, keep it at hand, then draw another one; if the new one is larger than
the largest number in the hand, keep it, otherwise, discard it. Stop when
you have the card N. Question: What is the expectation of the numbers of
cards at hand.

Hi iq987,

You have had one correct solution so far; here is another way to solve the problem. (You can never have too many solution methods.)

Let $\displaystyle X_i = 1$ if card $\displaystyle i$ is the largest seen so far, i.e. $\displaystyle X_i > X_j \text{ for all } j < i$, and let $\displaystyle X_i = 0$ otherwise.

What is the probability that $\displaystyle X_i = 1$? There have been $\displaystyle i$ cards dealt so far, and each is equally likely to be the largest of $\displaystyle X_1, X_2, \dots ,X_i$; so

$\displaystyle Pr(X_i =1) = 1/i$
and
$\displaystyle E(X_i) = 1/i$

Hence
$\displaystyle E(X_1 + X_2 + \dots + X_N) = E(X_1) + E(X_2) + \dots + E(X_N) = 1 + 1/2 + \dots + 1/N$.

Here we have used the theorem that $\displaystyle E(X+Y) = E(X) + E(Y)$. This is true even if X and Y are not independent, which is essential to the solution because the $\displaystyle X_i$'s are not independent.

4. Originally Posted by awkward
Hi iq987,

You have had one correct solution so far; here is another way to solve the problem. (You can never have too many solution methods.)

Let $\displaystyle X_i = 1$ if card $\displaystyle i$ is the largest seen so far, i.e. $\displaystyle X_i > X_j \text{ for all } j < i$, and let $\displaystyle X_i = 0$ otherwise.

What is the probability that $\displaystyle X_i = 1$? There have been $\displaystyle i$ cards dealt so far, and each is equally likely to be the largest of $\displaystyle X_1, X_2, \dots ,X_i$; so

$\displaystyle Pr(X_i =1) = 1/i$
and
$\displaystyle E(X_i) = 1/i$

Hence
$\displaystyle E(X_1 + X_2 + \dots + X_N) = E(X_1) + E(X_2) + \dots + E(X_N) = 1 + 1/2 + \dots + 1/N$.

Here we have used the theorem that $\displaystyle E(X+Y) = E(X) + E(Y)$. This is true even if X and Y are not independent, which is essential to the solution because the $\displaystyle X_i$'s are not independent.
I was holding back to see if you'd apply your 'bus stop' technique here:

http://www.mathhelpforum.com/math-he...-stop-bus.html

5. Oh sure, pick the easy way to do the problem. I don't like it. Not enough sweat.

6. When you don't know much math you have to make the little bit you know work extra hard.

jw

7. Originally Posted by awkward
When you don't know much math you have to make the little bit you know work extra hard.

jw
So are you saying I don't know much math so I have to do a lot of work to get the same result?

Or are you saying you don't know much math so you have to squeeze every little bit out of it?

8. [joke] I'm saying I must force almost every problem into the Expected Value Theorem + Indicator Variable framework because it is one of the few methods I understand. [/joke]

it is an interview question

Originally Posted by meymathis
This is a nice problem! This is from high school???

Let's denote given $\displaystyle N$ cards, let $\displaystyle X$ be the number on the first card you pick, and let $\displaystyle C^N$ be the random variable of the number of cards you pick for $\displaystyle N$ cards. The reason, I have all the different random variables is that we are going to end up with a recurrence relation.

$\displaystyle \mathbf{E}[C^1]=1$

$\displaystyle \mathbf{E}[C^N]=\mathbf{E}[\mathbf{E}[C^N\ |\ X]]$

Since $\displaystyle \mathbf{P}(X=i)=\frac{1}{N}$:

$\displaystyle =\sum_{i=1}^{N}\mathbf{E}[C^N\ |\ X=i]\frac{1}{N}$

Ok, here is the trick. Suppose you pull a 4 (X=4). From the standpoint of $\displaystyle C^N$, you could just throw away the 1, 2, and 3 cards from the deck. They do not impact $\displaystyle C^N$ anymore. So now you have a deck containing 5 to N. The position you are in now is exactly the same as if you had N-5 cards and you hadn't started yet except that you already picked a card. So you get:

$\displaystyle =\frac{1}{N}\sum_{i=1}^{N}\left(\mathbf{E}[C^{N-i}]+1\right)$

A little manipulation and you get:
$\displaystyle \mathbf{E}[C^N]=1+\frac{1}{N}\sum_{i=1}^{N-1}\mathbf{E}[C^{\,i}]\hspace{1cm}(1)$

This is a nasty recurrence relation so let's try to get rid of most of the terms. So then:
$\displaystyle \mathbf{E}[C^{N-1}]=1+\frac{1}{N-1}\sum_{i=1}^{N-2}\mathbf{E}[C^{\,i}]\hspace{1cm}(2)$

Now multiply (2) by $\displaystyle (N-1)/N$ and subtract from (1) (so we can eliminate most of the terms in the sum).

$\displaystyle \mathbf{E}[C^N]-\frac{N-1}{N}\mathbf{E}[C^{N-1}]=1-\frac{N-1}{N}+\frac{1}{N}\mathbf{E}[C^{N-1}]$

More manipulation:

$\displaystyle \mathbf{E}[C^N]=\frac{1}{N}+\mathbf{E}[C^{N-1}]$

Yet more:

$\displaystyle \mathbf{E}[C^N]=\sum_{i=1}^N\frac{1}{i}$

10. don't understand your solution, it looks very neat though

what is the definition of X_i?
Why is 'There have been $\displaystyle i$ cards dealt so far, and each is equally likely to be the largest of $\displaystyle X_1, X_2, \dots ,X_i$'?

$\displaystyle Pr(X_i =1) = 1/i$?

thanks

Originally Posted by awkward
Hi iq987,

You have had one correct solution so far; here is another way to solve the problem. (You can never have too many solution methods.)

Let $\displaystyle X_i = 1$ if card $\displaystyle i$ is the largest seen so far, i.e. $\displaystyle X_i > X_j \text{ for all } j < i$, and let $\displaystyle X_i = 0$ otherwise.

What is the probability that $\displaystyle X_i = 1$? There have been $\displaystyle i$ cards dealt so far, and each is equally likely to be the largest of $\displaystyle X_1, X_2, \dots ,X_i$; so

$\displaystyle Pr(X_i =1) = 1/i$
and
$\displaystyle E(X_i) = 1/i$

Hence
$\displaystyle E(X_1 + X_2 + \dots + X_N) = E(X_1) + E(X_2) + \dots + E(X_N) = 1 + 1/2 + \dots + 1/N$.

Here we have used the theorem that $\displaystyle E(X+Y) = E(X) + E(Y)$. This is true even if X and Y are not independent, which is essential to the solution because the $\displaystyle X_i$'s are not independent.

11. Originally Posted by iq987
don't understand your solution, it looks very neat though

what is the definition of X_i?
Why is 'There have been $\displaystyle i$ cards dealt so far, and each is equally likely to be the largest of $\displaystyle X_1, X_2, \dots ,X_i$'?

$\displaystyle Pr(X_i =1) = 1/i$?

thanks
Originally Posted by awkward
[snip]

Let $\displaystyle X_i = 1$ if card $\displaystyle i$ is the largest seen so far, i.e. $\displaystyle X_i > X_j \text{ for all } j < i$, and let $\displaystyle X_i = 0$ otherwise.

[snip]
..