La cantidad de información que se puede transferir por la elección de un número de dos?

Question

Alice y Bob están jugando un juego. Alice (A) y Bob (B) un acuerdo sobre un protocolo antes de que el juego comience.

Alice recibe dos enteros aleatorios uniformemente (sin duplicados) de 1 a $n$, elige uno de los dos números, y comunica a Bob. Bob no se llega a ver otra cosa que el número que Alice eligió (y él sabe que el máximo de $n$, que se fija para el juego).

Cuántos bits de información $b(n)$, posiblemente, puede ser transmitida por el número en promedio, si Alice y Bob jugar a este juego durante un tiempo suficientemente largo?

$b(2) = 1$ es bastante obvio, pero aun $b(3)$ es difícil razonar acerca de.

Un protocolo que se me ocurrió es que Una siempre de salida $3$ entradas $\{1, 3\}, \{2, 3\}$, y la salida de $1$ o $2$ a la transferencia de $1$ bits de información cuando la entrada es $\{1, 2\}$. Este recibe un promedio de la velocidad de transmisión de $\frac{1}{3}$ bits por número. Pero no tengo idea de cómo generalizar esto a mayor $n$ o si incluso es óptima.

Answer 1

Para un gran $n$ podemos acercarnos a una eficiencia de $0.188$ bits por símbolo, de la siguiente manera:

En el protocolo de Alice puede enviar un poco de Bob "confiable pero lento" o "rápido-pero-no es fiable".

En fiable, pero lenta modo, Bob ignora a todos los demás símbolos, excepto $0$ o $1$, y Alice simplemente espera hasta que ella se de un par que le permite enviar el símbolo que ella necesita. Esto se lleva a $n/2$ símbolos en promedio.

En rápida pero poco fiable modo, Alice envía cualquier número de $0$ y cualquier número impar de $1$. Una cuarta parte de los bits que se envía será mutilado porque ella no tiene un número de la derecha de la paridad para enviar.

Alice y Bob está de acuerdo en avanzar en un tamaño de bloque de $b$, y la comunicación comienza cuando Alice se ha acumulado $b$ bits a enviar. Ella les envía el uso de fast-pero-no es fiable modo. Alice sabe que los bits que salió mal, así que calcula una corrección de la secuencia que Bob debe XOR de lo que él tiene con el fin de obtener el mensaje real. Los bits en la corrección de la secuencia no están uniformemente distribuidas: $0$ es tres veces más común que la $1$. Por lo tanto, Alice puede comprimir utilizando la codificación aritmética a una longitud de alrededor de $0.811$ original de la $b$ (es decir,$-\frac34 \log_2(\frac34) - \frac14 \log_2(\frac14)$).

Alice utiliza confiable pero lento bits para decirle a Bob la longitud exacta de los comprimidos de corrección de la secuencia, y ahora envía usando el mismo procedimiento que el bloque original, es decir, con su propia corrección de la secuencia siguiente, etc.

Cuando el comprimido correcciones de la secuencia es más corto que algunas de antemano longitud, Alice interruptores de enviarlo reliabe-pero-de modo lento.

Análisis. Al $b$ es grande, el número esperado de rápido-pero-no es fiable símbolos enviado es $$ b + 0.811b + 0.811^2b + 0.811^3b + \cdots = \frac{1}{1-0.811} b $$ Habrá en el orden de $\log b$ anidada corrección de secuencias, cada una necesidad hasta el $\log b$ confiable pero lento bits para codificar sus longitudes. Así que todo en la confiable pero lento fases de uso acerca de la $\frac n2 (\log^2 b+C)$ símbolos, donde $C$ cuentas para el final confiable pero lento correcciones de la secuencia).

Para cada uno de los $n$, por la elección de $b$ lo suficientemente grande, Alice y Bob puede hacer la $\frac n2 (\log^2 b+C)$ tan pequeño en comparación con $\frac{1}{1-0.811} b$ como ellos quieren! Así, en el límite de un gran $b$ se deben lograr $1-0.811 = 0.189$ bits por símbolo.

---

Si $n\le 10$, la modalidad fiable es en realidad más rápido que el comportamiento asintótico de aquí, y debe ser utilizado en su lugar.

---

