Results 1 to 11 of 11

Math Help - another probability question

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    5

    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.

    details please
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jul 2008
    Posts
    138
    This is a nice problem! This is from high school???

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

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

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

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

    =\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 C^N, you could just throw away the 1, 2, and 3 cards from the deck. They do not impact 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:

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

    A little manipulation and you get:
    \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:
    \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 (N-1)/N and subtract from (1) (so we can eliminate most of the terms in the sum).

    \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:

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

    Yet more:

    \mathbf{E}[C^N]=\sum_{i=1}^N\frac{1}{i}
    Last edited by meymathis; July 15th 2008 at 12:10 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by iq987 View Post
    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.

    details please
    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 X_i = 1 if card i is the largest seen so far, i.e. X_i > X_j \text{ for all } j < i, and let X_i = 0 otherwise.

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

    Pr(X_i =1) = 1/i
    and
    E(X_i) = 1/i

    Hence
    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 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 X_i's are not independent.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by awkward View Post
    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 X_i = 1 if card i is the largest seen so far, i.e. X_i > X_j \text{ for all } j < i, and let X_i = 0 otherwise.

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

    Pr(X_i =1) = 1/i
    and
    E(X_i) = 1/i

    Hence
    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 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 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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2008
    Posts
    138
    Oh sure, pick the easy way to do the problem. I don't like it. Not enough sweat.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    When you don't know much math you have to make the little bit you know work extra hard.

    jw
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2008
    Posts
    138
    Quote Originally Posted by awkward View Post
    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?

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    [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]
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jul 2008
    Posts
    5
    thanks for your reply
    it is an interview question

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

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

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

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

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

    =\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 C^N, you could just throw away the 1, 2, and 3 cards from the deck. They do not impact 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:

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

    A little manipulation and you get:
    \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:
    \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 (N-1)/N and subtract from (1) (so we can eliminate most of the terms in the sum).

    \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:

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

    Yet more:

    \mathbf{E}[C^N]=\sum_{i=1}^N\frac{1}{i}
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2008
    Posts
    5
    don't understand your solution, it looks very neat though

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

    Pr(X_i =1) = 1/i?

    thanks

    Quote Originally Posted by awkward View Post
    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 X_i = 1 if card i is the largest seen so far, i.e. X_i > X_j \text{ for all } j < i, and let X_i = 0 otherwise.

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

    Pr(X_i =1) = 1/i
    and
    E(X_i) = 1/i

    Hence
    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 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 X_i's are not independent.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by iq987 View Post
    don't understand your solution, it looks very neat though

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

    Pr(X_i =1) = 1/i?

    thanks
    Quote Originally Posted by awkward View Post
    [snip]

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

    [snip]
    ..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: February 10th 2013, 03:11 PM
  2. Probability question..
    Posted in the Statistics Forum
    Replies: 0
    Last Post: January 21st 2011, 06:04 PM
  3. Probability question involving (A given B type question )
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 9th 2009, 10:08 AM
  4. Probability question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 2nd 2008, 02:39 PM
  5. A probability question and an Expectations question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 29th 2006, 07:13 PM

Search Tags


/mathhelpforum @mathhelpforum