An original math problem

[bigpooch]

This is related to a recent post on SMP.

The "proposition"
----------------

You pay $7 for the privilege of playing this game with an
ordinary deck of cards: 26 red cards and 26 black. You
simply guess red or black through the entire deck one card
at a time and get paid $1 per correct guess, but pay out $1
for each wrong guess. The only information you have are
the cards that have gone by. Obviously, if your first pick
is correct, you'll get at least 27 right (or you shouldn't
lose more than $5 in this case). The deck is randomly
shuffled for each game.

1) What is the optimal strategy? (not hard)

2) What are the chances you'll only guess 26 right, i.e.,
lose $7 (playing optimally)?

3) What is the EV/value of this game?

4) Let n be the number of cards for each color (n=26 in the
original game). What is a good approximation for the
number of correct guesses above n/2 for large n? For which
values of n is the $7 fee too high for the game to be +EV?

For the sake of those trying to solve this, please post
solutions in white.

[thylacine]

<font color="white"> O(\sqrt(n)) I guess. Not my area. Strategy, choose more common remaining color. </font>

[pzhon]

[ QUOTE ]

1) What is the optimal strategy? (not hard)


[/ QUOTE ]
<font color="white">Bet on whatever is favored to show up. When the deck is even, what you bet on doesn't matter.</font>

[ QUOTE ]
3) What is the EV/value of this game?

[/ QUOTE ]
<font color="white">The amount you win (ignoring the $7 fee) is $k if you guess correctly k times while the deck is even. When the deck is unbalanced by n cards, you will win precisely $n by the time the deck becomes even again.

So, the expected win is $0.50 times the expected number of times the deck is even, or $0.50 times the sum of the probabilities that the deck is even after 0,2,4,...,50 cards. The probability the deck is even after 2i cards is (2iCi)((52-2i)C(26-i))/(52C26). The sum is not a smooth number, so I don't think this sum simplifies. The sum of the probabilities is about 8.08, so the expected gain within the game is $4.04. You lose $2.96 by paying $7 to play.</font>

[ QUOTE ]
2) What are the chances you'll only guess 26 right, i.e.,
lose $7 (playing optimally)?


[/ QUOTE ]
<font color="white">I've seen this part before. Without loss of generality, guess one color whenever the deck is even. Then you break even after the fee only if the cards seen so far is never in favor of the color you are guessing. That's a Catalan-type problem, and the number of such shuffles is the 26th Catalan number, (52C26)/27, so the probability is 1/27.</font>

[ QUOTE ]
4) Let n be the number of cards for each color (n=26 in the
original game). What is a good approximation for the
number of correct guesses above n/2 for large n? For which
values of n is the $7 fee too high for the game to be +EV?


[/ QUOTE ]
<font color="white">Asymptotically, (2kCk) ~ 4^k/sqrt(pi k). So, we can approximate (2iCi)(2n-2iCn-i)/(2nCn) by sqrt(pi n)/(sqrt(pi i)sqrt(pi n-i)) ~ 1/sqrt(pi n) 1/sqrt((i/n)(1-i/n)). The point of that last manipulation is that the sum of f(i/n)/n as i ranges from 0 to n-1 is about the integral from 0 to 1 of f(x) dx, so this sum is about sqrt(n)/sqrt(pi) times the integral from x=0 to x=1 of 1/sqrt(x(1-x)) dx, or sqrt(n)/sqrt(pi) * pi ~ sqrt(n pi). The expected value of this game is $0.50 times that, or about sqrt(n pi)/2 dollars, which is high by about 48 cents for n=26. It's high by 47 cents for n=1000.

The value with 71 cards of each color is $6.98. With 71 or fewer, it is not worth paying $7. The value with 72 cards of each color is $7.03. With any more, the game is worth playing.
</font>

[bigpooch]

It was your post on SMP that inspired me to post this
problem; it's helpful for part 3).

[bigpooch]

<font color="white">
A simple arithmetic error in 3): if you get 30 right
(approximately what you'd expect when the deck evens out 8
times), excluding the fee, the gain is $30-$22 = $8.

The expression you mentioned in 3) does simplify (refer to
an earlier post by thylacine in SMP).

Similarly, for 4)

</font>

[pzhon]

Oops, good catch. So a few of my answers were off by a factor of 2.

<font color="white">So if you include the end, the expected number of times the deck is even is 4^n/(2nCn). Your expected value is 4^n/(2nCn) - 1.
</font>
It was a good observation that this was connected to the previous problem.

The value is also very similar to the value of the multiplicative version.

[thylacine]

[ QUOTE ]
It was your post on SMP that inspired me to post this
problem; it's helpful for part 3).

[/ QUOTE ]

I see. Nice.

[bigpooch]

Basically, pzhon answered it all but he wasn't explicit
about 4):

<font color="white">
A very rough approximation for the EV of the game for
general n is sqrt(pi*n) - 8 (including the $7 fee for the
privilege of playing) and the expected number of correct
guesses above n/2 is very roughly 1/2[sqrt(pi*n)-1].

It is a mere check to see that the game is +EV for n&gt;=21
and -EV for n&lt;=20.
</font>