Can you beat the Casino?

Probability Level 5

You enter the casino with unlimited cash at your disposal. The casino offers you the following deal...

There is a stack of $100$ blank cards. The casino dealer then proceeds to secretly write any positive integer on each of the cards. Once he is done, the deck is handed over to you, numbers facing down. You may shuffle cards as you desire. You can then count and turn over as many cards as you wish.

If the last card that you choose to flip turns out to be the card with the highest number in the deck, you win. Otherwise you lose.

Each game costs $100$ bucks to play. If you win the game, you get $500$ bucks; otherwise you lose only the $100$ bucks you paid to play. The dealer writes down a new set of numbers every game.

Do you think you should play this game?

Using OPTIMAL strategy, what is the expected value of your profit (or loss designated by negative sign) after playing $400$ games ?

The answer is 34209.

1 solution

Satyen Nabar
May 13, 2015

The optimal strategy is to divide the deck in half and make two stacks of $50$ cards each. Now turn over all the cards of stack $1$ and set aside the highest number you find.Then turn over the cards, one by one, of stack $2$ till you get a number higher than the card you set aside. This is the last card you flip.

There is a $50$ % probability that the highest card is in stack $2$ (either it is or it isn't!) and a $50$ % chance that the second-highest card is in stack $1$ .

Combining the probabilities there is a $25$ % chance of getting the scenario mentioned above. So there is a $\dfrac{3}{4}$ chance of losing and $\dfrac{1}{4}$ chance of winning a game.

If you lose, you lose $100$ bucks, if you win you make profit of $400$ bucks

Expected value of winnings per game =

$\dfrac{3}{4}* (-100)\ + \dfrac{1}{4}*400\ = 25$

Expected value of winnings over $400$ games = $400*25= 10000$ bucks.

Can you prove your claim that this is indeed the optimal strategy?

I think this is basically a variant of the famous secretary problem . (I suggest reading that article before reading this. Believe me, it is worth the time.) In fact, I think your problem makes even more sense in real life as compared to the secretary problem, where you would have a lot of data beforehand, to judge candidates; unlike here, where you have no idea of how good a number is to bet on. The article also claims (without proof, I might add) that the optimal solution is to only analyse the first r-1 cards, and reject them altogether, no matter how good you think they are, and then flip the remaining cards until you get the first one higher that the best of those r-1 . Then, it goes further to find, with proof (the proof is short and elegant), an optimal value of r-1 . It turns out to be close to n/e for n cards, where n is significantly greater than 1 . For 100 cards, the approximation works quite well. 100/e ~ 36.8 and I verified that r-1=37 gives an optimal probability ~0.3710428 (the formula is derived in the article) which is greater than 25% also. In this case, the expected gain is 34209 bucks.

It's great how you could individually came up with the 'stopping' solution yourself. (I had read about the secretary problem earlier, so it was easier for me.) However, you have arbitrarily assumed that stopping at 50 is optimal (as it seems to be a good balance between both things). Further, there is one more small error in your answer, that being that you have missed the case where the first stack has the n th ( n>2 ) highest card and the second stack has the first n-1 highest cards, but the highest is picked up by you first. Thus, the probability that you win is greater than 25% even in the 50-50 case.

I apologise for the long comment, but I had to explain myself properly, given that this is a Level 5 problem. Kindly inform me if I have misunderstood something. If not, then I request you to change the answer to 34209 .

Aalap Shah - 6 years, 1 month ago

Dear Aalap, I think you are absolutely correct. I have changed the answer. Can you please post a separate solution so that i can delete my incorrect solution?

Satyen Nabar - 6 years, 1 month ago

Can you beat the Casino?

The answer is 34209.

1 solution

0 pending reports