Many years ago, when I was teaching at Cornell, my then-colleague Nick Kiefer kept me endlessly amused with the creative assignments he dreamed up for the students in his Decision Theory class. I’m reporting this from memory, so I don’t guarantee that I have it exactly right, but I think this was one of those problems:
- On Day Zero (before classes start), Nick uses his pocket calculator to generate, at random, a secret number between 0 and 100. This number is drawn from a uniform distribution, which means (roughly) that the drawing is unbiased, so any number is as likely to come up as any other. The students’ job is to guess this number.
- On Day One — the first day of class — Nick uses his pocket calculator to generate a Number of the Day. He doesn’t tell the students what the Number of the Day is, but he does tell them whether it’s larger or smaller than the secret number.
- On Days Two, Three, and so forth, he does the same thing. He generates a Number of the Day and announces whether it’s bigger or smaller than the secret number.
- You, the student, can submit your guess on the day of your choice.
- You are then assessed two penalties. The first penalty is equal to the square of the error in your guess. So if the correct number is 3 and your guess is 5, your penalty is 22, or 4. The second penalty is equal to the natural logarithm of the day when you submit your guess. So if you submit your guess on Day 7, your penalty is the log of 7, which is 1.94591.
- These penalties are subtracted from some some fixed number of points that you’re given to start out with (say 1000). The result, after the subtraction, is your score for the assignment. This score counts for a significant fraction of your course grade.
Clearly, there’s some tension between the two penalties. To minimize the first penalty, you want to submit your guess as late as possible, when you’ve got the most information. To minimize the second penalty, you want to submit your guess as early as possible. To minimize the sum of the penalties — well, what should you do, exactly?
I remember loving the whole idea of this problem when Nick first described it to me, but, oddly, I don’t remember actually trying to solve it (in the sense of devising a strategy). I should probably be embarrassed by this failure of curiosity, but I made up for it a couple of days ago when I recalled the problem and worked on it for a while.
To avoid spoilers, I won’t say any more about my calculations. But: Suppose you’re in Nick’s class and your career depends on this assignment. What’s your strategy?
PS: When this first posted at 2:01AM Eastern Time, there was a final paragraph saying that I thought the problem would be more interesting with a different set of penalties. It is now 2:11AM Eastern time and I no longer believe that, so I’ve struck that final paragraph. (For the record, my mistake was caused by forgetting that the random number was between 0 and 100 and solving the problem as if it were between 0 and 1.)
Addendum: I believe the solution to the problem as stated involves waiting an unrealistic number of days (that is, many more days than are in the typical academic semester). This doesn’t particularly bother me, but if it bothers you, you might want to tackle a revised problem in which the first penalty is divided by 10.