15
$\begingroup$

Alice chooses a binary vector $V$ of length $n$ which is unknown to Bob. In each round Bob can choose any number of indices $i$ and then Alice tells Bob how many of the $V_i$ are set to $1$. The game terminates when Bob can say with certainty exactly which binary vector Alice has. Alice would like the game to go on as long as possible and Bob would like to make it as short as possible.

What are Alice and Bob's best strategies and how long does the game take?

For $n=7$ the following strategy always works.

Bob chooses indices 35, 234, 24567, 12356,14567 . This takes $5$ rounds.

For $n=10$ the following strategy always works.

Bob chooses indices 1-3-4-5-6-7-8, 3-5-9, 1-2-3-8-10,1-2-4-5-9-10,1-2-5-7-8, 1-2-3-4-5-8-10, 2-4-7-8-10. This takes $7$ rounds.

$\endgroup$
  • 2
    $\begingroup$ Alice has only one move, which is to choose the binary vector. After that, she has to react deterministically to Bob. Alice's best strategy is to maximize the entropy of the vector, which she can do by randomly setting $n/2$ entries to 0 and $n/2$ entries to 1. $\endgroup$ – Carl Dec 9 '13 at 20:14
  • $\begingroup$ Is there any strategy for Bob that would terminate in less than $n$ steps? Or maybe Bob does not know $n$ either? $\endgroup$ – gt6989b Dec 9 '13 at 20:26
  • $\begingroup$ @gt6989b Bob knows $n$. Maybe he needs $n$ steps in the worst case, I don't know. $\endgroup$ – marshall Dec 9 '13 at 20:27
  • 2
    $\begingroup$ For $n=5$, it suffices to ask $4$ questions, and these can be independent of the answers: $12345$, $123$, $34$, $24$. $\endgroup$ – Carsten S Dec 9 '13 at 23:57
  • 1
    $\begingroup$ Note, the OP has asked an equivalent version of this at mathoverflow.net/questions/151390/… $\endgroup$ – Barry Cipra Dec 11 '13 at 23:39
3
+150
$\begingroup$

This problem was solved (up to a small multiplicative factor) by Erdos and Renyi.

$\endgroup$
4
$\begingroup$

Under the following two assumptions, this question comes down to experimental design (in the information theoretic sense).

  1. Bob is allowed to use the information after moves $1, 2, \ldots, k-1$ to determine move $k$.
  2. Alice either chooses and sticks to a binary vector, $V$, or is allowed to change bits before each of Bob's moves -- that is, before she knows which indices Bob will pick next -- as long as the changes are consistent with Bob's existing information. (Information theoretically, the case where Alice is not allowed to change bits and the case where Alice is allowed to change bits without knowing what Bob will do next are equivalent.)

There is a true state of $V$ that Bob is trying to discover through measurements. Each experiment entails Bob selecting a set of indices, based on the information that he has already, and then discovering at how many of those indices there are ones in $V$. Bob's experimental design question, at any step, is At which indices should I measure next so as to maximize the expected information gain from the measurement?

This is equivalent to the question, Which choice of indices maximizes the entropy of the probability distribution over possible outcomes at those indices? The base-2 entropy of a discrete random variable, $X$, with $m$ possible outcomes $\{x_1,x_2,\ldots,x_m\}$, that are distributed according to the probability mass function, $P(x_i)$, is defined as $$ H_2(X) = -\sum_{i=1}^m P(x_i)\log_2 P(x_i) $$ In this case, the possible outcomes are the different possible integer answers that Bob can get when asking Alice how many entries in $V$ are $1$ for a given set of indices and $P(x_i)$ gives the probability of getting each of the possible integer answers.

For example, let's say $n=4$ and Bob already knows that the total number of $1$ bits is $3$. We write this as $$A(1,2,3,4) = 3$$ meaning the answer that Alice gives when asked how many of bits $1$, $2$, $3$ and $4$ are set. What is the expected information gain if Bob next asks for $A(1)$ or $A(1,2)$ or $A(1,2,3)$ or $A(1,2,3,4)$? (These are the only questions Bob has to consider since all others follow from symmetry.) $$ \begin{array}{l|l|l} & P(x_i) & H_2(X) \\ \hline A(1) & \left\{0: \frac{1}{4},\ 1: \frac{3}{4}\right\} & 2 - \frac{3\log_2 3}{4} \approx 0.81 \\ A(1,2) & \left\{1: \frac{1}{2},\ 2: \frac{1}{2}\right\} & 1 \\ A(1,2,3) & \left\{2: \frac{3}{4},\ 3: \frac{1}{4}\right\} & 2 - \frac{3\log_2 3}{4} \approx 0.81 \\ A(1,2,3,4) & \left\{3: 1\right\} & 0 \end{array} $$ This means that Bob's best move is to ask for $A(1,2)$ -- or any other 2-index set, by symmetry -- since that is the move that maximizes the expected information gain. Note that the expected information gain from $A(1,2,3,4)$ is $0$ since we already have deterministic information about the value of that measurement. After learning the value of $A(1,2)$, Bob has a new constraint on the possible values of different measurements, can update the probability distributions associated with those measurements, recalculate their entropies and determine his next move.

$\endgroup$
  • 4
    $\begingroup$ How do we know this greedy approach for Bob is optimal? Maybe he should choose a suboptimal move now so that he can make a better one later on and learn more information overall? $\endgroup$ – marshall Dec 10 '13 at 20:20
  • $\begingroup$ @marshall This approach is provably optimal because it uses all the information that Bob has available at a given step, to make the decision that leads to the greatest expected information gain. This is optimal in the sense that, under the probability distribution over possible outcomes, it will lead to the smallest expected number of measurements. Note that these are all expected values and probability distributions, which means there is uncertainty, but that is the best we can do with limited information. I suggest you read more at the link in the first paragraph. $\endgroup$ – Carl Dec 10 '13 at 20:27
  • 1
    $\begingroup$ Can it be used to give bounds for how long the game lasts for? $\endgroup$ – marshall Dec 10 '13 at 20:37
  • 1
    $\begingroup$ Say we are playing a similar game, where we have a fixed set of vectors in $\mathbb N^3$, Alice chooses one and Bob is allowed to ask for any of the three components of the vector. Say the vectors are (in abbreviated notation) $111,121,132,142,211,226,233,242,314,325,333,343,414,425,434,445$. What would your theory suggest that the first question should be? $\endgroup$ – Carsten S Dec 10 '13 at 21:06
  • 1
    $\begingroup$ [continued] So if I understand it correctly, then your procedure will suggest to ask for the third entry. However, you will then (in case the vector is not $226$) still have to ask two more questions to know what the vector is. On the other hand it suffices to ask for the first two entries to know the vector. So in this example your procedure would indeed be too greedy, a possibility which @marshall mentioned. So it seems to me that you give a useful heuristic, but no proof of anything. $\endgroup$ – Carsten S Dec 11 '13 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.