# Expected number of times of choosing a word out of a given vocabulary when words are grouped

Two players (player C and player G) are playing a (modified) word guessing game. Both players share the same vocabulary $$V$$ and words in $$V$$ are grouped into $$K$$ bins, denoted as $$b_1$$, $$b_2$$, ..., $$b_{K}$$. Furthermore, we know that $$b_{i} \subset V$$ and $$\cup_{i=1}^{K} b_i = V$$. Note here we do not have $$b_i \cap b_j = \emptyset$$ for $$i \neq j$$.

The game protocol is described as follows:

1. Player C uniformly chooses a word $$w$$ from the vocabulary $$V$$. Player G does not know which word $$w$$ is.

2. Player G chooses one bin and asks Player C whether his/her chosen word $$w$$ is in the bin. If it is, the game ends. Otherwise, Player G will choose another bin.

Questions: What is the best bin choosing order and what is the expected number of times of choosing the bin, according to the best possible order?

Example:

Suppose we have a vocabulary consisting of ten words $$V = \{w_1, w_2, ..., w_{10} \}$$ and three bins $$b_1 = \{w_1, w_2, ..., w_5\}$$, $$b_2 = \{w_6, w_7 \}$$, and $$b_3 = \{w_8, w_9, w_{10} \}$$.

One possible bin choosing order is $$b_1 \rightarrow b_3 \rightarrow b_2$$ and the expected number of times of choosing the bin is $$\frac{1}{2}*1 + \frac{1}{2}*\frac{3}{5}*2 + \frac{1}{2}*\frac{2}{5}*\frac{2}{2}*3 = 1.7$$. I suspect this is the best bin choosing order but how can we prove this result?

Thanks.

Note

A related question (which has additional non-overlapping constraints on the bins) is asked in MO and in its comment, the user @DavidG.Stork gives a good answer (an intuitive proof of best ordering) for the case when those bins have no overlap.

• No problem. Your use of the term "game" just had me thinking about strategies for each player, when in fact only one "player" can be said to have a strategy here. And the best strategy is not actually obvious. If the bins were $b_1 = \{1,2,3,4,5,6 \}$, $b_2 = \{1,2,3,7,8 \}$ and $b_3 = \{4,5,6,9,10 \}$, the "obvious" choice of selecting bin $b_1$ first would not be correct. – Jens Mar 25 '19 at 1:09
• Simulposted to MO, mathoverflow.net/questions/326236/… with no notice to either site. – Gerry Myerson Mar 25 '19 at 3:49
• @Jens, when you're hungry, do you order pizza from several different pizzerias at a time, or just from one? – Gerry Myerson Mar 25 '19 at 4:15
• @Gerry Myerson: I ask everyone I know or can think of if they can satisfy my hunger. I could now say "you didn't answer my question", but it would distract from the question at hand. Do you have a relevant input to it? – Jens Mar 25 '19 at 4:19
• @Jens, what do you do when three delivery boys show up at your door with pizzas for you? Do you tell two of them, sorry that I've wasted your time, but I already got the pizza from the first guy? – Gerry Myerson Mar 25 '19 at 4:23

## 1 Answer

Not an answer but too long for a comment.

For a given ordering of bins, lets say $$a_{1}, a_{2}, ..., a_{K}$$ (which is a permutation of the $$b_i$$'s), let $$f(w)$$ be the discovery time for word $$w$$. Then $$f(w) = j$$, i.e. it will be discovered during the $$j$$th bin, iff $$w \in c_j$$ where $$c_j = a_{j} - \bigcup^{j-1}_{i=1} a_i$$. I.e. $$c_j$$ are the new words introduced by bin $$a_j$$.

To calculate the expected number of turns, sum up all the discovery times $$f(w)$$ and then divide by the number of words. So the expected number is minimized when $$\sum_{w \in V} f(w)$$ is minimized.

In the OP's original example all $$b_i$$'s are disjoint, so it's pretty clear that $$\sum_{w \in V} f(w)$$ is minimized when you assign the most number of them as $$1$$s, then the next-most number of them as $$2$$s, etc. In this example the expected number of turns $$= {5\times 1 + 3 \times 2 + 2 \times 3 \over 10} = 1.7$$.

When the $$b_i$$'s are not disjoint, then as shown by the excellent example of @Jens in the comments, the greedy strategy can be suboptimal - it assigns the numbers $$1,1,1,1,1,1,2,2,3,3$$ for a total of $$16$$ when the optimal strategy assigns the numbers $$1,1,1,1,1,2,2,2,2,2$$ for a total of $$15$$.

• Thanks for the complement! One might think the way forward was to find the smallest subset of bins which together contain all the words, but consider the following example: $b_1 = \{1,2,3,4,5,6,7 \}$, $b_2 = \{1,2,3, 8\}$, $b_3 = \{4,5,9 \}$, $b_4 = \{6,7,10 \}$. In this case, selecting $b_1$ first is actually the right strategy. – Jens Mar 25 '19 at 3:46
• @Jens I had the exact same conjecture as yours and then also came up with a counterexample: $\{1,2,3,4,5\}, \{6,7,8,9,10\},\{1,2,3,4,6,7,8,9\}$ where $8 \times 1 + 2 + 3 = 13 < 15$. I'm quite curious what the answer is. Now that the first two obvious strategies don't work, I wonder if it might actually be NP complete. – antkam Mar 25 '19 at 3:51