We decide to play the following game: An integer N will be randomly selected from the interval 0 - 100, inclusive. You try to guess N. After each guess, I tell you whether N is higher or lower than your guess.
If you successfully guess the integer, you win N dollars. Each guess costs you K dollars.
For each of the variants (a) and (b) below, what is the maximum value of K for which you'd be willing to play this game? Which strategy would you use to try to maximize your winnings in the long run?
(a) Once you start a round, you must continue until you guess N exactly.
(b) You may stop playing a round if you determine that N is too small to keep paying more money to guess N exactly. The money you've already spent on guesses is lost, but you may then start a new round with a new N.
Having looked at this a little, I suspect that the strategy is to pick a number X, and make your go/no-go decision before the 2nd turn. If N is lower than your first guess, drop out of the game. If N is higher, commit and do a binary search until you find it. In my experimenting with ranges, this turned out to be the case. And I think I can make an effective argument that this is the right strategy for large ranges also.
Which just leaves the question of what the initial guess should be. Well, it is the X which yields the highest break-even.
Let's say that we are considering the 0 to 100 range.
For a given X, the expected payout is 0 with probability X/101, and (X+100)/2 the rest of the time. In other words, the expected payout P(X) of this strategy is (X+100)*(101 - X)/202.
And what is the expected number of guesses? Well, it is the initial 1 guess plus 0 more guesses with probability (X+1)/101 and the rest of the time it is E(100-X) more guesses where E(y) = expected number of guesses when the remaining range is y. In other words, it is 1+E(100-X)*(100-X)/101. Let's call that G(X).
B(X) = Breakeven (as a function of X) is P(X)/G(X)
= (X+100)(101-X)/(202 + 2(100-X)*E(100-X))
Let's try some numbers.
Extending my table from a previous post,
E(2) = 3/2
E(3) = 5/3
E(4) = 8/4
E(5) = 11/5
E(6) = 14/6
E(7) = 17/7
E(11) = 33/11
E(12) = 37/12
E(13) = 41/13
E(14) = 45/14
E(15) = 49/15
E(23) = 89/23
E(24) = 94/24
E(25) = 99/25
E(31) = 129/31
E(48) = 231/48
E(49) = 237/49
E(50) = 243/50
E(63) = 321/63
E(101) = 587/101
Let's calculate B(50). It is 150*51/(202 + 2*50*E(50)) = 7650/(202+2*243) = 7650/688 = $11.12
Let's calculate B(51). It is 151*50/(202 + 2*49*E(49)) = 7550/676 = $11.17.
This Breakeven is higher than B(50), so we are going in the right direction. X should be greater than 50.
Let's calculate B(52). It is 152*49/(202 + 2*48*E(48)) = 7448/664 = $11.22.
Skipping around, Let's try B(69). It is 169*32/(202+2*31*E(31)) = 5408/460 = $11.76. Only 54 cents higher. Our rate of increase is slowing. I think we are still approaching the maximum.
Let's try B(85). It is 185*16/(202+2*15*E(15)) = 2960/300 = $9.87. I expect that our best X is somewhere between 69 and 85, closer to 69.
But I am probably boring you with the pencil and paper arithmetic. I will switch to Excel. Stay tuned for results.
Part b strategy and methodology (a start)
