Technische Samenvatting: Combinatorische Capaciteitsgrenzen voor het $q$-aire Deletiekanaal

Probleemstelling

Het artikel behandelt het fundamentele probleem van het karakteriseren van de capaciteit van het $q$-aire deletiekanaal. In dit kanaalmodel wordt elk verzonden symbool uit een alfabet $\Sigma_q$ onafhankelijk verwijderd met een waarschijnlijkheid $d$, waarbij de ontvanger de overlevende subreeks observeert zonder kennis van welke posities zijn verwijderd. Ondanks decennia van onderzoek blijft een nauwe karakterisering van de capaciteit voor dit kanaal een open probleem, met name voor algemene alfabetgroottes $q \ge 2$ en eindige bloklengtes $n$. Bestaande grenzen zijn vaak zwak, en exacte capaciteitsberekeningen zijn computationeel onhandelbaar voor grote $n$.

Methodologie

De auteurs introduceren een zelfvoorzienend combinatorisch kader dat gecentreerd is rond de patroon-tel scalaire, aangeduid als $N_n(x, y)$. Deze gehele scalaire wordt gedefinieerd als het aantal verschillende deletiesubsets $S \subseteq [n]$ van grootte $n-k$ waarvoor het verwijderen van de posities in $S$ uit een invoerwoord $x \in \Sigma_q^n]$ een uitvoerwoord $y \in \Sigma_q^k$ oplevert.

De methodologie verloopt via de volgende stappen:

1. Factorisatie: De overgangswaarschijnlijkheid van het kanaal wordt gefactoriseerd in het probabilistische gewicht van een specifiek deletiepatroon en de combinatorische telling $N_n(x, y)$. Specifiek geldt $\Pr(Y=y | X=x) = N_n(x, y) \cdot d^{n-k}(1-d)^k$.
2. Recursieve Structuur: Een twee-geval recursie voor $N_n$ wordt vastgesteld die uniform geldt voor alle $q \ge 2$. Deze recursie scheidt de combinatorische structuur van het kanaal van de probabilistische gewichten.
3. Som-identiteiten: Twee belangrijke identiteiten worden bewezen:
   • Rij-som identiteit: Voor een vaste invoer $x$ is de som van $N_n(x, y)$ over alle mogelijke uitvoeren $y$ van lengte $k$ gelijk aan $\binom{n}{k}$.
   • Kolom-som identiteit: Voor een vaste uitvoer $y$ is de som van $N_n(x, y)$ over alle mogelijke invoeren $x$ gelijk aan $q^{n-k}\binom{n}{k}$.
4. Entropie-analyse: Deze identiteiten worden gebruikt om de exacte uitvoerentropie af te leiden onder een uniforme invoerdistributie. De auteurs introduceren vervolgens een entropie-correctieterm, $\Phi_{k,n}$, die de concentratie van de conditionele distributie kwantificeert wanneer meerdere deletiesubsets dezelfde invoer naar dezelfde uitvoer mappen (d.w.z. wanneer $N_n(x, y) \ge 2$).

Belangrijkste Bijdragen

1. Exacte Uitvoerentropie en Capaciteit-Sandwich

Onder de aanname van een uniforme invoerdistributie leiden de auteurs een gesloten vorm af voor de uitvoerentropie $H(Y)$. Dit leidt tot een "sandwich"-grens voor de eindige-blok capaciteit $C_{q,n}$:
$$(1-d)\log_2 q - h_2(d) \le C_{q,n} \le (1-d)\log_2 q$$
waarbij $h_2(d)$ de binaire entropiefunctie is. De bovenste grens is klassiek, terwijl de onderste grens direct is afgeleid van de uniforme invoeranalyse.

2. Aangescherpte Ondergrens via Entropie-correctie

De primaire bijdrage van het artikel is de verfijning van de ondergrens door rekening te houden met de niet-uniformiteit van de conditionele uitvoerdistributie. De auteurs definiëren een correctieterm $\Delta_n(d)$ gebaseerd op de waarden van $N_n(x, y)$:
$$\Delta_n(d) = \sum_{k=0}^n w_k \Phi_{k,n}$$
waarbij $w_k$ de waarschijnlijkheid is dat de uitvoerlengte $k$ is, en $\Phi_{k,n}$ de gemiddelde entropiecorrectie is afgeleid van de gehele waarden van $N_n$. Dit levert een exacte expressie op voor de wederzijdse informatie onder uniforme invoer:
$$\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}$$
Aangezien capaciteit de maximale wederzijdse informatie is, biedt deze expressie een gecertificeerde ondergrens:
$$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. Positiviteit en Asymptotische Grenzen

De auteurs bewijzen dat $\Delta_n(d) > 0$ voor alle $n \ge 2$ en $d \in (0, 1)$, waarmee zij certificeren dat de aangescherpte grens strikt beter is dan de basis-ondergrens. Ze bieden een gesloten vorm voor een ondergrens van $\Phi_{k,n}$ en leiden de kleine-deletie asymptotische gedraging af:
$$C_q(d) \ge \log_2 q + d \log_2 d + O(d)$$
Dit resultaat is geldig voor alle $q \ge 2$.

4. Numerieke Verificatie

Het artikel presenteert numerieke experimenten voor $q \in \{2, 3\}$ en bloklengtes $n \in \{3, 5, 10\}$. Met behulp van het Blahut–Arimoto algoritme om de exacte eindige-blok capaciteit te berekenen, demonstreren de auteurs dat hun aangescherpte ondergrens ($LB+$) strikt dichter bij de ware capaciteit ligt dan eerdere grenzen (zoals de Diggavi–Grossglauser grens of de Kanoria–Montanari expansie voor $q=2$). De kloof tussen de aangescherpte grens en de ware capaciteit wordt kleiner naarmate $n$ toeneemt.

Betekenis en Claims

Het artikel claimt een zelfvoorzienende $q$-aire behandeling van het deletiekanaal te bieden die de combinatorische structuur verenigt met probabilistische analyse. Door gebruik te maken van de patroon-tel scalaire $N_n(x, y)$, organiseren de auteurs alle capaciteitsberekeningen via een enkele gehele array.

De betekenis van dit werk ligt in:

• Gecertificeerde Grenzen: Het biedt expliciete, gecertificeerde ondergrenzen voor de capaciteit van het $q$-aire deletiekanaal voor elke $q \ge 2$, wat bestaande resultaten verbetert door een exacte entropie-correctieterm op te nemen.
• Analytisch Gemak: Het toont aan dat hoewel de uniforme invoer niet voor alle $q$ en $d$ globaal optimaal kan zijn, deze wel een behapbare, exacte uitvoerentropie en een rigoureuze ondergrens oplevert die verbetert naarmate de bloklengte toeneemt.
• Structureel Inzicht: De recursieve structuur van $N_n$ en de afgeleide som-identiteiten bieden een nieuw combinatorisch perspectief op het kanaal, waarbij het tellen van deletiepatronen wordt gescheiden van hun waarschijnlijkheden.

De auteurs merken bescheiden op dat de uniforme invoer is gekozen voor de behapbaarheid en niet beweren dat deze voor alle $q$ en $d$ capaciteitsbereikend is. Echter, de afgeleide grenzen zijn geldig voor de ware capaciteit, en de numerieke resultaten bevestigen dat de voorgestelde ondergrenzen nauw zijn voor kleine $n$ en verbeteren met grotere $n$. Toekomstig werk dat door de auteurs wordt gesuggereerd, omvat de asymptotische karakterisering van $\Delta_n(d)/n$ als $n \to \infty$ en de uitbreiding van deze methoden naar insertie-deletiekanalen.