Poll

1 vote (25%)
No votes (0%)
1 vote (25%)
1 vote (25%)
2 votes (50%)
1 vote (25%)
2 votes (50%)
1 vote (25%)
1 vote (25%)
2 votes (50%)

4 members have voted

Wizard
Administrator
Wizard
  • Threads: 1520
  • Posts: 27103
Joined: Oct 14, 2009
Thanked by
RS
January 4th, 2020 at 2:14:36 AM permalink
I think I'm going to call 2020 the year of math appreciation.

In celebration, here is your next math puzzle.

  1. A deck begins with one white and one black card
  2. You draw a card at random
  3. If you draw a black card, the game ends and you're paid $1 for each black card in the deck, including the one you drew.
  4. If you drew a white card, it is added back to the deck along with another black card. Then go back to rule 2.


What is the expected value of this game?

As usual, a beer to the first correct answer and solution. Previous winners of a beer are asked to not post their own answers for 24 hours from this posting. To get the beer, an expression of the answer is need, not an estimate or result of a simulation.

Please use spoiler tags for answers and solutions.
Last edited by: Wizard on Jan 4, 2020
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
charliepatrick
charliepatrick
  • Threads: 39
  • Posts: 3016
Joined: Jun 17, 2011
January 4th, 2020 at 3:05:43 AM permalink
Did you mean the number of black cards drawn, the number of white cards drawn, or the number of black cards that landed up in the deck?

If it's the number of black cards drawn then "3) if you draw a black card, the game ends." so you can only ever draw one black card.

If it's how long you keep going then the problem is essentially that you win N-1 units if you can keep going until the Nth round. The chances of getting through each round get lower and lower, so does the sum of (N-1) / p (picking N-1 white cards, then a black card) converge.
unJon
unJon 
  • Threads: 16
  • Posts: 4779
Joined: Jul 1, 2018
January 4th, 2020 at 4:27:28 AM permalink
Quote: Wizard

I think I'm going to call 2020 the year of math appreciation.

In celebration, here is your next math puzzle.

  1. A deck begins with one white and one black card
  2. You draw a card at random
  3. If you draw a black card, the game ends and you're paid $1 for each black card you drew
  4. If you drew a white card, a black card is added to the deck. Then go back to rule 2.


What is the expected value of this game?

As usual, a beer to the first correct answer and solution. Previous winners of a beer are asked to not post their own answers for 24 hours from this posting. To get the beer, an expression of the answer is need, not an estimate or result of a simulation.

Please use spoiler tags for answers and solutions.



I think you misdescribed the game somewhere. You can only ever draw one black card, so triggering the payment of $1 per black card drawn just means that each game is worth exactly $1.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
charliepatrick
charliepatrick
  • Threads: 39
  • Posts: 3016
Joined: Jun 17, 2011
January 4th, 2020 at 5:42:45 AM permalink
Quote: unJon

I think you misdescribed the game...

I think it's easier to assume the payout depends on something like how many cards you manage to draw or rounds you keep going. Depending on your assumptions for starting conditions (e.g. do you get paid $0 if your first card is black, and $1 if your first two cards are white then black, etc. ) the answer will be something like x or x-1.

I had already sent a PM to Mike but it's now overnight in the US
Wizard
Administrator
Wizard
  • Threads: 1520
  • Posts: 27103
Joined: Oct 14, 2009
January 4th, 2020 at 7:22:02 AM permalink
I did explain the problem incorrectly. Step 3 should say you're paid $1 for each black card in the deck, including the one you drew.

For example, there is a 50% chance you pick the black card immediately and win $1.
There is a (1/2)*(2/3) chance you pick a white card first and then a black one, winning $2.
There is a (1/2)*(1/3)*(3/4) chance you pick a white card first, then another white card, and then a black one, winning $3.

I apologize for the typo.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 122
  • Posts: 6718
Joined: Jun 22, 2011
January 4th, 2020 at 8:52:56 AM permalink
I assume that if you draw the white card, it is put back into the deck along with an additional black card - otherwise, the most you can win is $2, since the second draw will be from a deck with 2 black and no white cards
Ace2
Ace2
  • Threads: 32
  • Posts: 2706
Joined: Oct 2, 2017
January 4th, 2020 at 11:12:24 AM permalink
Assume the game costs $1 to play. The return on a “for-1” basis will be:

1st draw: 1/2 * $2 = 1 / 1!
2nd draw: 1/2 * 2/3 * $3 = 2 / 2!
3rd draw: 1/2 * 1/3 * 3/4 * $4 = 3 / 3!

This is clearly the series 1/1! + 2/2! + 3/3! .... which equals e for a return of 2.72 for 1 or 1.72 to 1.

So the value of the game is e - 1 = $1.72
It’s all about making that GTA
Wizard
Administrator
Wizard
  • Threads: 1520
  • Posts: 27103
