Twenty questions with uncertain answers
Jul. 1st, 2011 02:31 pmIf you're playing twenty questions (say on something simple like "numbers from 1 to a 1000") the best strategy is to divide the output into two with each guess[1]. Eg. Higher than 500? Yes. Higher than 750? No. Higher than 625? Yes. Etc. Etc. This will take log(N) questions to find the exact answer. (Guessing randomly may produce the answer quicker, but on average will take mcuh longer.)
However, suppose when you ask a question, you're given the answer, but it's right only 90% of the time. (For simplicity, assume you can find out if you've got the right single answer at the end.) What's the right strategy? Is it to ask "Higher than 500" twice or more until you're sure? Or to follow the normal strategy until it gives a unique answer, and if that's wrong, start again?
The second game feels like what I often end up feeling like in real life... :)
[1] I remember reading a book that said learning to "gain information" from a guess rather than "make a right guess" was quite difficult for children to learn -- a teacher reported many children guess "higher than X" when they already knew it true, because they'd been so conditioned by class to expect a "yes, that's right" to be a good thing and "no, that's wrong" to be a bad thing.
However, suppose when you ask a question, you're given the answer, but it's right only 90% of the time. (For simplicity, assume you can find out if you've got the right single answer at the end.) What's the right strategy? Is it to ask "Higher than 500" twice or more until you're sure? Or to follow the normal strategy until it gives a unique answer, and if that's wrong, start again?
The second game feels like what I often end up feeling like in real life... :)
[1] I remember reading a book that said learning to "gain information" from a guess rather than "make a right guess" was quite difficult for children to learn -- a teacher reported many children guess "higher than X" when they already knew it true, because they'd been so conditioned by class to expect a "yes, that's right" to be a good thing and "no, that's wrong" to be a bad thing.