Sospecho que esto podría ser asintóticamente óptimo para un gran $n$. Traté de variantes, tales como disminuir el porcentaje de error de la "rápida" de modo a expensas de la velocidad mediante la asignación de una fracción de la $n$ símbolos como "ignorar este símbolo de" marcadores en lugar de dejar que todos ellos codifican los bits reales. Pero parece que siempre se traduce en peor rendimiento general.

Answer 2

Si Alice no eran capaces de ver los números antes de enviar el max o min, la mejor tasa de interés posible sería:

$$C=\fbox{$1-\frac{1}{n-2}\sum_{k=2}^{n-1}H\left(\frac{n-k}{n-1}\right)$}$$

Alicia en el OP del problema ha estrictamente más funciones de las que Alice ya he escrito de ella, por lo que la tasa "OP Alice" puede alcanzar es mayor que el de la fórmula de arriba.

Para un gran $n$ la suma se vuelve como una integral: $$1 - \frac{1}{n-2}\sum_{y=2}^{n-1} H\left(\frac{n-y}{n-1}\right) \aprox 1-\int_0^1 H(p) dp = 1-1/\log(4)\aprox 0.2787.$$

---

Su 'elegir dos números' especifica un canal del estado:

$$Z=(z_1,z_2)\sim \operatorname{Uniform}\{(a,b), 1\leq a< b\leq n\}$$

En cada turno, el remitente recibe a la entrada $z_1$ o $z_2.$ por Lo que el canal de entrada es de unos $X$ sobre un alfabeto $\{\phi_i:\phi_i(Z)=z_i\},$ y el canal de salida es $Y=X(Z).$ Ahora tiene un canal:

$$X\rightarrow \overset{\huge\overset{Z}{\downarrow}}{\fbox{$P_{Y|X,Z}$}}\rightarrow Y$$

y por el ruido de codificación de canal teorema es suficiente para calcular la capacidad del canal: \begin{align} C = \max_{p_X} I(X;Y) &=\max_{P_X} H(X)-H(X|Y) \\ &=\max_{p} H(p)-H(X|Y) \end{align} donde$p=\mathbb{P}(X=\phi_1),\ H(p)=-p\log_2(p)-(1-p)\log_2(1-p)$$H(X|Y)=\sum_y P_Y(y)H(P_{X|Y=y}(\phi_1))$.

Para ser capaz de ir más allá que debemos iniciar el cómputo de probabilidades, que es simple, si usted coloca. Ver su espacio de $Z$'s plantea como un triángulo: \begin{matrix} (1,2) \\ (1,3) & (2,3) \\ \vdots & & \ddots \\ (1,n) & \dots & & (n-1, n) \end{de la matriz} Ahora podemos ver: \begin{align} P_{Y|X=\phi_1}(y)&\textstyle =P(Z\text{ in }y^{th}\text{ column})=\mathbf{1}_{[1:n-1]}(y)\frac{n-y}{\frac{(n-1)\cdot (n-2)}{2}}=\mathbf{1}_{[1:n-1]}(y)\frac{2\cdot (n-y)}{(n-1)\cdot (n-2)},\\ P_{Y|X=\phi_2}(y)&\textstyle =P(Z\text{ in }(y-1)^{th}\text{ row})=\mathbf{1}_{[2:n]}(y)\frac{y-1}{\frac{(n-1)\cdot (n-2)}{2}}=\mathbf{1}_{[2:n]}(y)\frac{2\cdot (y-1)}{(n-1)\cdot (n-2)},\\ P_Y(y)&\textstyle = pP_{Y|X=\phi_1}(y)+(1-p)P_{Y|X=\phi_2}(y) = \left\lbrace \begin{matrix} \frac{2 p\cdot(n-y)}{(n-1)\cdot (n-2)} & y=1 \\ \frac{2 p\cdot(n-y)+2\cdot(1-p)\cdot(y-1)}{(n-1)\cdot (n-2)} & y\in [2:n-1] \\ \frac{2\cdot(1-p)\cdot(y-1)}{(n-1)\cdot (n-2)} & y=n \end{de la matriz}\right.\\ P_{X|Y=Y}(\phi_1)&\estilo de texto = \left\lbrace \begin{matrix} 1 & y=1 \\ \frac{p\cdot (n-y)}{p\cdot(n-y)+(1-p)\cdot(y-1)} & y\in [2:n-1] \\ 0 & y=n \end{de la matriz}\right. \end{align}

