The Binomial Channel: On Capacity, Optimal Inputs, and Beta-Binomial Approximation

Resumen Técnico: El Canal Binomial: Sobre la Capacidad, los Inputs Óptimos y la Aproximación Beta-Binomial

Planteamiento del Problema
Este artículo investiga el canal binomial, un modelo de comunicación donde la entrada $X$ es una variable aleatoria continua en el intervalo $[0, 1]$ y la salida $Y$ es una variable aleatoria discreta en $\{0, \dots, n\}$, regida por la distribución binomial $P_{Y|X}(y|x) = \binom{n}{y} x^y (1-x)^{n-y}$. Los objetivos principales son determinar la capacidad del canal $C(n)$ y caracterizar la estructura de la distribución de entrada que alcanza la capacidad, denotada como $P_{X^\star}$. Un desafío significativo abordado es que, si bien el alfabeto de salida es finito, el alfabeto de entrada es continuo; consecuentemente, la información mutua no es estrictamente cóncava con respecto a la distribución de entrada, lo que complica la prueba de unicidad y la determinación del tamaño del soporte del input óptimo.

Metodología
Los autores emplean una combinación de optimización de la teoría de la información, teoría de la estimación y teoría de la aproximación:

1. Condiciones KKT: El análisis se basa en las condiciones de Karush-Kuhn-Tucker (KKT) para caracterizar el soporte de la entrada óptima. El conjunto de puntos donde la densidad de información es igual a la capacidad ($A_n$) es central para demostrar la discreción y la unicidad.
2. Identidades de la Teoría de la Estimación: El artículo utiliza fórmulas de derivadas para la densidad de información y propiedades de la media condicional $E[X|Y=y]$, estableciendo su monotonicidad.
3. Distribución de Referencia: Se introduce una entrada de referencia específica $X_r \sim \text{Beta}(1/2, 1/2)$. Esta distribución es el prior de Jeffreys para el canal binomial e induce una salida Beta-Binomial $Y_r$.
4. Polinomios Ortogonales y Aproximación: Para acotar el tamaño del soporte, los autores utilizan la teoría de los polinomios ortogonales (específicamente los polinomios de Chebyshev desplazados) asociados con la distribución Beta(1/2, 1/2). Derivan una identidad de tipo Parseval para la divergencia $\chi^2$ entre una mezcla binomial general y la salida Beta-Binomial de referencia.
5. Redundancia Minimax: Se derivan cotas superiores para la capacidad utilizando la construcción de redundancia minimax de Xie y Barron, mientras que las cotas inferiores se obtienen evaluando la información mutua en la entrada de referencia $X_r$.

Contribuciones Clave y Resultados

• Propiedades Estructurales de la CAID:

  • Discreción y Unicidad: Los autores demuestran que todas las distribuciones que alcanzan la capacidad son discretas y, crucialmente, que la CAID es única. Esta unicidad se establece al mostrar que la información mutua es estrictamente cóncava sobre el conjunto de distribuciones soportadas en cualquier conjunto de $n+1$ puntos, combinado con el hecho de que el conjunto $A_n$ tiene una cardinalidad de como máximo $n+1$.
  • Simetría y Soporte: La entrada óptima es simétrica alrededor de $1/2$, y su soporte incluye necesariamente los extremos $\{0, 1\}$.
  • Restricciones de Soporte: Existe a lo sumo un punto de soporte en los intervalos $(0, 1/n]$ y $[1-1/n, 1)$.

• Cotas de Capacidad:

  • El artículo deriva cotas superiores y inferiores no asintóticas explícitas para $C(n)$.
  • Estas cotas implican el comportamiento asintótico: $C(n) = \frac{1}{2} \log \left( \frac{n\pi}{2e} \right) + o(1)$.
  • La cota inferior se logra mediante la entrada de referencia $X_r$, y la brecha entre las cotas superior e inferior desaparece cuando $n \to \infty$.

• Cotas del Tamaño del Soporte:

  • Cota Superior: La clásica cota superior de tipo Witsenhausen de orden $n$ se mejora a una cota superior de orden $n/2$.
  • Cota Inferior: El artículo establece una nueva cota inferior para la cardinalidad del soporte. Al demostrar que la salida Beta-Binomial inducida por $X_r$ es asintóticamente óptima y cercana a la verdadera salida que alcanza la capacidad en términos de entropía relativa y divergencia $\chi^2$, y combinando esto con una cota inferior de aproximación de mezcla finita, los autores derivan una cota inferior del tamaño del soporte de orden $\Omega(\sqrt{n} \log \log n)$.

• Resultados Numéricos:

  • Los autores proporcionan estimaciones numéricas para la CAID y la capacidad para $n$ hasta 350.
  • Los resultados sugieren que los puntos de soporte de la entrada óptima, cuando son transformados por la función de distribución acumulativa de la entrada Beta(1/2, 1/2), están aproximadamente espaciados uniformemente.
  • Los datos numéricos para $n \le 350$ parecen ser consistentes con una conjetura de que el tamaño del soporte escala como $\Theta(n^{3/4})$, aunque los autores advierten que este rango aún puede estar en un régimen de $n$ finito donde el escalamiento asintótico no es completamente visible.

Significancia
El artículo proporciona una imagen teórica más detallada del canal binomial, cerrando brechas respecto a la unicidad y las propiedades estructurales específicas de la distribución de entrada óptima. Al establecer que la entrada óptima es única y discreta, y al proporcionar cotas ajustadas sobre la capacidad y el tamaño del soporte, el trabajo avanza en la comprensión de canales con entradas continuas y salidas finitas. La derivación de la cota inferior $\Omega(\sqrt{n} \log \log n)$ del tamaño del soporte representa una mejora significativa sobre las cotas previas de orden $\sqrt{n}$, utilizando una combinación novedosa de la teoría de la mejor aproximación y medidas de divergencia de la teoría de la información. Los resultados también resaltan la optimalidad asintótica de la distribución Beta-Binomial, vinculando la teoría de la información con la estimación bayesiana (prior de Jeffreys).