Combinatorial Capacity Bounds for the $q$-ary Deletion Channel
Provides the first exact closed-form entropy and tight finite-block capacity bounds for the q-ary deletion channel, a fundamental problem in coding theory.
The paper derives exact closed-form output entropy and finite-block capacity bounds for the q-ary deletion channel, yielding a capacity lower bound of (1-d)log2 q - h2(d) + Δ_n(d)/n and a small-d expansion log2 q + d log2 d + O(d). Numerical experiments for n=3,5,10 and q=2,3 confirm the bounds.
We study the \(q\)-ary deletion channel via the pattern-count scalar \(N_n(x,y)\), the number of deletion subsets mapping \(x\inΣ_q^n\) to \(y\inΣ_q^k\), which factorizes the transition probability. Two sum identities on \(N_n\) certify stochastic normalization and, under uniform input, yield an exact closed-form output entropy. These give the finite-block capacity sandwich \( (1-d)\log_2 q-h_2(d)\;\le\; C_{q,n}\;\le\;(1-d)\log_2 q. \) The exact uniform-input rate is \( \frac{1}{n}I_U(X;Y) =(1-d)\log_2 q+\frac{1}{n}H_{\mathrm{Bin}}(n,1-d)-h_2(d)+\frac{Δ_n(d)}{n}, \) from which the simpler certified bound \( C_{q,n}\ge (1-d)\log_2 q-h_2(d)+\frac{Δ_n(d)}{n} \) follows. The small-\(d\) bound \(C_q(d)\ge\log_2 q+d\log_2 d+O(d)\) follows for all \(q\ge 2\). Numerical experiments at \(n=3,5,10\) and \(q=2,3\) confirm all bounds.