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.
(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 |