Empirical coordination in the finite blocklength regime: an achievability result---Extended version

Technische Samenvatting: Empirische Coördinatie in het Regime van Eindige Bloklengte

Probleemformulering
Dit artikel onderzoekt het probleem van empirische coördinatie onder beperkingen van eindige bloklengte. In deze setting observeert een encoder een bronsequentie $U^n$ en zendt een bericht $M$ uit een eindige verzameling $\mathcal{M}$ naar een decoder. De decoder genereert een outputsequentie $V^n$. Het doel is om de acties van de encoder en decoder te coördineren zodat de gezamenlijke empirische verdeling van het paar $(U^n, V^n)$ dicht bij een doel-gezamenlijke verdeling $P_{UV}$ ligt. Specifiek streeft het systeem ernaar te garanderen dat $(U^n, V^n)$ met hoge waarschijnlijkheid binnen de verzameling van gezamenlijk typische sequenties $\mathcal{T}^n(UV)$ valt.

Het artikel definieert een verdeling $P_{UV}$ als $(n, |\mathcal{M}|, \epsilon)$-bereikbaar als er een code $(\sigma, \tau)$ bestaat zodat de waarschijnlijkheid dat het paar $(U^n, V^n)$ niet gezamenlijk typisch is, ten hoogste $\epsilon$ bedraagt. De centrale grootheid van belang is de optimale snelheid $R(n, \epsilon)$, gedefinieerd als de minimale genormaliseerde log-grootte van de berichtverzameling die nodig is om deze betrouwbaarheid te bereiken. In tegenstelling tot asymptotische analyses waarbij $n \to \infty$, richt dit werk zich op het regime waarbij $n$ vast en eindig is, en kwantificeert het de trade-offs tussen bloklengte, foutkans en communicatiesnelheid.

Methodologie
De auteurs hanteren Shannons redenering van willekeurige codering gecombineerd met de methode van types om een bereikbaarheidsbound af te leiden. De bewijsstrategie volgt een drie-staps structuur die doet denken aan recente resultaten voor eindige bloklengte in de theorie van rate-distortion (bijvoorbeeld Kostina en Verdú [8]):

1. Analyse van Willekeurige Codeboeken: De auteurs analyseren de gemiddelde prestaties van een willekeurig codeboek waarbij codewoorden i.i.d. worden gegenereerd volgens de marginale verdeling $P_V$. Zij leiden een exacte uitdrukking af voor de verwachte foutkans, die afhankelijk is van de waarschijnlijkheid dat een willekeurig gegenereerde sequentie gezamenlijk typisch is met de bronsequentie.
2. Typicaliteit en Divergentie-Bounds: Met behulp van de methode van types stellen de auteurs een ondergrens vast voor de waarschijnlijkheid dat een sequentie gezamenlijk typisch is. Dit houdt in dat de waarschijnlijkheid wordt gerelateerd aan de conditionele Kullback-Leibler (KL) divergentie $D(P_{V|U} \| P_V)$. Een belangrijke technische stap bestaat uit het benaderen van het conditionele type van de gegenereerde sequentie met de doel-conditionele verdeling, waarbij gebruik wordt gemaakt van bounds op de divergentie tussen types.
3. Concentratieongelijkheden: Om over te gaan van de exacte bound voor eindige bloklengte naar een asymptotische expansie, passen de auteurs de Berry–Esseen-stelling toe. Dit stelt hen in staat de verdeling van de som van onafhankelijke willekeurige variabelen (specifiek de som van conditionele divergenties) te benaderen door een Gaussische verdeling, waarmee het tweede-orde gedrag van de snelheid wordt gekarakteriseerd.

Belangrijkste Bijdragen en Resultaten
De primaire bijdrage is de afleiding van een bereikbaarheidsresultaat voor empirische coördinatie dat zowel een exacte bound voor eindige bloklengte als een tweede-orde asymptotische expansie biedt.

• Exacte Bound (Stelling 2): Het artikel stelt een exacte bovengrens vast voor de optimale snelheid $R(n, \delta, \epsilon)$ voor een vaste typicaliteitsdrempel $\delta$. Deze bound bevat termen die rekening houden met de bloklengte $n$, de alfabetgroottes en de variantie van de conditionele informatiedichtheid.

• Asymptotische Expansie (Stelling 1): Het hoofdresultaat presenteert de optimale snelheid als:
  $$R(n, \epsilon) \leq I(U; V) + \sqrt{\frac{\text{Var}(E[\imath(U; V)|U])}{n}} Q^{-1}(\epsilon) + o\left(\frac{1}{\sqrt{n}}\right)$$
  Hierbij is $I(U; V)$ de wederzijdse informatie, $Q^{-1}$ de inverse Gaussische staartfunctie, en is de variantieterm expliciet gedefinieerd als de variantie van de conditionele verwachting van de informatiedichtheid $\imath(U; V)$.

• Karakterisering van Variantie: Een belangrijke technische inzicht is de identificatie van de variantieterm. De auteurs tonen aan dat de relevante variantie $\text{Var}(E[\imath(U; V)|U])$ is, wat strikt kleiner dan of gelijk is aan de onvoorwaardelijke variantie $\text{Var}(\imath(U; V))$ die typisch wordt aangetroffen in kanaalcoderingsproblemen. Deze term ontstaat natuurlijk uit de methode van types en de specifieke structuur van het coördinatieprobleem, en onderscheidt zich van de "gekipte informatie"-variantie die wordt aangetroffen in rate-distortion-problemen.

Betekenis en Claims
Het artikel claimt de analyse voor eindige bloklengte, die eerder was vastgesteld voor kanaalcodering en broncodering met verlies, uit te breiden naar de setting van empirische coördinatie. Hiermee vult het bestaande resultaten over sterke coördinatie (in het bijzonder het werk van Cervia et al. [19]) aan door de zwakkere, maar praktisch relevante, notie van empirische coördinatie aan te pakken.

De auteurs benadrukken dat hun resultaten overeenstemmen met de heersende karakterisering in de literatuur over eindige bloklengte, en bieden een niet-asymptotisch perspectief dat direct relevant is voor praktische systemen met beperkte bloklengtes. Het werk toont aan dat de fundamentele trade-offs in coördinatie met dezelfde precisie kunnen worden gekwantificeerd als bij klassieke coderingsproblemen, waarbij de specifieke variantieterm de unieke beperkingen weerspiegelt van het coördineren van acties onder communicatiebeperkingen. Het artikel levert numerieke simulaties die de exacte gemiddelde prestaties van willekeurige codeboeken vergelijken met de afgeleide asymptotische bounds, waarmee de nauwkeurigheid van de theoretische resultaten voor gematigde bloklengtes wordt gevalideerd.