Technical Summary: Combinatorial Capacity Bounds for the q-ary Deletion Channel

Problem Statement

The paper addresses the fundamental problem of characterizing the capacity of the $q$-ary deletion channel. In this channel model, each transmitted symbol from an alphabet $\Sigma_q$ is independently deleted with probability $d$, and the receiver observes the surviving subsequence without knowledge of which positions were deleted. Despite decades of research, tight capacity characterizations for this channel remain an open problem, particularly for general alphabet sizes $q \ge 2$ and finite block lengths $n$. Existing bounds are often loose, and exact capacity calculations are computationally intractable for large $n$.

Methodology

The authors introduce a self-contained combinatorial framework centered on the pattern-count scalar, denoted $N_n(x, y)$. This integer scalar is defined as the number of distinct deletion subsets $S \subseteq [n]$ of size $n-k$ such that deleting the positions in $S$ from an input word $x \in \Sigma_q^n$ yields the output word $y \in \Sigma_q^k$.

The methodology proceeds through the following steps:

1. Factorization: The transition probability of the channel is factorized into the probabilistic weight of a specific deletion pattern and the combinatorial count $N_n(x, y)$. Specifically, $\Pr(Y=y | X=x) = N_n(x, y) \cdot d^{n-k}(1-d)^k$.
2. Recursive Structure: A two-case recursion for $N_n$ is established that holds uniformly for all $q \ge 2$. This recursion separates the combinatorial structure of the channel from its probabilistic weights.
3. Sum Identities: Two key identities are proven:
   • Row-sum identity: For a fixed input $x$, the sum of $N_n(x, y)$ over all possible outputs $y$ of length $k$ equals $\binom{n}{k}$.
   • Column-sum identity: For a fixed output $y$, the sum of $N_n(x, y)$ over all possible inputs $x$ equals $q^{n-k}\binom{n}{k}$.
4. Entropy Analysis: These identities are used to derive the exact output entropy under a uniform input distribution. The authors then introduce an entropy correction term, $\Phi_{k,n}$, which quantifies the concentration of the conditional distribution when multiple deletion subsets map the same input to the same output (i.e., when $N_n(x, y) \ge 2$).

Key Contributions

1. Exact Output Entropy and Capacity Sandwich

Under the assumption of a uniform input distribution, the authors derive a closed-form expression for the output entropy $H(Y)$. This leads to a "sandwich" bound for the finite-block capacity $C_{q,n}$:
$$(1-d)\log_2 q - h_2(d) \le C_{q,n} \le (1-d)\log_2 q$$
where $h_2(d)$ is the binary entropy function. The upper bound is classical, while the lower bound is derived directly from the uniform input analysis.

2. Tightened Lower Bound via Entropy Correction

The paper's primary contribution is the refinement of the lower bound by accounting for the non-uniformity of the conditional output distribution. The authors define a correction term $\Delta_n(d)$ based on the values of $N_n(x, y)$:
$$\Delta_n(d) = \sum_{k=0}^n w_k \Phi_{k,n}$$
where $w_k$ is the probability of the output length being $k$, and $\Phi_{k,n}$ is the average entropy correction derived from the integer values of $N_n$. This yields an exact expression for the mutual information under uniform input:
$$\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}$$
Since capacity is the maximum mutual information, this expression provides a certified lower bound:
$$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. Positivity and Asymptotic Bounds

The authors prove that $\Delta_n(d) > 0$ for all $n \ge 2$ and $d \in (0, 1)$, certifying that the tightened bound is strictly better than the basic lower bound. They provide a closed-form lower bound for $\Phi_{k,n}$ and derive the small-deletion asymptotic behavior:
$$C_q(d) \ge \log_2 q + d \log_2 d + O(d)$$
This result holds for all $q \ge 2$.

4. Numerical Verification

The paper presents numerical experiments for $q \in \{2, 3\}$ and block lengths $n \in \{3, 5, 10\}$. Using the Blahut–Arimoto algorithm to compute the exact finite-block capacity, the authors demonstrate that their tightened lower bound ($LB+$) is strictly closer to the true capacity than previous bounds (such as the Diggavi–Grossglauser bound or the Kanoria–Montanari expansion for $q=2$). The gap between the tightened bound and the true capacity narrows as $n$ increases.

Significance and Claims

The paper claims to provide a self-contained $q$-ary treatment of the deletion channel that unifies combinatorial structure with probabilistic analysis. By utilizing the pattern-count scalar $N_n(x, y)$, the authors organize all capacity calculations through a single integer array.

The significance of this work lies in:

• Certified Bounds: It offers explicit, certified lower bounds for the capacity of the $q$-ary deletion channel for any $q \ge 2$, improving upon existing results by incorporating an exact entropy correction term.
• Analytic Convenience: It demonstrates that while the uniform input may not be globally optimal for all $d$, it yields a tractable, exact output entropy and a rigorous lower bound that improves as block length increases.
• Structural Insight: The recursive structure of $N_n$ and the derived sum identities provide a new combinatorial perspective on the channel, separating the counting of deletion patterns from their probabilities.

The authors modestly note that the uniform input is chosen for tractability and does not claim to be capacity-achieving for all $q$ and $d$. However, the derived bounds are valid for the true capacity, and the numerical results confirm that the proposed lower bounds are tight for small $n$ and improve with larger $n$. Future work suggested by the authors includes the asymptotic characterization of $\Delta_n(d)/n$ as $n \to \infty$ and the extension of these methods to insertion-deletion channels.