Joined: Oct 14, 2009
January 4th, 2020 at 12:02:20 PM permalink
Quote: ThatDonGuy

I assume that if you draw the white card, it is put back into the deck along with an additional black card - otherwise, the most you can win is $2, since the second draw will be from a deck with 2 black and no white cards



Yes, I just reworded again to make that clear.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1520
  • Posts: 27103
Joined: Oct 14, 2009
January 4th, 2020 at 12:03:12 PM permalink
Quote: Ace2

Assume the game costs $1 to play. The return on a “for-1” basis will be:

1st draw: 1/2 * $2 = 1 / 1!
2nd draw: 1/2 * 2/3 * $3 = 2 / 2!
3rd draw: 1/2 * 1/3 * 3/4 * $4 = 3 / 3!

This is clearly the series 1/1! + 2/2! + 3/3! .... which equals e for a return of 2.72 for 1 or 1.72 to 1.

So the value of the game is e - 1 = $1.72



I agree! I owe you a beer.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 122
  • Posts: 6718
Joined: Jun 22, 2011
January 4th, 2020 at 12:49:54 PM permalink
Quote: Wizard

Quote: Ace2

Assume the game costs $1 to play. The return on a “for-1” basis will be:

1st draw: 1/2 * $2 = 1 / 1!
2nd draw: 1/2 * 2/3 * $3 = 2 / 2!
3rd draw: 1/2 * 1/3 * 3/4 * $4 = 3 / 3!

This is clearly the series 1/1! + 2/2! + 3/3! .... which equals e for a return of 2.72 for 1 or 1.72 to 1.

So the value of the game is e - 1 = $1.72



I agree! I owe you a beer.


Since somebody solved this, here's a more rigorous proof:


The probability of stopping after N black cards are in the deck is 1/2 x 1/3 x ... x 1/N x N/(N + 1) = N / (N + 1)!, so the EV for N black cards is N x N / (N + 1)! = N{sup]2 / (N + 1)!
The total EV = 12 / 2! + 22 / 3! + 32 / 4! + ...

Start with 1 / 0! + (1 / 1! - 1 / 1!) + (1 / 2! - 1 / 2!) + (1 / 3! - 1 / 3!) + ... = 1 / 0! = 1
(1 / 0! + 1 / 1! + 1 / 2! + 1 / 3! + ...) - (1 / 1! + 1 / 2! + 1 / 3! + ...) = 1
(1 x 1) / (0! x 1) + (1 x 2) / (1! x 2) + (1 x 3) / (2! x 3) + (1 x 4) / (3! x 4) + ...) - (1 / 1! + 1 / 2! + 1 / 3! + ...) = 1
(1 / 1! + 2 / 2! + 3 / 3! + 4 / 4! + ...) - (1 / 1! + 1 / 2! + 1 / 3! + ...) = 1
(1 - 1) / 1! + (2 - 1) / 2! + (3 - 1) / 3! + (4 - 1) / 4! + ... = 1
1 / 2! + 2 / 3! + 3 / 4! + 4 / 5! + ... = 1
(1 x 3) / (2! x 3) + (2 x 4) / (3! x 4) + (3 x 5) / (4! x 5) + (4 x 6) / (5! x 6) + ... = 1
(1 x 3) / 3! + (2 x 4) / 4! + (3 x 5) / 5! + (4 x 6) / 6! + ... = 1
((1 x 3) / 3! + (2 x 4) / 4! + (3 x 5) / 5! + (4 x 6) / 6! + ...) + (1 / 3! + 1 / 4! + 1 / 5! + 1 / 6! + ...) = 1 + (1 / 3! + 1 / 4! + 1 / 5! + 1 / 6! + ...)
(1 x 3 + 1) / 3! + (2 x 4 + 1) / 4! + (3 x 5 + 1) / 5! + (4 x 6 + 1) / 6! + ... = 1 + (1 / 3! + 1 / 4! + 1 / 5! + 1 / 6! + ...)
Substitute n2 for (n - 1)(n + 1) + 1:
22 / 3! + 32 / 4! + 42 / 5! + ... = 1 + 1 / 3! + 1 / 4! + 1 / 5! + 1 / 6! + ...
Add 1/2 (= 12 / 2! = 1 / 2!) to both sides:
12 / 2 + 22 / 3! + 32 / 4! + 42 / 5! +... = 1 + 1 / 2! + 1 / 3! + 1 / 4! + 1 / 5! + 1 / 6! + ...
The left side of the equation is the EV; the right side is (1 / 0! + 1 / 1! + 1 / 2! + 1 / 3! + 1 / 4! + 1 / 5! + 1 / 6! + ...) - 1
1 / 0! + 1 / 1! + 1 / 2! + 1 / 3! + 1 / 4! + 1 / 5! + 1 / 6! + ... = e by Taylor's theorem, so the EV = e - 1

