Resumo Técnico: Limites de Capacidade Combinatória para o Canal de Deleção $q$-ário

Definição do Problema

O artigo aborda o problema fundamental de caracterizar a capacidade do canal de deleção $q$-ário. Neste modelo de canal, cada símbolo transmitido de um alfabeto $\Sigma_q$ é deletado independentemente com uma probabilidade $d$, e o receptor observa a subsequência sobrevivente sem conhecimento de quais posições foram deletadas. Apesar de décadas de pesquisa, as caracterizações de capacidade estreitas para este canal permanecem um problema em aberto, particularmente para tamanhos de alfabeto gerais $q \ge 2$ e comprimentos de bloco finitos $n$. Os limites existentes são frequentemente frouxos, e os cálculos exatos de capacidade são computacionalmente intratáveis para $n$ grandes.

Metodologia

Os autores introduzem um arcabouço combinatório autocontido centrado no escalar de contagem de padrões, denotado por $N_n(x, y)$. Este escalar inteiro é definido como o número de subconjuntos de deleção distintos $S \subseteq [n]$ de tamanho $n-k$ tal que a deleção das posições em $S$ de uma palavra de entrada $x \in \Sigma_q^n$ resulta na palavra de saída $y \in \Sigma_q^k$.

A metodologia procede através das seguintes etapas:

1. Fatoração: A probabilidade de transição do canal é fatorizada no peso probabilístico de um padrão de deleção específico e na contagem combinatória $N_n(x, y)$. Especificamente, $\Pr(Y=y | X=x) = N_n(x, y) \cdot d^{n-k}(1-d)^k$.
2. Estrutura Recursiva: Uma recursão de dois casos para $N_n$ é estabelecida, a qual se mantém uniforme para todos os $q \ge 2$. Esta recursão separa a estrutura combinatória do canal de seus pesos probabilísticos.
3. Identidades de Soma: Duas identidades fundamentais são provadas:
   • Identidade de soma de linha: Para um $x$ fixo, a soma de $N_n(x, y)$ sobre todos os possíveis outputs $y$ de comprimento $k$ é igual a $\binom{n}{k}$.
   • Identidade de soma de coluna: Para um $y$ fixo, a soma de $N_n(x, y)$ sobre todos os possíveis inputs $x$ é igual a $q^{n-k}\binom{n}{k}$.
4. Análise de Entropia: Estas identidades são usadas para derivar a entropia de saída exata sob uma distribuição de entrada uniforme. Os autores então introduzem um termo de correção de entropia, $\Phi_{k,n}$, que quantifica a concentração da distribuição condicional quando múltiplos subconjuntos de deleção mapeiam o mesmo input para o mesmo output (ou seja, quando $N_n(x, y) \ge 2$).

Principais Contribuições

1. Entropia de Saída Exata e Sanduíche de Capacidade

Sob a suposição de uma distribuição de entrada uniforme, os autores derivam uma expressão de forma fechada para a entropia de saída $H(Y)$. Isso leva a um limite de "sanduíche" para a capacidade de bloco finito $C_{q,n}$:
$$(1-d)\log_2 q - h_2(d) \le C_{q,n} \le (1-d)\log_2 q$$
onde $h_2(d)$ é a função de entropia binária. O limite superior é clássico, enquanto o limite inferior é derivado diretamente da análise de entrada uniforme.

2. Refinamento do Limite Inferior via Correção de Entropia

A principal contribuição do artigo é o refinamento do limite inferior ao considerar a não-uniformidade da distribuição de saída condicional. Os autores definem um termo de correção $\Delta_n(d)$ baseado nos valores de $N_n(x, y)$:
$$\Delta_n(d) = \sum_{k=0}^n w_k \Phi_{k,n}$$
onde $w_k$ é a probabilidade de o comprimento da saída ser $k$, e $\Phi_{k,n}$ é a média da correção de entropia derivada dos valores inteiros de $N_n$. Isso resulta em uma expressão exata para a informação mútua sob entrada uniforme:
$$\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}$$
Como a capacidade é o máximo da informação mútua, esta expressão fornece um limite inferior certificado:
$$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. Positividade e Limites Assintóticos

Os autores provam que $\Delta_n(d) > 0$ para todo $n \ge 2$ e $d \in (0, 1)$, certificando que o limite refinado é estritamente melhor que o limite inferior básico. Eles fornecem um limite inferior de forma fechada para $\Phi_{k,n}$ e derivam o comportamento assintótico de pequena deleção:
$$C_q(d) \ge \log_2 q + d \log_2 d + O(d)$$
Este resultado é válido para todos os $q \ge 2$.

4. Verificação Numérica

O artigo apresenta experimentos numéricos para $q \in \{2, 3\}$ e comprimentos de bloco $n \in \{3, 5, 10\}$. Usando o algoritmo de Blahut–Arimoto para calcular a capacidade exata de bloco finito, os autores demonstram que seu limite inferior refinado ($LB+$) é estritamente mais próximo da capacidade real do que os limites anteriores (como o limite de Diggavi–Grossglauser ou a expansão de Kanoria–Montanari para $q=2$). O gap entre o limite refinado e a capacidade real diminui conforme $n$ aumenta.

Significância e Alegações

O artigo alega fornecer um tratamento $q$-ário autocontido do canal de deleção que unifica a estrutura combinatória com a análise probabilística. Ao utilizar o escalar de contagem de padrões $N_n(x, y)$, os autores organizam todos os cálculos de capacidade através de um único array de inteiros.

A significância deste trabalho reside em:

• Limites Certificados: Oferece limites inferiores explícitos e certificados para a capacidade do canal de deleção $q$-ário para qualquer $q \ge 2$, melhorando os resultados existentes ao incorporar um termo de correção de entropia exato.
• Conveniência Analítica: Demonstra que, embora a entrada uniforme possa não ser globalmente ótima para todos os $q$ e $d$, ela produz uma entropia de saída tratável e exata, bem como um limite inferior rigoroso que melhora conforme o comprimento do bloco aumenta.
• Insight Estrutural: A estrutura recursiva de $N_n$ e as identidades de soma derivadas fornecem uma nova perspectiva combinatória sobre o canal, separando a contagem de padrões de deleção de suas probabilidades.

Os autores observam modestamente que a entrada uniforme é escolhida pela tratabilidade e não alegam que ela seja alcançadora de capacidade para todos os $q$ e $d$. No entanto, os limites derivados são válidos para a capacidade real, e os resultados numéricos confirmam que os limites inferiores propostos são estreitos para $n$ pequeno e melhoram com $n$ maior. Trabalhos futuros sugeridos pelos autores incluem a caracterização assintótica de $\Delta_n(d)/n$ conforme $n \to \infty$ e a extensão destes métodos para canais de inserção-deleção.