An Improved Lower Bound on Support Size of Capacity-Achieving Inputs for the Binomial Channel: Extended version

Resumen Técnico: Un Límite Inferior Mejorado para el Tamaño del Soporte de las Entradas que Alcanzan la Capacidad en el Canal Binomial

Enunciado del Problema
Este trabajo investiga las propiedades estructurales de la distribución de entrada que alcanza la capacidad para el canal binomial, definida por la probabilidad de transición $P_{Y|X}(y|x) = \binom{n}{y} x^y (1-x)^{n-y}$ para $x \in [0, 1]$ y $y \in \{0, \dots, n\}$. Si bien está establecido que la distribución de entrada que alcanza la capacidad $P_{X^*}$ es discreta y está soportada en un número finito de puntos, la tasa de crecimiento precisa de este tamaño del soporte a medida que aumenta el número de ensayos $n$ sigue siendo objeto de estudio. Resultados anteriores de [10] establecieron que el tamaño del soporte está acotado inferiormente por un término de orden $\sqrt{n}$ y acotado superiormente por un término de orden $n/2$. Sin embargo, la brecha entre los límites de capacidad conocidos en [10] no se desvaneció cuando $n \to \infty$, lo que limitó la capacidad de derivar límites inferiores más agudos para la cardinalidad.

Metodología
Los autores emplean un marco analítico de tres pasos para derivar un límite inferior más ajustado para el tamaño del soporte:

1. Límites de Capacidad Ajustados: Los autores derivan primero nuevos límites explícitos superior e inferior para la capacidad del canal $C(n)$. El límite inferior se obtiene evaluando la información mutua en una entrada de referencia $X_r \sim \text{Beta}(1/2, 1/2)$, mientras que el límite superior utiliza la construcción de redundancia minimax de Xie–Barron [8]. Crucialmente, se demuestra que estos límites tienen una brecha que se desvanece cuando $n \to \infty$, lo que produce la expansión asintótica $C(n) = \frac{1}{2} \log \frac{n\pi}{2e} + o(1)$.

2. Optimalidad de la Salida de Referencia: Utilizando la brecha de capacidad que se desvanece, los autores demuestran que la distribución de salida inducida por la entrada de referencia, $P_{Y_r}$ (una distribución Beta-binomial), es asintóticamente óptima. Específicamente, prueban que la entropía relativa $D(P_{Y_r} \| P_{Y^*})$ y la divergencia $\chi^2$ $\chi^2(P_{Y^*} \| P_{Y_r})$ entre la salida de referencia y la verdadera salida que alcanza la capacidad $P_{Y^*}$ se desvanecen a una tasa proporcional a la brecha de capacidad.

3. Límite Inferior de Aproximación por Mezcla Finita: El núcleo del argumento se basa en un límite inferior cuantitativo para aproximar la salida Beta-binomial de referencia utilizando una mezcla finita de distribuciones binomiales. Inspirados en técnicas utilizadas para el canal gaussiano aditivo [11] y la teoría de mejor aproximación [12], los autores adaptan el método de momentos trigonométricos. Utilizan polinomios ortogonales (polinomios de Chebyshev desplazados) asociados con la distribución Beta(1/2, 1/2) para construir una matriz de momentos. Al aplicar el teorema de Eckart-Young-Mirsky a esta matriz, derivan un límite inferior para la divergencia $\chi^2$ entre la salida de una entrada arbitraria de $K$ puntos y la salida de referencia.

Contribuciones y Resultados Clave
La contribución principal de este artículo es un límite inferior mejorado para la cardinalidad del soporte de la distribución de entrada que alcanza la capacidad $P_{X^*}$.

• Límite Inferior Mejorado: Los autores prueban que el tamaño del soporte $|\text{supp}(P_{X^*})|$ está acotado inferiormente por un término de orden $\sqrt{n} \log \log n$. Específicamente, para $n$ suficientemente grande:
  $$|\text{supp}(P_{X^*})| \geq \Omega\left(\sqrt{n} \log \log n\right)$$
  Esto mejora el límite anterior de $\Omega(\sqrt{n})$ establecido en [10].

• Caracterización de la Capacidad: El artículo proporciona límites explícitos superior e inferior para $C(n)$ con una brecha que se desvanece, confirmando el comportamiento asintótico $C(n) = \frac{1}{2} \log \frac{n\pi}{2e} + o(1)$.

• Teoría de Aproximación: El trabajo establece un límite inferior específico para la divergencia $\chi^2$ entre una distribución Beta-binomial y cualquier mezcla binomial con $K$ componentes, mostrando que tal aproximación no puede ser arbitrariamente cercana a menos que $K$ sea suficientemente grande.

Significado
El artículo afirma que la brecha que se desvanece en las estimaciones de capacidad es el ingrediente esencial que permite la conexión entre el valor de la capacidad y el tamaño del soporte. Al demostrar que la salida que alcanza la capacidad debe estar cerca de la salida de referencia Beta-binomial en términos de divergencia $\chi^2$, y al probar que esta salida de referencia no puede ser bien aproximada por una mezcla dispersa, los autores fuerzan la conclusión de que la entrada que alcanza la capacidad debe poseer un soporte significativamente mayor que el demostrado anteriormente.

Los autores señalan que, aunque la mejora de $\sqrt{n}$ a $\sqrt{n} \log \log n$ es asintótica y las constantes explícitas no están optimizadas, el resultado estrecha la brecha entre el límite inferior conocido y el límite superior de orden $n/2$. El artículo concluye identificando preguntas abiertas, incluyendo la determinación del crecimiento asintótico exacto del tamaño del soporte y el refinamiento de las constantes explícitas y las estimaciones no asintóticas.