Wizard
Administrator
Wizard
  • Threads: 1520
  • Posts: 27103
Joined: Oct 14, 2009
January 4th, 2020 at 2:52:15 PM permalink
Wizard solution (PDF) .

Note the humdinger. Without that I think I would have got stuck.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Ace2
Ace2
  • Threads: 32
  • Posts: 2706
Joined: Oct 2, 2017
January 4th, 2020 at 6:42:20 PM permalink
In my opinion, the efficiency of the solution is almost as important as the solution itself.
It’s all about making that GTA
charliepatrick
charliepatrick
  • Threads: 39
  • Posts: 3016
Joined: Jun 17, 2011
January 5th, 2020 at 3:18:21 AM permalink
Quote: Ace2

...the efficiency of the solution is almost as important as the solution itself.

When I posted my hint you may have noticed that I said the "answer was something like x or x-1". Here is a variant of the solution I sent the wizard (as I wasn't quite sure whether you got a $1 if you immediately lost.)
The puzzle boils down to if you pick a white card you win $1 and another black card is then added to the deck. You can continue to win $1s until you eventually pick a black card. The starting conditions are you also receive $1 either when you eventually choose a black card or, for mathematical purposes, in Round 0.

The answer seems to be e-1 as at each round your chances of winning $1s are 1/2 * 1/3 * ... (since there was initially 1/2 chance of getting through, in the second round it's 1/2 * 1/3, etc.)

Consider
Round 0) Chances of getting paid = 1/1 (this is mathematically equivalent to being paid the $1 when you eventually pick a black card).
Round 1) Chances of getting through = 1/2; so probability of getting this far (and winning another $1) = 1/2 = 1/2!
Round 2) Chances of getting through = 1/3; so probability of getting this far (and winning another $1) = 1/2 * 1/3 = 1/3!
Round N) 1/2 * 1/3 * ... * 1/N; etc.
So your expected winnings are 1/1! + 1/2! + 1/3! + ....
Since e = 1/0! + 1/1! + 1/2!... = 1 + (1/1!+1/2!+...), your expected winnings are e-1.
Wizard
Administrator
Wizard
  • Threads: 1520
  • Posts: 27103
Joined: Oct 14, 2009
Thanked by
charliepatrick
January 5th, 2020 at 5:37:35 AM permalink
Sorry I didn't look carefully at your solution before, Charlie. I agree it is much simpler than mine.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Ace2
Ace2
  • Threads: 32
  • Posts: 2706
Joined: Oct 2, 2017
January 24th, 2020 at 7:50:53 AM permalink
Quote: Wizard


  1. A deck begins with one white and one black card
  2. You draw a card at random
  3. If you draw a black card, the game ends and you're paid $1 for each black card in the deck, including the one you drew.
  4. If you drew a white card, it is added back to the deck along with another black card. Then go back to rule 2.

.

A variant of this game is:

3) If you drew a black card, the game ends and you get paid at the ratio of total cards to white cards. So, for instance, if the game ends on the first draw you get paid 2/1 = $2.00, if it ends on the fifth draw you get paid 6/5 = $1.20

4) If you drew a white card it gets added back to the deck along with another white card (instead of another black card). Then go back to rule 2.

What’s the value of this game?
Last edited by: Ace2 on Jan 24, 2020
It’s all about making that GTA
ThatDonGuy
ThatDonGuy
  • Threads: 122
  • Posts: 6718
Joined: Jun 22, 2011
January 24th, 2020 at 5:09:10 PM permalink
Quote: Ace2

Quote: Wizard


  1. A deck begins with one white and one black card
  2. You draw a card at random
  3. If you draw a black card, the game ends and you're paid $1 for each black card in the deck, including the one you drew.
  4. If you drew a white card, it is added back to the deck along with another black card. Then go back to rule 2.

.

A variant of this game is:

3) If you drew a black card, the game ends and you get paid at the ratio of total cards to white cards. So, for instance, if the game ends on the first draw you get paid 2/1 = $2.00, if it ends on the fifth draw you get paid 6/5 = $1.20

4) If you drew a white card it gets added back to the deck along with another white card (instead of another black card). Then go back to rule 2.

What’s the value of this game?



1/2 x 2/3 x ... x (n-1)/n x 1/(n+1) = 1/(n (n+1)) of the time, you draw the black card with n white cards in the deck; the EV of this is 1/(n (n+1)) x (n+1) / n = 1 / n2.

The sum of the squares of the reciprocals is PI2 / 6. Don't ask me for a proof of this; it's a little above my math pay grade.

Ace2
Ace2
  • Threads: 32
  • Posts: 2706
Joined: Oct 2, 2017
January 25th, 2020 at 12:28:45 AM permalink
Correct. So the value is PI^2 / 6 = $1.64, a bit less than the original game. “The Basel Problem” describes the history, solution and proof of the series.
It’s all about making that GTA
  • Jump to: