Cómo podría ayudar Bob a Alice

Question

Supongamos que hay una secuencia $a$ 0 o 1, que es el tiempo suficiente , por ejemplo, la $length(a)=2^n$, $n$ suficientemente suficientemente grande entero. Ahora Alice es adivinar el contenido de $a$.

Si Alice no sabe nada acerca de $a$, en el peor de los casos sus suposiciones podían ser del todo mal, o le nota como $\inf P=0$ donde $P$ es la probabilidad de que Alice derecho de adivinar.

Ahora vamos a decir Bob sabe que el contenido de $a$ y puede ayudar a Alice con el pasar de ella una serie infinita $b$ 0 o 1, sin embargo, Alice podía ver sólo la primera $k$ bits en $b$.

Si $k=1$, Bob podría ayudar a Alice a empujar $\inf P=50\%$, si están de acuerdo de antemano que el primer bit $b$ $b_1$ que puede ser 0 o 1, indica $a$ tiene al menos la mitad 0s o 1s.

Q1. ¿Cómo podría ayudar a Bob a Alice si $k=2$?

Q2. ¿Cómo podría ayudar a Bob a Alice en general para un determinado $k$?

Q3. Hay una estrategia que como $k$ crece, Alicia conjeturas podría mejorar?

Por supuesto, hay un poco de la estrategia que establezca $b$$a$, entonces si Alice pudo ver el primer $k$ bits, ella siempre podría hacer $k$ derecho conjeturas sobre las $a$. Pero esta estrategia funciona bastante mal como pequeño $k$s, por ejemplo, si $k=1$, Alice podría única garantía de 1 bit para ser adivina correctamente , en lugar de $50\%$.

Existe una mejor estrategia ?

Answer 1

No es una solución completa, pero demasiado largo para un comentario.

Definir la distancia entre dos secuencias de $a$ e $b$ a ser el número de lugares en los que son diferentes, o $d(a,b)=\sum|a_i-b_i|$. Esta es una métrica en el espacio de $A$ de las secuencias binarias de longitud $N$. Para $a\in A$ e $r\geq 0$, definir el balón en $a$ y con un radio de $r$ por $B(a, r) = \{b\in A : d(b,a)\leq r\}$.

Si $k$ es conocido por Alice y Bob por adelantado, entonces no se $2^k$ diferentes señales que Bob puede enviar a Alice, y para cada uno de ellos Alice va a hacer un especial de adivinar $a^{(j)}$, $j=1,\dots,2^k$. La pregunta es, entonces, el lugar de la $a^{(j)}$ tal que $A$ es cubierto por $B(a^{(1)},r)\cup\dots\cup B(a^{(2^k)},r)$ con $r$ tan pequeño como sea posible.

Por ejemplo, si $k=2$ e $N=4$, entonces Alice y Bob está de acuerdo en que las cuatro palabras $00,01,10,11$ debería estar a favor de las conjeturas $0000, 1001, 1110$, e $0111$, respectivamente. Entonces Alice se garantiza una puntuación de al menos el 75 %, $A$ es cubierto por las bolas de radio 1 sobre las cuatro secuencias, así que vamos a hacer en más de un error.

Y si $k=1$ e $N$ es arbitrario, las dos palabras $0$ e $1$ podría representar a cualquier secuencia $a^{(1)}$ y su opuesto secuencia $a^{(2)}$.

Pero si $k$ no se conoce de antemano, el problema parece menos claro, como las diferentes estrategias que puede funcionar mejor para diferentes valores de $k$. Cualquier estrategia, a continuación, dar a Alice una secuencia no decreciente $p_1,p_2,\dots$, donde $p_k$ es la garantía de la puntuación que Alice puede estar seguro de cuándo $k$ es revelado, y allí seguramente no será cualquier estrategia que es mejor para todos los $k$.

Si las estrategias están ordenados lexicográficamente, mirando el primer $p_k$ donde se diferencian, entonces el problema se convierte en bien definido, pero parece difícil de encontrar estrategias óptimas, excepto por fuerza bruta. Es posible, sin embargo, para resolver el problema para cada una de las $k$ y para transmitir las palabras de código para cada una de las $k$ sucesivamente.