Así, en nuestra entropía de expansión tenemos: \begin{align} \max_{P_X}I(X;Y) &= \max_{p\in[0,1]} H(p) - \sum_{y=2}^{n-1}P(Y=y)H(X|Y=y) \\ &= \textstyle \max_{p\in[0,1]} H(p) - \sum_{y=2}^{n-1}\frac{2p\cdot(n-y)+2\cdot(1-p)\cdot(y-1)}{(n-1)\cdot (n-2)} H\left(\frac{p\cdot (n-y)}{p\cdot(n-y)+(1-p)\cdot(y-1)}\right). \end{align}

Los puntos críticos de esta función en $p$ son: \begin{align} \textstyle \left\lbrace p: - \log_2\left(\frac{p}{1-p}\right) + \sum_{y=2}^{n-1}\frac{2p\cdot(n-y)+2\cdot(1-p)\cdot(y-1)}{(n-1)\cdot (n-2)} \log_2\left(\frac{p\cdot (n-y)}{(1-p)\cdot(y-1)}\right)- \sum_{y=2}^{n-1}\left(\frac{2\cdot (n-2y+1)}{(n-1)\cdot (n-2)}\right)H\left(\frac{p\cdot (n-y)}{p\cdot(n-y)+(1-p)\cdot(y-1)}\right) = 0 \right\rbrace. \end{align}

Es fácil comprobar que $p^\ast=0.5$ es un punto crítico. (De hecho, en este caso el primer suma de los telescopios y se cancela la sesión por primera vez, y la segunda suma se vuelve simétrica y cancela a 0 desde que se $H(p)=H(1-p)$).

También es el único punto crítico: la segunda derivada puede ser delimitada por debajo de 0 (simple cálculo pero tedioso escribir, recordar $H''(p)=1/(p^2-p)$$1-1/x \leq \log(x)\leq x-1$), por lo tanto la función es cóncava, con su máximo en su punto crítico $p^\ast = 0.5.$

Así, la tasa máxima posible de la confiabilidad de la transmisión de la información se reduce a:

\begin{align} C&= 1 - \sum_{y=2}^{n-1}\frac{1}{n-2} H\left(\frac{n-y}{n-1}\right). \end{align}

Answer 3

Alice divide los números enteros de 1 a n en dos subgrupos distintos de T y F (por ejemplo, T = números <= n y F = números de > n, o T = número par y F = números impares). Si n es incluso entonces hay n/2 números en cada subconjunto, si n es impar entonces ella tiene dos conjuntos con n/2 números más un número adicional (que puede ser considerado como el único elemento de un tercer set O).

Para transmitir CIERTO que envía un número de T si es posible, de lo contrario a partir de S si es posible, de lo contrario a partir de F si ambos números son de ese conjunto. Para transmitir FALSAS ella hace todo lo contrario.

Bob asume cualquier T número es CIERTO, y el número F es falso, y cualquier número no lleva ninguna información.

Para n = 2, 3, 4, 5, 6, 7... el número de bits transmitidos es 1, 2/3, 2/3, 3/5, 3/5, 4/7, 4/7... . Yo pienso que el patrón es evidente. Por lo suficientemente grandes de n, el límite es de 1/2 bits por transmisión.

Answer 4

Esta es una solución parcial basa en los siguientes supuestos:

1. Alice quiere transmitir una secuencia $\{x_i\}_{i\in\mathbb{N}}$ de bits en $\{0,1\}$. La probabilidad de que la primera $k$ símbolos de esta secuencia será un determinado $w\in\{0,1\}^k$ es distribuido uniformemente.
2. "Transferencia de bits" se define como el inequívoco a la transferencia de un símbolo en la palabra $w\in\{0,1\}^*$ que Alice desea enviar.
3. Bob recibe los bits en orden. Por lo tanto, la única manera de bits de código es a través de códigos prefijo (es decir, - Alice y Bob están de acuerdo de antemano que cada elemento de un conjunto a $S$ de las palabras, ninguno de los cuales es un prefijo de otra, corresponde a una única palabra $w\in\{0,1\}^*$ y Alice envía su secuencia $\{x_i\}_{i\in\mathbb{N}}$ de bits mediante la elección de los números de $c_i\in[1,n]$, de modo que la correspondiente cadena es un código para un prefijo de su mensaje,$\{x_i\}_{i\in\mathbb{N}}$).
4. Para simplificar, vamos a suponer que el conjunto de $S$ de prefijo de códigos es finito.

