### Order of cards

**Source:**Asked to me by Prateek Srivastava (CSE IITB Alumnus & Yahoo! Software Engineer)

**Problem:**

I have ten cards, Ace,2,3,4,5,6,7,8,9,10. The value of the Ace is 1.

They’re shuffled, then dealt one by one, face up. For the first card, you automatically win $10. For the next 9 cards, if the card face-up is greater than every previous card, you win $10 more.

What is the expected winning amount?

Clarification:

1) Game does not end when you draw a card that is not a winning card. ie, if I pick a 5 first, then a 6, then a 4, the game is not over. I keep drawing until all of the cards are gone

2) It might be useful to know that the chance of winning $100 is 1/10!, because the cards will have to be drawn in the order: {A, 2, 3, 4 … , 9, 10}.

Update (Dec 08, 2010)

Update (Dec 08, 2010)

**Solution:**Posted by Goutham Valeti (Aero IITB Alumnus, Fair Issac Research Scientist) in comments! A more mathematical solution posted by me in comments!
Another solution (Already seen yours, which is a lot sleeker I must say .. but I had to prove to Prateek that it could be done this way too! :D)

ReplyDeleteSo lets say E(n) is the expected value of winnings for the same game involving n cards

So E(1) = 10

E(2) = 15 [10 if its 2,A, 20 if its A,2] and so on..

One thing to note is that once the Highest card (10) appears there is no chance of winning any more money.

Now for E(10)

Probability that 10 appears in the first draw = 1/10

Money won = 10$

Probability that 10 appears in the second draw = 1/10

Money won = 10$ (for 2nd draw) + (Money won in first draw)

Probability that 10 appears in the third draw = 1/10

Money won = 10$ (for 3nd draw) + (Money won in first 2 draws)

Probability that 10 appears in the fourth draw = 1/10

Money won = 10$ (for 4th draw) + (Money won in first 3 draws)

Now we have to calculate the "Money won in the first i draws", This can be mapped back to the original game.

For example, lets look at the last case, That 10 appears in the 4th draw, so any 3 cards can appear in the first 3

draws, these 3 cards can be mapped to A,2,3 and Expected Value of winnings is just E(3) and similarly for all cases

so now

E(10) = 1/10*(10) + 1/10*(10 + E(1)) + 1/10*(10 + E(2)) + .... + 1/10*(10 + E(9))

For a general n

n*E(n) = 10 + (10 + E(1)) + ... + (10 + E(n-1))

n+1*E(n+1) = 10 + (10 + E(1)) + ... + (10 + E(n-1)) + (10 + E(n))

=> n+1(E(n) - E(n+1)) = 10

=> E(n+1) - E(n) = 10/(n+1)

=> E(10) - E(1) = 10/2 + 10/3 + 10/4 + .. + 10/10

=> E(10) = 10(1 + 1/2 + 1/3 + ... + 1/10)

@Goutham (Scrouge of God)..

ReplyDeleteYour solution is correct.

Just for clarity, the solution I gave to Prateek was:

Let the random variable Xi be the amount in dollars I get in the ith draw.

So, X1=10

X2, X3 .. etc are not independent

X= X1+X2+X3+.. X10

We need to find E[X]

Note that E[Xi]=10*P(last number is the largest if I draw i numbers from a set of n numbers) = 10*1/i

So, E[Xi]=10/i

E[X1]=10

E[X2]=10/2

E[X3]=10/3

and so on

By linearity of expectation,

E[X]=10(1+1/2+1/3+1/4..+1/10)

Hence proved.

I agree with Goutham that my solution is sleeker :P. Thanks.

106,286,400 / 10!, if you may!

ReplyDelete@Gangal. :P

ReplyDeleteOn doing more calculations, another sleeker representation is 29.2896825.

We could have guessed this using the following line of thought:

(We know that!) H(n)-ln(n) reduces monotonically to Euler Mascheroni constant (0.577)

H(10)-ln(10) < H(5)-ln(5)

So, H(10) < ln(2)+1+0.5+0.33+0.25+0.2

H(10) < 2.28+ln2 < 2.98

Also, H(10)-ln(10) > 0.577

H(10) > 2.879

So, we could have guessed that our answer 10*H(10) lies between 28.79 and 29.8

[Not a bad estimation!]

[Of course, you needed to know the values of ln(10) and ln(2) for this, which I happened to remember from JEE days]