All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Best guess (Posted on 2015-07-30) Difficulty: 3 of 5
A player draws from a bag containing 10 black and 10 white marbles one by one, without putting them back in.
Every time before drawing a marble he guesses the color of the marble he will draw.
He decides to always guess the color that occurs most frequently remaining in the bag (if there is a tie, he chooses either color).

Find the expected number of correct guesses.

Find a formula for the number of correct guesses for starting with X black and Y white marbles.

This problem is a modified version of Guessing suit and addresses an interesting question that came up in the comments.

No Solution Yet Submitted by Jer    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
re(2): computer solution -- a mathematical-type formula Comment 3 of 3 |
(In reply to re: computer solution by Jer)

If E(W,B) is the expected number of correct guesses when starting from a state of W white marbles and B black marbles:

If either B or W is zero, E(B,W) = the non-zero argument.
Otherwise:
If B>W then E(W,B) = (W/(W+B)) * E(W-1,B) + (B/W+B) * (E(W,B-1) + 1)
Otherwise:
      E(W,B) = (W/(W+B)) * (E(W-1,B) + 1) + (B/W+B) * E(W,B-1)
      
It looks like I could have avoided the more complex logic of checking for zeros each time by simply, in line 70, had Black > 0 rather than Black >= 0 in that IF statement, to avoid the bad subscript error, as I had already populated the (w,0) and (0,b) entries in lines 20 and 30, as represented in line 1 of the formula above.

BTW, in my recent foray into Project Euler (thanks to the mention on this site), one thing I picked up was the concept of "dynamic programming". Note that while the function is defined recursively, it was calculated from the small numbers first, and then the larger numbers, with the smaller results stored for future use. If starting with, say E(10,10), we'd need to calculate E(9,10) and E(10,9), but both of those use E(9,9), so those would be calculated twice when programmed strictly recursively from large to small values, rather than iteratively from small to large. (I hesitate to say top-down vs bottom-up, as the concepts are the reverse of how they are displayed on a table.)  Then as you get to smaller and smaller values, the number of times each would calculated would expand exponentially (powers of 2 in this case), though at some point the number of points needed would go down.

  Posted by Charlie on 2015-08-01 08:24:47
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information