Bajo los dos siguientes supuestos, esta cuestión se reduce a diseño experimental (en el sentido de la teoría de la información).
- Bob puede utilizar la información después de los movimientos $1, 2, \ldots, k-1$ para determinar el movimiento $k$ .
- Alice elige y se ciñe a un vector binario, $V$ o se le permite cambiar los bits antes de cada uno de los movimientos de Bob -es decir, antes de saber qué índices elegirá Bob a continuación- siempre que los cambios sean coherentes con la información existente de Bob. (Desde el punto de vista de la información, el caso en el que no se permite a Alice cambiar los bits y el caso en el que se permite a Alice cambiar los bits sin saber qué hará Bob a continuación son equivalentes).
Existe un verdadero estado de $V$ que Bob intenta descubrir a través de las mediciones. Cada experimento implica que Bob seleccione un conjunto de índices, basándose en la información que ya tiene, y luego descubra en cuántos de esos índices hay unos en $V$ . La pregunta de diseño experimental de Bob, en cualquier paso, es ¿En qué índices debo medir a continuación para maximizar la ganancia de información esperada de la medición?
Esto equivale a la pregunta, ¿Qué elección de índices maximiza la entropía de la distribución de probabilidad sobre los posibles resultados en esos índices? La entropía de base 2 de una variable aleatoria discreta, $X$ con $m$ posibles resultados $\{x_1,x_2,\ldots,x_m\}$ que se distribuyen según la función de masa de probabilidad, $P(x_i)$ se define como $$ H_2(X) = -\sum_{i=1}^m P(x_i)\log_2 P(x_i) $$ En este caso, los posibles resultados son las diferentes respuestas enteras que puede obtener Bob al preguntar a Alice cuántas entradas hay en $V$ son $1$ para un conjunto determinado de índices y $P(x_i)$ da la probabilidad de obtener cada una de las posibles respuestas enteras.
Por ejemplo, digamos que $n=4$ y Bob ya sabe que el número total de $1$ bits es $3$ . Lo escribimos como $$A(1,2,3,4) = 3$$ es decir, la respuesta que da Alicia cuando se le pregunta cuántos bits $1$ , $2$ , $3$ y $4$ están fijados. ¿Cuál es la ganancia de información esperada si Bob pide a continuación $A(1)$ o $A(1,2)$ o $A(1,2,3)$ o $A(1,2,3,4)$ ? (Estas son las únicas preguntas que Bob tiene que considerar, ya que todas las demás se derivan de la simetría). $$ \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} $$ Esto significa que la mejor jugada de Bob es pedir $A(1,2)$ --o cualquier otro conjunto de 2 índices, por simetría-- ya que es el movimiento que maximiza la ganancia de información esperada. Nótese que la ganancia de información esperada de $A(1,2,3,4)$ es $0$ puesto que ya tenemos información determinista sobre el valor de esa medida. Tras conocer el valor de $A(1,2)$ En este caso, Bob tiene una nueva restricción sobre los posibles valores de las diferentes mediciones, puede actualizar las distribuciones de probabilidad asociadas a esas mediciones, recalcular sus entropías y determinar su próximo movimiento.
