Un problema de complejidad de comunicación para encontrar coincidencias cercanas

Question

Estoy atascado con este problema que parece que debería ser un argumento de conteo. Considere dos cadenas binarias $A$ y $B$ . Cuerda $A$ es de longitud $n$ y $B$ es de longitud $2n$ .

Alice tiene las dos cuerdas $A$ y $B$ y quiere enviar un solo mensaje a Bob (que no llega a ver las cuerdas en absoluto) diciéndole aproximadamente lo cerca que está $A$ es a cada subcadena de $B$ de longitud $n$ . En particular, para cada subcadena de $B$ de longitud $n$ Bob quiere ser capaz de calcular la distancia de Hamming entre $A$ y esa subcadena dentro de un factor multiplicador de $2$ sólo de este único mensaje.

Como ejemplo, dejemos que $A = 101$ y $B = 011001$ . Las verdaderas distancias de Hamming son $2, 2, 1, 1$ . Bob, habiendo recibido el mensaje de Alice, tiene que emitir 4 números. Los valores de salida de Bob deben estar en el rango de 2 a 4 para los dos primeros números y de 1 a 2 para los dos siguientes.

Asumiendo que Alice y Bob puedan acordar un protocolo determinista de antemano, ¿cuántas piezas tiene Alice que enviar a Bob?

Answer 1

Esta no es una respuesta completa hasta una función en forma cerrada o una suma trivial, pero sólo una reducción a una pura combinación problema.

¿Es posible enviar datos? Sí, Alice puede enviar sólo un concatenación de $A$ y $B$ y ser feliz sin hacer nada. Esto toma $3n$ trozos. Hay una forma trivial de ahorrar un poco. Tenga en cuenta que $A$ y $B$ dan la misma secuencia que $\overline {A}$ y $\overline {B}$ , donde $\overline {S}$ significa cadena $S$ con cada personaje volteado (i. es decir, 0 se convierte en 1 y 1 se convierte en 0). Así que podemos tirar el primer personaje $a_0$ de $A$ suponiendo que sea cero (de lo contrario, sustituya $A$ y $B$ con $\overline {A}$ y $\overline {B}$ en consecuencia). Así que tenemos $3n - 1$ trozos. Este enfoque que yo llamo trivial .

¿Es posible guardar un número significativo de bits sin información ¿Pérdida? La mejor manera de hacerlo es la siguiente. Dejar que $D = D(A, B)$ ser un secuencia de distancias deseada. Dejemos que Alice y Bob enumeren todo posibles tales secuencias, es decir, todas las secuencias $D_i$ de tal manera que hay es al menos un par $(A_i, B_i)$ de tal manera que $D_i = D(A_i, B_i)$ . Luego Alice le envía a Bob un número de serie cero de $D$ . Tan nuevo La pregunta es: ¿cuántas secuencias diferentes pueden ser producidas por todos pares de $A$ y $B$ de longitud $n$ y $2n$ en consecuencia? Hay a relacionado pregunta para el caso en que la longitud de $B$ es $2n-1$ . Ten en cuenta que si Bob no lo hace conocer $n$ entonces Alice puede añadir ceros a la cifra para hacer la longitud de su mensaje una información sobre $n$ . Tengo razones para dicen que el número de secuencias de diferencias es mayor que $2^n$ así que la longitud del mensaje con el número de serie de la secuencia refleja el valor de $n$ .

Ahora veamos cómo es posible guardar aún más información usando el error unilateral permitido del resultado de Bob. Dejemos que Alice después de calcular la secuencia $D$ lo transforman en una secuencia $T = T(D)$ de la siguiente manera y enviar un número de serie de $T$ . Cada 0 sigue siendo 0. Cada 1 es reemplazado por 2, y cada 2 sigue siendo 2. Cada 3, 4, 5 son reemplazados por 6, y cada 6 queda para ser 6, etc. Es decir, cada número $2^k - 1, 2^k, \ldots , 2^{k + 1} - 3$ es reemplazado por $2^{k + 1} - 2$ y $2^{k + 1} - 2$ no ha cambiado. Es fácil ver que al tomar la secuencia $T$ en lugar de la secuencia $D$ Bob comete un error unilateral permitido. Así que la pregunta deseada es: ¿cuántas secuencias diferentes $T(D(A, B))$ hay para cada uno $n$ ? También es posible que la información sobre $n$ debería ser añadido de alguna manera.

Y la tercera versión del problema es sobre el error de dos caras permitido. Sugiero la misma idea: dejar que Alice se transforme $D$ en $T' = T'(D)$ de la siguiente manera y enviar un número de serie de $T'$ . Cada 0 sigue siendo 0. Cada 1, 2, 3 y 4 se convierten en 2. Cada 5, 6, $\ldots$ 20 se convierten en 10. Así que, cada uno $\frac {4^k - 1}{3}, \frac {4^k - 1}{3} + 1, \ldots , \frac {4^{k + 1} - 4}{3}$ se convierte en $\frac {2 \cdot 4^k - 2}{3}$ . Es fácil ver que la secuencia de toma $T'$ en lugar de la secuencia $D$ Bob comete un error de dos caras permitido. Así que la nueva pregunta es: ¿cuántas secuencias diferentes $T'(D(A, B))$ hay para cada uno $n$ ? También es posible que la información sobre $n$ debería ser añadido de alguna manera.

Y finalmente doy algunos resultados computacionales y los comparo con uno trivial. $$\begin {array}{|c|r|l|r|l|r|l|} \hline n & \#D & \frac { \log_2 \#D}{3n - 1} & \#T & \frac { \log_2 \#T}{3n - 1} & \#T' & \frac { \log_2 \#T'}{3n - 1} \\\hline 1 & 4 & 1 & 4 & 1 & 4 & 1 \\\hline 2 & 21 & 0.878463 & 8 & 0.6 & 8 & 0.6 \\\hline 3 & 124 & 0.869275 & 41 & 0.669694 & 14 & 0.475919 \\\hline 4 & 825 & 0.88075 & 132 & 0.640399 & 23 & 0.411233 \\\hline 5 & 6024 & 0.896893 & 326 & 0.596338 & 109 & 0.483442 \\\hline 6 & 47391 & 0.913666 & 700 & 0.555954 & 363 & 0.500225 \\\hline 7 & 395944 & 0.929747 & 2698 & 0.569884 & 1149 & 0.508308 \\\hline 8 & 3396881 & 0.943295 & 9129 & 0.57201 & 3230 & 0.50684 \\\hline 9 & 30095408 & 0.955502 & 31348 & 0.574465 & 7209 & 0.492907 \\\hline 10 & 267147407 & 0.965278 & 102212 & 0.573835 & 14910 & 0.478069 \\\hline 11 & ? & ? & 297939 & 0.568271 & 31060 & 0.466337 \\\hline \end {array}$$

Parece que el envío de una secuencia sin errores tiende a no tener ningún beneficio significativo, mientras que el error de dos caras permitido reduce las cantidades de información aproximadamente dos veces.