Game: Asking yes-no questions wisely
Asking yes-no questions when probability values are known
Before reading the following, the reader should read the introduction to ''games as trees'' here. The game introduced in this webpage is an example of ''games as trees''.
In the well-known game Twenty questions, one person thinks of an object, such as Cornell University in NY or LA Lakers, the 2009 NBA Champion. Another person tries to guess the object by asking no more than twenty questions, each answerable by either yes or no only. The best questions are usually those that divide the set of possible objects into two subsets as nearly equal in number as possible. The following example will illustrate this fact.
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Example:
If a person has chosen as his ''object'' a number from 1 through 9, it can be guessed by this procedure in no more than four questions (possibly less). We can use the following two strategies:
Strategy 1:
The first question is: Is the number larger than 4? If the answer is yes, then you can ask: Is the number larger than 6? If yes, then ask: Is the number larger than 8? If yes, then the number is 9. If no, then the number is either 7 or 8 so one more question is needed. If the answer to the first question is no, then you can ask: Is the number bigger than 2? If yes then the number is either 3 or 4 so one more question is required. If no then the number is either 1 or 2 so again one more question is required.
Under this strategy, notice that if the number is 1,2,3,4,5,6,9, then the number of questions needed is three. If the number is 7 or 8, then the number of questions needed is four. Hence, a total of 3x7+4x2=21+8=29 questions are needed. An average of 29/9 = 3.22 questions are needed.
Strategy 2:
For the same problem, we can use the following strategy:
The first question is: Is the number is greater than 8? If yes then the number is 9. If no, then ask: Is the number is greater than 4? If yes, then ask: If the number greater than 6? If yes, then the number is either 7 or 8 SO one more question is needed. If no, then the number is either 5 or 6 so again one more question is needed. If the answer to the second question '' Is the number greater than 4'' is no, then ask: Is the number greater than 2? Is yes then the number is either 3 or 4 so one more question is needed. If no then the number is either 1 or 2 so again one more question is needed.
Under this strategy 2, if the number chosen is 9, then only one question is needed. But if the number is not 9, then four questions are needed to get the right answer. Hence, a total of 1+8x4=33 questions are needed. An average of 33/9=3.66 questions are needed.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Therefore, the expected number of questions needed under strategy 2 is BIGGER than the expected number of questions needed under strategy 1. Notice that the first question in strategy 2 does not divide the set of objects into two subsets as nearly equal in number as possible. Hence, the best questions are usually those that divide the set of possible objects into two subsets as nearly equal in number as possible.
We are interested in the expected (average) number of questions needed because it shows the efficiency of our question-asking strategy: If the expected number of questions needed is lower, then the strategy is more efficient.
In fact, four questions are enough to determine a number chosen from 1 to 2^4 (=16). Mathematically, in twenty questions, one can guess any number from 1 to 2^20 (2 to the power 20, or numerically 1048576)
In the above example, the probability that each number can be chosen is the same. Now, suppose that each of the possible objects can be given a different value to represent the probability that it has been chosen. In reality, there are lots of such games that can be played by anybody without knowing any mathematics. The following is one of the examples:
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Problem :
For example, assume that a deck of cards consists of one ace of spades, two deuces of spades, three threes and on up to nine nines, making 45 spade cards in all. The deck is shuffled; someone draws a card. You are to guess it by asking yes-no questions.
The problem now is:
How can you minimize the number of questions that you will probably have to ask? (That is, to find a strategy of asking yes-no questions such that the expected number of questions needed is as low as possible.)
Think about it before looking at the answer below.
Answer:
The first step is to list in order the probability values for the nine cards: 1/45, 2/45, 3/45,... The two lowest values are combined to form a new element: 1/45 + 2/45 = 3/45. In other words, the probability that the chosen card is either an ace or deuce is 3/45.
There are now eight elements: the ace-deuce set, the three, the four and so on, up to nine. Again, the two lowest probabilities are combined: the ace-deuce value of 3/45 and the 3/45 probability that the card is a three. This new element, consisting of aces, deuces and threes, has a probability value of 6/45. This is greater than the values for either the fours or fives, so when the two lowest values are combined again, we must pair the fours and fives to obtain an element with the value of 9/45.
This procedure of pairing the lowest elements is continued until only one element remains. This only element will have the probability value of 45/45 or 1, of course.
The following chart shows how the elements are combined. The strategy for minimizing the number of questions is to take these pairings in reverse order.
Thus, the first question could be: Is the card in the set of fours, fives and nines?
If the answer is no, you know that it is in the other set so you ask next: Is it a seven or eight?
And so on until the card is guessed.
Note that if the card should be an ace or deuce then it will take five questions to pinpoint it. A binary strategy, of simply dividing the elements as nearly as possible into halves for each question, will ensure that no more than four questions need be asked, and you might even guess the card in three. Nevertheless, the previously described procedure will give a slightly lower expected minimum number of questions in the long run. In fact, the lowest possible. In this case, the minimum number is three.
The minimum is computed as follows: Five questions are needed if the card is an ace. Five are also needed if the card is deuce, but there are two deuces, making ten questions in all. Similarly, the three threes call for three times four, or 12 questions. The total number of questions for all forty five cards is 135, or an average of three questions per card.
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Exercise 1: Use some other strategies for the above card-choosing problem, then compute the expected number of questions needed. And see if it is lower or higher than three, the average number of questions needed for the above strategy in the answer.
Exercise 2: Find some other games like the above problem, that is, the probability that each object can be chosen is different. And play the game with your friends.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Remark:
We can make the game more tricky: If the person who answers is permitted one lie. A more challenging question can be asked:
What is the minimum number of questions required to determine a number between 1 and one million?
If there are no lies, the answer is of course 20. If just one lies, 25 questions suffice. This was proved, by Ivan Niven in ''Coding theory applied to a problem of Ulam'', Mathematics Magazine, Vol. 61, pages 275-281, December, 1988.
Furthermore, if two lies are allowed, then 29 questions suffice. It was proved by Jurek Czyzowicz, Andrzej Pelc and Daniel Mundici in the Journal of Combinatorial theory (Series A), Vol. 49, pages 384-388, November 1988.
However, the general case that multiple lies are allowed, is far from being solved.