Con los supuestos anteriores, podemos definir numéricamente para un conjunto dado $S\in\{1,...,n\}^*$ con el prefijo de la propiedad (que dice que ninguna cadena es un prefijo de otra) y la función $f:S\to\{0,1\}^*$ el promedio de poco tiempo de espera de $(S,f)$, que denotamos $\beta(S,f)$, para ser igual a:

$$\lim_{k\to\infty}\frac{1}{2^k}\sum_{w\in\{0,1\}^k}{E(w)}$$

donde $E(w)$ es el valor esperado del número de símbolos en $\{1,...,n\}$ que tendrá que ser enviado antes de que Bob puede estar seguro de que $w$ es un prefijo de $\{x_i\}_{i\in\mathbb{N}}$. Luego podemos ver que estamos buscando $(S,f)$ tal que $\beta(S,f)$ es mínimo. En otras palabras, queremos saber:

$$b(n)=\sup_{(S,f)}{\frac{1}{\beta(S,f)}}$$

Si usted está confundido acerca de la realidad que nos llevó a la inversa de $\beta$, cabe recordar que la $\beta$ se definió para darle el promedio de tiempo de espera un poco, que es la inversa de la real de transferencia de bits esperar. Obviamente, este es un problema no trivial. De hecho, puede incluso no ser una solución óptima, ya que hay una infinidad de posibles $S$, por no hablar de la aún mayor número posible de funciones $f$. Por lo tanto, podría ser posible que, dada una estrategia de $(S,f)$ siempre podemos encontrar uno mejor $(S',f')$.

Para remediar estos problemas, se puede poner una restricción en el tipo de $(S,f)$ cuales son permitidas. Podríamos dejar $l_i$ ser la máxima longitud de una palabra en $S$ $l_o$ la longitud máxima de una palabra en $f(S)$, y luego hacer la pregunta por las estrategias óptimas para cada una de las $l_i$$l_o$. Como he dicho esto es una respuesta parcial, voy a dar la solución para $l_i=1$.

En primer lugar, tenga en cuenta que esto implica que es óptima para nosotros para permitir a $S=\{1,...,n\}$. Ahora, dados dos distintos $u,v\in\{1,...,n\}$ tal que $f(u),f(v)≠\epsilon$, entonces como es posible obtener un $(u,v)$ como una pareja debe ser el caso de que no importa la palabra $\{x_i\}_{i\in\mathbb{N}}$ que Alicia quiere enviar una de las cadenas de $f(u)$ o $f(v)$ se debe asignar a un prefijo de Alicia palabra. Esto implica que debemos tener $\{f(u),f(v)\}=\{0,1\}$.

Como corolario, exactamente dos cartas en $[1,n]$ son "portadores de información" y que corresponden a un cero y un uno, y todos los otros que corresponden a la palabra vacía y por lo tanto no llevan ninguna información. Ya un poco teniendo en cuenta que hay un $\frac{3n-2}{n^2}$ de probabilidades de obtener el símbolo correspondiente a los bits que estamos buscando, $b(n)=\frac{3n-2}{n^2}$. En particular, puesto que hay un $1-\frac{\prod_{k=1}^{m}{n-k}}{n^k}$ oportunidad de anotar un símbolo correspondiente a un bit en particular si tenemos m símbolos diferentes para elegir, el valor de la generalizada $b$ función con la restricción $l_o=1$ es:

$$b(n,m)=1-\frac{\prod_{k=1}^{m}{n-k}}{n^k}$$

P. S. voy a tratar de generalizar el método que he utilizado para mostrar esto sin la $l_o=1$ restricción, ya que no es exactamente parece necesario para mí para esta prueba y así si tengo éxito, voy a añadir una edición a este post que muestra el verdadero valor de $b(n,m)$.