Resumen Técnico: Límites de Capacidad Combinatoria para el Canal de Eliminación $q$-ario

Planteamiento del Problema

El artículo aborda el problema fundamental de caracterizar la capacidad del canal de eliminación $q$-ario. En este modelo de canal, cada símbolo transmitido de un alfabeto $\Sigma_q$ es eliminado de forma independiente con una probabilidad $d$, y el receptor observa la subsecuencia superviviente sin conocimiento de qué posiciones fueron eliminadas. A pesar de décadas de investigación, las caracterizaciones de capacidad ajustadas para este canal siguen siendo un problema abierto, particularmente para tamaños de alfabeto generales $q \ge 2$ y longitudes de bloque finitas $n$. Los límites existentes suelen ser laxos y los cálculos exactos de la capacidad son computacionalmente intratables para $n$ grandes.

Metodología

Los autores introducen un marco combinatorio autónomo centrado en el escalar de conteo de patrones, denotado como $N_n(x, y)$. Este escalar entero se define como el número de distintos subconjuntos de eliminación $S \subseteq [n]$ de tamaño $n-k$ tales que la eliminación de las posiciones en $S$ de una palabra de entrada $x \in \Sigma_q^n$ produce la palabra de salida $y \in \Sigma_q^k$.

La metodología procede a través de los siguientes pasos:

1. Factorización: La probabilidad de transición del canal se factoriza en el peso probabilístico de un patrón de eliminación específico y el conteo combinatorio $N_n(x, y)$. Específicamente, $\Pr(Y=y | X=x) = N_n(x, y) \cdot d^{n-k}(1-d)^k$.
2. Estructura Recursiva: Se establece una recursión de dos casos para $N_n$ que se cumple uniformemente para todo $q \ge 2$. Esta recursión separa la estructura combinatoria del canal de sus pesos probabilísticos.
3. Identidades de Suma: Se prueban dos identidades clave:
   • Identidad de suma de filas: Para una entrada $x$ fija, la suma de $N_n(x, y)$ sobre todas las salidas posibles $y$ de longitud $k$ es igual a $\binom{n}{k}$.
   • Identidad de suma de columnas: Para una salida $y$ fija, la suma de $N_n(x, y)$ sobre todas las entradas posibles $x$ de longitud $n$ es igual a $q^{n-k}\binom{n}{k}$.
4. Análisis de Entropía: Estas identidades se utilizan para derivar la entropía de salida exacta bajo una distribución de entrada uniforme. Los autores introducen entonces un término de corrección de entropía, $\Phi_{k,n}$, que cuantifica la concentración de la distribución condicional cuando múltiples subconjuntos de eliminación mapean la misma entrada a la misma salida (es decir, cuando $N_n(x, y) \ge 2$).

Contribuciones Clave

1. Entropía de Salida Exacta y Sándwich de Capacidad

Bajo la suposición de una distribución de entrada uniforme, los autores derivan una expresión de forma cerrada para la entropía de salida $H(Y)$. Esto conduce a un límite de "sándwich" para la capacidad de bloque finito $C_{q,n}$:
$$(1-d)\log_2 q - h_2(d) \le C_{q,n} \le (1-d)\log_2 q$$
donde $h_2(d)$ es la función de entropía binaria. El límite superior es clásico, mientras que el límite inferior se deriva directamente del análisis de la entrada uniforme.

2. Límite Inferior Refinado mediante Corrección de Entropía

La principal contribución del artículo es el refinamiento del límite inferior al contabilizar la no uniformidad de la distribución de salida condicional. Los autores definen un término de corrección $\Delta_n(d)$ basado en los valores de $N_n(x, y)$:
$$\Delta_n(d) = \sum_{k=0}^n w_k \Phi_{k,n}$$
donde $w_k$ es la probabilidad de que la longitud de la salida sea $k$, y $\Phi_{k,n}$ es la corrección de entropía promedio derivada de los valores enteros de $N_n$. Esto produce una expresión exacta de la información mutua bajo una entrada uniforme:
$$\frac{1}{n}I_U(X; Y) = (1-d)\log_2 q + \frac{1}{n}H_{\text{Bin}}(n, 1-d) - h_2(d) + \frac{\Delta_n(d)}{n}$$
Dado que la capacidad es el máximo de la información mutua, esta expresión proporciona un límite inferior certificado:
$$C_{q,n} \ge (1-d)\log_2 q + \frac{1}{n}H_{\text{Bin}}(n, 1-d) - h_2(d) + \frac{\Delta_n(d)}{n}$$

3. Positividad y Límites Asintóticos

Los autores demuestran que $\Delta_n(d) > 0$ para todo $n \ge 2$ y $d \in (0, 1)$, certificando que el límite refinado es estrictamente mejor que el límite inferior básico. Proporcionan un límite inferior de forma cerrada para $\Phi_{k,n}$ y derivan el comportamiento asintótico de pequeña eliminación:
$$C_q(d) \ge \log_2 q + d \log_2 d + O(d)$$
Este resultado se sostiene para todo $q \ge 2$.

4. Verificación Numérica

El artículo presenta experimentos numéricos para $q \in \{2, 3\}$ y longitudes de bloque $n \in \{3, 5, 10\}$. Utilizando el algoritmo de Blahut–Arimoto para calcular la capacidad exacta de bloque finito, los autores demuestran que su límite inferior refinado ($LB+$) está estrictamente más cerca de la capacidad real que los límites previos (como el límite de Diggavi–Grossglauser o la expansión de Kanoria–Montanari para $q=2$). La brecha entre el límite refinado y la capacidad real se estrecha a medida que $n$ aumenta.

Significado y Reivindicaciones

El artículo afirma proporcionar un tratamiento $q$-ario autónomo del canal de eliminación que unifica la estructura combinatoria con el análisis probabilístico. Al utilizar el escalar de conteo de patrones $N_n(x, y)$, los autores organizan todos los cálculos de capacidad a través de un único arreglo de enteros.

El significado de este trabajo reside en:

• Límites Certificados: Ofrece límites inferiores explícitos y certificados para la capacidad del canal de eliminación $q$-ario para cualquier $q \ge 2$, mejorando los resultados existentes al incorporar un término de corrección de entropía exacto.
• Conveniencia Analítica: Demuestra que, si bien la entrada uniforme puede no ser globalmente óptima para todos los $d$, produce una entropía de salida tratable y exacta, así como un límite inferior riguroso que mejora conforme aumenta la longitud de bloque.
• Perspectiva Estructural: La estructura recursiva de $N_n$ y las identidades de suma derivadas proporcionan una nueva perspectiva combinatoria sobre el canal, separando el conteo de los patrones de eliminación de sus probabilidades.

Los autores señalan modestamente que la entrada uniforme se elige por su tratabilidad y no afirman que sea la que alcanza la capacidad para todos los $q$ y $d$. Sin embargo, los límites derivados son válidos para la capacidad real, y los resultados numéricos confirman que los límites inferiores propuestos son ajustados para $n$ pequeños y mejoran con $n$ mayor. El trabajo futuro sugerido por los autores incluye la caracterización asintótica de $\Delta_n(d)/n$ cuando $n \to \infty$ y la extensión de estos métodos a los canales de inserción-eliminación.