Empirical Coordination over Markov Channel with Independent Source

1. Problema de Estudio

El trabajo aborda el problema de la codificación conjunta fuente-canal (JSCC) en el contexto de canales de Markov (también conocidos como canales de estado finito, FSC). El objetivo principal es determinar las distribuciones conjuntas empíricas de los símbolos de la fuente y del canal que pueden ser inducidas por un esquema de codificación.

Configuración del sistema:

• Fuente: Genera símbolos de forma independiente e idénticamente distribuida (i.i.d.) en cada paso de tiempo.
• Codificador: Es estrictamente causal. Genera las entradas del canal basándose únicamente en la secuencia pasada de la fuente ($U^{t-1}$). No tiene acceso a los estados pasados del canal ni a las salidas del canal (sin retroalimentación o feedback). Esto significa que el codificador no adapta su entrada a la historia latente del estado del canal.
• Canal: Es un canal de Markov con memoria de un paso. El estado actual del canal ($Y_t$) depende de la entrada actual ($X_t$) y del estado anterior ($Y_{t-1}$). La evolución del estado está impulsada por la entrada del canal.
• Decodificador: Es no causal. Observa toda la secuencia de salida del canal ($Y^n$) para generar su secuencia de acciones ($V^n$).

El marco teórico utilizado es la coordinación empírica, donde el objetivo no es solo la comunicación fiable, sino inducir una distribución conjunta específica entre las variables de la red (fuente, entrada, estado del canal y salida).

2. Metodología

Para resolver este problema, los autores desarrollan un análisis teórico que combina teoría de la información y teoría de la probabilidad, introduciendo nuevas herramientas para manejar la dependencia temporal del canal.

A. Nuevas Herramientas: Tipicidad de Markov Impulsada por Entrada

Contrario a los esquemas clásicos de codificación de bloques Markovianos que dependen de la independencia entre bloques (típico en canales sin memoria), este trabajo explota directamente la estructura del canal de Markov.

• Se introduce un nuevo concepto llamado Tipicidad de Markov Impulsada por Entrada (Input-driven Markov Typicality).
• Esta definición se aplica a pares de secuencias $(X^n, Y^n)$ donde $X^n$ es i.i.d. y $Y^n$ es una cadena de Markov condicionada a $X^n$.
• Se demuestran propiedades fundamentales de esta tipicidad, incluyendo la Propiedad de Equipartición Asintótica (AEP) y un Lema de Empaquetamiento (Packing Lemma) adaptado a la dependencia de la memoria del canal.

B. Esquema de Codificación

Se utiliza un esquema de codificación aleatoria de bloques Markovianos (Block-Markov coding), extendido al marco de coordinación:

1. Generación de libros de códigos: Se generan secuencias de entrada $X^n$ y secuencias auxiliares $W^n$ condicionadas a $X^n$.
2. Codificación: El codificador busca un índice que haga que la secuencia de la fuente, la entrada y la variable auxiliar sean conjuntamente típicas (según la nueva definición).
3. Transmisión: El canal transmite la secuencia $X^n$, actualizando su estado de Markov.
4. Decodificación: El decodificador, al observar toda la salida, busca índices que satisfagan condiciones de tipicidad conjunta entre la salida, la entrada y la variable auxiliar, aprovechando la estructura de Markov para manejar la dependencia entre bloques.

3. Contribuciones Clave

1. Primera caracterización de JSCC en Canales de Markov bajo Coordinación Empírica: Este es el primer trabajo que estudia la coordinación empírica en canales de Markov con codificadores estrictamente causales y sin retroalimentación.
2. Introducción de la "Tipicidad de Markov Impulsada por Entrada": Una herramienta teórica novel que permite analizar secuencias donde la entrada i.i.d. impulsa una cadena de Markov, superando las limitaciones de los argumentos basados en independencia de bloques.
3. Límites de Información de Letra Única (Single-letter): Se derivan cotas internas y externas cerradas (en términos de letras únicas) para el conjunto de distribuciones conjuntas alcanzables.

4. Resultados Principales

El resultado central es el Teorema 1, que proporciona condiciones necesarias y suficientes para que una distribución conjunta $P_{U,X,Y',Y,V}$ sea alcanzable.

A. Cota Interna (Achievability)

Una distribución es alcanzable si existe una variable aleatoria auxiliar $W$ tal que la distribución se factoriza como:
$$P_{U,X,Y',Y,V} = P_U P_X P_{W|U,X} \pi_{Y'} W_{Y|X,Y'} P_{V|Y,X,W}$$
y satisface la restricción de información:
$$I(X; Y | Y') - I(U; W | X) \ge 0$$
Donde:

• $I(X; Y | Y')$ representa la capacidad del canal de Markov (información mutua condicional entre entrada y salida dado el estado anterior).
• $I(U; W | X)$ representa la tasa de información de la fuente que debe ser comprimida y enviada a través de la variable auxiliar $W$ dado $X$.
• $\pi_{Y'}$ es la distribución de equilibrio única de la cadena de Markov inducida por la distribución de entrada estacionaria $P_X$.

B. Cota Externa (Converse)

La cota externa comparte la misma expresión de restricción de información que la cota interna, pero se define sobre un conjunto más amplio de distribuciones, lo que implica que la cota externa es generalmente más holgada (looser). La demostración utiliza descomposiciones de información mutua y propiedades de cadenas de Markov para mostrar que cualquier esquema de codificación debe satisfacer dicha desigualdad.

C. Caso Especial: Separación Fuente-Canal

Cuando las variables de la fuente y del canal son independientes, la restricción de información se reduce a una forma análoga al teorema de separación de Shannon:
$$0 \le I(X; Y | Y') - I(U; V)$$
Esto confirma que la capacidad del canal de Markov (con retroalimentación implícita en la estructura de coordinación) menos la tasa de la fuente debe ser no negativa.

5. Significado e Impacto

• Avance Teórico: El trabajo demuestra que es posible obtener resultados de "letra única" para canales con memoria (Markov) sin depender de la independencia de bloques, lo cual era un desafío en la literatura de coordinación empírica.
• Generalización: Los resultados generalizan los trabajos anteriores sobre canales sin memoria (DMC) y canales con estado, unificando el análisis bajo el marco de coordinación.
• Aplicabilidad: Proporciona un marco para diseñar sistemas de control y comunicación distribuidos donde la coordinación de acciones es tan importante como la transmisión de datos, incluso en entornos con memoria y sin retroalimentación inmediata.
• Herramientas Nuevas: La definición de tipicidad impulsada por entrada abre la puerta a futuros análisis de sistemas de control estocástico y redes de sensores que operan sobre canales con memoria.

En resumen, el artículo establece los límites fundamentales de la coordinación en redes con canales de Markov, demostrando que la estructura de Markov puede ser explotada directamente mediante nuevas definiciones de tipicidad, logrando así una caracterización precisa de las distribuciones alcanzables.